Sign up ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

This is sort of a hypergraph-ish question that I feel should be easy to prove or disprove but I can't see it right now.

The setup is as follows. We have a vertex set partitioned in to sets $V_1,\ldots,V_\ell$ of size 8, and transversing these are sets $\mathcal S = \{ S_1,\ldots, S_r \}$ of size at most 9.

  • Each $S_i$ intersects each $V_j$ at most once.

  • Each vertex is in at most two sets of $\mathcal S$.

  • We will partition each $V_i$ into two sets $A_i$ and $B_i$, each of size 4. Let $A$ denote $\cup A_i$ and let $B$ denote $\cup B_i$.

The question is, can we find $A$ and $B$ such that no $S_i$ has at least four vertices in $A$ and at least four vertices in $B$? That is, each $S_i$ has at most three in $A$ or at most three in $B$.

Even better would be $A$ and $B$ such that each $S_i$ has at most two in $A$ or at most two in $B$, but I find this hard to believe.

share|cite|improve this question
Note that even if we replace 8 with $2k$ and ask the corresponding question for large $k$, the Local Lemma and random partitioning doesn't work: Prob that $S_i$ fails is $> 1/(2k+1)$, and each $S_i$ can be non-independent with up to $(2k+1)(2)(2k-1)$ other sets. – Andrew D. King Apr 13 '12 at 19:35
Could we say that you have a graph of maximum degree 9 whose edges are partitionned into matchings of size 8, and that you would like to color these egdes in such a way that each matching has 4 edges of each color and each vertex has degree at most 3 for some color ? – Nathann Cohen Apr 13 '12 at 20:45
Maybe there is some equivalence, but I don't see it. – Andrew D. King Apr 13 '12 at 22:00
Hellooo !!! Well, for me when you say that "each vertex is in atmost two sets of $S$" I head "än edge is incident to at most two vertices". So these things are your edges, the things you want to color. And each $S_i$ is a vertex of your graph, incident to all the edges that belong to $S_i$. Hence you now have a graph of maximum degree 9. Now, your edges are partitionned in sets $V_i$ such that any $S_i$ (any vertex) is adjacent to at most one element of $V_j$, hence the edges representing $V_j$ are the edges of a matching of size 8. Did I overlook something in the transformation ? O_o – Nathann Cohen Apr 15 '12 at 8:36
Oh, you are right, paralell edges ! I always overlook things like that. But why wouldn't you be sure that each matching is of size 8 ? It looks like it s a constraint of the problem you posed : that each set $V_l$ has size 8 ! – Nathann Cohen Apr 16 '12 at 8:47

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.