Hypergraphs do not jump (Q1114711): Difference between revisions

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.