Erdős–Ko–Rado theorems on the weak Bruhat lattice

NEW

Problem: Reconstructed conjecture: for fixed integers $1\le t\le r$, there is $n_0(t,r)$ such that for all $n\ge n_0(t,r)$, the rank-$r$ level $\mathcal B_r(n)$ of the weak Bruhat lattice on $S_n$ is $t$-EKR. Namely, every family $\mathcal F\subseteq \mathcal B_r(n)$ such that

has size at most the largest $t$-star

The left/right weak-order convention is immaterial, since the two are isomorphic.

Result: The conjecture is true.

Let

Weak order is graded by inversion number, and every element has at most $n-1$ upper covers, since covers are obtained by adjacent transpositions increasing length. Hence, for any $z\in\mathcal B_s(n)$,

Also, if $x\in\mathcal B_r(n)$, then $|L_t(x)|\le \binom rt$, because weak order is inclusion of inversion sets and a rank-$t$ lower element has a $t$-element inversion set contained in the $r$-element inversion set of $x$.

Put $k=r-t$. If $k=0$, then any $t$-intersecting family in $\mathcal B_t(n)$ has size at most $1$, because $x\wedge y$ has rank $t$ only when $x=y$. Thus the result is immediate.

Assume $k\ge1$. There is a $t$-star of order $\Omega(n^k)$: take

Appending in the remaining $n-t-1$ positions any permutation with $k$ inversions gives an element of $\mathcal B_r(n)$ above $a_n$. In particular, using $k$ disjoint adjacent swaps gives at least

such elements.

Now let $\mathcal F\subseteq\mathcal B_r(n)$ be $t$-intersecting. If

then $\mathcal F$ lies inside a $t$-star, so it has size at most the largest $t$-star.

Otherwise choose $x_0\in\mathcal F$. For each $a\in L_t(x_0)$, choose $x_a\in\mathcal F$ with $a\not\le x_a$. For any $y\in\mathcal F$, since $y$ and $x_0$ are $t$-intersecting, choose $a\in L_t(y)\cap L_t(x_0)$. Since $y$ and $x_a$ are $t$-intersecting, choose $b\in L_t(y)\cap L_t(x_a)$. Then $b\ne a$. Thus $y$ lies above both distinct rank-$t$ elements $a,b$, hence above $a\vee b$, whose rank is at least $t+1$. By (1), for each such pair $(a,b)$ there are at most $(n-1)^{r-t-1}$ possible $y$. Since there are at most $\binom rt^2$ such pairs,

For all sufficiently large $n$, this is strictly smaller than the $t$-star of size $\Theta(n^k)$ above. Therefore every maximum $t$-intersecting family is a $t$-star, and $\mathcal B_r(n)$ is $t$-EKR.

Citation: No prior resolution is used here. Standard weak-order facts used above are classical; see Björner–Brenti, Combinatorics of Coxeter Groups, Springer GTM 231, 2005.