User nomatter - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T20:51:26Z http://mathoverflow.net/feeds/user/17803 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/109482/counting-graphs-with-diameter-d Counting graphs with diameter d nomatter 2012-10-12T19:19:18Z 2012-10-12T23:32:13Z <p>Is there some known sequence which gives me the number of graphs with diameter d?</p> <p>Similarly is there some 2D-sequence which gives me the number of graphs with n vertices and diameter d?</p> <p>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": <a href="http://algo.inria.fr/flajolet/Publications/books.html" rel="nofollow">http://algo.inria.fr/flajolet/Publications/books.html</a></p> http://mathoverflow.net/questions/99019/how-can-pushing-a-vertex-in-a-polytope-lead-to-merging-facets How can pushing a vertex in a polytope lead to merging facets? nomatter 2012-06-07T08:56:03Z 2012-06-07T22:50:09Z <p>I'm trying to understand the Lemma 2.2 and Corollary 2.3 of Francisco Santos paper "A counterexample to the Hirsch conjecture": <a href="http://arxiv.org/abs/1006.2814" rel="nofollow">http://arxiv.org/abs/1006.2814</a></p> <p>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."</p> <p>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$.</p> <p>For proving that corollary the following Lemma 2.2 is stated and proofed:</p> <p>Let $Q'$ be obtained from $Q$ by pushing $v$. Then:</p> <ol> <li>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' )$.</li> <li>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$).</li> </ol> <p>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?</p> <p>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.</p> http://mathoverflow.net/questions/75447/computing-permutations-with-partial-duplicates/75503#75503 Answer by nomatter for Computing Permutations with Partial Duplicates nomatter 2011-09-15T11:09:00Z 2011-09-15T11:09:00Z <p>You could try to use exponential generating functions.</p> <p>For each of the N letters you could use the exponential generating function</p> <p>$$\sum_{i=0}^D \frac{x^i}{i!}$$</p> <p>Cause each letter can be used at most D times this is the same for each letter.</p> <p>Then for using all different letters the egf's have to be multipled (you have N different letters so N times):</p> <p>$$\left(\sum_{i=0}^D \frac{x^i}{i!}\right)^N$$</p> <p>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.</p> <p>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$.</p>