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.

  • 1
    $\begingroup$ 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. $\endgroup$ – Andrew D. King Apr 13 '12 at 19:35
  • 2
    $\begingroup$ 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 ? $\endgroup$ – Nathann Cohen Apr 13 '12 at 20:45
  • $\begingroup$ Maybe there is some equivalence, but I don't see it. $\endgroup$ – Andrew D. King Apr 13 '12 at 22:00
  • 1
    $\begingroup$ 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 $\endgroup$ – Nathann Cohen Apr 15 '12 at 8:36
  • 1
    $\begingroup$ 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 ! $\endgroup$ – Nathann Cohen Apr 16 '12 at 8:47

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.