Question about a Ramsey graph.

  • Thread starter cragar
  • Start date
  • Tags
    Graph
In summary, the Ramsey number of R(\omega,\omega) is \omega, but the Ramsey number of R(\omega+1,\omega) can vary depending on the ordering of the edges and is not necessarily equal to \omega_1.
  • #1
cragar
2,552
3
the Ramsey number of [itex] R(\omega,\omega)=\omega [/itex]
but then [itex] R(\omega+1,\omega)=\omega_1 [/itex]
My question is on the second one can we do a counter example to show that it can't
be any countable ordinal.
depending on how I count the natural numbers I can get any countable ordinal I want.
If we assume that [itex] R(\omega+1,\omega) [/itex] was equal to some countable ordinal
then I could just color [itex] \omega [/itex] edges with blue for example and i would stay
under the [itex] \omega+1 [/itex] limit . And the other color we would just use a finite number of them.
I guess i don't really understand why order matters for an infinite Ramsey graph.
It doesn't seem like it matters in the finite case.
 
Physics news on Phys.org
  • #2
The Ramsey number of R(\omega,\omega) is indeed equal to \omega, however this does not necessarily mean that R(\omega+1,\omega) is equal to \omega_1. This is because the Ramsey number of R(\omega+1,\omega) can depend on the specific ordering of the edges in the graph. For example, if we order the edges of the graph so that the two sets of \omega+1 edges are adjacent, then the Ramsey number of R(\omega+1,\omega) will be \omega_1. However, if we order the edges so that the two sets of \omega+1 edges are separated by some other edges, then the Ramsey number of R(\omega+1,\omega) could be lower than \omega_1. Therefore, it is not possible to provide a counter-example to show that R(\omega+1,\omega) cannot be any countable ordinal, as the actual value can depend on the ordering of the edges.
 

FAQ: Question about a Ramsey graph.

1. What is a Ramsey graph?

A Ramsey graph is a type of mathematical graph that represents relationships between a set of objects. In a Ramsey graph, each object is represented by a vertex, and the relationships between objects are represented by edges connecting the vertices. These graphs are named after mathematician Frank Plumpton Ramsey.

2. How is a Ramsey graph different from other types of graphs?

Ramsey graphs are unique because they have certain properties that make them useful for solving certain mathematical problems. One key property of a Ramsey graph is that it is a complete graph, meaning that every pair of vertices is connected by an edge. Additionally, Ramsey graphs are known for their colorful and symmetrical patterns, which are the basis for the Ramsey coloring problem.

3. What is the Ramsey coloring problem?

The Ramsey coloring problem is a mathematical problem that involves finding the minimum number of colors needed to color the vertices of a Ramsey graph in such a way that no two adjacent vertices are the same color. This problem has real-world applications in fields such as computer science and social networks, where it is used to identify patterns and relationships between objects.

4. How are Ramsey graphs used in real-world applications?

Ramsey graphs have a wide range of applications in various fields, including computer science, social networks, and game theory. They can be used to model relationships between objects, identify patterns and structures, and solve mathematical problems. For example, in computer science, Ramsey graphs are used to analyze the performance of algorithms and networks.

5. What is the significance of Ramsey graphs in mathematics?

Ramsey graphs have played a significant role in the development of mathematics, particularly in the areas of graph theory and combinatorics. They have been used to solve numerous mathematical problems and have inspired new theories and concepts in these fields. Moreover, Ramsey graphs have been instrumental in advancing our understanding of complex networks and relationships between objects in various systems.

Similar threads

Replies
14
Views
2K
Replies
2
Views
2K
Replies
15
Views
2K
Replies
12
Views
2K
Replies
28
Views
5K
Replies
2
Views
836
Replies
18
Views
2K
Replies
23
Views
5K
Back
Top