Some exact results for generalized Turán problems

Abstract: Fix a

k

-chromatic graph

F

. In this paper we consider the question to determine for which graphs

H

does the Tur'an graph

T_{k - 1} (n)

have the maximum number of copies of

H

among all

n

-vertex

F

-free graphs (for

n

large enough). We say that such a graph

H

is

F

-Tur'an-good. In addition to some general results, we give (among others) the following concrete results: (i) For every complete multipartite graph

H

, there is

k

large enough such that

H

is

K_{k}

-Tur'an-good. (ii) The path

P_{3}

is

F

-Tur'an-good for

F

with

c h i (F) g e q 4

. (iii) The path

P_{4}

and cycle

C_{4}

are

C_{5}

-Tur'an-good. (iv) The cycle

C_{4}

is

F_{2}

-Tur'an-good where

F_{2}

is the graph of two triangles sharing exactly one vertex.

Review text

The authors investigate the forbidden subgraph problem in the following general setting. Let \(F\) be a fixed graph. A graph is said to be \(F\)-free if it does not contain any copy of \(F\) as a subgraph. For graphs \(G\), \(H\), denote by \(\mathcal{N}(H, G)\) the number of copies of \(H\) in \(G\). For fixed graphs \(F\), \(H\), define \(\operatorname{ex}(n, H, F) := \max\{ \mathcal{N}(H, G) \}\), where the maximum is taken over all \(F\)-free graphs \(G\) on \(n\) vertices. The Turán graph \(T_{k-1}(n)\) is the complete \((k-1)\)-partite graph on \(n\) vertices with each part containing either \(\lfloor n/(k-1) \rfloor\) or \(\lceil n/(k-1) \rceil\) vertices. A classical result due to \textit{P. Turán} [Mat. Fiz. Lapok 48, 436--452 (1941; Zbl 0026.26903)] says, in the above language, that \(\operatorname{ex}(n, K_{2}, K_{k}) = \mathcal{N}(K_{2}, T_{k-1}(n)\). In other words, the Turán graph \(T_{k-1}(n)\) has the maximum number of edges in any \(n\)-vertex \(K_{k}\)-free graph. In this paper, the authors examine when the Turán graph is an extremal construction for more general \(F\) and \(H\). For a \(k\)-chromatic graph \(F\) and a graph \(H\) that is \(F\)-free, say that \(H\) is \(F\)-Turán-good if \(\operatorname{ex}(n, H, F) = \mathcal{N}(H, T_{k-1}(n))\) for all sufficiently large \(n\). When \(F = K_{k}\), shorten this to \(k\)-Turán-good. In Section 2, the case when \(F = K_{k}\) is taken up: \par 1) The following result gives a method for constructing new \(k\)-Turán-good graphs from a given \(k\)-Turán-good graph. Let \(H\) be a \(k\)-Turán-good graph. Let \(H^\prime\) be any graph constructed from \(H\) in the following way. Choose a complete subgraph of \(H\) with vertex set \(X\), add a vertex-disjoint copy of \(K_{k-1}\) to \(H\), and join the vertices in \(X\) to the vertices of \(K_{k-1}\) by edges arbitrarily. Then \(H^\prime\) is \(k\)-Turán-good. \par 2) The following is an asymptotic result on the number of copies of the path graph \(P_{\ell}\) on \(\ell\) vertices in a \(K_{k}\)-free graph, and indeed in any \(F\)-free graph where \(F\) has chromatic number \(\chi(F) = k\). If \(F\) is \(k\)-chromatic with \(k > 2\), then \(\operatorname{ex}(n, P_{\ell}, F) = (1 + o(1)) \mathcal{N}(P_{\ell}, T_{k-1}(n))\). \par 3) The main result in this section says that all complete multipartite graphs are \(k\)-Turán-good for sufficiently large \(k\). For every complete multipartite graph \(H\) there is an integer \(k_{0}\) such that if \(k \geq k_{0}\), then \(H\) is \(k\)-Turán-good. Say that an edge of a graph is color-critical if the chromatic number of the graph obtained by deleting that edge is smaller than the chromatic number of the original graph. In Section 3, the authors show that the path graph \(P_{3}\) is \(F\)-Turán-good for any \(F\) with chromatic number \(\chi(F) \geq 4\) and with a color-critical edge. In the rest of this section, they prove specific results for small path and cycle graphs, for various \(F\). In Section 3.1, the case when \(F = B_{2}\) is taken up, where the book \(B_{k}\) is the graph consisting of \(k\) triangles all sharing exactly one common edge. Define \(\overline{M_{k}}\) to be the graph obtained by removing a perfect matching from \(K_{2k}\). Define \(\overline{M_{k}}^{+}\) to be the graph obtained by adding an edge to \(\overline{M_{k}}\). Then, the following result is proved: Let \(H\) be a \(2k\)-vertex graph consisting of two vertex-disjoint copies of \(K_{k}\) joined together with edges arbitrarily. If \(\overline{M_{k}}\) has the maximum number of copies of \(H\) among all \(2k\)-vertex \(\overline{M_{k}}^{+}\)-free graphs, then \(H\) is \(\overline{M_{k}}^{+}\)-Turán-good. In particular, \(\overline{M_{k}}\) is \(\overline{M_{k}}^{+}\)-Turán-good. By specializing to the case \(k = 2\), one obtains as a corollary that \(P_{4}\) and \(C_{4}\) are both \(B_{2}\)-Turán-good. In Section 3.2, the case when \(F\) is an odd cycle is taken up. The authors show that \(P_{4}\) is \(C_{5}\)-Turán-good. Moreover, they prove a stability result as follows: If \(G\) is a \(C_{5}\)-free graph on \(n\) vertices and \(G\) has \(\alpha\) edges contained in triangles, then \(\mathcal{N}(P_{4}, G) \leq \mathcal{N}(P_{4}, T_{2}(n)) - (1+o(1)) \alpha n^{2}/12\). As a corollary to the proof, one also obtains that for a \(3\)-chromatic graph \(F\), if \(P_{2k}\) is \(F\)-Turán-good, then \(C_{2k}\) is \(F\)-Turán-good. In particular, \(C_{4}\) is \(C_{5}\)-Turán-good. In Section 3.3, the case when \(F = F_{2}\) is taken up, where the fan \(F_{k}\) is the graph consisting of \(k\) triangles all sharing exactly one common vertex. It is shown that \(C_{4}\) is \(F_{2}\)-Turán-good. In the final section, the authors raise the following conjectures: \par i) For every pair of integers \(\ell\) and \(k\), the path \(P_{\ell}\) is \(k\)-Turán-good. \par ii) For every graph \(H\) there is an integer \(k_{0}\) such that if \(k \geq k_{0}\), then \(H\) is \(k\)-Turán-good. The authors note that the above conjecture cannot hold for all (small) \(k\) in general. They also remark that while it can be observed in some of their examples that when a graph is \(k\)-Turán-good it is also \((k+1)\)-Turán-good, they do not know whether this is true for every graph \(H\). \par iii) The path \(P_{k}\) and the even cycle \(C_{2k}\) are \(C_{2\ell+1}\)-Turán-good. Lastly, the authors note that one can also ask when the Turán graph is the unique extremal construction for these generalized Turán-type problems. Call \(H\) to be strictly \(F\)-Turán-good when this happens. The authors remark that it is not hard to show that their results for graphs \(F\) with a color-critical edge (such as when \(F = B_{2}\) or \(C_{5}\), but not \(F_{2}\)) also hold for the strict version. A minor typo: read ``Conjecture in place of ``Construction on pages 4, 7, and 13.

Recommendations

Cites work

Cited in

(38)

This page was built for publication: Some exact results for generalized Turán problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2136200)