Questions tagged [set-system]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2 votes
1 answer
175 views

Is counting the union of power sets NP-complete?

Say we have $n$ sets $A_1,\dots,A_n$ with elements from a universal set $U$. We want to compute the cardinality of $\cup_{i=1}^n 2^{A_i}$ or at least decide on non-trivial bounds. Is this problem NP-...
Joseph Mckinsey's user avatar
11 votes
3 answers
819 views

Applications of sunflower lemma in theoretical computer science

In one lecture by Kewen Wu who is one of the authors of paper Improved bounds for the sunflower lemma, it is said that the sunflower lemma can be applied to many fields like circuit lower bounds ...
Bubble's user avatar
  • 490
6 votes
0 answers
354 views

Optimal set union tree

Suppose we have a ground set of $n$ elements and $m$ sets are defined over them $S_i \subseteq [n]$. Think of the following procedure: At each step take two of the sets, take the union, and add the ...
AmeerJ's user avatar
  • 679
4 votes
1 answer
100 views

Do these set systems imply a partition?

During research, I hit a set theoretic claim that I could neither proof nor disproof. Let $S_1,S_2,S_3$ be three set systems over the same finite universe $U$ such that $S_1,S_2,S_3$ are closed w.r....
Oliver Witt's user avatar
1 vote
1 answer
751 views

Rings and the set of all minimum s-t-cuts

Let $N$ be a flow network with nodes $V$ and edges $E$. For technical reasons, the source side of a minimum $s$-$t$ cut $(A,B)$ with $s \in A$ and $t \in B$ is defined as $A - \{s\}$. Now, let $\...
Oliver Witt's user avatar
1 vote
1 answer
327 views

Is there an analogy of a vertex separator for hypergraphs?

Numerous parameters are defined and considered in the graph theory. I am interested in analogy of these parameters in theory of hypergraphs. Is there some survey or book or lecture notes about ...
terne's user avatar
  • 27
7 votes
2 answers
291 views

The complexity of recognizing optimal set systems for the V-C dimension

The Vapnik-Chervonenkis dimension of a set system $(X,\mathcal S)$ with ground set $X$ is the maximum size of a set $X'\subseteq X$ such that for each subset $X'_i\subseteq X'$, there is a set $S_i\in\...
Florent Foucaud's user avatar
2 votes
1 answer
200 views

Dual/complement of independence system

An independence system is a pair $(I,\mathcal{I})$ where $I$ is a (usually finite) ground set and $\mathcal{I}$ is a collection of subsets of $I$ such that: $\emptyset \in \mathcal{I}$, and $I_1 \...
Austin Buchanan's user avatar
4 votes
0 answers
70 views

Set-systems with some version of independence

Let $S \subset [N]$ be a fixed set of size $n$. Suppose $p$ is the probability that a random set $T$ of size $m$ intersects $S$ in $k$ or more points. That is, $$ \Pr_{\substack{T\subset [N]\\|T| = m}}...
Ramprasad's user avatar
  • 2,482