Skip to main content
replaced http://mathoverflow.net/ with https://mathoverflow.net/
Source Link

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, thisthis 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.

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.

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.

Notice removed Draw attention by Per Alexandersson
Bounty Ended with domotorp's answer chosen by Per Alexandersson
Notice added Draw attention by Per Alexandersson
Bounty Started worth 50 reputation by Per Alexandersson
Source Link
Per Alexandersson
  • 15.8k
  • 10
  • 74
  • 133

Overlapping sets

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.