Structure and supersaturation for intersecting families

zbMATH Open1414.05286arXiv1802.08018MaRDI QIDQ2420562

Yanyan Li

Publication date: 6 June 2019

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Abstract: The extremal problems regarding the maximum possible size of intersecting families of various combinatorial objects have been extensively studied. In this paper, we investigate supersaturation extensions, which in this context ask for the minimum number of disjoint pairs that must appear in families larger than the extremal threshold. We study the minimum number of disjoint pairs in families of permutations and in $k$-uniform set families, and determine the structure of the optimal families. Our main tool is a removal lemma for disjoint pairs. We also determine the typical structure of $k$-uniform set families without matchings of size $s$ when $nge2sk+38s^4$, and show that almost all $k$-uniform intersecting families on vertex set $[n]$ are trivial when $nge(2+o(1))k$.

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

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

removal lemma for disjoint pairs

Mathematics Subject Classification ID

Hypergraphs (05C65) Enumeration in graph theory (05C30) Extremal set theory (05D05)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The clique density theorem
• Improved bounds for Erdős' matching conjecture
• Beyond sum-free sets in the natural numbers
• On the number of \(K_4\)-saturating edges
• On the number of monotone sequences
• A note on supersaturated set systems
• Supersaturation problem for color-critical graphs
• A quasi-stability result for dictatorships in \(S_n\)
• The minimum number of disjoint pairs in set systems and related problems
• Minimum number of additive tuples in groups of prime order
• On a theorem of Rademacher-Turán
• On the spectrum of the derangement graph
• Explicit construction of linear sized tolerant networks
• On the maximum number of permutations with given maximal or minimal distance
• Kleitman's conjecture about families of given size minimizing the number of \(k\)-chains
• Supersaturation in posets and applications involving the container method
• The minimum number of triangles in graphs of given order and size
• Set systems with few disjoint pairs
• Counting substructures. I: Color critical graphs
• Intersecting families of discrete structures are typically trivial
• Removal and Stability for Erdös--Ko--Rado
• Most Probably Intersecting Families of Subsets
• The number of cliques in graphs of given order and size
• A proof of the Cameron-Ku conjecture
• Friedgut--Kalai--Naor theorem for slices of the Boolean cube
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• On the Minimal Density of Triangles in Graphs
• On the Shannon capacity of a graph
• Counting Intersecting and Pairs of Cross-Intersecting Families
• Subsets of posets minimising the number of chains
• Supersaturation in the Boolean lattice
• Families with no s pairwise disjoint sets
• The number of additive triples in subsets of abelian groups
• Sperner's Theorem and a Problem of Erdős, Katona and Kleitman
• On generalized graphs
• SOME INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Intersecting families of permutations

Related Items (7)

Inverse problems of the Erdős-Ko-Rado type theorems for families of vector spaces and permutations ⋮ Sharp threshold for the Erdős–Ko–Rado theorem ⋮ Intersecting families of sets are typically trivial ⋮ Reflect-push methods. Part I: Two dimensional techniques ⋮ The structure of large intersecting families ⋮ Fractional \(L\)-intersecting families ⋮ On the intersecting family process

Recommendations

• Non-trivial intersecting families 👍 👎
• Some results on intersecting families of subsets 👍 👎
• The structure of large non-trivial \(t\)-intersecting families of finite sets 👍 👎
• Structural results for conditionally intersecting families and some applications 👍 👎
• Non-trivial \(d\)-wise intersecting families 👍 👎
• Multiply-intersecting families revisited 👍 👎
• The intersection structure of \(t\)-intersecting families 👍 👎
• The structure of large intersecting families 👍 👎
• A note on saturation for $k$-wise intersecting families 👍 👎
• Non-trivial \(r\)-wise intersecting families 👍 👎

This page was built for publication: Structure and supersaturation for intersecting families