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