Regular subgraphs of uniform hypergraphs

DOI10.1016/J.JCTB.2016.03.001MaRDI QIDQ273181zbMATH OpenOpenAlexFDO

Authors Jaehoon Kim

Publication date 21 April 2016

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1502.02177

zbMATH Keywords

stabilityhypergraphsmatchingsregular subgraphs

Mathematics Subject Classification ID

Hypergraphs (05C65) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: We prove that for every integer $rgeq2$, an $n$-vertex $k$-uniform hypergraph $H$ containing no $r$-regular subgraphs has at most $(1+o(1))n-1choosek-1$ edges if $kgeqr+1$ and $n$ is sufficiently large. Moreover, if $rin3,4$, $rmidk$ and $k,n$ are both sufficiently large, then the maximum number of edges in an $n$-vertex $k$-uniform hypergraph containing no $r$-regular subgraphs is exactly $n-1choosek-1$, with equality only if all edges contain a specific vertex $v$. We also ask some related questions.

Recommendations

• Regular subgraphs of hypercubes
• scientific article; zbMATH DE number 568811
• Two-regular subgraphs of odd-uniform hypergraphs
• Regular subgraphs of dense graphs
• Two-regular subgraphs of hypergraphs
• scientific article; zbMATH DE number 844701
• scientific article; zbMATH DE number 638692
• scientific article; zbMATH DE number 3857159
• Note on regular subgraphs
• Regularity Lemma for k-uniform hypergraphs

Cites work

• scientific article; zbMATH DE number 736294 (Why is no real title available?)
• scientific article; zbMATH DE number 3407723 (Why is no real title available?)
• An intersection theorem for systems of sets
• Dense graphs without 3-regular subgraphs
• Hypergraphs in which all disjoint pairs have distinct unions
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Intersection Theorems for Systems of Sets
• Intersection theorems for systems of sets
• Maximum hypergraphs without regular subgraphs
• On even-degree subgraphs of linear hypergraphs
• On extremal problems of graphs and generalized graphs
• On the maximum number of edges in a triple system not containing a disjoint family of a given size
• Regular subgraphs of dense graphs
• The maximum size of hypergraphs without generalized 4-cycles
• Two-regular subgraphs of hypergraphs

Cited in

(14)

• Configurations containing a given linear hypergraph
• Two-regular subgraphs of hypergraphs
• Two-regular subgraphs of odd-uniform hypergraphs
• scientific article; zbMATH DE number 68366 (Why is no real title available?)
• On even-degree subgraphs of linear hypergraphs
• Maximum hypergraphs without regular subgraphs
• Regular subgraphs of dense graphs
• Indecomposable regular graphs and hypergraphs
• Finding the shortest path for a hypergraph
• Regular subgraphs of linear hypergraphs
• Resolution of the Erdős–Sauer problem on regular subgraphs
• Note on regular subgraphs
• Regular graphs with forbidden subgraphs of \(K_n\) with \(k\) edges
• Finding a minimal spanning hypertree of a weighted hypergraph

This page was built for publication: Regular subgraphs of uniform hypergraphs

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