Relation between minimum degrees of hypergraphs

41 Views Asked by At

It is indicated by Page 146 of https://link.springer.com/content/pdf/10.1007%2F978-3-319-24298-9.pdf : an $n$-vertex $k$-uniform hypergraph $H$ has vertex-set $V=[n]$ and edge-set $E\subseteq\binom{[n]}{k}$. Given a vertex subset $S\subseteq V$, the degree of it is defined to be $$d_H(S):=|\{e\in E(H):S\subseteq e\}|.$$ And minimum $i$-degree of $H$ is the minimum degree over all $i$-vertex sets $S$, i.e., $$\delta_i(H):=\min_{S\subseteq V:|S|=i}d_H(S).$$

I found a relation says that for all $n$-vertex $k$-uniform hypergraphs $H$ and $0\le i\le k-2$, $$\frac{\delta_i(H)}{\binom{n-i}{k-i}}\ge \frac{\delta_{i+1}(H)}{\binom{n-i-1}{k-i-1}}.$$

I am wondering why it is true. Maybe by some double counting argument?

1

There are 1 best solutions below

0
On BEST ANSWER

We have $$(k-i)\delta_i(H)\ge (n-i)\delta_{i+1}(H)$$ by double-counting $$\{(v,e):S\subseteq e\in E(H), v\in e\setminus S\},$$ where $S$ is the $i$-vertex set with degree $\delta_i(H)$. And it is easy to see the equivalence between the two inequalities.