Inverse problems of the Erdős-Ko-Rado type theorems for families of vector spaces and permutations

DOI10.1007/S11425-020-1829-6zbMATH Open1494.05110arXiv2010.12118OpenAlexW3193793606WikidataQ113900262 ScholiaQ113900262MaRDI QIDQ2133641FDOQ2133641

Authors: Xiangliang Kong, Yuanxiao Xi, Bingchen Qian, Gennian Ge 

Publication date: 4 May 2022

Published in: Science China. Mathematics (Search for Journal in Brave)

Abstract: Ever since the famous ErdH{o}s-Ko-Rado theorem initiated the study of intersecting families of subsets, extremal problems regarding intersecting properties of families of various combinatorial objects have been extensively investigated. Among them, studies about families of subsets, vector spaces and permutations are of particular concerns. Recently, the authors proposed a new quantitative intersection problem for families of subsets: For $mathcalFsubseteq[n]choosek$, define its emph{total intersection number} as $mathcalI(mathcalF)=su{m}_{F_1,F_{2}inmathcalF}|F_{1}cap{F}_2|$. Then, what is the structure of $mathcalF$ when it has the maximal total intersection number among all families in $[n]choosek$ with the same family size? In cite{KG2020}, the authors studied this problem and characterized extremal structures of families maximizing the total intersection number of given sizes. In this paper, we consider the analogues of this problem for families of vector spaces and permutations. For certain ranges of family size, we provide structural characterizations for both families of subspaces and families of permutations having maximal total intersection numbers. To some extent, these results determine the unique structure of the optimal family for some certain values of $|mathcalF|$ and characterize the relation between having maximal total intersection number and being intersecting. Besides, we also show several upper bounds on the total intersection numbers for both families of subspaces and families of permutations of given sizes.

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

Recommendations

• Intersection theorems for \(\{0,\pm1\}\)-vectors and \(s\)-cross-intersecting families
• The Erdős-Ko-Rado theorem for vector spaces
• Intersecting families of discrete structures are typically trivial
• The number of \(k\)-intersections of an intersecting family of \(r\)-sets
• An Erdős--Ko--Rado theorem for partial permutations

zbMATH Keywords

permutationsvector spacestotal intersection number

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Linear programming (90C05) Association schemes, strongly regular graphs (05E30) Extremal set theory (05D05)

Cites Work

• Classification of subsets with minimal width and dual width in Grassmann, bilinear forms and dual polar graphs
• Algebraic Graph Theory
• The representation theory of the symmetric groups
• Title not available (Why is that?)
• Title not available (Why is that?)
• On the maximum number of permutations with given maximal or minimal distance
• Stable sets of maximal size in Kneser-type graphs
• Erdős–Ko–Rado Theorems: Algebraic Approaches
• Intersecting families of permutations
• The Hook Graphs of the Symmetric Group
• Intersecting families of discrete structures are typically trivial
• Most probably intersecting families of subsets
• Compressions and probably intersecting families
• The minimum number of disjoint pairs in set systems and related problems
• The Erdős-Ko-Rado theorem for vector spaces
• Shadows and intersections in vector spaces
• Intersecting families of permutations
• Stability for \(t\)-intersecting families of permutations
• A Hilton-Milner theorem for vector spaces
• A note on supersaturated set systems
• Title not available (Why is that?)
• LOW-DEGREE BOOLEAN FUNCTIONS ON , WITH AN APPLICATION TO ISOPERIMETRY
• A quasi-stability result for dictatorships in \(S_n\)
• Lower bound on the dimensions or irreducible representations of symmetric groups and on the exponents of varieties of Lie algebras
• Removal and stability for Erdős-Ko-Rado
• Cayley graph on symmetric group generated by elements fixing \(k\) points
• On the partition associated to the smallest eigenvalues of the \(k\)-point fixing graph
• Disjoint pairs in set systems with restricted intersection
• Structure and supersaturation for intersecting families

Cited In (1)

• \(r\)-cross \(t\)-intersecting families for vector spaces

This page was built for publication: Inverse problems of the Erdős-Ko-Rado type theorems for families of vector spaces and permutations

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