Cross-intersecting families and primitivity of symmetric systems

DOI10.1016/J.JCTA.2010.09.005zbMATH Open1220.05130arXiv1007.0795OpenAlexW1998914526MaRDI QIDQ618301FDOQ618301

Authors: Jun Wang, Hua Jun Zhang 

Publication date: 14 January 2011

Published in: Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Abstract: Let $X$ be a finite set and $mathfrakpsubseteq{2}^X$, the power set of $X$, satisfying three conditions: (a) $mathfrakp$ is an ideal in $2^X$, that is, if $Ainmathfrakp$ and $BsubsetA$, then $Binmathfrakp$; (b) For $Ain{2}^X$ with $|A|geq2$, $Ainmathfrakp$ if $x,yinmathfrakp$ for any $x,yinA$ with $xeqy$; (c) $xinmathfrakp$ for every $xinX$. The pair $(X,mathfrakp)$ is called a symmetric system if there is a group $Gamma$ transitively acting on $X$ and preserving the ideal $mathfrakp$. A family $A_1,A_2,ldots,A_{m}subseteq{2}^X$ is said to be a cross-$mathfrakp$-family of $X$ if $a,binmathfrakp$ for any $ain{A}_i$ and $bin{A}_j$ with $ieqj$. We prove that if $(X,mathfrakp)$ is a symmetric system and $A_1,A_2,ldots,A_{m}subseteq{2}^X$ is a cross-$mathfrakp$-family of $X$, then [sum_{i=1}^m|{A}_i|leqleft{ �egin{array}{cl} |X| & hbox{if $mleqfrac|X|alpha(X,,mathfrakp)$,} \ m, alpha(X,, mathfrak p) & hbox{if $mgeqfrac|X|alpha(X,,mathfrakp)$,} end{array} ight.] where $alpha(X,,mathfrakp)=max|A|:Ainmathfrakp$. This generalizes Hilton's theorem on cross-intersecting families of finite sets, and provides analogs for cross-$t$-intersecting families of finite sets, finite vector spaces and permutations, etc. Moreover, the primitivity of symmetric systems is introduced to characterize the optimal families.

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

Recommendations

• Cross-intersecting families of finite sets
• Cross-intersecting families of permutations
• Cross-Intersecting Families of Partial Permutations
• Uniformly cross intersecting families
• The maximum product of sizes of cross-intersecting families

zbMATH Keywords

permutationprimitivityintersecting familyfinite vector spacecross-intersecting familysymmetric systemErdős-Ko-Rado theorem

Mathematics Subject Classification ID

Hypergraphs (05C65) Extremal set theory (05D05)

Cites Work

• Homomorphisms of 3-chromatic graphs
• Intersection theorems for systems of finite vector spaces
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Title not available (Why is that?)
• A new proof of the Erdős-Ko-Rado theorem for intersecting families of permutations
• On the maximum number of permutations with given maximal or minimal distance
• Stable sets of maximal size in Kneser-type graphs
• Primitivity and independent sets in direct products of vertex-transitive graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• On Representatives of Subsets
• Intersecting families of permutations
• The exact bound in the Erdős-Ko-Rado theorem
• On the maximal subgroups of the finite classical groups
• An Erdős--Ko--Rado theorem for partial permutations
• Erdős-Ko-Rado-type theorems for colored sets
• Intersecting families in the alternating group and direct product of symmetric groups
• An Erdős-Ko-Rado-type theorem in Coxeter groups.
• On \(t\)-intersecting families of signed sets and permutations
• Multiple cross-intersecting families of signed sets
• The Erdős-Ko-Rado theorem for vector spaces
• Extremal t -intersecting sub-families of hereditary families
• Title not available (Why is that?)
• A short proof of a cross-intersection theorem of Hilton
• Cross-intersecting families of permutations
• Intersecting and cross-intersecting families of labeled sets
• An Intersection Theorem for a Collection of Families of Subsets of a Finite Set
• A classification of certain maximal subgroups of symmetric groups.

Cited In (23)

• An Erdős-Ko-Rado theorem for unions of length 2 paths
• Nearly extremal non-trivial cross \(t\)-intersecting families and \(r\)-wise \(t\)-intersecting families
• Structure of independent sets in direct products of some vertex-transitive graphs
• Independent sets in direct products of vertex-transitive graphs
• Intersecting Families in Symmetric Unions of Direct Products of Set Families
• The maximum product of sizes of cross-intersecting families
• On symmetric intersecting families
• A short proof of an Erdős-Ko-Rado theorem for compositions
• A proof of Frankl's conjecture on cross-union families
• The maximum product of weights of cross-intersecting families
• A Deza-Frankl type theorem for set partitions
• The maximum sum and the maximum product of sizes of cross-intersecting families
• r$r$‐Cross t$t$‐intersecting families via necessary intersection points
• A non-trivial intersection theorem for permutations with fixed number of cycles
• Independent sets in tensor products of three vertex-transitive graphs
• Unifying the representation of symmetric crossing families and weakly partitive families
• How to tidy up a symmetric set-system by use of uncrossing operations
• On non-empty cross-\(t\)-intersecting families
• A cross‐intersection theorem for subsets of a set
• Cross-intersecting subfamilies of levels of hereditary families
• A sharp bound for the product of weights of cross-intersecting families
• Strongly intersecting integer partitions
• Cross-intersecting sub-families of hereditary families

This page was built for publication: Cross-intersecting families and primitivity of symmetric systems

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