×

zbMATH — the first resource for mathematics

Hypergraphs do not jump. (English) Zbl 0663.05047
Let \(G=G(V,E)\) be a graph on \(n\) vertices with \(V=\) vertex set and \(E=\) edge set \(\subset V\times V)\). The ratio of the number edges in the graph to the total number possible is called the density of \(G\), i.e. \(d(G)=| E| /\binom{n}{2}\). There is an unexpected “jump” in the density of a subgraph versus the graph itself. It follows by a theorem of Erdős, Stone and Simonovitis that for any positive integer \(m\geq 2\), real \(0\leq \alpha \leq 1\), and \(n\) sufficiently large, any graph on \(n\) vertices having density greater than \(\alpha\) contains a subgraph on m vertices having density greater than \(\alpha +c\), where \(c\) is some fixed, positive constant not depending on \(m\) or \(n\). For example, in the class of complete \(\ell\)-partite graphs whose partition classes are of size \(k\) there exist subgraphs which are complete \(m\)-points with densities \(=1\) that exceed \(d(G)\) by more than \(c=1/(\ell +1)\) for arbitrary \(k>\ell\) and \(2\leq m\leq \ell\) (since in this case \(d(G)=(k\ell +k)/(k\ell -1)).\)
In this interesting paper, the authors extend the problem to include \(r\)-uniform hypergraphs – graphs whose “edges” are \(r\)-element subsets of \(V\) (in this more general setting, \(d(G)=| E| /\binom{n}{r}\). The precise definition for jump used here is: a real number \(0\leq \alpha \leq 1\) is a jump for \(r\) provided that for any positive \(c\) and any integer \(m\geq r\), an \(r\)-uniform hypergraph with \(n>n_ 0(\varepsilon,m)\) vertices and density at least \(\alpha +\varepsilon\) contains a subgraph on \(m\) vertices with density at least \(\alpha +c\), where \(c=c(\alpha)\) does not depend on \(\varepsilon\) and \(m\). By use of the Lagrange function on graphs and an analysis of complete \(\ell\)-partite \(r\)-uniform graphs, the authors prove that the numbers \(1-1/\ell^{r-1}\) for \(\ell =2r+1,2r+2,\dots\) are not jumps if \(r\geq 3\). This settles a question of Erdős who has offered a $ 1,000 prize for the answer.
Reviewer: D. Kay

MSC:
05C65 Hypergraphs
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] P. Erdös, On extremal problems of graphs and generalized graphs,Israel J. Math. 2 (1965), 183–190. · Zbl 0129.39905 · doi:10.1007/BF02759942
[2] P. Erdös, Problems and Results on Graph and Hypergraphs, Similarities and Differences. · Zbl 0725.05051
[3] P. Erdös andM. Simonovits, A limit theorem in graph theory,Studia Sci. Mat. Hung. Acad. 1 (1966), 51–57.
[4] P. Erdös andA. H. Stone, On the structure of linear graphs,Bull. Amer. Math. Soc. 52 (1946), 1087–1091. · Zbl 0063.01277 · doi:10.1090/S0002-9904-1946-08715-7
[5] V. Jarník,Differentialrechnung, Prague 1956.
[6] G. Katona, T. Nemetz andM. Simonovits, On a graph-problem of Turán,Mat. Lapok 15 (1964), 228–238.
[7] P. Turán, On an extremal problem in graph theory (in Hungarian),Mat. Fiz. Lapok 48 (1941), 436–452.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.