Intersecting families, signed sets, and injection

MaRDI QIDQ5109063zbMATH OpenFDO

Authors Carl Feghali

Publication date 7 May 2020

Full work available at URL https://arxiv.org/abs/1912.10324, http://ajc.maths.uq.edu.au/pdf/76/ajc_v76_p226.pdf

zbMATH Keywords

finite setsintersecting familyintersection

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Signed and weighted graphs (05C22) Extremal set theory (05D05)

Abstract: Let $k,r,ngeq1$ be integers, and let $S_{n,k,r}$ be the family of $r$-signed $k$-sets on $[n]=1,dots,n$ given by ${\displaystyle }$ mathcal{S}_{n, k, r} = Big{{(x_1, a_1), dots, (x_k, a_k)}: {x_1, dots, x_k} in �inom{[n]}{k}, a_1, dots, a_k in [r] Big}. ${\displaystyle }$ A family $mathcalAsubseteq{S}_{n,k,r}$ is emph{intersecting} if $A,BinmathcalA$ implies $AcapBot=emptyset$. A well-known result (first stated by Meyer and proved using different methods by Deza and Frankl, and Bollob'as and Leader) states that if $mathcalAsubseteqmathcal{S}_{n,k,r}$ is intersecting, $rgeq2$ and $1leqkleqn$, then ${\displaystyle }$|mathcal{A}| leq r^{k-1}�inom{n-1}{k - 1}.${\displaystyle }$ We provide a proof of this result by injection (in the same spirit as Frankl and F"uredi's and Hurlbert and Kamat's injective proofs of the ErdH{o}s--Ko--Rado Theorem, and Frankl's and Hurlbert and Kamat's injective proofs of the Hilton--Milner Theorem) whenever $rgeq2$ and $1leqkleqn/2$, leaving open only some cases when $kleqn$.

Recommendations

• Multiple cross-intersecting families of signed sets
• On t-intersecting families of signed sets and permutations
• Intersecting and cross-intersecting families of labeled sets
• On cross-intersecting families of sets
• Almost Intersecting Families of Sets
• Some results on intersecting families of subsets
• Cross-intersecting families of labeled sets
• INTERSECTING FAMILIES OF SEPARATED SETS
• Intersecting families of sets and permutations: a survey
• Cross-intersecting families of finite sets

Cites work

• A Hilton-Milner-type theorem and an intersection conjecture for signed sets
• A new short proof of the EKR theorem
• A simple proof of the Erdős-Chao Ko-Rado theorem
• A simple proof of the Hilton-Milner theorem
• An Erdős-Ko-Rado theorem for signed sets
• An Erdős-Ko-Rado theorem for the subcubes of a cube
• An intersection theorem for weighted sets
• An ordered version of the Erdős-Ko-Rado theorem
• Erdös–Ko–Rado Theorem—22 Years Later
• Erdős-Ko-Rado from Kruskal-Katona
• Extremal Finite Set Theory
• Intersecting systems of signed sets
• Intersection theorems for systems of finite sets
• INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• Multiple cross-intersecting families of signed sets
• New injective proofs of the Erdős-Ko-Rado and Hilton-Milner theorems
• Non-trivial intersecting families
• SOME INTERSECTION THEOREMS FOR SYSTEMS OF FINITE SETS
• The diametric theorem in Hamming spaces---optimal anticodes

Cited in

(5)

• On t-intersecting families of signed sets and permutations
• New injective proofs of the Erdős-Ko-Rado and Hilton-Milner theorems
• A Hilton-Milner-type theorem and an intersection conjecture for signed sets
• Large non-trivial \(t\)-intersecting families of signed sets
• Multiple cross-intersecting families of signed sets

This page was built for publication: Intersecting families, signed sets, and injection

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