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.

$\endgroup$
6
  • $\begingroup$ What does 2F'_x mean? It looks like maybe you're assuming some kind of structure on I? $\endgroup$ – Russ Woodroofe Sep 19 '13 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 Sep 19 '13 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 Sep 19 '13 at 19:12
  • $\begingroup$ Ah! I missed that F_x was a count, rather than itself a set. Thanks. $\endgroup$ – Russ Woodroofe Sep 20 '13 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 Sep 21 '13 at 20:12
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.

$\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.

$\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 Sep 20 '13 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 Sep 21 '13 at 9:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.