Mathematics – Combinatorics
Scientific paper
2010-09-21
Mathematics
Combinatorics
There are 12 pages
Scientific paper
We consider the following generalization of the seminal Erd\H{o}s-Ko-Rado theorem, due to Frankl. For some k>=2, let F be a k-wise intersecting family of r-subsets of an n element set X, i.e. for any k sets F1,...,Fk in F, their intersection is nonempty. If r <= ((k-1)n)/k, then |F|<= {n-1 \choose r-1}. We prove a stability version of this theorem, analogous to similar results of Dinur-Friedgut, Keevash-Mubayi and others for the Erd\H{o}s-Ko-Rado theorem. The technique we use is a generalization of Katona's circle method, initially employed by Keevash, which uses expansion properties of a particular Cayley graph of the symmetric group. Next, we extend Frankl's theorem in a graph-theoretic direction. For a graph G, and r>=1, let I^r(G) denote the set of all independent vertex sets of size r. Similarly, let M^r(G) denote the family of all vertex sets of size r containing a maximum independent set, and let H^r(G) be the union of I^r(G) and M^r(G). We will consider k-wise intersecting families in H^r(M_n), where M_n is a perfect matching on 2n vertices, and prove an analog of Frankl's theorem. This theorem can also be considered as a k-wise version of a theorem of Bollob\'as and Leader.
No associations
LandOfFree
k-wise Erdős-Ko-Rado Theorems: Stability Analysis and New Generalizations does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with k-wise Erdős-Ko-Rado Theorems: Stability Analysis and New Generalizations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and k-wise Erdős-Ko-Rado Theorems: Stability Analysis and New Generalizations will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-696861