Embedding loose spanning trees in 3-uniform hypergraphs
Copyright policy )Embedding loose spanning trees in 3-uniform hypergraphs
In 1995, Komlós, Sárközy and Szemerédi showed that every large n-vertex graph with minimum degree at least (1/2+γ)n contains all spanning trees of bounded degree. We consider a generalization of this result to loose spanning hypertrees in 3-graphs, that is, linear hypergraphs obtained by successively appending edges sharing a single vertex with a previous edge. We show that for all γ and Δ, and n large, every n-vertex 3-uniform hypergraph of minimum vertex degree (5/9+γ)(n/2) contains every loose spanning tree T with maximum vertex degree Δ. This bound is asymptotically tight, since some loose trees contain perfect matchings.
Journal of Combinatorial Theory, Series B, 168
ISSN:0095-8956
- ETH Zurich Switzerland
- London School of Economics and Political Science United Kingdom
- Department of Mathematics
Minimum degree thresholds, Spanning trees, Extremal graph theory, extremal graph theory, Hypergraphs, EP/V038168/1, Trees, Absorption, hypergraph regularity lemma, Hypergraph regularity lemma, Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.), FOS: Mathematics, Mathematics - Combinatorics, 05C35, 05Dxx, 05Cxx, Extremal problems in graph theory, CRSII5 173721, Dirac-type theorems, Extremal graph theory; Hypergraphs; Spanning trees; Minimum degree threshold; Dirac-type theorems; Absorption; Hypergraph regularity lemma, minimum degree thresholds, spanning trees, hypergraphs, external graph theory, Combinatorics (math.CO), Minimum degree threshold, dirac-type theorems, absorption
Minimum degree thresholds, Spanning trees, Extremal graph theory, extremal graph theory, Hypergraphs, EP/V038168/1, Trees, Absorption, hypergraph regularity lemma, Hypergraph regularity lemma, Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.), FOS: Mathematics, Mathematics - Combinatorics, 05C35, 05Dxx, 05Cxx, Extremal problems in graph theory, CRSII5 173721, Dirac-type theorems, Extremal graph theory; Hypergraphs; Spanning trees; Minimum degree threshold; Dirac-type theorems; Absorption; Hypergraph regularity lemma, minimum degree thresholds, spanning trees, hypergraphs, external graph theory, Combinatorics (math.CO), Minimum degree threshold, dirac-type theorems, absorption
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).1 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Average influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Average impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Average
Citations provided by BIP!Popularity provided by BIP!