On cross-intersecting families of independent sets in graphs

Details On cross-intersecting families of independent sets in graphs On cross-intersecting families of independent sets in graphs

2010-10-05

arxiv.org/abs/1010.0947v1

Mathematics

Combinatorics

There are 9 pages

Scientific paper

Let A_1,...,A_k be a collection of families of subsets of an n-element set. We say that this collection is cross-intersecting if for any i,j in [k] with i not equal to j, A in A_i and B in A_j implies that the intersection of A and B is nonempty. We consider a theorem of Hilton which gives a best possible upper bound on the sum of the cardinalities of uniform cross-intersecting subfamilies. We formulate a graph-theoretic analogue of Hilton's cross-intersection theorem, similar to the one developed by Holroyd, Spencer and Talbot for the Erdos-Ko-Rado theorem. In particular we build on a result of Borg and Leader for signed sets and prove a theorem for uniform cross-intersecting subfamilies of independent vertex subsets of a disjoint union of complete graphs. We proceed to obtain a result for a much larger class of graphs, namely chordal graphs and propose a conjecture for all graphs. We end by proving this conjecture for the cycle on n vertices.

Affiliated with

Also associated with

No associations

Rating

On cross-intersecting families of independent sets in graphs 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 On cross-intersecting families of independent sets in graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On cross-intersecting families of independent sets in graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-87313