Hypergraphs not containing a tight tree with a bounded trunk II: 3-trees with a trunk of size 2

Zoltán Füredi, Tao Jiang, Alexandr Kostochka, Dhruv Mubayi, Jacques Verstraëte

Research output: Contribution to journalArticlepeer-review

Abstract

A tight r-tree T is an r-uniform hypergraph that has an edge-ordering e1,e2,…,et such that for each i≥2, ei has a vertex vi that does not belong to any previous edge and ei−vi is contained in ej for some j<i. Kalai conjectured in 1984 that every n-vertex r-uniform hypergraph with more than [Formula presented] edges contains every tight r-tree T with t edges. A trunk T of a tight r-tree T is a tight subtree T of T such that vertices in V(T)∖V(T) are leaves in T. Kalai's Conjecture was proved (Frankl and Füredi, 1987) for tight r-trees that have a trunk of size one. In a previous paper (Füredi et al., 2019) we proved an asymptotic version for all tight r-trees that have a trunk of bounded size. In this paper we continue that work to establish the exact form of Kalai's Conjecture for all tight 3-trees of at least 8 edges that have a trunk of size two.

Original languageEnglish (US)
Pages (from-to)50-59
Number of pages10
JournalDiscrete Applied Mathematics
Volume276
DOIs
StatePublished - Apr 15 2020

Keywords

  • Extremal hypergraph theory
  • Hypergraph trees
  • Turán problem

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Hypergraphs not containing a tight tree with a bounded trunk II: 3-trees with a trunk of size 2'. Together they form a unique fingerprint.

Cite this