Sunday, 27 July 2014

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


No comments:

Post a Comment