6
$\begingroup$

Consider the following problem:

Let $F \subseteq 2^{I}$ be a finite family of finite subsets of some index set $I.$

Let $F_x$ be defined as the number of elements of $F$ that contains $x.$

Assume that for each $x \in I,$ $F_x$ is an even number. Under what conditions on $F$ can we find a subset $F'$ of $F$ such that $2F'_x = F_x$ for all $x$?

Note that if $I$ is the set of natural numbers, then for any family $F$ which consists of intervals (satisfying the extra property that $F_x$ is always even), this problem is solvable, and it is easy to prove. (However, it does not generalize to rectangles, where there are counter examples)

Now, there are several ways to generalize/specialize this problem in various directions, for example, this question is such a generalization.

I am curios if there is any research done on problems that is similar to this type of problem above.

Improve this question
$\endgroup$
6
  • $\begingroup$ What does 2F'_x mean? It looks like maybe you're assuming some kind of structure on I? $\endgroup$
    – Russ Woodroofe
    Commented Sep 19, 2013 at 18:04
  • $\begingroup$ 2F'_x just means 2 times the number of subsets in F', that contains x. There is some structure on I of course, namely that F_x is even for every x. A simple example is when I is the real numbers and F is some intervals of the form ]a,b] on the real line. Then F_x being even for all x, is just another way of saying that every point in the real line is covered by an even number of intervals in F. It is easy to show that in this case, we can find a subset F' in F, that covers every point x "half as much" as F. $\endgroup$
    – Per Alexandersson
    Commented Sep 19, 2013 at 18:27
  • $\begingroup$ You might look at some additional restrictions on F, e.g. E in F implies E has two elements. One small F for which there is no F' is the edge set of a triangle. Characterizing "graphs" F with such a property may turn out to be related to an NP-complete problem. Gerhard "Ask Me About System Design" Paseman, 2013.09.19 $\endgroup$
    – Gerhard Paseman
    Commented Sep 19, 2013 at 19:12
  • $\begingroup$ Ah! I missed that F_x was a count, rather than itself a set. Thanks. $\endgroup$
    – Russ Woodroofe
    Commented Sep 20, 2013 at 19:00
  • $\begingroup$ Just a remark. The statement about segments of integers holds even if all $F_x$ are divisible by $k$; in this case you may split the family into $k$ `equal' parts. $\endgroup$
    – Ilya Bogdanov
    Commented Sep 21, 2013 at 20:12

2 Answers 2

Reset to default
4
+50
$\begingroup$

Your question is equivalent to whether the combinatorial discrepancy of the dual hypergraph is zero. (In case you are unfamiliar with the notion, start here: http://en.wikipedia.org/wiki/Discrepancy_of_hypergraphs) This problem is well-known to be NP-complete, you can easily reduce e.g., 1-in-3 SAT to it.

Improve this answer
$\endgroup$
3
$\begingroup$

In Research Problems in Discrete Geometry by Peter Brass, William O. J. Moser, János Pach, in section 2.1 page 75, "Decomposition of multiple packings and coverings", problems with a similar flavour are listed, some with solutions, about covering of the plane with discs, or the space with spheres. Typically, for a covering $F$ of the space by unit spheres, such that for some $a$ (large enough), $$\{a\le F_x\le 2^{\tfrac{a}3-8}, \forall x\}$$ there always exists a partition $F=\tilde F\cup \hat F$ with $\{\tilde F_x\ge 1, \forall x\}$ and $\{\hat F_x\ge 1, \forall x\}$. A probabilistic proof uses the local Lovasz lemma.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Ah, interesting! This do require an infinite number of elements in F, \tilde F and \hat F, it seems like, but this is certainly a bit related. $\endgroup$
    – Per Alexandersson
    Commented Sep 20, 2013 at 9:52
  • $\begingroup$ While a bit related, this problem is not exactly what you are looking for. In case you want to know more about geometric cover-decomposition, let me recommend the first part of my PhD: cs.elte.hu/~dom/cikkek/thesis.pdf $\endgroup$
    – domotorp
    Commented Sep 21, 2013 at 9:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .