For every t > 1 and positive n we construct explicit examples of graphs G with |V(G)| = n, |E(G)| ≥ ct · n2-1/t which do not contain a complete bipartite graph Kt,t!+1. This establishes the exact order of magnitude of the Turán numbers ex(n,Kt,s) for any fixed t and all s ≥ t! + 1, improving over the previous probabilistic lower bounds for such pairs (t,s). The construction relies on elementary facts from commutative algebra.
All Science Journal Classification (ASJC) codes
- Discrete Mathematics and Combinatorics
- Computational Mathematics