# Some extremal problem for uniform hypergraph with fixed number of edges.

Let S = {1, .. ,n}.
Let H = (S, E) be the m-uniform hypergraph with r edges. Let F(H, k) = #{B | |B| = k, $\exists R \in E, B \cap R = \emptyset$ } - a number of k-subsets, that doesn't intersect with edges of H.

I am interested in following two problems:

Let r, m, k be fixed parameters.

1. For which hypergraph H, F(H, k) be minimal?
2. For which H, F(H, k) be maximal?

I have a conjecture for the first problem, but can't prove it.

Introduce a total order $\preceq$ on m-element subsets of S: $a \preceq b$ iff $\exists s$, such that $s \in a, s \notin b$ and $\forall i < s, i \in a \cap b \mbox{ or } i \notin a \cup b$.
Example: 3-subsets from 5 element set in ascending order according to $\preceq$.
11100
11010
11001
10110
10101
10011
01110
01101
01011
01111

Conjecture For all k minimal value of F(H, k) achieved on hypergraph, whose edges are r first sets from ${S \choose m}$ according to $\preceq$ order.

-
Namely, if you let $H^c=(S,E')$ be the family of complements, i.e. $X \in E'$ iff $S \setminus X \in E$, then $F(H,k)$ is simply the number of $k$-element subsets contained in edges of $H^c$, which is simply the $l$-th shadow of $H^c$, where $l=(n-m) - k$. You should get that the minimal value of $F(H,k)$ corresponds to the initial segment under the colex ordering for $H^c$; taking the complements of that family should resolve your conjecture.