# Tag Info

5

They don't necessarily imply a partition, here is a counterexample. Each set in each $S_i$ will have an even size, while $U$ will have an odd number of elements, this already guarantees that a partition is impossible. $U$ is the nine vertices of a cycle of length $9$, whose edges are colored with $3$ colors, in an alternating way. With the union operation ...

5

The usual terms I know from the theory of posets and lattices are downset and upset (or upper set). Also as the empty set is a subset of every set, I think your first condition is vacuous as long as the system is not empty. Same for the first condition in the second definition. If a downset is closed under joins (in your case set unions), it is called an ...

4

Håstad, Jukna, and Pudlák used the sunflower lemma to prove lower bounds on depth-$3$ $AC^0$ circuits: http://www.csc.kth.se/~johanh/topdowndepth3.pdf This is also explained in Section 6.3 of the book of Jukna on extremal combinatorics, and in Section 11.3 of his book on boolean function complexity.

4

Razborov's lower bound on the size of monotone boolean circuits for the clique problem is an early application in TCS.  A. A. Razborov, Some lower bounds for the monotone complexity of some Boolean functions, Soviet Math. Dokl. 31 (1985), 354-357. A good reference for learning about this is chapter 9 in Jukna's book "Boolean Function Complexity: Advances and ...

4

Sunflower lemma has applications in data structure lower bounds(as mentioned above). For eg. see: Lower Bounds on Non-Adaptive Data Structures Maintaining Sets of Numbers, from Sunflowers.

1

Here I'll show that the statement is true, assuming that $V=U\cup\{s,t\}$, i.e. source and sink are not elements of $U$. Let $S=\bigcap\limits_{R\in\mathcal R}R$, $P=\bigcup\limits_{R\in\mathcal R}R\setminus S$ and $T=U\setminus(S\cup P)$. Construct a flow network $N$ with nodes $U\cup\{s,t\}$ and the following edges: From $s$ to every element of $S$. From ...

1

heres an example PARTITIONING HYPERGRAPHS IN SCIENTIFIC COMPUTING APPLICATIONS THROUGH VERTEX SEPARATORS ON GRAPHS KAYAASLAN et al (there is also some research on hypergraph edge separators used in SAT solvers & other edge separators but not incl it because you asked for vertex separators although there is possibly/presumably some connection.)

1

This doesn't answer the question, but it might be helpful. Mossel and Umans have made a detailed study of the complexity of approximating VC-dimension, when the set system is succinctly presented: On the Complexity of Approximating the VC Dimension http://users.cms.caltech.edu/~umans/papers/MU01-final.ps

Only top voted, non community-wiki answers of a minimum length are eligible