Behavior of generalized hypergraph Ramsey numbers
Search
Subjects
- All (170)
- Ramsey Theory (40)
- Extremal Graph Theory (40)
- Coloring, Packing, and Covering (25)
- Random Graphs and Graph Enumeration (16)
- Hypergraphs (35)
- Infinite Graphs (14)
About Erdös
About This Site
Denote by \( F^{(t)}(n, \alpha)\) the largest integer for which it is possible to split the \( t\)-tuples of a set \( S\) of \( n\) elements into \( 2\) classes so that for every \( X \subset S\) with \( \vert X\vert \geq F^{(t)}(n, \alpha)\), each class contains more than \( \alpha \binom{\vert X\vert}{t} \) \( t\)-tuples of \( X\). Note that \( F^{(t)}(n,0)\) is just the usual Ramsey function \( r_t(n,n)\). It is easy to show that for every \( 0 \leq \alpha \leq 1/2\),
It is conjectured [1] that for \( t=2\),
As Erdös says in [1], the situation for \( t \geq 3\) is much more mysterious. It is well-known[1] that if \( \alpha\) is sufficiently close to \( 1/2\), then
Problem ($ 500)
Does the change in \(F^{(t)} (n,\alpha)\) occur continuously, or are there jumps?Erdös suspected there might only be one jump, this occurring at 0.
Bibliography | |
---|---|
1 |
P. Erdös,
Problems and results on graphs and hypergraphs: similarities and
differences,
Mathematics of Ramsey theory, Algorithms Combin., 5,
(J. Nešetril and V. Rödl, eds.),
12-28,
Springer, Berlin, 1990.
|
2 | P. Erdös, A. Hajnal and R. Rado. Partition relations for cardinal numbers, Acta Math. cad. Sci. Hungar. 16 (1965), 93-196.
|