Probably intersecting families are not nested

DOI10.1017/S0963548312000387MaRDI QIDQ4903268zbMATH OpenOpenAlexFDO

Authors Paul A. Russell, Mark Walters

Publication date 21 January 2013

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

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

zbMATH Keywords

most probably intersecting family

Mathematics Subject Classification ID

Extremal set theory (05D05)

Abstract: It is well known that an intersecting family of subsets of an n-element set can contain at most 2^(n-1) sets. It is natural to wonder how `close' to intersecting a family of size greater than 2^(n-1) can be. Katona, Katona and Katona introduced the idea of a `most probably intersecting family.' Suppose that X is a family and that 0<p<1. Let X(p) be the (random) family formed by selecting each set in X independently with probability p. A family X is `most probably intersecting' if it maximises the probability that X(p) is intersecting over all families of size |X|. Katona, Katona and Katona conjectured that there is a nested sequence consisting of most probably intersecting families of every possible size. We show that this conjecture is false for every value of p provided that n is sufficiently large.

Recommendations

• Most probably intersecting hypergraphs
• Most probably intersecting families of subsets
• Compressions and probably intersecting families
• A note on large H-intersecting families
• Almost intersecting families

Cites work

• Compressions and probably intersecting families
• Graphs with maximal number of adjacent pairs of edges
• Most probably intersecting families of subsets
• On the minimum number of disjoint pairs in a family of finite sets
• Simple hypergraphs with maximal number of adjacent pairs of edges

Cited in

(5)

• Most probably intersecting hypergraphs
• Removal and stability for Erdős-Ko-Rado
• Most probably intersecting families of subsets
• Compressions and probably intersecting families
• A simple removal lemma for large nearly-intersecting families

This page was built for publication: Probably intersecting families are not nested

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