New results on the Zarankiewicz problem (Q2643330)

From MaRDI portal
scientific article
Language Label Description Also known as
English
New results on the Zarankiewicz problem
scientific article

    Statements

    New results on the Zarankiewicz problem (English)
    0 references
    23 August 2007
    0 references
    The Zarankiewicz problem asks how many edges can be added to a bipartite graph \(K(m,n)\) while avoiding a complete bipartite subgraph \(K(s,t)\). The maximum number of edges is denoted by \(z(m,n;s,t)\). In the paper are found exact values of the function \(z(m,n;s,t)\) for special values of parameters and also corresponding extremal graphs are characterized. First, it is proved that \(z(m,n;s,t) = mn-(m+n-s-t+1)\) if \(\max \{m,n\} \leq s+t-1\). The next results deal with the case \(s=t\). It is proved that if \(2\leq t \leq m \leq 2t\) then \(z(m, 2t; t, t)=m\cdot 2t - (2m-t +1)\), and if \(2\leq t \leq m \leq n\) and \(2t < n \leq 3t -1\) then \(z(m, n; t, t)=m\cdot n - (2m + n-3t +1)\).
    0 references
    Zarankiewicz problem
    0 references
    extremal graphs
    0 references
    0 references
    0 references
    0 references

    Identifiers