Exact values for \(t_3(n, 4) \)
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\).
For a finite family \( \mathcal F\) of \( r\)-graphs, one can define the Turán number \( t_r(n,{\mathcal F})\) to be the largest integer \( t\) such that there is an \( r\)-graph on \( n\) vertices with \( t\) edges which does not contain any \( F \in {\mathcal F}\) as a subgraph. We let \( K_k^{(r)}\) denote a complete \( r\)-graph on \( k\) vertices and we write \( t_r(n,K_k^{(r)})=t_r(n,k)\).
The case of \( r=3\) and \( k=4\) is of special interest.
Turán's conjecture for \(3\)-graphs, $500 (proposed by Turán[4], 1941)
\[ t_3(n,4) = \left\{ \begin{array}{c l} k^2(5k-3)/2 & \mbox{ if \(n=3k\),} \\ k(5k^2+2k-1)/2 & \mbox{ if \(n=3k+1\) }\\ k(k+1)(5k+2) & \mbox{ if \(n=3k+2\). } \end{array} \right. \]Many constructions are known which achieve this value [1], [3]. For example, in [3], Kostochka showed that there are \( 2^{k-2}\) non-isomorphic extremal \( 3\)-graphs on \( 3k\) vertices. The above conjecture, if true, will give
Bibliography | |
---|---|
1 |
W. G. Brown, On an open problem of Paul Turán concerning \( 3\)-graphs,
Studies in Pure Math., 91-93, Birkhäuser, Basel-Boston, MA, 1983.
|
2 |
D. de Caen,
The current status of Turán's problem on hypergraphs,
Extremal Problems for Finite Sets, Visegrád, 1991,
Bolyai Soc. Math. Studies 3, 187-197.
|
3 | A. V. Kostochka, A class of constructions for Turán's \( (3,4)\)-problem,
Combinatorica 2 (1982), 187-192.
|
4 |
P. Turán,
On an extremal problem in graph theory (in Hungarian),
Mat. Fiz. Lapok. 48 (1941), 436-452.
English translation in Collected Papers of Paul Turán
(P. Erdös, ed.), 231-240, Akadémiai Kiadó, Budapest, 1990.
|