×

zbMATH — the first resource for mathematics

Chromatic Turán problems and a new upper bound for the Turán density of \(\mathcal K^{-}_{4}\). (English) Zbl 1128.05030
For positive integers \(k,r\) and an \(r\)-graph \(\mathcal F\), \(\text{ex}_k(n,{\mathcal F})\) denotes the maximum number of edges in an \(\mathcal F\)-free, \(k\)-colourable \(r\)-graph on \(n\) vertices; the Turán density of \(\mathcal F\) is \(\pi(\mathcal F) =\lim_{n\to\infty}\frac{\text{ex}(n,{\mathcal F})}{\binom{n}{r}}\); the \(k\)-chromatic Turán density is \(\pi_k(\mathcal F) =\lim_{n\to\infty}\frac{\text{ex}_k(n,{\mathcal F})}{\binom{n}{r}}\). It is observed (Corollary 3) that \(\pi_k(G)\) is known for 2-graphs from the Erdős-Simonovits-Stone theorem [P. Erdős and M. Simonovits, Stud. Sci. Math. Hung. 1, 51–57 (1966; Zbl 0178.27301)]. The 3-graph \({\mathcal K}_4^-\) has 4 vertices and 3 edges; the problem of determining \(\pi({\mathcal K}_4^-)\) is a special case of a question proposed in [W. G. Brown, P. Erdős and V. T. Sós, Some extremal problems on \(r\)-graphs. New Direct. Theory Graphs, Proc. Third Ann Arbor Conf., Univ. Michigan 1971, 53–63 (1973; Zbl 0258.05132)].
Theorem 4: There exists \(\omega_2>0\) such that \(0.25682<\pi_2({\mathcal K}_4^-)<\frac3{10}-\omega_2\).
Theorem 5: There exists \(\omega_3>0\) such that \(\frac{5}{18}\leq\pi_3({\mathcal K}_4^-)<\frac{3+\sqrt{\frac{11}3}}{15}-\omega_3\).
A lower bound for \(\pi({\mathcal K}_4^-)\) was determined in [P. Frankl and Z. Füredi, Discrete Math. 50, 323–328 (1984; Zbl 0538.05050)]. Improving on upper bounds in [D. de Caen, Ars Comb. 16, 5-10 (1983; Zbl 0532.05037), and D. Mubayi, Electron. J. Comb. 10, No. 1, Research paper N10, 4 p. (2003); printed version J. Comb. 10, No. 3 (2003; Zbl 1023.05105)], the author proves Theorem 1: \(\frac27<\pi({\mathcal K}_4^-)<0.32975<\frac13-\frac1{280}\). It is conjectured (Conjecture 1) that \(\pi_3({\mathcal K}_4^-)=\frac{5}{18}\).

MSC:
05C35 Extremal problems in graph theory
05C15 Coloring of graphs and hypergraphs
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Brown, W.G.; Erdős, P.; Sós, V.T., Some extremal problems on \(r\)-graphs, (), 55-63
[2] de Caen, D., Extension of a theorem of Moon and Moser on complete subgraphs, Ars combin., 16, 5-10, (1983) · Zbl 0532.05037
[3] de Caen, D.; Füredi, Z., The maximum size of 3-uniform hypergraphs not containing a Fano plane, J. combin. theory ser. B, 78, 274-276, (2000) · Zbl 1027.05073
[4] Chung, F.; Lu, L., An upper bound for the Turán number \(t_3(n, 4)\), J. combin. theory ser. A, 87, 381-389, (1999) · Zbl 0946.05063
[5] Erdős, P.; Simonovits, M., A limit theorem in graph theory, Studia. sci. math. hungar., 1, 51-57, (1966) · Zbl 0178.27301
[6] Erdős, P.; Sós, V.T., On ramsey – turán type theorems for hypergraphs, Combinatorica, 2, 289-295, (1982) · Zbl 0511.05049
[7] Erdős, P.; Stone, A.H., On the structure of linear graphs, Bull. amer. math. soc., 52, 1087-1091, (1946) · Zbl 0063.01277
[8] Frankl, P.; Füredi, Z., A new generalization of the erdős – ko – rado theorem, Combinatorica, 3, 341-349, (1983) · Zbl 0529.05001
[9] Frankl, P.; Füredi, Z., An exact result for 3-graphs, Discrete math., 50, 2-3, 323-328, (1984) · Zbl 0538.05050
[10] Frankl, P.; Füredi, Z., Extremal problems whose solutions are the blowups of small Witt-designs, J. combin. theory ser. A, 52, 129-147, (1989) · Zbl 0731.05030
[11] Füredi, Z.; Pikhurko, O.; Simonovits, M., The Turán density of the hypergraph \(a b c, a d e, b d e, c d e\), Electron. J. combin., 10, 7pp, (2003)
[12] Mubayi, D., On hypergraphs with every four points spanning at most two triples, Electron. J. combin., 10, 10, (2003) · Zbl 1023.05105
[13] Ruzsa, I.Z.; Szemerédi, E., Triple systems with no six points carrying three triangles, (), 939-945 · Zbl 0393.05031
[14] Turán, P., On an extremal problem in graph theory, Mat. fiz. lapok, 48, 436-452, (1941), (in Hungarian)
[15] Turán, P., Turán memorial volume, J. graph theory, 1, 2, (1977)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.