Kevash, Peter and Sudakov, Benny (2005) Set Systems with Restricted CrossIntersections and the Minimum Rank of Inclusion Matrices. SIAM Journal on Discrete Mathematics, 18 (4). pp. 713727. ISSN 08954801. doi:10.1137/S0895480103434634. https://resolver.caltech.edu/CaltechAUTHORS:KEEsiamjdm05

PDF
See Usage Policy. 222kB 
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:KEEsiamjdm05
Abstract
A set system is Lintersecting if any pairwise intersection size lies in L, where L is some set of s nonnegative integers. The celebrated FranklRayChaudhuriWilson theorems give tight bounds on the size of an Lintersecting set system on a ground set of size n. Such a system contains at most $\binom{n}{s}$ sets if it is uniform and at most $\sum_{i=0}^s \binom{n}{i}$ sets if it is nonuniform. They also prove modular versions of these results. We consider the following extension of these problems. Call the set systems $\mathcal{A}_1,\ldots,\mathcal{A}_k$ {\em Lcrossintersecting} if for every pair of distinct sets A,B with $A \in \mathcal{A}_i$ and $B \in \mathcal{A}_j$ for some $i \neq j$ the intersection size $A \cap B$ lies in $L$. For any k and for n > n 0 (s) we give tight bounds on the maximum of $\sum_{i=1}^k \mathcal{A}_i$. It is at most $\max\, \{k\binom{n}{s}, \binom{n}{\lfloor n/2 \rfloor}\}$ if the systems are uniform and at most $ \max\, \{k \sum_{i=0}^s \binom{n}{i} , (k1) \sum_{i=0}^{s1} \binom{n}{i} + 2^n\}$ if they are nonuniform. We also obtain modular versions of these results. Our proofs use tools from linear algebra together with some combinatorial ideas. A key ingredient is a tight lower bound for the rank of the inclusion matrix of a set system. The s*inclusion matrix of a set system $\mathcal{A}$ on [n] is a matrix M with rows indexed by $\mathcal{A}$ and columns by the subsets of [n] of size at most s, where if $A \in \mathcal{A}$ and $B \subset [n]$ with $B \leq s$, we define M AB to be 1 if $B \subset A$ and 0 otherwise. Our bound generalizes the wellknown result that if $\mathcal{A} < 2^{s+1}$, then M has full rank $\mathcal{A}$. In a combinatorial setting this fact was proved by Frankl and Pach in the study of null tdesigns; it can also be viewed as determining the minimum distance of the ReedMuller codes.
Item Type:  Article  

Related URLs: 
 
Additional Information:  © 2005 Society for Industrial and Applied Mathematics Received by the editors September 18, 2003; accepted for publication (in revised form) August 13, 2004; published electronically April 22, 2005. We would like to thank an anonymous referee for some useful remarks. This author’s [BS] research was supported in part by NSF grants DMS0355497 and DMS0106589, and by an Alfred P. Sloan fellowship.  
Subject Keywords:  set systems, restricted intersections, inclusion matrices  
Issue or Number:  4  
DOI:  10.1137/S0895480103434634  
Record Number:  CaltechAUTHORS:KEEsiamjdm05  
Persistent URL:  https://resolver.caltech.edu/CaltechAUTHORS:KEEsiamjdm05  
Usage Policy:  No commercial reproduction, distribution, display or performance rights in this work are provided.  
ID Code:  3925  
Collection:  CaltechAUTHORS  
Deposited By:  Archive Administrator  
Deposited On:  19 Jul 2006  
Last Modified:  08 Nov 2021 20:13 
Repository Staff Only: item control page