An ordered Turán problem for bipartite graphs

Craig Timmons¹

¹University of California San Diego

The electronic journal of combinatorics, Tome 19 (2012) no. 4

Résumé

Let $F$ be a graph. A graph $G$ is $F$-free if it does not contain $F$ as a subgraph. The Turán number of $F$, written $\textrm{ex}(n,F)$, is the maximum number of edges in an $F$-free graph with $n$ vertices. The determination of Turán numbers of bipartite graphs is a challenging and widely investigated problem. In this paper we introduce an ordered version of the Turán problem for bipartite graphs. Let $G$ be a graph with $V(G) = \{1, 2, \dots , n \}$ and view the vertices of $G$ as being ordered in the natural way. A zig-zag $K_{s,t}$, denoted $Z_{s,t}$, is a complete bipartite graph $K_{s,t}$ whose parts $A = \{n_1 < n_2 < \dots < n_s \}$ and $B = \{m_1 < m_2 < \dots < m_t \}$ satisfy the condition $n_s < m_1$. A zig-zag $C_{2k}$ is an even cycle $C_{2k}$ whose vertices in one part precede all of those in the other part. Write $\mathcal{Z}_{2k}$ for the family of zig-zag $2k$-cycles. We investigate the Turán numbers $\textrm{ex}(n,Z_{s,t})$ and $\textrm{ex}(n,\mathcal{Z}_{2k})$. In particular we show $\textrm{ex}(n, Z_{2,2}) \leq \frac{2}{3}n^{3/2} + O(n^{5/4})$. For infinitely many $n$ we construct a $Z_{2,2}$-free $n$-vertex graph with more than $(n - \sqrt{n} - 1) + \textrm{ex} (n,K_{2,2})$ edges.

Détail

DOI : 10.37236/2471

Classification : 05C35, 05C70
Mots-clés : Turán problem, Turán number, bipartite graphs, zig-zag graph