Degree versions of theorems on intersecting families via stability

DOI10.1016/J.JCTA.2019.06.002MaRDI QIDQ2326331zbMATH OpenOpenAlexWikidataFDO

Authors Andrey B. Kupavskii

Publication date 7 October 2019

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

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

zbMATH Keywords

stabilityextremal set theoryintersecting familiesErdős-Ko-Rado theorem

Mathematics Subject Classification ID

Extremal set theory (05D05)

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.

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

Cites work

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

Cited in

(14)

• Shadows of 3-uniform hypergraphs under a minimum degree condition
• Improved bound on vertex degree version of Erdős matching conjecture
• Minimum degree and diversity in intersecting antichains
• On dividing sets into parts of smaller diameter
• On a degree property of cross-intersecting families
• Families with restricted matching number and multiply covered shadows
• Bounds on Borsuk numbers in distance graphs of a special type
• Diversity
• Maximum size intersecting families of bounded minimum positive co-degree
• Sharp results concerning disjoint cross-intersecting families
• Asymptotics of the independence number of a random subgraph of the graph \(G(n,r,<s)\)
• Degree versions of the Erdős-Ko-Rado theorem and Erdős hypergraph matching conjecture
• 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)\)

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)