A short proof of a lower bound for Tur\'an numbers

arXiv1710.10973MaRDI QIDQ6293243FDOQ6293243

Dhruv Mubayi

Publication date: 30 October 2017

Abstract: Let $F$ be a strictly balanced $r$-uniform hypergraph with $e>2$ edges and $r$-density $m$. We give a new short proof of the fact that the Tur'an number $ex(n,F)$ is greater than $c,n^{r-1/m}(logn{)}^{1/(e-1)}$ where $c$ depends only on $F$. The previous proof of this for $r=2$ by Bohman and Keevash and for $rge3$ by Bennett and Bohman used a random greedy process and its analysis using the differential equations method. Our proof uses elementary probabilistic arguments together with a (nontrivial) classical result about independent sets in hypergraphs.

Mathematics Subject Classification ID

Combinatorics (05-XX)

This page was built for publication: A short proof of a lower bound for Tur\'an numbers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6293243)