Originator: Robert Jamison (presented by Amelia Tebbe - REGS 2011)
Definitions: A hypergraph $H$ has the Equal Union Property (EUP) if there are disjoint sets $A,B\subset E(H)$ such that $\bigcup_{a\in A}a=\bigcup_{b\in B}b\subset V(H)$. Similarly, $H$ has the more restrictive Full Equal Union Property (FEUP) if there are disjoint sets $A,B\subset E(H)$ such that $\bigcup_{a\in A}a=\bigcup_{b\in B}b= V(H)$.
Background: Lindström [L] showed that if $\{M_i\colon\, i \in I)$ is a family of subsets of a finite set $S$ such that $|I|\gt |S|(r-1)$, then there are $r$ disjoint subsets $I_1,\ldots,I_r$ of $I$ such that $\bigcup_{i\in I_1} M_i=\ldots=\bigcup_{i\in I_r} M_i$. Jacobs and Jamison [JJ] studied the algorithmic aspects of recognizing the EUP.
Problem 1: Let $L(n,k,r)$ be the minimum $m$ such that every $n$-vertex hypergraph whose edges all have at least $k$ vertices satisfies the EUP for $r$ disjoint sets. Find good upper and lower bounds for $L(n,k,r)$. Do the same for the restriction to $k$-uniform hypergraphs.
Problem 2: Let $L(n,k,r)$ be the minimum $m$ such that every $n$-vertex hypergraph whose edges all have at least $k$ vertices satisfies the FEUP for $r$ disjoint sets. Find good upper and lower bounds for $L(n,k,r)$. Do the same for the restriction to $k$-uniform hypergraphs.
References:
[L] B. Lindström, A theorem on families of sets, J. of Combinatorial
Theory (A) 13 (1972), 274–277.
[JJ] David Pokrass Jacobs, Robert E. Jamison: Polynomial recognition of
equal unions in hypergraphs with few vertices of large degree. J. Discrete
Algorithms 4(2): 201-208 (2006)