Hypergraphs do jump - Mathematics > CombinatoricsReportar como inadecuado




Hypergraphs do jump - Mathematics > Combinatorics - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Abstract: We say that $\alpha\in 0,1$ is a jump for an integer $r\geq 2$ if thereexists $c\alpha>0$ such that for all $\epsilon >0 $ and all $t\geq 1$ any$r$-graph with $n\geq n 0\alpha,\epsilon,t$ vertices and density at least$\alpha+\epsilon$ contains a subgraph on $t$ vertices of density at least$\alpha+c$. The Erd\H os-Stone-Simonovits theorem implies that for $r=2$every $\alpha\in 0,1$ is a jump. Erd\H os showed that for all $r\geq 3$,every $\alpha\in 0,r!-r^r$ is a jump. Moreover he made his famous -jumpingconstant conjecture- that for all $r\geq 3$, every $\alpha \in 0,1$ is ajump. Frankl and R\-odl disproved this conjecture by giving a sequence ofvalues of non-jumps for all $r\geq 3$. We use Razborov-s flag algebra method toshow that jumps exist for $r=3$ in the interval $2-9,1$. These are the firstexamples of jumps for any $r\geq 3$ in the interval $r!-r^r,1$. To be precisewe show that for $r=3$ every $\alpha \in 0.2299,0.2316$ is a jump. We alsogive an improved upper bound for the Tur\-an density of$K 4^-=\{123,124,134\}$: $\piK 4^-\leq 0.2871$. This in turn implies that for$r=3$ every $\alpha \in 0.2871,8-27$ is a jump.



Autor: Rahil Baber, John Talbot

Fuente: https://arxiv.org/







Documentos relacionados