@article{9d976876717740cbbb40df01440c02f5,

title = "Hypergraphs not containing a tight tree with a bounded trunk",

abstract = "An r-uniform hypergraph is a tight r-tree if its edges can be ordered so that every edge e contains a vertex v that does not belong to any preceding edge and the set e - v lies in some preceding edge. A conjecture of Kalai personal communication published in Frankl and Furedi, J. Combin. Theory Ser. A, 45 (1987), pp. 226-262, generalizing the Erdos-Sos conjecture for trees, asserts that if T is a tight r-tree with t edges and G is an n-vertex r-uniform hypergraph containing no copy of T, then G has at most t-1/r(n/r-1 edges. A trunk T'of a tight r-tree T is a tight subtree such that every edge of T-T' has r-1 vertices in some edge of T' and a vertex outside T'. For r≥3, the only nontrivial family of tight r-trees for which this conjecture has been proved is the family of r-trees with trunk size one in J. Combin. Theory Ser. A, 45 (1987), pp. 226-262. Our main result is an asymptotic version of Kalai's conjecture for all tight trees T of bounded trunk size. This follows from our upper bound on the size of a T-free r-uniform hypergraph G in terms of the size of its shadow. We also give a short proof of Kalai's conjecture for tight r-trees with at most four edges. In particular, for 3-uniform hypergraphs, our result on the tight path of length 4 implies the intersection shadow theorem of Katona Acta Math. Acad. Sci. Hungar., 15 (1964), pp. 329-337.",

keywords = "Hypergraph, Kalai, Tight tree, Turan",

author = "Zoltan Furedi and Tao Jiang and Alexandr Kostochka and Dhruv Mubayi and Jacques Verstraete",

note = "Funding Information: \ast Received by the editors December 12, 2017; accepted for publication (in revised form) February 27, 2019; published electronically May 21, 2019. http://www.siam.org/journals/sidma/33-2/M116092.html Funding: The first author's research is supported by grant K116769 from the National Research, Development and Innovation Office and by Simons Foundation Collaboration grant 317487. The second author's research is partially supported by NSF award DMS-1400249. The third author's research is supported in part by NSF grant DMS-1600592 and by grants 15-01-05867 and 16-01-00499 of the Russian Foundation for Basic Research. The fourth author's research is partially supported by NSF award DMS-1300138. The fifth author's research is supported by NSF award DMS-1556524. \dagger Alfr\e'd R\e'nyi Institute of Mathematics, Hungarian Academy of Sciences, Re\a'ltanoda utca 13-15, H-1053, Budapest, Hungary (zfuredi@gmail.com). \ddagger Department of Mathematics, Miami University, Oxford, OH 45056 (jiangt@miamioh.edu). \S University of Illinois at Urbana-Champaign, Urbana, IL 61801, and Sobolev Institute of Mathematics, Novosibirsk 630090, Russia (kostochk@math.uiuc.edu). \P Department of Mathematics, Statistics and Computer Science, University of Illinois at Chicago, Chicago, IL 60607 (mubayi@uic.edu). \| Department of Mathematics, University of California at San Diego, La Jolla, CA 92093-0112 (jverstra@math.ucsd.edu). Publisher Copyright: {\textcopyright} 2019 Society for Industrial and Applied Mathematics Publications. All rights reserved.",

year = "2019",

doi = "10.1137/17M1160926",

language = "English (US)",

volume = "33",

pages = "862--873",

journal = "SIAM Journal on Discrete Mathematics",

issn = "0895-4801",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "2",

}