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

From MaRDI portal
Importer (talk | contribs)
Created a new Item
 
Import240304020342 (talk | contribs)
Set profile property.
 
(One intermediate revision by one other user not shown)
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank
links / mardi / namelinks / mardi / name
 

Latest revision as of 05:21, 5 March 2024

scientific article
Language Label Description Also known as
English
An ordered Turán problem for bipartite graphs
scientific article

    Statements

    An ordered Turán problem for bipartite graphs (English)
    0 references
    0 references
    7 June 2013
    0 references
    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.
    0 references
    Turán problem
    0 references
    Turán number
    0 references
    bipartite graphs
    0 references
    zig-zag graph
    0 references

    Identifiers