Regular subgraphs of uniform hypergraphs

DOI10.1016/J.JCTB.2016.03.001zbMATH Open1334.05094arXiv1502.02177OpenAlexW1582582384MaRDI QIDQ273181FDOQ273181

Authors: Jaehoon Kim 

Publication date: 21 April 2016

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

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.

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

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

zbMATH Keywords

stabilityhypergraphsmatchingsregular subgraphs

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (14)

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

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)