most recent 30 from http://mathoverflow.net 2013-05-25T11:54:00Z http://mathoverflow.net/feeds/user/1539 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/42187/spanning-trees-in-planar-graphs utdiscant 2010-10-14T18:08:05Z 2013-02-07T13:39:26Z

<p>Is the 3-connected graph(s) on $n$ vertices with the minimum number of spanning trees always planar?</p>

http://mathoverflow.net/questions/116437/counting-spanning-trees-when-blowing-up-vertices utdiscant 2012-12-15T11:00:54Z 2012-12-16T04:11:13Z

<p>I have a cubic graph $G$ with $\tau(G)$ spanning trees. Now I replace each vertex in $G$ by a triangle giving me a new graph $G'$ - this operation is sometimes referred to as blowing up the vertex to a triangle or truncating the vertex. I want to find a formula for the number of spanning trees in $G'$.</p> <p>For example, the complete graph on 4 vertices $K_4$ has 16 vertices, and blowing up each vertex in $K_4$ gives a graph on 12 vertices with 6000 spanning trees. If it is not possible to give a formula for blowing up the vertices in a general cubic graph, a formula for the specific case where the starting graph is $K_4$ is much appreciated.</p> <p>As an example of how the operation works, I have provided a drawing of the graph obtained from performing the operation once on $K_4$.</p> <p><img src="http://s18.postimage.org/cgnyvoi89/image.png" alt="alt text"></p>

http://mathoverflow.net/questions/100265/not-especially-famous-long-open-problems-which-anyone-can-understand/103143#103143 utdiscant 2012-07-26T01:30:28Z 2012-07-26T01:30:28Z

<p>The following conjecture by Carsten Thomassen:</p> <blockquote> <p>If $G$ is a 3-connected graph, every longest cycle in $G$ has a chord.</p> </blockquote> <p>Thomassen has proven the conjecture true for 3-connected cubic graphs.</p>

http://mathoverflow.net/questions/53122/mathematical-urban-legends/65794#65794 utdiscant 2011-05-23T20:02:03Z 2011-05-23T20:02:03Z

<p>Heard from Carsten Thomassen:</p> <p>He was giving a lecture on matchings in graph theory, and presented a game where two players would alternately pick some edge in a graph, and at the end one person would win (i do not remember the exact rules of the game). Then Carsten asked the students, which player would win this game. A student raised his hand and replied "You will".</p>

http://mathoverflow.net/questions/52410/testing-connectivity-when-deleting-an-edge utdiscant 2011-01-18T15:02:16Z 2011-01-18T21:21:46Z

<p>I want to determine if a given graph is a minimal 3-connected graph. That is, deletion of any edge will reduce the vertex connectivity to 2.</p> <p>My approach right now, is to look at every edge where both endpoints have degree 4 or more, remove the edge and see if the vertex connectivity has decreased to 2 in the whole graph.</p> <p>My question is, can I use the following approach instead: Look at every edge $e=xy$ where both endpoints have degree $\geq$ 4. Remove $e$ and check if the connectivity between $x$ and $y$ has decreased.</p> <p>So I want to know if I can reduce the problem to considering only the connectivity between the endpoints of the edge I am removing.</p>

http://mathoverflow.net/questions/8609/favorite-popular-math-book/49048#49048 utdiscant 2010-12-11T14:42:20Z 2010-12-11T14:42:20Z

<p><strong>Title:</strong> The Mathematician's Brain</p> <p><strong>Author:</strong> David Ruelle</p> <p><strong>Short description:</strong> (++) A book describing how Mathematics are founded, and tries to give a reasoning for the brain-work needed to do math. </p> <p><strong>From Amazon:</strong> The Mathematician's Brain poses a provocative question about the world's most brilliant yet eccentric mathematical minds: were they brilliant because of their eccentricities or in spite of them? In this thought-provoking and entertaining book, David Ruelle, the well-known mathematical physicist who helped create chaos theory, gives us a rare insider's account of the celebrated mathematicians he has known-their quirks, oddities, personal tragedies, bad behavior, descents into madness, tragic ends, and the sublime, inexpressible beauty of their most breathtaking mathematical discoveries.</p>

http://mathoverflow.net/questions/43125/a-theory-of-3-connected-graphs utdiscant 2010-10-22T04:29:54Z 2010-10-22T15:40:21Z

<p>Does anybody in here know how to get hold of this article:</p> <p>"Tutte, W.T., A Theory of 3-connected graphs, Indag. Math. 23 (1961) 441-455"</p> <p>or have it on paper?</p>

http://mathoverflow.net/questions/42189/number-of-edges-in-low-complexity-graphs utdiscant 2010-10-14T18:12:16Z 2010-10-15T01:06:38Z

<p>Is the number of edges in the 3-connected graph with the minimum number of spanning trees always $\lceil {\frac{3}{2}}n\rceil$?</p>

http://mathoverflow.net/questions/39243/enumerating-triangulations-of-quadrangulations-in-cycles utdiscant 2010-09-18T20:20:04Z 2010-09-18T21:15:30Z

<p>Consider a cycle of length $(2n+2)$. Now we quadrangulate this cycle into $n$ quadrants. We want to enumerate the number of quadrangulations, and we denote this number by $q_n$. Now we triangulate this quadrangulation by triangulating each quadrant. We denote the number of triangulations $t_n$. It is clear that $t_n = 2^nq_n$.</p> <p>Do I count some triangulations multiple times? That is, will some triangulation be the result of multiple different quadrangulations?</p>

http://mathoverflow.net/questions/24662/amortized-expected-and-average-time-complexity/24665#24665 utdiscant 2010-05-14T21:24:31Z 2010-05-14T21:24:31Z

<p>Seems that the article on Amortized Analysis have the answer:</p> <p>"Amortized analysis finds the average running time per operation over a worst-case sequence of operations. Amortized analysis differs from average-case performance in that probability is not involved; amortized analysis guarantees the time per operation over worst-case performance. Notice that average-case analysis and probabilistic analysis are not the same thing as amortized analysis. In average-case analysis, we are averaging over all possible inputs; in probabilistic analysis, we are averaging over all possible random choices; in amortized analysis, we are averaging over a sequence of operations. Amortized analysis assumes worst-case input and typically does not allow random choices."</p>

http://mathoverflow.net/questions/20355/book-for-probability/24664#24664 utdiscant 2010-05-14T21:11:55Z 2010-05-14T21:11:55Z

<p>I would definitely go for "Probability" by Jim Pitman. It is a very good book for learning Probability Theory, one of the best text books I have encountered in my studies.</p>

http://mathoverflow.net/questions/42187/spanning-trees-in-planar-graphs/116474#116474 utdiscant 2013-02-07T11:26:31Z 2013-02-07T11:26:31Z

What about the following graph <a href="http://imgur.com/Eow3L6L" rel="nofollow">imgur.com/Eow3L6L</a> which have 3965 spanning trees?

http://mathoverflow.net/questions/116437/counting-spanning-trees-when-blowing-up-vertices utdiscant 2012-12-15T12:04:39Z 2012-12-15T12:04:39Z

I have provided an image of $K_4$ after the operation has been applied.

http://mathoverflow.net/questions/67045/lower-bound-on-spanning-trees-in-a-connected-graph utdiscant 2011-06-22T22:15:27Z 2011-06-22T22:15:27Z

Hey David. I am doing some research on the graphs with the minimum number of spanning trees. I have some unpublished results right now. If you send me an e-mail, I might have some of the answers you are looking for. I could not find your e-mail anywhere. Write me at utdiscant@gmail.com

http://mathoverflow.net/questions/52410/testing-connectivity-when-deleting-an-edge utdiscant 2011-01-18T15:16:46Z 2011-01-18T15:16:46Z

It seems to be the same thing when I try to use that approach in my code.

http://mathoverflow.net/questions/42187/spanning-trees-in-planar-graphs utdiscant 2010-10-15T02:07:24Z 2010-10-15T02:07:24Z

It is not true that all minimal 3-connected graphs are planar, look for example at K3,3.

http://mathoverflow.net/questions/42187/spanning-trees-in-planar-graphs utdiscant 2010-10-15T02:02:48Z 2010-10-15T02:02:48Z

And of course I meant &quot;fewer edges&quot; instead of &quot;fewer vertices&quot; in my last comment.

http://mathoverflow.net/questions/42189/number-of-edges-in-low-complexity-graphs/42242#42242 utdiscant 2010-10-15T02:01:19Z 2010-10-15T02:01:19Z

Also, I can't seem to find the paper [&quot;3-connected graphs of minimal size&quot;.] which you are referring too, do you have a link?

http://mathoverflow.net/questions/42189/number-of-edges-in-low-complexity-graphs/42242#42242 utdiscant 2010-10-15T01:57:47Z 2010-10-15T01:57:47Z

It is true that the 3-connected graph(s) with the minimum number of spanning trees must be found among the 3-connected graphs with the minimal number of edges, but this is not enough to draw a conclusion, since it is easy to find examples showing that minimal 3-connected graphs have more than ceil(3n/2) edges. For instance the Wheel Graph on 6 vertices is a minimal 3-connected graph, but has 10 edges.

http://mathoverflow.net/questions/42189/number-of-edges-in-low-complexity-graphs utdiscant 2010-10-14T20:50:29Z 2010-10-14T20:50:29Z

It seems there are no classes which achieve the minimum always. An example of a class which achieve a low number of spanning trees are Prism Graphs, but they do not always have the minimum number of spanning trees.

http://mathoverflow.net/questions/42187/spanning-trees-in-planar-graphs utdiscant 2010-10-14T19:27:35Z 2010-10-14T19:27:35Z

As stated in my previous comment, that is what Tutte conjectured, but this is wrong, and a counter example can be found at 30 edges. Take a path of length 2 and a path of length 12, then glue each vertex from the short path to each vertex of the long path. This graph is 3-connected, planar and has fewer vertices than the wheel-graph of the same size.

http://mathoverflow.net/questions/42187/spanning-trees-in-planar-graphs utdiscant 2010-10-14T19:17:53Z 2010-10-14T19:17:53Z

This question came up when considering an old conjecture of Tutte &quot;Among all 3-connected planar graphs with 2m edges, the graph with the smallest number of spanning trees is the wheel W(m+1)&quot; which is wrong. Then it became interesting to look at a more general version of this question.

http://mathoverflow.net/questions/39243/enumerating-triangulations-of-quadrangulations-in-cycles/39247#39247 utdiscant 2010-09-18T23:11:24Z 2010-09-18T23:11:24Z

This approach seems easiest to prove.

http://mathoverflow.net/questions/39243/enumerating-triangulations-of-quadrangulations-in-cycles utdiscant 2010-09-18T20:21:54Z 2010-09-18T20:21:54Z

When I talk about quadrangulations, I mean planar quadrangulations.