Asymptotic behavior of generalized Ramsey numbers
Home
Search
Subjects
About Erdös
About This Site
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\),
\(\displaystyle c(\alpha) \log n < F^{(2)} (n,\alpha) < c'(\alpha) \log n. \)
Conjecture
Prove that \[ F^{(2)}(n,\alpha) \sim c \log n \] for an appropriate \(c\) and determine \(c\).
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.
|