Degree versions of theorems on intersecting families via stability

DOI10.1016/J.JCTA.2019.06.002zbMATH Open1421.05090arXiv1810.00915OpenAlexW2964166146WikidataQ127624242 ScholiaQ127624242MaRDI QIDQ2326331FDOQ2326331

Andrey B. Kupavskii

Publication date: 7 October 2019

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

Abstract: The matching number of a family of subsets of an $n$-element set is the maximum number of pairwise disjoint sets. The families with matching number $1$ are called intersecting. The famous ErdH os-Ko-Rado theorem determines the size of the largest intersecting family of $k$-sets. Its generalization to the families with larger matching numbers, known under the name of the ErdH{o}s Matching Conjecture, is still open for a wide range of parameters. In this paper, we address the degree versions of both theorems. More precisely, we give degree and $t$-degree versions of the ErdH{o}s-Ko-Rado and the Hilton-Milner theorems, extending the results of Huang and Zhao, and Frankl, Han, Huang and Zhao. We also extend the range in which the degree version of the ErdH{o}s Matching conjecture holds.

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

Recommendations

• Degree versions of the Erdős-Ko-Rado theorem and Erdős hypergraph matching conjecture
• A degree version of the Hilton-Milner theorem
• Erdős-Ko-Rado theorem with conditions on the maximal degree
• The structure of large intersecting families
• Size and structure of large \((s,t)\)-union intersecting families

zbMATH Keywords

stability[https://portal.mardi4nfdi.de/w/index.php?title=+Special%3ASearch&search=Erd%EF%BF%BD%EF%BF%BDs-Ko-Rado+theorem&go=Go Erd��s-Ko-Rado theorem]extremal set theoryintersecting families

Mathematics Subject Classification ID

Extremal set theory (05D05)

Cites Work

• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Embedding large subgraphs into dense graphs
• Independence numbers and chromatic numbers of the random subgraphs of some distance graphs
• On Perfect Matchings in Uniform Hypergraphs with Large Minimum Vertex Degree
• On the stability of the Erdős-Ko-Rado theorem
• Title not available (Why is that?)
• SOME INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• On the stability of the independence number of a random subgraph
• Nontrivial independent sets of bipartite graphs and cross-intersecting families
• Independence numbers of random subgraphs of some distance graph
• Independence numbers of random subgraphs of distance graphs
• Erdős-Ko-Rado theorem with conditions on the maximal degree
• Improved bounds for Erdős' matching conjecture
• SETS OF INDEPENDENT EDGES OF A HYPERGRAPH
• Large matchings in uniform hypergraphs and the conjectures of Erdős and samuels
• The maximum sum and the maximum product of sizes of cross-intersecting families
• Invitation to intersection problems for finite sets
• Degree versions of the Erdős-Ko-Rado theorem and Erdős hypergraph matching conjecture
• The maximum size of a non-trivial intersecting uniform family that is not a subfamily of the Hilton-Milner family
• The maximum product of weights of cross-intersecting families
• The structure of large intersecting families
• On the stability of some Erdős-Ko-Rado type results
• On random subgraphs of Kneser graphs and their generalizations
• A note on Huang-Zhao theorem on intersecting families with large minimum degree
• On the maximum number of edges in a hypergraph with given matching number
• Families with no s pairwise disjoint sets
• On the chromatic number of a random subgraph of the Kneser graph
• Stability versions of Erdős-Ko-Rado type theorems via isoperimetry
• Two extremal problems on intersecting families
• Diversity of uniform intersecting families
• Regular bipartite graphs and intersecting families
• Counting Intersecting and Pairs of Cross-Intersecting Families
• Sharp results concerning disjoint cross-intersecting families
• Erdős-Ko-Rado theorem for \(\{0,\pm 1\}\)-vectors
• A degree version of the Hilton-Milner theorem
• Non-trivially intersecting multi-part families
• Two problems on matchings in set families -- in the footsteps of Erdős and Kleitman

Cited In (12)

• Asymptotics of the independence number of a random subgraph of the graph \(G(n,r,<s)\)
• On stability of the independence number of a certain distance graph
• Asymptotics of the independence number of a random subgraph of the graph \(G(n, r, < s)\)
• Improved bound on vertex degree version of Erdős matching conjecture
• Shadows of 3-Uniform Hypergraphs under a Minimum Degree Condition
• Sharp results concerning disjoint cross-intersecting families
• Minimum degree and diversity in intersecting antichains
• Bounds on Borsuk numbers in distance graphs of a special type
• Diversity
• On dividing sets into parts of smaller diameter
• On a degree property of cross-intersecting families
• Maximum Size Intersecting Families of Bounded Minimum Positive Co-degree

This page was built for publication: Degree versions of theorems on intersecting families via stability

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