Hypergraphs do not jump
type: Item
instance of: scholarly article
title: Hypergraphs do not jump
zbMATH Open document ID: 0663.05047
DOI: 10.1007/BF02579215
author: Vojtěch Rödl
author: Peter Frankl
published in: Combinatorica
publication date: 1984-01-01T00:00:00Z
review text: 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…
Mathematics Subject Classification ID: 05C65
zbMATH DE Number: 4083672
zbMATH Keywords: density
zbMATH Keywords: hypergraphs
zbMATH Keywords: jump
MaRDI profile type: Publication
cites work: On extremal problems of graphs and generalized graphs
cites work: Q5203056
cites work: On the structure of linear graphs
full work available at URL: https://doi.org/10.1007/bf02579215
OpenAlex ID: W1978688508
description: scientific article; zbMATH DE number 4083672