An ordered Turán problem for bipartite graphs (Q1953354): Difference between revisions

Summary: 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 \(\text{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 \(\text{ex}(n,Z_{s,t})\) and \(\text{ex}(n,\mathcal{Z}_{2k})\). In particular we show \(\text{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) + \text{ex} (n,K_{2,2})\) edges.