Norm-graphs and bipartite Turán numbers

János Kollár; Lajos Rónyai; Tibor Szabó

doi:10.1007/bf01261323

Norm-graphs and bipartite Turán numbers

János Kollár, Lajos Rónyai, Tibor Szabó

Research output: Contribution to journal › Article › peer-review

123 Scopus citations

Abstract

For every t > 1 and positive n we construct explicit examples of graphs G with |V(G)| = n, |E(G)| ≥ c_t · n^2-1/t which do not contain a complete bipartite graph K_t,t!+1. This establishes the exact order of magnitude of the Turán numbers ex(n,K_t,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.

Original language	English (US)
Pages (from-to)	399-406
Number of pages	8
Journal	Combinatorica
Volume	16
Issue number	3
DOIs	https://doi.org/10.1007/bf01261323
State	Published - 1996
Externally published	Yes

All Science Journal Classification (ASJC) codes

Discrete Mathematics and Combinatorics
Computational Mathematics

Access to Document

10.1007/bf01261323

Cite this

@article{66960cddec1b4cc0a3b520fe3ccb0f23,

title = "Norm-graphs and bipartite Tur{\'a}n numbers",

abstract = "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{\'a}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.",

author = "J{\'a}nos Koll{\'a}r and Lajos R{\'o}nyai and Tibor Szab{\'o}",

year = "1996",

doi = "10.1007/bf01261323",

language = "English (US)",

volume = "16",

pages = "399--406",

journal = "Combinatorica",

issn = "0209-9683",

publisher = "Janos Bolyai Mathematical Society",

number = "3",

}

TY - JOUR

T1 - Norm-graphs and bipartite Turán numbers

AU - Kollár, János

AU - Rónyai, Lajos

AU - Szabó, Tibor

PY - 1996

Y1 - 1996

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/0030490245

UR - https://www.scopus.com/inward/citedby.url?scp=0030490245&partnerID=8YFLogxK

U2 - 10.1007/bf01261323

DO - 10.1007/bf01261323

M3 - Article

AN - SCOPUS:0030490245

SN - 0209-9683

VL - 16

SP - 399

EP - 406

JO - Combinatorica

JF - Combinatorica

IS - 3

ER -

Norm-graphs and bipartite Turán numbers

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this