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.),
1228,
Springer, Berlin, 1990.
