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$ Jun 11, 2017 at 2:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.