User derrick stolee - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-20T02:41:54Z http://mathoverflow.net/feeds/user/4167 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/123990/does-the-cubic-planar-graph-with-6-3-faces-and-6-7-faces-have-a-name Does the cubic planar graph with 6 3-faces and 6 7-faces have a name? Derrick Stolee 2013-03-08T15:56:15Z 2013-03-09T07:45:45Z <p>There is exactly one cubic planar graph with six 3-faces and six 7-faces (and no other faces). Surely it must have a name. What is it called?</p> <p>Here is a picture of the graph embedded on the plane with a point at infinity:</p> <p><img src="http://www.math.illinois.edu/~stolee/blogimg/plane37.png" alt="alt text"></p> <p>A slightly more general question: How can I find out what the names are of semi-famous graphs? A graph is semi-famous if it has an established name but is not easily found in a standard textbook on the subject.</p> <p>I did try the <a href="http://hog.grinvin.org/" rel="nofollow">House of Graphs</a> by searching using their drawing tool, but found nothing.</p> http://mathoverflow.net/questions/102544/non-uniform-root-of-polynomial-in-open-cube Non-Uniform Root of Polynomial in Open Cube Derrick Stolee 2012-07-18T13:52:43Z 2012-07-18T17:44:47Z <p>I'm looking to find a root $(x_1,\dots,x_n)$ of a polynomial $p \in {\mathbb R}[x_1,\dots,x_n]$ such that $0 \leq x_i &lt; 1$ for all $i$. Further, I know in advance that setting $x_1 = \cdots = x_n$ is a root of $p$, but wish to avoid this root. How can I find at least one of these roots, preferably using a computer?</p> <p>In more detail, $p$ is formed by taking two homogeneous polynomials $q_1, q_2$ (of degrees $d_1$ and $d_2$) where every coefficient is either zero or one, letting $D$ be the least common multiple of $d_1$ and $d_2$, and setting $p = q_1^{D/d_1} - q_2^{D/d_2}$. This is encoding the simultaneous solution to the equations $$q_1(x) = y^{d_1}, \quad q_2(x) = y^{d_2}$$ over $(x_1,\dots,x_n, y) \in [0,1)^{n+1}$.</p> http://mathoverflow.net/questions/71736/number-of-closed-walks-on-an-n-cube/71737#71737 Answer by Derrick Stolee for Number of closed walks on an $n$-cube Derrick Stolee 2011-07-31T16:59:57Z 2011-07-31T16:59:57Z <p>Assuming a "closed walk" can repeat vertices, we can count closed walks starting at $0$ by counting the $r$-sequences of $[n]$ so that each number appears an even number of times. The bijection is given by labeling edges by the coordinate that is toggled between the vertices. You can probably count these sequences by inclusion/exclusion and then multiply by $2^n/r$ to account for the choice of start position.</p> http://mathoverflow.net/questions/29949/what-is-the-shortest-program-for-which-halting-is-unknown/58082#58082 Answer by Derrick Stolee for What is the shortest program for which halting is unknown? Derrick Stolee 2011-03-10T15:48:16Z 2011-03-10T15:48:16Z <p>This doesn't qualify as "shortest" but is my favorite example of why humans can't solve the halting problem:</p> <blockquote> <p>for all odd numbers $n = 1,3,5,...$</p> <p>&nbsp;&nbsp;&nbsp;&nbsp;if $n$ is perfect, halt.</p> </blockquote> <p>This program halts if and only if there is an <a href="http://en.wikipedia.org/wiki/Perfect_number#Odd_perfect_numbers" rel="nofollow">odd perfect number</a>. Of course, the query "is $n$ perfect" is not terribly short (but can be computed by adding one more for loop).</p> http://mathoverflow.net/questions/52333/proving-that-every-graph-is-an-induced-subgraph-of-an-r-regular-graph/52345#52345 Answer by Derrick Stolee for Proving that every graph is an induced subgraph of an r-regular graph Derrick Stolee 2011-01-17T19:34:37Z 2011-01-17T19:34:37Z <p>You can construct the graph explicitly as well, although the one I describe is much larger than the one you get from the Gale-Ryser technique.</p> <p>Take your input graph $G$ with maximum degree $\Delta$ and a number $r \geq \Delta$.</p> <p>Create $(r+1)!$ copies of $G$. For each vertex $v_i \in V(G)$, let $d_i$ be the degree of $v_i$ in $G$. Partition the $(r+1)!$ copies of $G$ into parts of size $r-d_i+1$ (which divides $(r+1)!$). For each part, connect all copies of $v_i$ with edges. This increases the degree at each $v_i$ from $d_i$ by $r-d_i$ to $r$.</p> http://mathoverflow.net/questions/51458/is-there-a-canonical-labelling-package-optimised-for-small-graphs/51460#51460 Answer by Derrick Stolee for Is there a canonical labelling package optimised for small graphs? Derrick Stolee 2011-01-08T04:17:25Z 2011-01-08T04:17:25Z <p>Nauty really is optimized for small graphs, if you use the C library interface. McKay (and others, such as myself) frequently use this library to generate all graphs of a given small order, which requires canonical labeling of small graphs very quickly. This happens many many many times (see <a href="http://oeis.org/A000088" rel="nofollow">http://oeis.org/A000088</a> for the growth of the number of unlabeled graphs). In fact, McKay's program geng can compute all 12,005,168 graphs on 10 nodes in less than an hour on my laptop.</p> http://mathoverflow.net/questions/41194/are-almost-all-strongly-regular-graphs-rigid Are "almost all" strongly regular graphs rigid? Derrick Stolee 2010-10-05T18:53:36Z 2010-10-06T14:55:27Z <p>I have heard through the academic rumor mill (my advisor heard from so-and-so about a result they heard from big-name who saw it in some journal, etc.) of the following theorem:</p> <p><strong>Theorem:</strong> Almost all <a href="http://en.wikipedia.org/wiki/Strongly_regular_graph" rel="nofollow">strongly regular graphs</a> have trivial automorphism group.</p> <p>This contrasts that most known families of strongly regular graphs have high symmetry, due to their constructions using algebraic objects.</p> <p>Does anyone know the reference for this theorem? Also, what is the measure used to describe "almost all"?</p> http://mathoverflow.net/questions/26467/reconstructing-maximal-planar-graphs Reconstructing Maximal Planar Graphs Derrick Stolee 2010-05-30T16:14:14Z 2010-05-30T18:08:31Z <p>Has it been proven that maximal planar graphs are reconstructible? </p> <p>It seems like an easy result, but I am unable to find it in the literature. Classes of planar graphs that I know are reconstructible are: maximal outerplanar (Manvel 1970), maximal minimally non-outerplanar (has a single interior vertex) (Kunni, Annigeri, 1979), and classes where planar isn't the key property: like trees or cacti (Geller, Manvel, 1969).</p> <p>Perhaps this has not been explicitly answered because it was only recently (Bilinski, Kwon, Yu, 2007) when it was proven that planar graphs are recognizable, which is the "hard" part of this result.</p> <p>Bonus question: Are there other classes of planar graphs that are known to be reconstructible?</p> http://mathoverflow.net/questions/123990/does-the-cubic-planar-graph-with-6-3-faces-and-6-7-faces-have-a-name/124053#124053 Comment by Derrick Stolee Derrick Stolee 2013-03-09T14:10:49Z 2013-03-09T14:10:49Z I'm familiar with the Sage graph library, but not familiar with a functionality that allows me to give it a graph and ask for its name. The only thing I can think about is trying all graph.NAME objects and testing isomorphism (and some are parameterized). http://mathoverflow.net/questions/102544/non-uniform-root-of-polynomial-in-open-cube/102567#102567 Comment by Derrick Stolee Derrick Stolee 2012-07-18T20:40:41Z 2012-07-18T20:40:41Z Thanks! This solution was easy to implement and worked for my project. http://mathoverflow.net/questions/89365/how-to-find-independence-number-of-g-and-its-complement-g Comment by Derrick Stolee Derrick Stolee 2012-02-24T04:29:36Z 2012-02-24T04:29:36Z This question is at the level of a homework problem. http://mathoverflow.net/questions/71736/number-of-closed-walks-on-an-n-cube/71737#71737 Comment by Derrick Stolee Derrick Stolee 2011-07-31T17:03:49Z 2011-07-31T17:03:49Z That should be $r!/2^r$. http://mathoverflow.net/questions/71736/number-of-closed-walks-on-an-n-cube/71737#71737 Comment by Derrick Stolee Derrick Stolee 2011-07-31T17:03:19Z 2011-07-31T17:03:19Z If we assume the path moves in each dimension 0 or 2 times, you can select ${n \choose r/2}$ dimensions and then permute them $r^1/2^r$ ways. This is a lower bound on the number of walks and is likely the right asymptotics. http://mathoverflow.net/questions/70425/why-is-a-block-graph-of-a-steiner-triple-system-is-a-strongly-regular-graph/70433#70433 Comment by Derrick Stolee Derrick Stolee 2011-07-15T19:51:52Z 2011-07-15T19:51:52Z Your counts of $v(v-1)$ pairs in $[v]$ and $6$ pairs in $[3]$ are really ordered pairs. The conditions are over unordered pairs, so you should say it is ${v \choose 2} / {3\choose 2}$. Since the factors of two cancel, you get the same number, but your reasoning isn't perfect. http://mathoverflow.net/questions/3512/top-specialized-journals/9941#9941 Comment by Derrick Stolee Derrick Stolee 2011-04-27T18:46:48Z 2011-04-27T18:46:48Z I would appreciate if someone is able to comment on (and compare the above journals to) the following journals: &quot;Combinatorics, Probability, and Computing&quot;, &quot;Journal of Combinatorics&quot;, and &quot;Journal of Graph Theory&quot;. http://mathoverflow.net/questions/59939/identifying-poisoned-wines/59953#59953 Comment by Derrick Stolee Derrick Stolee 2011-03-29T13:25:50Z 2011-03-29T13:25:50Z I believe that since there are exponentially many choices for the probabilistic experiment, but only polynomially many ways the poison could be picked, there is some single string of random bits that works with $O(\log n)$ rats for all possible arrangements of the bottles. This requires using a concentration bound, such as Chernoff bounds. http://mathoverflow.net/questions/55200/good-programs-for-drawing-graphs-directed-weighted-graphs/55224#55224 Comment by Derrick Stolee Derrick Stolee 2011-02-13T14:44:07Z 2011-02-13T14:44:07Z You can also use NetworkX directly within Sage to have more control over your plotting options. (Sage's Graph class is a wrapper which hides a lot of functionality and is not compatible with the advanced plotting tools.) http://mathoverflow.net/questions/54193/graph-containing-all-trees/54196#54196 Comment by Derrick Stolee Derrick Stolee 2011-02-03T19:43:57Z 2011-02-03T19:43:57Z Some care must be taken here: the star on $n-1$ vertices has maximum degree $n-1$. A tree given by an edge with each endpoint adjacent to $\frac{n-2}{2}$ vertices has two vertices of maximum degree $\frac{n-1}{2}$. For $k \geq 3$, the tree with a $k$-degree vertex whose neighbors are adjacent to $\frac{n-(k+1)}{k}$ other vertices has $k$ vertices of maximum degree $\frac{n-1}{k}$. Following your technique, the $k$ vertices of degree at least $\frac{n-1}{k}$ could be the first $k$ of the $k+1$ vertices of degree at least $\frac{n-1}{k+1}$, but one is missing. This gives $nH_n = cn\log n$ edges. http://mathoverflow.net/questions/52371/code-that-produces-all-possible-trees-with-n-nodes Comment by Derrick Stolee Derrick Stolee 2011-01-18T03:52:04Z 2011-01-18T03:52:04Z To prevent comments such as the one above, ask &quot;An algorithm that...&quot; instead of &quot;code that...&quot;. Usually, you'll also get an implementation of that algorithm. http://mathoverflow.net/questions/52333/proving-that-every-graph-is-an-induced-subgraph-of-an-r-regular-graph/52375#52375 Comment by Derrick Stolee Derrick Stolee 2011-01-18T03:49:46Z 2011-01-18T03:49:46Z This is a nice recursive construction. http://mathoverflow.net/questions/50025/problems-where-we-cant-make-a-canonical-choice-solved-by-looking-at-all-choices Comment by Derrick Stolee Derrick Stolee 2010-12-21T04:21:59Z 2010-12-21T04:21:59Z And of course, the probabilistic method is really a special kind of counting. http://mathoverflow.net/questions/50025/problems-where-we-cant-make-a-canonical-choice-solved-by-looking-at-all-choices Comment by Derrick Stolee Derrick Stolee 2010-12-21T04:21:27Z 2010-12-21T04:21:27Z Do you mean something more like using expectation in the probabilistic method? Or perhaps entropy? Both of these deal with &quot;average&quot; properties, on random variables which are too complicated to even sample algorithmically. http://mathoverflow.net/questions/40337/ingenuity-in-mathematics/40400#40400 Comment by Derrick Stolee Derrick Stolee 2010-11-30T07:40:49Z 2010-11-30T07:40:49Z This is my favorite example of a non-constructive proof.