Probabilistic Extensions of the Erd\H os-Ko-Rado Property

A family of sets is intersecting if no two of its members are disjoint, and has the Erd\H{o}s-Ko-Rado property (or is EKR) if each of its largest intersecting subfamilies has nonempty intersection. Denote by $\mathcal{H}_k(n,p)$ the random family in which each $k$-subset of $\{1\dots n\}$ is present with probability $p$, independent of other choices. A question first studied by Balogh, Bohman and Mubayi asks: \[ \mbox{for what $p=p(n,k)$ is $\mathcal{H}_k(n,p)$ likely to be...

A family of subsets of $\{1,\ldots,n\}$ is called {\it intersecting} if any two of its sets intersect. A classical result in extremal combinatorics due to Erd\H{o}s, Ko, and Rado determines the maximum size of an intersecting family of $k$-subsets of $\{1,\ldots, n\}$. In this paper we study the following problem: how many intersecting families of $k$-subsets of $\{1,\ldots, n\}$ are there? Improving a result of Balogh, Das, Delcourt, Liu, and Sharifzadeh, we determine this q...

A family $\mathcal{F}$ is $t$-$\it{intersecting}$ if any two members have at least $t$ common elements. Erd\H os, Ko, and Rado proved that the maximum size of a $t$-intersecting family of subsets of size $k$ is equal to $ {{n-t} \choose {k-t}}$ if $n\geq n_0(k,t)$. Alon, Aydinian, and Huang considered families generalizing intersecting families, and proved the same bound. In this paper, we give a strengthening of their result by considering families generalizing $t$-intersect...

For natural numbers $n,r \in \mathbb{N}$ with $n\ge r$, the Kneser graph $K(n,r)$ is the graph on the family of $r$-element subsets of $\{1,\dots,n\}$ in which two sets are adjacent if and only if they are disjoint. Delete the edges of $K(n,r)$ with some probability, independently of each other: is the independence number of this random graph equal to the independence number of the Kneser graph itself? We answer this question affirmatively as long as $r/n$ is bounded away fro...

The classical Erd\H os-Ko-Rado theorem states that if $k\le\floor{n/2}$ then the largest family of pairwise intersecting $k$-subsets of $[n]=\{0,1,...,n\}$ is of size ${{n-1}\choose{k-1}}$. A family of $k$ subsets satisfying this pairwise intersecting property is called an EKR family. We generalize the EKR property and provide asymptotic lower bounds on the size of the largest family ${\cal A}$ of $k$-subsets of $[n]$ that satisfies the following property: For each $A,B,C\in{...

Two families $\mathcal{A}$ and $\mathcal{B}$, of $k$-subsets of an $n$-set, are {\em cross $t$-intersecting} if for every choice of subsets $A \in \mathcal{A}$ and $B \in \mathcal{B}$ we have $|A \cap B| \geq t$. We address the following conjectured cross $t$-intersecting version of the Erd\H os--Ko--Rado Theorem: For all $n \geq (t+1)(k-t+1)$ the maximum value of $|\mathcal{A}||\mathcal{B}|$ for two cross $t$-intersecting families $\mathcal{A}, \mathcal{B} \subset\binom{[n]}...

Our main result is a new upper bound for the size of k-uniform, L-intersecting families of sets, where L contains only positive integers. We characterize extremal families in this setting. Our proof is based on the Ray-Chaudhuri--Wilson Theorem. As an application, we give a new proof for the Erd\H{o}s-Ko-Rado Theorem, improve Fisher's inequality in the uniform case and give an uniform version of the Frankl-F\"uredi conjecture .

A $k\ell$-subset partition, or $(k,\ell)$-subpartition, is a $k\ell$-subset of an $n$-set that is partitioned into $\ell$ distinct classes, each of size $k$. Two $(k,\ell)$-subpartitions are said to $t$-intersect if they have at least $t$ classes in common. In this paper, we prove an Erd\H{o}s-Ko-Rado theorem for intersecting families of $(k,\ell)$-subpartitions. We show that for $n \geq k\ell$, $\ell \geq 2$ and $k \geq 3$, the largest $1$-intersecting family contains at mos...

Let $\A\subset\binom{[n]}{r}$ be a compressed, intersecting family and let $X\subset[n]$. Let $\A(X)={A\in\A:A\cap X\ne\emptyset}$ and $\S_{n,r}=\binom{[n]}{r}({1})$. Motivated by the Erd\H{o}s-Ko-Rado theorem, Borg asked for which $X\subset[2,n]$ do we have $|\A(X)|\le|\S_{n,r}(X)|$ for all compressed, intersecting families $\A$? We call $X$ that satisfy this property EKR. Borg classified EKR sets $X$ such that $|X|\ge r$. Barber classified $X$, with $|X|\le r$, such that $X...

We investigate the asymptotic version of the Erd\H{o}s-Ko-Rado theorem for the random $k$-uniform hypergraph $\mathcal{H}^k(n,p)$. For $2 \leq k(n) \leq n/2$, let $N=\binom{n}k$ and $D=\binom{n-k}k$. We show that with probability tending to 1 as $n\to\infty$, the largest intersecting subhypergraph of $\mathcal{H}^k(n,p)$ has size $(1+o(1))p\frac kn N$, for any $p\gg \frac nk\ln^2\!\left(\frac nk\right)D^{-1}$. This lower bound on $p$ is asymptotically best possible for $k=\Th...