1
$\begingroup$

Let $H=(V,E)$ be a $k$-uniform hypergraph with $n$ vertices, that is, $V:=V(H)$ is a $n$-element finite set of vertices and $E:=E(H)\subset\binom{V}{k}$ is a family of $k$-element subsets of $V$.

Given $d$ vertices $v_1,v_2,\ldots,v_d\in V(H)$, $1\leq d\leq k-1$, we denote by $deg_H(v_1,v_2,\ldots,v_d)$ the degree of the $d$-tuple $\{v_1,v_2,\ldots,v_d\}$ in $H$, that is, the number of edges of $H$ which contain $v_1,v_2,\ldots,v_d$.

Further, let $$\delta_d(H):=\delta_d=\min\{deg_H(v_1,v_2,\ldots,v_d):\{v_1,v_2,\ldots,v_d\}\subset V(H)\}.$$

How to prove that $$\delta_{d-1}(H)\geq\frac{n-d+1}{k-d+1}\times\delta_d(H).$$

$\endgroup$

1 Answer 1

3
$\begingroup$

Double counting (as the form of the answer more or less says it has to be). Fix a $(d-1)$-set $X$; sum over vertices $v\not\in X$ the number of edges containing $X$ and $v$. You obviously count every edge containing $X$, and each edge is counted $k-d+1$ times. Since the sum is over $n-d+1$ vertices not in $X$, plugging in the minimum $d$-degree as a lower bound gives the desired inequality.

$\endgroup$
1
  • $\begingroup$ Thanks for your valuable comment that solved my problem entirely. $\endgroup$ Commented Jun 11, 2017 at 2:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .