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

DOI10.1016/J.DAM.2018.12.019MaRDI QIDQ2026320zbMATH OpenOpenAlexFDO

Authors Vikram Kamat, K. Meagher, Susanna Fishel, Glenn H. Hurlbert

Publication date 19 May 2021

Published in Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

Bruhat latticeErdős-Ko-Rado theoremintersecting permutations

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Extremal set theory (05D05)

Abstract: Let $mathscrL=(X,preceq)$ be a lattice. For $calPsubseteqX$ we say that $calP$ is $t$-{it intersecting} if $sfrank(xwedgey)get$ for all $x,yincalP$. The seminal theorem of ErdH{o}s, Ko and Rado describes the maximum intersecting $calP$ in the lattice of subsets of a finite set with the additional condition that $calP$ is contained within a level of the lattice. The ErdH{o}s-Ko-Rado theorem has been extensively studied and generalized to other objects and lattices. In this paper, we focus on intersecting families of permutations as defined with respect to the weak Bruhat lattice. In this setting, we prove analogs of certain extremal results on intersecting set systems. In particular we give a characterization of the maximum intersecting families of permutations in the Bruhat lattice. We also characterize the maximum intersecting families of permutations within the $r^{extrmth}$ level of the Bruhat lattice of permutations of size $n$, provided that $n$ is large relative to $r$.

Recommendations

• Erdős-Ko-Rado theorems in certain semilattices
• An analogue of the Erdős-Ko-Rado theorem for weak compositions
• Erdős-Ko-Rado theorems. Algebraic approaches
• The Erdős-Ko-Rado bound for the function lattice
• A generalization of the Erdős-Ko-Rado theorem
• A generalization of the Erdős-Ko-Rado theorem
• scientific article; zbMATH DE number 1420985
• scientific article; zbMATH DE number 3900758
• A new generalization of the Erdős-Ko-Rado theorem
• On the stability of the Erdös-Ko-Rado theorem

Cites work

• A generalization of the Erdős-Ko-Rado theorem to t-designs in certain semilattices
• Compression and Erdős-Ko-Rado graphs
• Erdős-Ko-Rado theorems. Algebraic approaches
• scientific article; zbMATH DE number 6016068 (Why is no real title available?)
• scientific article; zbMATH DE number 3621717 (Why is no real title available?)
• scientific article; zbMATH DE number 1222942 (Why is no real title available?)
• Improved bounds for Erdős' matching conjecture
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Intersection theorems for systems of finite sets
• Product decompositions of the symmetric group induced by separable permutations
• SOME INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• The complete intersection theorem for systems of finite sets
• The exact bound in the Erdős-Ko-Rado theorem

Cited in

(2)

• An Erdős-Ko-Rado theorem for integer sequences of given rank
• On a Counting Theorem for Weakly Admissible Lattices

This page was built for publication: Erdős-Ko-Rado theorems on the weak Bruhat lattice

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