User nomatter - MathOverflow

Counting graphs with diameter d

2012-10-12T19:19:18Z

Is there some known sequence which gives me the number of graphs with diameter d?

Similarly is there some 2D-sequence which gives me the number of graphs with n vertices and diameter d?

If there is no closed form is there some way to study this problem in terms of generating function and apply to it some asymptotic analysis like in "Analytic Combinatorics": http://algo.inria.fr/flajolet/Publications/books.html

How can pushing a vertex in a polytope lead to merging facets?

2012-06-07T08:56:03Z

I'm trying to understand the Lemma 2.2 and Corollary 2.3 of Francisco Santos paper "A counterexample to the Hirsch conjecture": http://arxiv.org/abs/1006.2814

Corollary 2.3 is a proof of a result of Klee saying: "For every polytope Q there is a simplicial polytope Q of the same dimension and number of vertices and with the same or greater dual diameter."

The definiton of pushing is the following: We say that a polytope $Q'$ is obtained from $Q$ by pushing $v$ if the vertices of $Q'$ are $ V \setminus \lbrace v \rbrace \cup \lbrace v' \rbrace $ for a certain point $v' \in Q$ and the only hyperplanes spanned by vertices of $Q$ that intersect the segment $vv'$ are those containing $v$.

For proving that corollary the following Lemma 2.2 is stated and proofed:

Let $Q'$ be obtained from $Q$ by pushing $v$. Then:

Let $F'$ be a facet of $Q$ with vertex set $S$ and let $S = S' \setminus \lbrace v' \rbrace \cup \lbrace v \rbrace$ or $S = S'$ depending on whether $v' \in F'$ or not. Then, there is a unique facet $\phi(F')$ of $Q$ such that $S \subset \phi(F' )$.
The map $F' → \phi(F')$ sends adjacent facets of $Q'$ to either the same or adjacent facets of $Q$. (That is, $\phi$ is a simplicial map between the dual graphs of $Q'$ and $Q$).

In the definition of the Lemma and also in its proof (see the paper, especially te sentence proofing part 2) it is mentioned that at the "beginning" of the pushing it can happen that two facets merge. I wasn't able to find an example how this can happen. Can anybody explain to me how this is possible?

I also don't get how The Corollary (which is actually the interesting part) is proofed from that Lemma, but i think this has to do with not understanding how this merging of facets happens.

Answer by nomatter for Computing Permutations with Partial Duplicates

2011-09-15T11:09:00Z

You could try to use exponential generating functions.

For each of the N letters you could use the exponential generating function

$$ \sum_{i=0}^D \frac{x^i}{i!} $$

Cause each letter can be used at most D times this is the same for each letter.

Then for using all different letters the egf's have to be multipled (you have N different letters so N times):

$$ \left(\sum_{i=0}^D \frac{x^i}{i!}\right)^N $$

Then you are looking for the amount of different words of length K which is if you expand the expression above (which is possible if you put into it values for $D, N$. Then the coefficient of $x^K$ multiplied by $k!$ is your solution.

What I wasn't able to do right now is trying to expand the generating function into a series without using concrete values for $D$ and $N$.