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



Some extremal problem for uniform hypergraph with fixed number of edges.
The answer to your first question should follow from a more or less straightforward application of Kruskal-Katona. 


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.


