A Ramsey-Turán lower bound for \(3\)-graphs
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
A hypergraph \( H\) consists of a vertex set \( V\) together with a family \( E\) of subsets of \( V\), which are called the edges of \( H\). A \( r\)-uniform hypergraph, or \( r\)-graph, for short, is a hypergraph whose edge set consists of \( r\)-subsets of \( V\). A graph is just a special case of an \( r\)-graph with \( r=2\).
Ramsey-Turán problems for graphs can be naturally generalized to hypergraphs [1]. For an \( r\)-graph \( H\) and an integer \( k\), we denote by \( rt_r(n,H;k)\) the maximum number of edges in an \( r\)-graph \( G\) on \( n\) vertices when \( G\) contains no independent set of size \( k\), and \( G\) does not contain a \( H\) as a subgraph. The problems of estimating \( rt_r(n,H;k)\) for \( r\)-graphs \( H\), \( r \geq 3\), are considerably harder than the case for graphs. Known results on this problem are contained in [1] and [2] Numerous problems on Ramsey-Turán type problems are open (e.g., see [1]). Erdös and Sós [1] showed that there is an \( \alpha < 1\) such that \( rt_3(n,K_4^{(3)}; n^{\alpha}) \geq c_{\alpha} n^3\) for a constant \( c_{\alpha}\). They asked:
Problem: (proposed Erdös and Sós [1])
Is \[ \inf \{ \alpha : \lim_{n \rightarrow \infty} \frac{ rt_3(n, K_4^{(3)}; n^{\alpha})}{\binom n 3 } >0 \} > 0 ? \]See also this conjecture for the corresponding upper bound.
Bibliography | |
---|---|
1 | P. Erdös and V. T. Sós. On Ramsey-Turán type theorems for hypergraphs. Combinatorica 2 (1982), 289-295.
|
2 | P. Frankl and V. Rödl. Some Ramsey-Turán type results for hypergraphs. Combinatorica 8 (1988), 323-332.
|