Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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$.

Thanks!

share|improve this question
add comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.