Back to Search Start Over

A Note on Non-jumping Numbers for <italic>r</italic>-Uniform Hypergraphs.

Authors :
Liu, Shaoqiang
Peng, Yuejian
Source :
Graphs & Combinatorics. May2018, Vol. 34 Issue 3, p489-499. 11p.
Publication Year :
2018

Abstract

A real number α∈[0,1)&lt;inline-graphic&gt;&lt;/inline-graphic&gt; is a jump for an integer r≥2&lt;inline-graphic&gt;&lt;/inline-graphic&gt; if there exists a constant c&gt;0&lt;inline-graphic&gt;&lt;/inline-graphic&gt; such that any number in (α,α+c]&lt;inline-graphic&gt;&lt;/inline-graphic&gt; cannot be the Tur&#225;n density of a family of &lt;italic&gt;r&lt;/italic&gt;-uniform graphs. Erdős and Stone showed that every number in [0,1) is a jump for r=2&lt;inline-graphic&gt;&lt;/inline-graphic&gt;. Erdős asked whether the same is true for r≥3&lt;inline-graphic&gt;&lt;/inline-graphic&gt;. Frankl and R&#246;dl gave a negative answer by showing the existence of non-jumps for r≥3&lt;inline-graphic&gt;&lt;/inline-graphic&gt;. Recently, Baber and Talbot showed that every number in [0.2299,0.2316)⋃[0.2871,827)&lt;inline-graphic&gt;&lt;/inline-graphic&gt; is a jump for r=3&lt;inline-graphic&gt;&lt;/inline-graphic&gt; using Razborov’s flag algebra method. Pikhurko showed that the set of non-jumps for every r≥3&lt;inline-graphic&gt;&lt;/inline-graphic&gt; has cardinality of the continuum. But, there are still a lot of unknowns regarding jumps for hypergraphs. In this paper, we show that 1+r-1lr-1-rlr-2&lt;inline-graphic&gt;&lt;/inline-graphic&gt; is a non-jump for r≥4&lt;inline-graphic&gt;&lt;/inline-graphic&gt; and l≥3&lt;inline-graphic&gt;&lt;/inline-graphic&gt; which generalizes some earlier results. We do not know whether the same result holds for r=3&lt;inline-graphic&gt;&lt;/inline-graphic&gt;. In fact, when r=3&lt;inline-graphic&gt;&lt;/inline-graphic&gt; and l=3&lt;inline-graphic&gt;&lt;/inline-graphic&gt;, 1+r-1lr-1-rlr-2=29&lt;inline-graphic&gt;&lt;/inline-graphic&gt;, and determining whether 29&lt;inline-graphic&gt;&lt;/inline-graphic&gt; is a jump or not for r=3&lt;inline-graphic&gt;&lt;/inline-graphic&gt; is perhaps the most important unknown question regarding this subject. Erdős offered $500 for answering this question. [ABSTRACT FROM AUTHOR]

Details

Language :
English
ISSN :
09110119
Volume :
34
Issue :
3
Database :
Academic Search Index
Journal :
Graphs & Combinatorics
Publication Type :
Academic Journal
Accession number :
129020783
Full Text :
https://doi.org/10.1007/s00373-018-1888-6