User derrick stolee - MathOverflow

Does the cubic planar graph with 6 3-faces and 6 7-faces have a name?

2013-03-08T15:56:15Z

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?

Here is a picture of the graph embedded on the plane with a point at infinity:

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.

I did try the House of Graphs by searching using their drawing tool, but found nothing.

Non-Uniform Root of Polynomial in Open Cube

2012-07-18T13:52:43Z

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 < 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?

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

Answer by Derrick Stolee for Number of closed walks on an $n$-cube

2011-07-31T16:59:57Z

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.

Answer by Derrick Stolee for What is the shortest program for which halting is unknown?

2011-03-10T15:48:16Z

This doesn't qualify as "shortest" but is my favorite example of why humans can't solve the halting problem:

for all odd numbers $n = 1,3,5,...$

if $n$ is perfect, halt.

This program halts if and only if there is an odd perfect number. Of course, the query "is $n$ perfect" is not terribly short (but can be computed by adding one more for loop).

Answer by Derrick Stolee for Proving that every graph is an induced subgraph of an r-regular graph

2011-01-17T19:34:37Z

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.

Take your input graph $G$ with maximum degree $\Delta$ and a number $r \geq \Delta$.

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

Answer by Derrick Stolee for Is there a canonical labelling package optimised for small graphs?

2011-01-08T04:17:25Z

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 http://oeis.org/A000088 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.

Are "almost all" strongly regular graphs rigid?

2010-10-05T18:53:36Z

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:

Theorem: Almost all strongly regular graphs have trivial automorphism group.

This contrasts that most known families of strongly regular graphs have high symmetry, due to their constructions using algebraic objects.

Does anyone know the reference for this theorem? Also, what is the measure used to describe "almost all"?

Reconstructing Maximal Planar Graphs

2010-05-30T16:14:14Z

Has it been proven that maximal planar graphs are reconstructible?

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

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.

Bonus question: Are there other classes of planar graphs that are known to be reconstructible?

Comment by Derrick Stolee

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

Comment by Derrick Stolee

2012-07-18T20:40:41Z

Thanks! This solution was easy to implement and worked for my project.

Comment by Derrick Stolee

2012-02-24T04:29:36Z

This question is at the level of a homework problem.

Comment by Derrick Stolee

2011-07-31T17:03:49Z

That should be $r!/2^r$.

Comment by Derrick Stolee

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.

Comment by Derrick Stolee

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.

Comment by Derrick Stolee

2011-04-27T18:46:48Z

I would appreciate if someone is able to comment on (and compare the above journals to) the following journals: "Combinatorics, Probability, and Computing", "Journal of Combinatorics", and "Journal of Graph Theory".

Comment by Derrick Stolee

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.

Comment by Derrick Stolee

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

Comment by Derrick Stolee

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.

Comment by Derrick Stolee

2011-01-18T03:52:04Z

To prevent comments such as the one above, ask "An algorithm that..." instead of "code that...". Usually, you'll also get an implementation of that algorithm.

Comment by Derrick Stolee

2011-01-18T03:49:46Z

This is a nice recursive construction.

Comment by Derrick Stolee

2010-12-21T04:21:59Z

And of course, the probabilistic method is really a special kind of counting.

Comment by Derrick Stolee

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 "average" properties, on random variables which are too complicated to even sample algorithmically.

Comment by Derrick Stolee

2010-11-30T07:40:49Z

This is my favorite example of a non-constructive proof.