User douglas s. stones - MathOverflow

Generating spatially-aware degree-preserving random graphs?

2012-12-18T22:43:58Z

In the study of biological neural networks, researchers sometimes compare hypotheses vs. a degree-preserving random null model. One major criticism against this approach is that connections in neural networks are greatly affected by their location in 3D Euclidean space (whereas the null model isn't).

Question: Is there a random graph model that both

preserves vertex degrees, and

accounts for the 3D location of vertices in space (i.e., nearby vertices are more likely to be connected than distant vertices)?

I'd be interested in both directed or undirected graphs (usually they can be adapted to suit, anyway).

Answer by Douglas S. Stones for Can pure mathematics harness citizen science?

2012-11-19T03:09:51Z

I have a suggestion. In fact, I've had this idea on the backburner for some time.

Question: Given a triple of permutations $\theta=(\alpha,\beta,\gamma)$, with $\alpha,\beta,\gamma \in S_n$, does there exist a Latin square that admits $\theta$ as an autotopism?

(If you're an algebraist, take the same question and replace "Latin square" with "quasigroup".)

I nearly went bonkers answering this question up to $n=17$ for this paper.

While algorithmic methods would take big chunks out of this problem, there would always be some cases that wouldn't work. Backtracking algorithms would sometimes paint themselves into a corner early on, and take virtually forever to escape. And, even if they did work, as soon as I resolve all cases for some value of $n$, it left open the $n+1$ case.

Why this is suitable for crowd computing:

Answering an instance of this question is much like solving a Sudoku problem. All the user has to do is input numbers in a matrix and the computer can check that there's no clashes.

Humans have an advantage over computers: they will be able to see that they painted themselves into a corner early on.

An individual question is not that hard (but there's a lot of them).

Once you have a solution, it's straightforward to check that it's correct, and can act forever as a "certificate" for a given $\theta$.

I foresee implementing this as a puzzle, where the user is presented with a $n \times n$ matrix, with some boundaries (representing the cycles of $\alpha$ and $\beta$) and they place in a symbol from $\{1,2,\ldots,n\}$ into any empty cell. Given that entry, the computer generates the orbit under the action of $\langle \theta \rangle$, thereby filling in some more cells. From the user's point of view, it looks like the numbers "wrap around" and orbits also "pass through" walls in the matrix.

Does a graph with all vertex degrees divisible by 3 contain a cubic subgraph?

2012-11-10T22:43:53Z

In this question, a "graph" and a "subgraph" will always be a loop-free multigraph (finite, undirected, unweighted).

Motivation: Given a graph in which each vertex has even degree, we can find a cycle (possibly a 2-cycle). If we delete this subgraph, we preserve the vertex degrees modulo $2$. Thus, we can repeatedly use this process to decompose the graph into cycles.

I'm interested into whether or not a similar property is true for cubic (i.e. 3-regular) subgraphs.

Question: Does a graph with all vertex degrees divisible by 3 contain a cubic subgraph?

If it does, then we can use the same argument to show that any such graph decomposes into cubic subgraphs. If it doesn't, then we have a counter-example. So, this is the same question as:

Question: Does a graph with all vertex degrees divisible by 3 decompose into cubic subgraphs?

I find it hard to believe that nobody has considered this problem before. So my suspicion is that either the proof is hard, the proof is easy (and I've missed something obvious) or there's a folklore counter-example.

I found some related papers: Spanning cubic graph designs, by Peter Adams and others, and Cubic factorizations by Moshe Rosenfeld and Vũ Đình Hòa, but they restrict their attention to decomposing the complete graph.

Does there exist $a,n \in \mathbb{Z}^+$, where $n \geq 2$, such that $a, an, an^2,an^3,\ldots,an^5$ are all palindromes in base 10?

2012-11-05T01:46:46Z

Question: Does there exist $a,n \in \mathbb{Z}^+$, where $n \geq 2$, such that $$a, an, an^2,an^3,\ldots,an^5$$ are all palindromes in base 10?

We see that $a=1$ and $n=11$ give rise to $$1, 11, 121, 1331, 14641$$ which is basically the first few rows of Pascal's triangle. There are infinitely many other examples of length 5, which we can generate by generalising the Pascal's triangle construction, giving $$11, 1111, 112211, 11333311, 1144664411$$ $$111, 111111, 111222111, 111333333111, 111444666444111$$ and so on.

Some other examples are:

$$147741, 13444431, 1223443221, 111333333111, 10131333313101$$

$$1478741, 134565431, 12245454221, 1114336334111, 101404606404101$$

However, I checked for $a,n \leq 10^7+1$, and didn't find any of length greater than 5.

Almost all loops have a trivial automorphism group; almost all groups have a non-trivial automorphism group. What goes on in between?

2012-07-14T14:41:50Z

NB: For this question, everything is finite.

Recently I've been fascinated by the following two observations:

Almost all loops have a trivial automorphism group (McKay & Wanless, 2005, in the context of Latin squares).
Almost all groups have a non-trivial automorphism group (in fact, all groups of order $n \geq 3$ admit a non-trivial automorphism).

However, the only difference between loops and groups is "cancellation" vs. "associativity". (Actually, in a loop, an element's left inverse might not equal its right inverse, but the equality of left and right inverses in a group does not need to be included as a group axiom.)

Question: How can we strengthen the loop axioms so as to preserve the property that "almost all X have a trivial automorphism group"?

Question: How can we weaken the group axioms so as to preserve the property that "almost all Y have a non-trivial automorphism group"?

Question: Is the a set of axioms "between" the loop axioms and the group axioms for which "almost all Z have a trivial automorphism group" and "almost all Z have a non-trivial automorphism group" are both false?

How many Tutte polynomials of complete graphs are known?

2012-01-19T03:07:43Z

I would like to compute the Tutte polynomial of the complete graph $K_n$ for n as large as possible. Using a program by Björklund, Husfeldt, Kaski, Koivisto (here), I managed to compute up to n=18 on my home computer (in serial) in less than a day. Overall, I've been very impressed by this program.

I'm likely to include the results of these computations in an upcoming paper, so, for comparison, I would also like to mention what people have done previously in the area. (Also, I'd like to check that the computations are consistent with one another.)

Question: How far have others computed the Tutte polynomial of the complete graph?

An example of when nauty, on two different platforms, gives different canonical labels for the same input graph?

2012-05-29T03:22:46Z

Let $G$ be a graph. I've heard that, if we use nauty to canonically label $G$ on two different platforms, it's possible to obtain distinct labels. However, I've never actually seen this occur.

The nauty user guide (pdf) writes:

Beginning at version 2.1, the canonical labelling does not depend on the compiler, the system, or the word size.

This seems to imply that it's still possible to receive distinct canonical labels on different platforms. (This might also be somewhat out of context, since this sentence is written in the "dreadnaut" section.)

Question: What is an example of a situation where, on two different platforms, nauty would canonically label the same graph differently (if there are any)?

If it can still occur, is it a rare occurrence?

In how many ways can we generate a given bipartite multigraph via the bipartite configuration model?

2012-04-24T10:54:36Z

Suppose I have two multisets, $A=\{a_1,a_2,\ldots,a_n\}$ and $B=\{b_1,b_2,\ldots,b_n\}$. We can construct a (random) bipartite multigraph with the vertex bipartition $\text{set}(A) \cup \text{set}(B)$ by the following process:

start with the null graph on vertex multiset $A \cup B$,
pick a (random) permutation $\alpha$ of $\{1,2,\ldots,n\}$,
draw edges from $a_i$ to $b_{\alpha(i)}$ for all $i \in \{1,2,\ldots,n\}$,
identify vertices $a_i$ and $a_j$ whenever $a_i=a_j$, and similarly, identify vertices $b_i$ and $b_j$ whenever $b_i=b_j$.

This could be described as a version of the configuration model for bipartite graphs (although, usually the configuration model restarts if parallel edges occur, and I don't want to do that).

For example, if $A=\{1,2,2,2,3\}$ and $B=\{4,4,5,5,5\}$, and $\alpha=\text{id}$ then we generate the multigraph with bipartition $\{1,2,3\} \cup \{4,5\}$ and edge multiset $\{14,24,25,25,35\}$. We could also have generated the same multigraph with $\alpha=(12)$, and $\alpha=(23)$ and a variety of other ways.

Question: Given a bipartite multigraph, in how many ways could it have been generated by the above process?

A related problem, the enumeration of contingency tables, is #P-complete (this gives the number of distinct bipartite graphs that could have arisen). See: M. Dyer, R. Kannan, J. Mount, Sampling Contingency Tables, Random Structures & Algorithms 10 (1997), 487–506.

Presumably, the problem I mention above is "hard" (although, feel free to prove me wrong!), which suggests an algorithmic approach is required to answer the question in general.

This leads me to the sub-questions:

Sub-question: Is there an efficient way to compute these numbers (other than some kind of backtracking algorithm)?

and

Sub-question: Does there exist a graph whose automorphisms correspond (naturally) to the different ways of generating a given bipartite multigraph by the above method?

If it is possible to do the above, then we could use e.g. nauty to compute it easily.

(Note: This question is "the other side of the coin" of a math.SE question: What is the number of bijections between two multisets? However, I tried to make this question self-contained.)

A graph $G$ with two $K_6$ subgraphs, in which any one-factor of $G$ induces a one-factor in exactly one of the $K_6$ subgraphs?

2012-03-24T21:55:34Z

I'm seeking a simple graph $G$ of the following type:

It contains two disjoint copies of $K_6$ (the complete graph on 6 nodes), $H$ and $H'$ say.
Any one-factor of $G$ must contain either (a) a one factor of $H$ and no edges in $H'$ or (b) a one factor of $H'$ and no edges in $H$.
There exists a one-factor of $G$ that contains a one-factor of $H$.
There exists a one-factor of $G$ that contains a one-factor of $H'$.

Question: Does $G$ exist?

I'm also interested in the same problem with $K_6$ replaced by $K_{2n}$.

My motivation for this question comes from an attempt to rephrase a question about Latin squares as a question about one-factors.

Existence problem for a generalisation of Latin squares (matrices with fixed row and column sets)

2012-03-02T23:13:50Z

Let $R_1,\ldots,R_n$ and $C_1,\ldots,C_n$ be sets of size n.

When does there exist an $n \times n$ matrix in which the $i$-th row is a permutation of $R_i$, for all $1 \leq i \leq n$, and the $j$-th column is a permutation of $C_j$, for all $1 \leq j \leq n$?

Easy observations:

A Latin square is an example when $R_1=\ldots=R_n=C_1=\ldots=C_n$. (So this is indeed a generalisation of the existence problem for Latin squares.)
The multiset $\cup R_i$ equals the multiset $\cup C_i$.

The motivation for this question comes from a Latin square completion problem. If we have a $2n \times 2n$ partial Latin square with the structure:

\begin{array}{|cc|} \hline A & \emptyset \\ \emptyset & B \\ \hline \end{array}

where $A$ and $B$ are $n \times n$ matrices, and $\emptyset$ represents $n \times n$ empty blocks. When does such a partial Latin square complete?

(0,1)-matrix congruence: is it known?

2010-04-14T08:55:21Z

[[UPDATE: This work has now been published at SIAM J Discrete Math.: Formulae for the Alon–Tarsi Conjecture.]]

By equating two formulae (one congruence by Glynn (1) (which has just appeared) and one unpublished formula) for the number of even Latin squares minus the number of odd Latin squares, we find the following result.

For odd primes $p$ we have \[\sum_{A \in B} (-1)^{\sigma_0(A)} \equiv 1 \pmod p\] where $B$ is the set of $(p-1) \times (p-1)$ $\,(0,1)$-matrices whose determinant is indivisible by $p$ and $\sigma_0(A)$ is the number of zeroes in $A$. It happens to be true for $p=2$ also (but it does not follow from Glynn's result).

Is this result already known? If so, it would provide an alternate proof of Glynn's result.

To illustrate, consider when $p=3$. The (0,1)-matrices whose determinants are indivisible by $p$ are

01 10       01 10 11 11
10 01  and  11 11 01 10

So the sum becomes $+2-4=-2 \equiv 1 \pmod 3$.

It is equivalent to the congruence \[\sum_{A \in C} (-1)^{\sigma_0(A)} \det(A)^{p-1} \equiv 1 \pmod p\] where $C$ is the set of all $(p-1) \times (p-1)$ $\,(0,1)$-matrices (via Fermat's Little Theorem).

(1) Glynn, D., 2010. The conjectures of Alon-Tarsi and Rota in dimension prime minus one. SIAM J. Discrete Math., 24 (2010), 394-399.

A more efficient way to generate random graphs with a given degree sequence?

2012-01-23T02:50:45Z

In graph data mining it is often useful to generate random (simple) graphs with a given degree sequence (e.g. in searching for network motifs), and ideally these would be uniformly at random.

[For this question, we'll consider the undirected case (the directed case can also be treated similarly, but it's a bit more messy).]

We could use the configuration model to generate these graphs (each node is given stubs corresponding to its degree, and these stubs are connected uniformly at random; repeat until a simple graph is obtained). But, unfortunately, often this results in too many restarts, and is impractical. This is worse for larger graphs, or graphs with unfavourable degree distributions. [When it does work, however, the configuration model is surprisingly quick.]

In cases when the configuration model is impractical, a switching method is often used, where two edges {a,b} and {c,d} are replaced by {a,d} and {b,c}, provided no clashes arise (loops or parallel edges). If we perform this operation a zillion times, we'll get something empirically fairly close to the uniform distribution (it is not actually uniform, but is plenty good enough for most real-world studies, where other errors dominate).

Let me propose another scheme: We select some induced subgraph H, and use the configuration model on H alone. Repeat this a zillion times.

Question: Has this scheme, or a similar scheme, been considered previously? If so, would it result in a distribution that is "empirically close" to uniform? Could it possibly be more efficient than the "switching pairs of edges" method?

When I say, "more efficient" I don't mean O(...) efficiency. E.g. simply being twice as fast would be great.

[NB. In the above, I'm (for the time being) putting aside the process of choosing the subgraph H, which is a problem in itself.]

Answer by Douglas S. Stones for Compressing Graphs (Kolmogorov complexity of graphs)

2011-11-07T05:55:11Z

Graph compression algorithms are starting to be used in biological applications (e.g. Itzkovitz, et al. Coarse-graining and self-dissimilarity of complex networks; L. Peshkin, Structure induction by lossless graph compression; M. Hayashida and T. Akutsu Comparing biological networks via graph compression). Unlike the pure mathematical side, the networks involved are not the whole class of (non-isomorphic) (un)labelled graphs.

Motivated by string compression, these algorithms can detect frequently occurring induced subgraphs. Recently, the related topic of network motifs (small connected subgraphs that occur as an induced subgraph significantly more frequently than in randomized networks) has received an explosion of interest. It is hoped that graph compression algorithms can provide insight into network motifs (and other small induced sugraphs, or "graphlets"), and thus provide insight into the (biological) network as a whole.

Answer by Douglas S. Stones for Graphs with few induced subgraphs

2011-08-05T11:43:11Z

Here's an example $G$ for all $i \geq 8$ and $n \geq 2i+1$ that contains only $8$ induced subgraphs (up to isomorphism).

If we choose $i$ vertices from the top row, we obtain $\overline{K_i}$.

If we choose $i-1$ vertices from the top row, we obtain $K_{1,i-1}$ or $\overline{K_i}$.

If we choose $i-2$ vertices from the top row, we obtain $\overline{K_i}$ or $\overline{K_{i-2}} \cup K_2$ or $K_{1,i-2} \cup K_1$ or $K_{1,i-1}$.

If we choose $i-3$ vertices from the top row, we obtain the subgraphs induced by $i-3 \text{ vertices from a,b,c,d,... } \cup {e,g,h}$ or $i-3 \text{ vertices from a,b,c,d,... } \cup {e,f,g}$ or $K_{1,i-2} \cup K_1$ or $\overline{K_{i-3}} \cup P_3$ (path with three vertices).

If we choose $i-4$ vertices from the top row, we obtain the graph induced by $i-4 \text{ vertices from a,b,c,d,... } \cup {e,f,g,h}$.

Since we must choose at least $i-4$ vertices from the top row, in total, that's 8 isomorphism classes of graphs. We can see that $G$ and its complement both contain a triangle (and are therefore not bipartite) and are connected (each vertex is not adjacent to either h or a).

Generalising this technique, we can replace {e,f,g,h} by any non-bipartite connected subgraph of diameter at least 2. In this case, there would exist some I, N such that for all i>=I and n>=max(N,2i+1) which would satisfy the required conditions.

Answer by Douglas S. Stones for Switching Research Fields

2011-06-22T23:30:18Z

While it seems a bit late for the OP, I'd like to add some remarks that might be helpful to the subsequent readers.

Having completed my PhD in Combinatorics, I seem to be inevitably converting to Computational Biology. Let me point out some of the most significant aspects that I have encountered:

Obstacles:

The letters of recommendation. Although mentioned by Deane Yang, I feel this was not mentioned strongly enough. I find this to be a major obstacle to my future in computational biology. I have lots of people who would be willing to vouch for me for my expertise in combinatorics, but very few who would vouch for my expertise in computational biology. Those who can vouch for me are only able to make limited comments due to only working in the area a short time. [PS. One tip -- make sure the referees in your previous field have some idea of the significance of your work in the new field (thereby reducing the problem raised by Deane Yang)]
Lack of publications. And moreover, the overall lack of relevant brownie points -- e.g. I've refereed papers in combinatorics, I'm a member of the AMS and other societies, and so on, which are not very relevant.

Advantages:

It is multidisciplinary. So most people who enter this area have a PhD in Biology, Computer Science, Mathematics, Statistics, etc., but not in Computational Biology itself. So most people are in the same boat.
These are neighbouring fields. The advantages of this have already been discussed.
There is significantly more funding in computational biology. This is sheer numbers -- there are more jobs available, so they are easier to get.
There are real world applications. It makes it much easier to argue that this research is worth funding (thinking research grants).

Finally, one tip: try not to "switch" fields, but gradually change from one to another.

Answer by Douglas S. Stones for Top specialized journals

2009-12-28T06:52:40Z

Combinatorics: In my opinion, Discrete Mathematics is only a mediocre journal (I wouldn't consider this top journal). Yes, it contains good papers, but it contains a lot of papers... on average... it's average.

Some other ones worth a mention (on top of JCTA, JACO and EJoC mentioned earlier): Journal of Combinatorial Theory Series B, Journal of Combinatorial Designs, Annals of Combinatorics, Combinatorica.

The Electronic Journal of Combinatorics should probably go on the top list in combinatorics, but since it's a free, open access journal, it's usually assumed to be worse than it actually is.

Combinatorics, Probability, and Computing, the Journal of Graph Theory and the Electronic Journal of Combinatorics seem to be widely regarded as excellent journals, at the level of the ones mentioned above (except Discrete Mathematics).

Formerly, the "Journal of Combinatorics" referred to a printed version of the "Electronic Journal of Combinatorics" (which has led to some confusion, see e.g. http://symomega.wordpress.com/2010/03/30/the-arc-the-era-and-the-ejc/), although most people in combinatorics haven't even heard of it.

Joel Reyes Noche's comment points out that there is a new journal entitled "Journal of Combinatorics".

What packages for subgraph enumeration are available?

2011-01-15T11:42:30Z

In learning about network motifs, I discover claims that Mfinder (circa 2004) is the "the first motif-mining tool" (Kashani et al. 2009). Motifs are connected induced subgraphs that occur more frequently than in "similar random graphs" (these graphs may be directed or undirected).

While Mfinder might be the first specifically aimed at finding motifs, I suspect there will have been earlier packages that could count the number of induced subgraphs isomorphic to a small graph H in a large graph G.

Question: What are some earlier packages that enable counting the number of induced subgraphs in G that are isomorphic to some given small graph H?

After Mfinder a range of motif finding packages have been developed. The ones I've heard of are MAVisto, FanMod, NoMoFinder, an unnamed package by Grochow and Kellis and Kavosh. I'd also be interested in hearing about any other packages that can perform subgraph enumeration.

What is the largest family F of subsets of [n] for which any two distinct sets A and B in F have an intersection of size at most min(|A|,|B|)/2?

2011-01-13T04:14:29Z

This problem arose in the study of Latin squares with a large number of subsquares, although it appears interesting in its own right.

Question: What is the maximum cardinality of a family $F \subseteq 2^{[n]}$ of subsets of $[n]:=\{1,2,\ldots,n\}$ for which any two distinct $A,B \in F$ satisfy $|A \cap B| \leq \tfrac{1}{2} \min(|A|,|B|)$?

Some observations:

We have the trivial lower bound $\max |F| \geq {n \choose 2}$ by taking all the subsets of size 2.
When $n \geq 3$, $F$ should not have any sets of size 1. If $\{a\} \in F$, then we can replace it by $\{a,x\}$ for all $x \in [n] \setminus \{a\}$ for any $x$ that belongs to a set of size 2 or more (since no other set in $F$ can contain an $a$). If every set has size 1, then $|F|=n$ which can be beaten.
$F$ should not have any sets of size 3. If $\{a,b,c\} \in F$, then we can replace it by $\{a,b\},\{a,c\},\{b,c\}$ (since any other set in $F$ may intersect $\{a,b,c\}$ in at most one element).
With the above simplifications in mind, I wrote a backtracking algorithm which says that for $3 \leq n \leq 7$ (and it's progressing through $n=8$), that $F$ is uniquely maximized when $F$ consists of all 2-subsets.

Is there a canonical labelling package optimised for small graphs?

2011-01-08T03:34:40Z

Recently, I've been looking into motifs in networks (directed graphs) -- small connected induced subgraphs that appear significantly more frequently than in a "similar random graph".

In practice, we need to enumerate the induced subgraphs (up to isomorphism) in thousands of large random networks, which can take a long time, and requires some form of canonical labelling (e.g. FANMOD uses nauty). My feeling is that nauty is quite bulky and seems likely to be overkill for this feature because e.g. we only need to canonically label small graphs (in FANMOD they have at most 8 vertices -- although I haven't seen much interest in motifs with more than 4 vertices).

Question: Is there a package that specialises in the canonical labelling of small directed graphs?

In the case I'm interested in, we need to label millions of graphs on a small number of vertices.

What is the number of k-regular subgraphs of $K_{12,12}$?

2010-12-11T23:57:48Z

I'm thinking about making an attempt at counting the number of Latin squares of order 12. Currently I'm in (what I call) the "sanity check" stage, where we check that the ranges that need searching through aren't too massive.

The standard method of counting Latin squares involves building up from Latin rectangles. We get an improvement if we "forget" the structure of the Latin rectangle and remember only which symbols occur in which column (in fact, this is what's makes counting Latin squares possible-ish, the idea goes back to Sade). This can be achieved by interpreting the Latin rectangle as a k-regular subgraph of $K_{n,n}$.

So, in order to perform my sanity check, I'm after the number of non-isomorphic $k$-regular subgraphs of $K_{12,12}$ where $k \in \{1,2,\ldots,6\}$ (where subgraphs include all 24 vertices). (Sloane's http://oeis.org/A008327). I'm particularly interested in the case $k=6$.

Question: What is the number of non-isomorphic $k$-regular subgraphs of $K_{12,12}$?

Actually, an estimate would be good enough for what I want. So perhaps it's more realistic to hope for an answer to this question:

Question: What is an easy way to estimate the number of non-isomorphic $k$-regular subgraphs of $K_{12,12}$?

McKay and Wanless (2005) write:

It is unlikely that [the number of Latin squares of order 12] will be computable by the same method for some time, since the number of regular bipartite graphs of order $24$ and degree $6$ is more than $10^{11}$.

Searching through $10^{11}$ graphs is not completely out-of-the-question, but if it were much more than this I would have to reconsider.

Answer by Douglas S. Stones for What is the number of k-regular subgraphs of $K_{12,12}$?

2010-12-12T04:15:50Z

This answer is mostly a thanks to Igor Riven, and to give the details for those who may follow. So I think I got a configuration model to work...

We construct a random k-regular bipartite multi-graph by generating a random permutation $\sigma$ from {1,...,kn}. Then draw an edge from 1 to $\sigma(1),\sigma(2),\ldots,\sigma(k)$, then draw an edge from 2 to $\sigma(k+1),\sigma(k+2),\ldots,\sigma(2k)$, and so on.

The size of the set being sampled from has size approximately $(kn)!/(k!^{2n})$ -- the same graph will be drawn if we permute within the sets $\{1,\ldots,k\},\{k+1,\ldots,2k\},\ldots$, and if we permute $\{\sigma(1),\ldots,\sigma(k)\},\{\sigma(k+1),\ldots,\sigma(2k)\},\ldots$. If we ignore the possibility of obtaining the same permutation back again after performing these operations, we obtain a biased estimator for the number of k-regular bipartite multi-graphs generated.

Restricting to the types of isomorphisms considered by McKay and Wanless, we should anticipate each isomorphism class to have size $2 n!^2$ (another biased estimator), which we divide by to give the desired result.

Here's the GAP code I wrote to perform these estimates.

This function tests if the graph is a simple graph:

NoIntersectionContainsMoreThanOneElement:=function(A,B)
  local S1,S2;
  for S1 in A do for S2 in B do
    if(Size(Intersection(S1,S2))>1) then return false; fi;
  od; od;
  return true;
end;;

This function generates iter instances of the random graph described above.

EstimateNrRandomKRegularSubgraphOfKNN:=function(k,n,iter)
  local p,q,A,S1,S2,count_total,count_good;
  count_total:=0;
  count_good:=0;
  A:=List([1..n],i->List([1..k],j->k*(i-1)+j));
  for count_total in [1..iter] do
    p:=RandomPermutationList(k*n);
    q:=List([1..n],i->List([1..k],j->p[k*(i-1)+j]));
    # Print(p,"\n",q,"\n",NoIntersectionContainsMoreThanOneElement(q,A),"\n\n");
    if(NoIntersectionContainsMoreThanOneElement(q,A)) then count_good:=count_good+1; fi;
  od;
  return count_good/count_total*Factorial(k*n)/Factorial(k)^(2*n);
end;;

[RandomPermutationList() and Decimal() are non-GAP functions that I implemented myself]

Here is the test output for 5-regular subgraphs of $K_{11,11}$:

gap> k:=5;; n:=11;; iter:=1000000;; EstimateNrRandomKRegularSubgraphOfKNN(k,n,iter)/(2*Factorial(n)^2);
32487228876370918434190864363106201/424673280000000000000000000
gap> Decimal(last);
76499347.6311269652
gap> k:=5;; n:=11;; iter:=1000000;; EstimateNrRandomKRegularSubgraphOfKNN(k,n,iter)/(2*Factorial(n)^2);
4290766078011253378100680198900819/56623104000000000000000000
gap> Decimal(last);
75777655.6723427486

which is reasonably close to 78322916 (the number being estimated, as given by McKay and Wanless).

Estimating 6-regular subgraphs of $K_{12,12}$ this way looks like it's going to take much longer (although, within reason).

What is the p-adic valuation of a number?

2010-11-07T09:09:57Z

There seem to be two conflicting definitions for p-adic valuation in the literature.

Firstly, for any non-zero integer n, we have $\nu=\nu_p(n)$ is the greatest non-negative integer such that $p^\nu$ divides $n$. Secondly, we have $|n|_p$ which is defined as $1/p^\nu$. [These definitions can be extended to the rationals.]

$\nu$ is defined as the p-adic valuation in Khrennikov, Nilson, P-adic deterministic and random dynamics (for example) and $|\cdot|_p$ is defined as the p-adic valuation in Khrennikov, P-adic and group valued probabilities, in Harmonic, wavelet and p-adic analysis (for example).

Question: Is there a preferred definition for p-adic valuation?

Which integer recurrence relations can be formulated as counting walks on a graph?

2010-10-29T06:04:38Z

Observation: If we take the graph with two vertices, A and B, with a loop {A,A} and undirected edge {A,B}, then the number of closed walks $W_n$ of length $n \geq 1$ starting from A we get $W_1=1$ (counting AA), $W_2=2$ (counting AAA and ABA) and $W_n=W_{n-1}+W_{n-2}$, i.e. the Fibonacci numbers.

Question: Which types of recurrences can be realised as the number of closed walks from the origin of a graph?

More generally, which types of recurrences can be realised as the number of walks of some type in some graph?

If we can interpret a recurrence relation as the number of walks in a graph in some way, then might be able to use spectral theory to find formulas for the sequence. (see: Frank Harary and Allen J. Schwenk, The spectral approach to determining the number of walks in a graph. Pacific J. Math. Volume 80, Number 2 (1979), 443-449.)

How to resolve an issue with Pranesachar et al.'s formula for the number of four-line Latin rectangles?

2010-10-07T00:22:36Z

The same formula for the number of four-line Latin rectangles was given in:

Athreya, K. B., Pranesachar, C. R. and Singhi, N. M. On the Number of Latin Rectangles and Chromatic Polynomial of $L(K_{r,s})$, European Journal of Combinatorics, (1) 1980, 9-17.
Pranesachar, C. R., Enumeration of Latin Rectangles via SDR's, Lecture Notes in Math., 1981, Springer, 380-390.

I'll reproduce the formula below:

\[L(4,k,n)=\frac{n!k!}{(n-k)!^4} \sum \frac{(-1)^{\sum \beta_i+\varepsilon} 2^{\sum \delta_i} 6^\varepsilon}{\alpha! \prod (\beta_i!) \prod (\gamma_i!) \prod (\delta_i!) \varepsilon!} \times T \times S \] where the sum is over all \[\alpha+\sum_{i=1}^6 \beta_i+\sum_{i=1}^3 \gamma_i + \sum_{i=1}^4 \delta_i + \epsilon=k.\] Further \begin{align*} T=& \sum_{\theta_1,\theta_2,\theta_3 \geq 0} {{\beta_1+\gamma_1} \choose \theta_1} {{\beta_6+\gamma_1} \choose \theta_1} \theta_1! {{\beta_2+\gamma_2} \choose \theta_2} {{\beta_5+\gamma_2} \choose \theta_2} \theta_2! \times\\ & {{\beta_3+\gamma_3} \choose \theta_3} {{\beta_4+\gamma_3} \choose \theta_3} \theta_3! (\underbrace{n-(\sum \beta_i+2\sum \gamma_i+\sum \delta_i+\epsilon)+\theta_1+\theta_2+\theta_3}_{\text{can be negative?!}})! \end{align*} and \begin{align*} S=& (n-k+\alpha+\beta_4+\beta_5+\beta_6+\delta_1)! (n-k+\alpha+\beta_2+\beta_3+\beta_6+\delta_2)! \times\\ & (n-k+\alpha+\beta_1+\beta_3+\beta_5+\delta_3)! (n-k+\alpha+\beta_1+\beta_2+\beta_4+\delta_4)!. \end{align*}

The four-line Latin rectangles case is when k=n. In trying to implement this formula, I find that one of the terms can be a negative factorial. I've (unsuccessfully) tried replacing the negative factorials by 0 or 1.

Does anyone know how to resolve this problem and get this formula to actually count four-line Latin rectangles?

My interest in this formula is mostly historical since Doyle gave a superior formula here.

Hamilton cycle decompositions of the complete graph

2010-01-03T10:37:22Z

I'm looking for the number of Hamilton cycle decompositions of the labelled complete graph $K_n$ for small $n$. From such a decomposition, we can construct a special type of Latin square (called a row-Hamiltonian Latin square).

Edit: Clearly, we require $n$ to be odd. To ensure that each Hamilton cycle decomposition is counted once, we only include the $n$-cycle permutations $\alpha$ of ${1,2,\ldots,n}$ that have $\alpha(1)<\alpha^{-1}(1)$. We also write the decomposition $\alpha\beta\ldots$ such that $\alpha(1)<\beta(1)<\cdots$.

The count for $n=3$ is $1$ counting (123). The count for $n=5$ is $6$, counting the following: $(12345)(13524)$, $(12354)(13425)$, $(12453)(14325)$, $(12435)(13254)$, $(12543)(14235)$ and $(12534)(13245)$. Assuming my code is correct, the count for $n=7$ is $960$.

Answer by Douglas S. Stones for Enumerative algorithm through inclusion-exclusion

2010-09-10T09:33:00Z

Both yes and no. Let me illustrate...

Inclusion-exclusion is typically used to find the cardinality of a set A contain all combinatorial objects that avoid a substructure S (either that, or the complement of A).

Suppose you are at object $x \in A$ and the next object is $y \in A$. Whatever method you use for finding y from x would need to find the combinatorial trade T formed from the difference between y and x. The trade T will typically depend on the structure of x and y, that is, you will probably not be able to use the same trade T in going from most x' to y' later in the iterator.

For example, consider (0,1) sequences of length n without two consecutive 1s. Here's the list for n=3.

These can be counted using inclusion-exclusion. Notice that, no matter which order we choose to iterate in, the trade T that arises in going from 000 to abc will somehow contain the information of which of a,b,c are non-zero -- i.e. which numbers to toggle. This trade can clearly not be used everywhere in the iterator, although in some cases it could: e.g. if 000 -> 001 then the trade could be reused in going from 100 -> 101.

In some areas of combinatorics, such as Latin squares, we start off with one member L of the set A, then store a sequence of trades $t_1,t_2,\ldots$ (this can require much hard-disk space). We iterate through the Latin squares quickly by applying the trades in sequence, that is, $L \mapsto t_i L$ iteratively.

The problem therefore becomes finding a sequence of trades that are quite "small" (and therefore require less storage) -- e.g. in the binary sequences case, toggles only one or two bits.

Value of "of course" in the mathematical literature

2010-02-23T21:42:45Z

I've been thinking about the value of writing "of course" in mathematical papers (or its variants such as "obviously" etc.). In particular, my current train of thought is, if something is obvious, then it is obvious that it is obvious (so why include it at all?).

The example that inspired this post is: If d divides a and d divides b, then of course d also divides a+b.

Are there examples in the mathematical literature where the term "of course" is of value?

More precisely, I'm after an example (or a few), ideally by a well-known author, where "of course" or "obviously" or similar actually adds tangible value to a sentence (rather than just implying: (a) it's obvious to me, I'm so smart or (b) I can't actually be bothered working out the details)

What can I say about the permutation $\alpha\beta$ if I know the permutation $\beta\alpha$?

2010-08-21T02:54:02Z

I'm looking into a secret sharing scheme that has a secret permutation $\theta$ which has the cycle structure (n/2)+(n/2) (i.e. two (n/2)-cycles).

The permutation $\theta$ is decomposed into two permutations $\alpha$ and $\beta$, where $\alpha$ is generated uniformly at random. So with knowledge of both $\alpha$ and $\beta$, we can find $\theta$, while with knowledge of $\alpha$ xor $\beta$, we cannot find $\theta$ (although, we could guess).

At this point, I want to make public $\beta\alpha(L)$ (L is actually a Latin square, but this is not too relevant for the question I want to ask). It is possible that an attacker could find $\beta\alpha$ from $\beta\alpha(L)$. However, I worry that knowledge of $\beta\alpha$ might give information about $\theta$.

If I know $\theta=\alpha\beta$, and I'm given the permutation $\beta\alpha$, what can I say about $\theta$? (without a priori knowledge of $\alpha$, $\beta$ or $\theta$)

Answer by Douglas S. Stones for Does Burnside's Lemma / Counting Formula have a Cousin?

2010-07-26T09:00:56Z

Maybe you're after the Orbit-Stabiliser Theorem. Let $G$ be a group that acts on a set $X$ and let $x \in X$. Then $|G|=|G_x||G(x)|$ where $G_x$ is the stabliser of $x$ in $G$ and $G(x)$ is the orbit of $x$.

Does there exist a pure recurrence formula with polynomial coefficients for Fibonacci(2^n)?

2010-07-21T09:18:34Z

Let F(n) be the Fibonacci sequence as defined by F(1)=1, F(2)=1, F(n)=F(n-1)+F(n-2) for n>=3. I'm looking for a pure recurrence formula for the function X(i)=F(2ⁱ) whose coefficients may be polynomials in i. This is Sloane's A058635. I also would like it to be "pure" in the sense that there is no auxiliary function involved. Is such a formula known?

I attempted using Sister Celine's technique (as described in A=B) with the data up to 2²¹ without success.

My motivation is that I have a fairly complicated recurrence formula for another sequence, but I am only interested in the terms whose indices are of the form 2ⁱ-3. The existence (or non-existence) of a recursion for X(i) would be a kind of "proof of concept" as to whether or not I should explore the possibility of finding such a recursion for my sequence.

Comment by Douglas S. Stones

2013-01-06T07:59:12Z

This would work if "substructure" means "connected induced subgraph". Our program, NetMODE (ref: dx.doi.org/10.1371/journal.pone.0050093), runs in a terminal so a script could repeatedly call it for each graph. (Since you're not after the biological application, you'd want to use 0 comparison graphs.)

Comment by Douglas S. Stones

2012-12-19T04:07:00Z

My guess is that multigraphs are interpreted as edge-weighted networks.

Comment by Douglas S. Stones

2012-12-19T02:27:02Z

Hmmm, thanks for that. I see what you're doing there, but this wouldn't preserve vertex in-degrees, which would be a disadvantage. (I'll have to think about whether this would be a significant disadvantage for the application I have in mind.)

Comment by Douglas S. Stones

2012-11-11T00:03:54Z

Thanks for that!

Comment by Douglas S. Stones

2012-05-30T00:42:37Z

That's good then. Thanks Brendan.

Comment by Douglas S. Stones

2012-04-23T10:47:37Z

Perhaps "exponentially many" means $O(2^n)$? This could arise in a worst-case analysis of a graph algorithm. And it's certainly true, since there are $2^n$ induced subgraphs, and any subtree of a tree must be an induced subgraph.

Comment by Douglas S. Stones

2012-03-25T10:25:05Z

That's a nice proof! (and seems to work for n=2 too)

Comment by Douglas S. Stones

2012-03-25T08:48:56Z

Yes, you're right. I'll edit that in.

Comment by Douglas S. Stones

2012-03-25T05:41:00Z

Actually, I'm not sure for $K_4$ either. ($K_6$ just happened to be the case I was looking at.)

Comment by Douglas S. Stones

2012-01-23T23:54:49Z

Thanks for that! It has quite a lot of detail about a range of methods (including their own). Also, unlike the MCMC method, their method could readily be used in parallel computation (e.g. if you want to generate 1000 random graphs).

Comment by Douglas S. Stones

2012-01-20T21:41:13Z

Indeed, once it's pointed out that they're easy to count, the titled question is no longer relevant. Thanks for the links (they all look relevant)!

Comment by Douglas S. Stones

2012-01-19T05:18:33Z

PS. I tested "tutte" and "tutte_bhkk" on K_15 on my comp (which is much slower than yours): 19.468s vs. 7m42.791s, respectively (wow!). "tutte" computed K_18 in 9m11.544s.

Comment by Douglas S. Stones

2012-01-19T04:14:30Z

Thanks! That'll save me from wasting time doing it in a more complicated way.

Comment by Douglas S. Stones

2011-10-15T09:34:32Z

(a) no question; (b) not mathematics; (c) spam

Comment by Douglas S. Stones

2011-08-05T12:48:43Z

Right, I think it's fixed now. Wow, that was a bookkeeping nightmare.