MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

For a connected graph $G$, let $N_i$ be the number of connected subgraphs of size $i$. The vector $\langle N_0, N_1, \dots \rangle$ is also known as the $f$-vector for the graph.

As a superset of a connected subgraph is also connected, the Kruskal-Katona bounds apply to $f$-vector, giving lower bounds for $N_i$ of the form $$ N_i \geq \binom{m_j}{i} + \binom{m_{j-1}}{i-1} + \dots + $$ where, for some $j > i$, we have that $m_j, \dots$ is the $j$-canonical representation of $N_j$.

For graph connectivity the Kruskal-Katona are known not to be tight. Stanley discusses stronger bounds for $N_i$ due its shellability. However, these bounds are defined in terms of the $h$-vector, which is related to the $f$-vector.

Is there any way to translate these bounds into bounds on the $f$-vector itself? Basically, I would like a tight lower bound on $N_i$, given $N_j$ for $j > i$.


share|cite|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.