Using the existence of t-designs to prove Erdős-Ko-Rado

DOI10.1016/J.DISC.2018.11.006zbMATH Open1417.05237arXiv1802.03444OpenAlexW2963549579MaRDI QIDQ2317656FDOQ2317656

Authors: Krystal Guo, Chris Godsil 

Publication date: 12 August 2019

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

Abstract: In 1984, Wilson proved the ErdH{o}s-Ko-Rado theorem for $t$-intersecting families of $k$-subsets of an $n$-set: he showed that if $nge(t+1)(k-t+1)$ and $mathcalF$ is a family of $k$-subsets of an $n$-set such that any two members of $mathcalF$ have at least $t$ elements in common, then $$. His proof made essential use of a matrix whose origin is not obvious. In this paper we show that this matrix can be derived, in a sense, as a projection of $t$-$(n,k,1)$ design.

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

Recommendations

• A generalization of the Erdős-Ko-Rado theorem to \(t\)-designs in certain semilattices
• The exact bound in the Erdős-Ko-Rado theorem
• Improved Upper Bounds Concerning the Erdős-Ko-Rado Theorem
• The largest Erdős-Ko-Rado sets in \(2-(v,k,1)\) designs
• Erdős-Ko-Rado theorems in certain semilattices

zbMATH Keywords

linear algebraassociation schemesalgebraic graph theoryextremal set theory

Mathematics Subject Classification ID

Association schemes, strongly regular graphs (05E30) Other designs, configurations (05B30) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Extremal set theory (05D05)

Cites Work

• The complete nontrivial-intersection theorem for systems of finite sets
• The complete intersection theorem for systems of finite sets
• Erdős-Ko-Rado theorems. Algebraic approaches
• The exact bound in the Erdős-Ko-Rado theorem
• On the projection of norm one in \(W^*\)-algebras. III

Cited In (4)

• The Erdős-Ko-Rado theorem for 2-intersecting families of perfect matchings
• The largest Erdős-Ko-Rado sets in \(2-(v,k,1)\) designs
• A generalization of the Erdős-Ko-Rado theorem to \(t\)-designs in certain semilattices
• Linear dependencies among subsets of a finite set

This page was built for publication: Using the existence of \(t\)-designs to prove Erdős-Ko-Rado

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