Take the 2-minute tour ×

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

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.

share|improve this question
add comment

1 Answer

up vote 1 down vote accepted

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.

share|improve this answer
Thank you! I did the same reformulation of problem as you, but i didn't know about Kruskal-Katona theorem. –  ailyr Mar 19 '10 at 20:12
add comment

Your Answer


