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.
- For which hypergraph H, F(H, k) be minimal?
- 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.
No comments:
Post a Comment