# Chromatic Turán problems and a new upper bound for the Turán density of $K_4^-$

John Talbot

► To cite this version:

John Talbot. Chromatic Turán problems and a new upper bound for the Turán density of $K_4^-$. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. pp.77-80, 10.46298/dmtcs.3437. hal-01184394

HAL Id: hal-01184394

https://inria.hal.science/hal-01184394

Submitted on 14 Aug 2015

**HAL** is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire **HAL**, est destinée au dépôt et à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Chromatic Turán problems and a new upper bound for the Turán density of $K_4^-$

John Talbot

Department of Mathematics, University College London, UK
E-mail: talbot@math.ucl.ac.uk

We consider a new type of extremal hypergraph problem: given an $r$-graph $\mathcal{F}$ and an integer $k \ge 2$ determine the maximum number of edges in an $\mathcal{F}$-free, $k$-colourable $r$-graph on $n$ vertices.

Our motivation for studying such problems is that it allows us to give a new upper bound for an old problem due to Turán. We show that a 3-graph in which any four vertices span at most two edges has density less than $\frac{33}{100}$, improving previous bounds of $\frac{1}{3}$ due to de Caen [1], and $\frac{1}{3} - 4.5305 \times 10^{-6}$ due to Mubayi [9].

**Keywords:** Extremal combinatorics, Turán-type problems, Hypergraphs

Given an $r$-graph $\mathcal{F}$ the Turán number $\mathrm{ex}(n, \mathcal{F})$ is the maximum number of edges in an $n$-vertex $r$-graph not containing a copy of $\mathcal{F}$. The Turán density of $\mathcal{F}$ is

$$ \pi(\mathcal{F}) = \lim_{n \to \infty} \frac{\mathrm{ex}(n, \mathcal{F})}{\binom{n}{r}}. $$

For 2-graphs the Turán density is determined completely by the chromatic number of $\mathcal{F}$, but for $r \ge 3$ there are very few $r$-graphs for which $\pi(\mathcal{F})$ is known. (Examples of 3-graphs for which $\pi(\mathcal{F})$ is now known include the Fano plane [2], $\mathcal{F} = \{abc, abd, abe, cde\}$ [8] and $\mathcal{F} = \{abc, abd, cde\}$ [7].)

The two most well-known problems in this area are to determine $\pi(K_4)$ and $\pi(K_4^-)$, where $K_4 = \{abc, abd, acd, bcd\}$ is the complete 3-graph on 4 vertices and $K_4^- = \{abc, abd, acd\}$ is the complete 3-graph on 4 vertices with an edge removed. For $\pi(K_4)$ we have the following bounds due to Turán and Chung and Lu [3] respectively

$$ \frac{5}{9} \le \pi(K_4) \le \frac{3 + \sqrt{17}}{12} = 0.59359\dots $$

Although the problem of determining $\pi(K_4)$ is an extremely natural question in some respects the problem of determining $\pi(K_4^-)$ is even more fundamental since $K_4^-$ is the smallest 3-graph satisfying $\pi(\mathcal{F}) \ne 0$. Note also that this problem may be restated as follows: determine the maximum density of a 3-graph in which any four vertices span at most two edges.
The problem of determining $\pi(K_4^-)$ has been considered by many people, including Turán [12], Erdős and Sós [5], Frankl and Füredi [6], de Caen [1] and Mubayi [9]. Previously the best known bounds were

$$ \frac{2}{7} \le \pi(K_4^-) \le \frac{1}{3} - (4.5305 \times 10^{-6}). $$

The upper bound was proved by Mubayi [9], improving on the upper bound $\pi(K_4^-) \le 1/3$, due to de Caen [1]. The lower bound is from a construction due to Frankl and Füredi [6].

Our main result is the following theorem, improving the upper bound for $\pi(K_4^-)$.

**Theorem 1** The Turán density of $K_4^-$ satisfies

$$ \frac{2}{7} \le \pi(K_4^-) < \frac{33}{100}. $$

The proof of this result leads naturally to a new general class of extremal problems which we call chromatic Turán problems. These are questions of the form: given an $r$-graph $\mathcal{F}$ and an integer $k \ge 2$ determine the maximum number of edges in an $\mathcal{F}$-free, $k$-colourable $r$-graph on $n$ vertices. (Recall that an $r$-graph is $k$-colourable iff its vertices can be partitioned into $k$ classes, none of which contain an edge.) We denote this quantity by $\text{ex}_k(n, \mathcal{F})$. The corresponding $k$-chromatic Turán density is then defined to be

$$ \pi_k(\mathcal{F}) = \lim_{n \to \infty} \frac{\text{ex}_k(n, \mathcal{F})}{\binom{n}{r}}. $$

The following lemma shows that any upper bound for the chromatic Turán density $\pi_3(K_4^-)$ will yield an upper bound for the ordinary Turán density $\pi(K_4^-)$. (The proof of Theorem 1 actually requires a slightly stronger result but the principle is the same.)

**Lemma 1** If $\pi_3 = \pi_3(K_4^-)$ and $\pi = \pi(K_4^-)$ then

$$ \pi \le \frac{2 + \pi_3/\pi}{9}. $$

To prove Lemma 1 we first note that if $\mathcal{F}$ is a $K_4^-$-free 3-graph with $n$ vertices and $m$ edges then it satisfies

$$ mn = \sum_{xy \in V^{(2)}} d_{xy}^2 + q_1, \qquad (1) $$

where $q_1$ is the number of 4-sets in $\mathcal{F}$ spanning exactly one edge. Lemma 1 is proved by giving a lower bound for $q_1$.

This idea of giving a lower bound for $q_1$ was previously used by Mubayi [9] (he used supersaturation to achieve this). Our approach is quite different in that it involves a chromatic Turán problem.

To be more precise the key idea used in the proof of Lemma 1 is as follows. Let $\mathcal{F}$ be a $K_4^-$-free 3-graph of order $n$ and let $uvw \in \mathcal{F}$. If $E_{ij} = \{k : ijk \in \mathcal{F}\}$ then $E_{uv}, E_{uw}$ and $E_{vw}$ are pairwise disjoint. We say that an edge $xyz \in \mathcal{F}$ is bad relative to the edge $uvw$ if $xyz \cap vw = \emptyset$ and none of the following
4-sets span exactly one edge: uvwx, uvwy, uvwz, xyzu, xyzv, xyzw. It is straightforward to check that if xyz is bad relative to uvw then xyz ⊂ E$_{uv}$ ∪ E$_{uw}$ ∪ E$_{vw}$ and xyz is not contained entirely in either E$_{uv}$, E$_{uw}$ or E$_{vw}$. Hence the collection of bad edges relative to uvw is 3-colourable. This fact can then be used to give a lower bound for q$_{1}$ in terms of the 3-chromatic Turán density π$_{3}$ ( K$_{4}$ $^{−}$).

One obvious reason why chromatic Turán problems do not seem to have been considered before is that for 2-graphs they are rather uninteresting. If K$_{t}$ is the complete 2-graph of order t then Turán’s theorem determines not only their Turán numbers but also their chromatic Turán numbers.

**Theorem 2 (Turán[11])** If $t \ge 3$ then the unique $K_t$-free graph with $n$ vertices and $ex(n, K_t)$ edges is the complete $(t-1)$-partite graph whose vertex classes are as equal as possible in size.

**Corollary 1** If $t \ge 3$ and $k \ge 2$ then

$$ex_k(n, K_t) = \begin{cases} ex(n, K_t), & k \ge t-1, \\ ex(n, K_{k+1}), & k \le t-2. \end{cases}$$

For general r-graphs with $r \ge 3$ the problems of determining chromatic and ordinary Turán numbers seem to be genuinely different. While the extremal $K_t$-free 2-graph is not only $K_t$-free but also $(t-1)$-colourable this does not seem to be the case in general. For example the conjectured extremal $K_4^-$-free 3-graph has rather large chromatic number.

In order to make use of Lemma 1 we need an upper bound on $\pi_3(K_4^-)$. To achieve this we first consider $\pi_2(K_4^-)$.

**Theorem 3** The 2-chromatic Turán density $\pi_2(K_4^-)$ satisfies

$$\frac{4}{9\sqrt{3}} \le \pi_2(K_4^-) \le \frac{3}{10}.$$

*Proof:* The lower bound follows from a simple construction. For the upper bound let $\mathcal{F} = ((A, B), E)$ be a bipartite $K_4^-$-free 3-graph with $n$ vertices and $m$ edges. Let $|A| = \alpha n$, so $|B| = (1 - \alpha)n$. Then

$$\sum_{xy \in A \times B} d_{xy} = 2m, \qquad \sum_{xy \in A^{(2)} \cup B^{(2)}} d_{xy} = m. \qquad (2)$$

From (1) and the fact that $q_1 \ge 0$ we obtain

$$mn \ge \sum_{xy \in A \times B} d_{xy}^2 + \sum_{xy \in A^{(2)} \cup B^{(2)}} d_{xy}^2$$

Convexity and (2) then imply that

$$m \le \frac{n^3}{\frac{4}{\alpha(1-\alpha)} + \frac{2}{\alpha^2 + (1-\alpha)^2}} \le \frac{n^3}{20}.$$

The result then follows directly.

□

With some more work we can obtain an upper bound for $\pi_3(K_4^-)$. (Again the lower bound follows from a simple construction.)
**Theorem 4** *The 3-chromatic Turán density $\pi_3(K_4^-)$ satisfies*

$$ \frac{5}{18} \le \pi_3(K_4^-) < \frac{58}{177}. $$

## References

[1] D. de Caen, Extension of a theorem of Moon and Moser on complete subgraphs, Ars Combinatoria 16 (1983) 5-10.

[2] D. de Caen and Z. Füredi, The maximum size of 3-uniform hypergraphs not containing a Fano plane, Journal of Combinatorial Theory Series B, 78 (2000) 274-276.

[3] F. Chung and L. Lu, An upper bound for the Turán number $t_3(n, 4)$, Journal of Combinatorial Theory Series A, (1999) 87 381-389.

[4] P. Erdős and M. Simonovits, Supersaturated graphs and hypergraphs, Combinatorica 3 (1983) 181-192.

[5] P. Erdős and V.T. Sós, On Ramsey–Turán type theorems for hypergraphs, Combinatorica 2 (1982) 289-295.

[6] P. Frankl and Z. Füredi, An exact result for 3-graphs, Discrete Math. 50 (1984), no. 2-3, 323-328.

[7] P. Frankl and Z. Füredi, A new generalization of the Erdős–Ko–Rado theorem, Combinatorica 3 (1983) 341-349.

[8] Z. Füredi, O. Pikhurko and M. Simonovits, The Turán density of the hypergraph abc, ade, bde, cde, Electronic Journal of Combinatorics, 10 (2003) 7pp

[9] D. Mubayi, On hypergraphs with every four points spanning at most two triples, Electronic Journal of Combinatorics 10 (2003), #N10

[10] D. Mubayi and V. Rödl, On the Turán number of triple systems, Journal of Combinatorial Theory, Series A 100 (2002) 136-152.

[11] P. Turán, On an extremal problem in graph theory, Mat. Fiz. Lapok 48 (1941) 436-452 [in Hungarian].

[12] P. Turán, Turán memorial volume, Journal of Graph Theory 1 (2) (1977).