6
$\begingroup$

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.

Improve this question
$\endgroup$
7
  • 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
    Commented Apr 13, 2012 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
    Commented Apr 13, 2012 at 20:45
  • $\begingroup$ Maybe there is some equivalence, but I don't see it. $\endgroup$
    – Andrew D. King
    Commented Apr 13, 2012 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
    Commented Apr 15, 2012 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
    Commented Apr 16, 2012 at 8:47

0

Reset to default

You must log in to answer this question.