User brendan mckay - MathOverflow

Answer by Brendan McKay for Asymptotics of a function

2013-05-08T15:05:50Z

$f(n) = n^n 4^{-4n} (1 + O(n^{-4}))$. The sum is strongly dominated by its last term. I hope this isn't homework.

Apologies. I misread the question exact as Benoît suggests.

Answer by Brendan McKay for Counting matchings in a bipartite matching-covered graph

2013-05-02T15:43:27Z

Yes, it is still just as hard. Given an arbitrary bipartite graph, in polynomial time you can remove every edge that is not in a perfect matching (test one edge at a time), thus reducing the problem to a matching-covered graph.

How quickly can we test if a graph is distance-regular?

2013-05-01T07:48:52Z

A (simple, finite, connected) graph $G$ is distance regular if there exist integers $b_i,c_i,i=0,...,D$ such that for any two vertices $x,y$ in $G$ and distance $i=d(x,y)$, there are exactly $c_i$ neighbours of $y$ in $G_{i-1}(x)$ and $b_i$ neighbours of $y$ in $G_{i+1}(x)$, where $G_i(x)$ is the set of vertices $y$ of $G$ with $d(x,y)=i$. Here $d(x,y)$ is the distance between $x$ and $y$, and $D$ is the diameter.

My question is: given a graph $G$ with $n$ vertices and $m$ edges, how quickly can we test if $G$ is distance-regular?

Clearly it can be done in $O(nm)$ time, since in that amount of time we can find the distance partition from each vertex using breadth-first search and count edges between the different cells. Probably we can also do it by matrix multiplication in $O(Dn^\alpha)$ where $\alpha$ is the exponent for matrix multiplication (I didn't work out the details).

Can it be done quicker?

Answer by Brendan McKay for How dense is the set of asymmetric graphs?

2013-04-22T04:12:01Z

Almost all non-asymmetric graphs have exactly one non-trivial automorphism, namely a transposition swapping two vertices. So, an accurate estimate of their number is obtained by taking an arbitrary graph with one vertex less, choosing a vertex $v$, adding a new vertex $w$ with the same neighbours as $v$, then either joining or not joining $v$ to $w$. For labelled graphs, if $g_n=2^{\binom n2}$ is the number of them we have asymptotically $2ng_{n-1}$ non-asymmetric graphs. This is a small fraction. For unlabelled graphs, divide the total by $n!$ and the non-asymmetric ones by $n!/2$.

Answer by Brendan McKay for Minimize diameter of a tree

2013-04-15T15:39:53Z

The diameter of a tree is the length of a longest path, so to reduce the diameter you must remove an edge from each longest path. Find the center by repeatedly removing all the leaves until only one or two vertices are left (BFS is a terrible way to do it). If the center is an edge, removing that reduces the diameter. If the center is a vertex, you need to remove some edges incident to that vertex. Every longest path passes through the center. You need to remove enough edges incident to the center so that one edge from each longest path is included; it could be anything from one edge to all but one of the edges incident to the center.

partly obscured Rubik's cube

2012-10-10T03:12:17Z

I just came back from a beach which features a large Rubik's cube (2m high). The base of the cube is not visible and the top is not coloured. The four vertical sides are each divided $3\times 3$ into coloured squares as they should be. I was idly wondering: how can I tell if the patterns appearing on those four sides are actually possible for a real cube? Clearly there are necessary conditions like having at most 6 different colours and at most 9 squares of each colour, but is that sufficient? Can the legal configurations be characterized?

Answer by Brendan McKay for Rapid evaluation of multivariate normal integral

2013-04-04T12:08:13Z

I suggest you try Gauss-Hermite integration. You can guess the precision by increasing the number of abscissae. Tables of abscissae and weights are here.

Answer by Brendan McKay for Enumerating 0-1 finite boxes without null rays.

2013-03-30T06:33:25Z

Define $$ N(m,r,s) = \begin{cases} 0 & \text{if } r+s\gt m, \text{ otherwise} \\ 3^m-2 & \text{if } r=s=0 \\ 3^{m-s}-1 & \text{if } r=0,s\gt 0, \\ 3^{m-r}-1 & \text{if } r\gt 0,s=0, \\ 3^{m-r-s} & \text{if } r,s\gt 0. \end{cases} $$ Then $$ M(m,n,2) = \sum_{r,s,\ge 0} (-1)^{r+s} \binom{m}{r,s,m-r-s} N(m,r,s)^n. $$

For $M(n,n,2)$ I get 1, 35, 12757, 35420099, 780742441861, 145246791109197875, ...

Not in OEIS (and shouldn't be put there without checking).

Proof: $N(m,r,s)$ is the number of $2\times m$ binary arrays such that none of the $m+2$ lines sum to 0, and moreover a specified set of $r$ positions in the top row are 0 and a disjoint specified set of $s$ positions in the bottom row are 0. Now make an array by placing $n$ such arrays vertically. There are $2m$ horizontal lines which we still have to make non-zero. The multinomial counts the ways to choose $r$ positions in the top row and $s$ in the bottom row (which must be disjoint positions or one of the 2-element lines is zero). The formula is then just inclusion-exclusion.

The asymptotic number is $$ N(n,n,2) \sim 3^{n^2}, $$ which is easy to prove.

Another case: $M(n,2,2)$ is 1, 35, 313, 2339, 16681, 117395, 823033, 5763779, 40351561, 282471155, 1977318553, 13841270819, ... The sum above only has 4 non-zero terms so there is an explicit formula. Maybe it is $M(n,2,2) = 7^n - 2^{n+2} + 2$.

Answer by Brendan McKay for how rare random bipartite graphs in all random regular graphs

2013-03-24T00:31:16Z

Take $2n$ vertices. Regular bipartite graphs have $n$ vertices of each colour, and most have only one colouring because they are connected (for degree $\ge 3$). So take the asymptotic number of regular bipartite graphs, multiply by $\binom {2n}2$ graphs for the choice of colour classes, and divide by the asymptotic number of regular graphs. You can find all the necessary counts in many places such as this paper of Wormald.

6-regular bipartite graphs with no 8-cycles

2012-07-29T10:55:38Z

I'm looking for simple 6-regular bipartite graphs with no 8-cycles, as small as possible. It doesn't matter if there are 4-cycles or 6-cycles, provided there are no 8-cycles. Such graphs must exist since the girth can be arbitrarily high, but what smaller examples are there? There are certainly none on less than 46 vertices.

Answer by Brendan McKay for Invertibility of a certain matrix indexed by the Hamming cube

2013-03-07T12:50:35Z

For any $i,j,k$, the automorphism group of $A$ is transitive on the set of pairs $(I,J)$ such that $|I|=i, |J|=j, |I\cap J|=k$. Therefore the same is true of the inverse (if it exists). That is, the $(I,J)$-th entry of the inverse is $f(i,j,k)$ for some function $f$. I'm too lazy, but I bet that by examining Benjamin's example the function $f(i,j,k)$ can be guessed rather easily. Then we will have an explicit formula for the inverse.

Here's a WRONG guess: The $(I,J)$-th entry of the inverse is 0 unless $|I\cup J|=n$ and otherwise is $(-1)^{n+k+1}$.

Here's a RIGHT guess: The $(I,J)$-th entry of the inverse is 0 if $|I\cup J|\lt n$ and otherwise equals $(-1)^{k+1}$. I checked this up to n=8.

This is easy to prove by induction using Benjamin's recursive formula for the inverse.

Answer by Brendan McKay for Formal writing: numbers under 10

2013-03-06T12:30:46Z

Generally speaking you should try to distinguish between an English number and a mathematical number. As in "Over the next five chapters we will prove that 5 is a prime number." Never spell out a number which is a subject of study, like the "5" in that sentence.

However ordinals like in "Section 4" and "Lemma 2" are always written with digits. "There are three results in Theorem 3."

Answer by Brendan McKay for "Non-oriented" vs "undirected" graph

2013-03-02T03:57:31Z

Many people consider that an "oriented graph" is what you get from a simple undirected graph when you assign a direction to each edge. The difference between that and "directed graph" is that a directed graph can have cycles of length 2 even if it is qualified as "simple", whereas an "oriented graph" cannot. On the other hand, there are zillions of papers that use "oriented graph" with identical meaning to "directed graph".

Applying these meanings pedantically in the negative doesn't seem to be a good idea. I'd be very surprised to see anyone using "non-oriented" of a digraph to imply that it doesn't have 2-cycles. I only recall "non-oriented" meaning that the edges don't have directions, which is the same as "undirected".

Answer by Brendan McKay for Minimum number of edges - directed graph with given sums of weights

2013-03-01T12:17:23Z

First, divide the vertex weights into a maximum number of portions that each sum to 0 and handle them separately.

For each set of vertices whose weights sum to 0, you can can implement them as a path with edges forward or backward. Just arrange them in arbitrary order and decide one edge at a time. For example for $a=2, b=-3, c=-4, d=6, e=-1$, use order $a-b-c-d-e$, then you can set $a\to b$ weight 2, $c\to b$ weight 1, $d\to c$ weight 5, $d\to e$ weight 1. There is no way to go wrong.

So the answer is the number of vertices minus the maximum number of parts the weights can be divided into such that each part sums to 0.

Answer by Brendan McKay for Awfully sophisticated proof for simple facts

2013-02-24T07:35:39Z

The sum of the degrees of the vertices of a graph is even.

Proof: The number $N$ of graphs with degrees $d_1,\ldots,d_n$ is the coefficient of $x_1^{d_1}\cdots x_n^{d_n}$ in the generating function $\prod_{j\lt k}(1+x_jx_k)$. Now apply Cauchy's Theorem in $n$ complex dimensions to find that $$N = \frac{1}{(2\pi i)^n} \oint\cdots\oint \frac{\prod_{j\lt k}(1+x_jx_k)}{x_1^{d_1+1}\cdots x_n^{d_n+1}} dx_1\cdots dx_n,$$ where each integral is a simple closed contour enclosing the origin once. Choosing the circles $x_j=e^{i\theta_j}$, we get $$N = \frac{1}{(2\pi)^n} \int_{-\pi}^\pi\cdots\int_{-\pi}^\pi \frac{\prod_{j\lt k}(1+e^{\theta_j+\theta_k})}{e^{i(d_1\theta_1+\cdots +d_n\theta_n)}} d\theta_1\cdots d\theta_n.$$ Alternatively, choosing the circles $x_j=e^{i(\theta_j+\pi)}$, we get $$N = \frac{1}{(2\pi)^n} \int_{-\pi}^\pi\cdots\int_{-\pi}^\pi \frac{\prod_{j\lt k}(1+e^{\theta_j+\theta_k})}{e^{i(d_1\theta_1+\cdots +d_n\theta_n+k\pi)}} d\theta_1\cdots d\theta_n,$$ where $k=d_1+\cdots+d_n$. Since $e^{ik\pi}=-1$ when $k$ is an odd integer, we can add these two integrals to get $2N=0$.

Answer by Brendan McKay for many expected streaks imply high probability for a streak

2013-02-20T00:17:09Z

The broken logic in the book can bite in many places. Here is a simple example. If we make a random graph with $n$ vertices and edge probability $3/n$, the expected number of hamiltonian cycles goes to infinity exponentially fast, yet the probability of having any hamiltonian cycle at all goes to 0 exponentially fast.

Overlapping Gershgorin disks

2011-08-13T13:38:05Z

We all know Gershgorin's Circle Theorem, which I will summarise for convenience. Let $A=(a_{ij})$ be an $n\times n$ complex matrix. Define the disks $D_1,\ldots,D_n$ by $$D_i = \Bigl\{ z : |z-a_{ii}|\le \sum_{j\ne i} |a_{ij}|\Bigr\}.$$ Then each eigenvalue of $A$ lies in one of the disks. Moreover, if a connected component of the union of the disks contains $k$ disks, then exactly $k$ eigenvalues of $A$ lie in that union.

My question is when a stronger statement is true. When is it possible to list the eignvalues $\lambda_1,\ldots,\lambda_n$ in such an order that $\lambda_i\in D_i$ for all $i$?

What is a small counterexample for general matrices? Is there a counterexample for real symmetric matrices? Is there a nice family of matrices for which there is no counterexample?

Note that by Hall's marriage theorem, the stronger statement is equivalent to saying that for each $k$, the union of any $k$ disks includes at least $k$ eigenvalues.

Answer by Brendan McKay for Semimagic Squares and Partitions

2013-02-14T23:03:01Z

This is the same answer in different language. Every regular bipartite multigraph of degree $s$ has a proper edge colouring with $s$ colours. Make a bipartite multigraph with $n+n$ vertices, where $X_{ij}$ is the number of edges from vertex $i$ in the first part to vertex $j$ in the second part. This is a regular bipartite graph of degree $s$ and the edge colouring gives the necessary assignments.

Answer by Brendan McKay for Which finite group is not the automorphism group of some rooted finite trees

2013-02-08T11:42:41Z

If I remember correctly, the automorphism groups of trees are those groups which you can make from symmetric groups by direct products and wreath products. This is rather few groups.

An example of a group not occurring would be a nontrivial group with no subgroup of index 2. All simple groups from $Z_3$ upwards, for example.

ADDED: An application of the constructive characterization is that a positive integer is the order of the group of a tree iff it is a product of factorials. So there are no odd numbers, only 2 and 6 as twice an odd number, etc.. Apparently these are called the Jordan-Polya numbers.

For homework, which groups have one of the allowed orders but still aren't groups of trees?

Answer by Brendan McKay for Are all variables in a set of random variables independent if all pairs are independent?

2013-02-08T13:26:42Z

Steven's example is indeed the simplest. See chapter 3 of this book for counterexamples to lots of similar possibilities.

Answer by Brendan McKay for expected number of cycles in a "random" bipartite directed graph

2013-02-07T12:11:04Z

There are $$ \frac{\prod_{i=0}^{k-1}(n-i)^2}{k} $$ possible directed cycles with $2k$ vertices. Each such cycle occurs with probability $n^{-2k}$, so the exact expectation of the number of cycles is $$ \sum_{k=1}^n \frac{\prod_{i=0}^{k-1}(n-i)^2}{kn^{2k}} = \sum_{k=1}^n \frac{\prod_{i=0}^{k-1}(1-i/n)^2}{k}. $$ As $n\to\infty$, that sum is asymptotic to the integral $$ \int_1^\infty \exp(-x^2/n)/x~dx = \left[ -\frac12 Ei(1,x^2/n) \right]_1^\infty = \frac12\log n + O(1), $$ where $Ei$ is the exponential integral function and I'm relying on Maple a bit.

Answer by Brendan McKay for Mathematical techniques to reduce the amount of storage memory

2013-02-06T00:09:04Z

It seems like you want to use the same number of bits for each customer. That is a big mistake and you won't find a good solution unless you drop that requirement.

What you need is an adaptive scheme that is designed according to the customer profile. Allow enough space per customer that will be enough for say 95% of customers. That should be quite a small amount per customer since most people will buy few books. The 5% big spenders are also in this store, but instead of containing a list of books it has a special code indicating it is a big spender. Then you look them up in a second store that just contains the big spenders with more space for each (probably a variety of $B$-tree that allows variable space per customer). The average total space per customer will be small.

Clearly you can tune parameters, and even have more than two levels if you want.

By the way, this is all very very standard data-base methodology.

Answer by Brendan McKay for Finding a vertex equidistant from two given vertices in a digraph

2013-02-05T10:19:25Z

The set of walk lengths between two given vertices is a regular language, so it is the union of a finite number of (finite or infinite) arithmetic progressions. It is routine to determine whether two arithmetic progressions have an element in common, so the question comes down to how quickly this representation of the set of lengths can be computed. Unfortunately I think the number of arithmetic progressions might in general be exponential in the size of the graph.

Another problem it reduces to is whether two rational functions in a single variable have a power in common. (I mean a power of the variable that has nonzero coefficient in the Taylor expansion about 0.) The degrees of the numerators and denominators are at most $n$.

Answer by Brendan McKay for Who invented the expression "pairwise different" and what is its advantage over "different"

2013-02-04T09:09:41Z

When something is defined as a binary relation, "pairwise" is strictly-speaking required in order to apply it to a set larger than two. That's one advantage. Another is that in normal English "different" is the opposite of "equal".

That said, I think "pairwise different", and many similar things, are unnecessarily pedantic. If the meaning of "different" is so clear that most mathematicians wouldn't even pause to think about it, we don't need "pairwise".

The earliest appearance I found this 1941 paper of von Neumann, but I bet someone will find it in German much earlier. MathSciNet has 168 uses starting in 1949.

Answer by Brendan McKay for asymptotic or approximate formula for a combination expression

2013-01-31T10:39:59Z

If independent variables $X,Y$ are distributed Binom$(n,p)$, Binom$(m,p)$, respectively, then $q_1$ is the probability that $X>Y$. If $mp,np$ are large and the line $X=Y$ is not too far from the point $(np,mp)$, then the normal approximation of $X$ and $Y$ will give a reasonable answer since $X-Y$ has a 1-dimensional normal distribution. Namely, $X-Y\sim{}$N$(\mu,\sigma^2)$ where $\mu=(n-m)p$ and $\sigma^2=(n+m)p(1-p)$. If the normal approximation is not good, the same mean and variance are true so you can still get a fair idea.

Answer by Brendan McKay for Growth constant limit for sum of products of two binomial coefficients

2013-01-30T06:34:08Z

Let $\alpha\approx 0.0493932733732$ be the positive zero of $621\alpha^3+1242\alpha^2+585\alpha-32$. Then the limit you want is probably $$ \rho = \frac{729(2+3\alpha)^2}{64(1+\alpha)^2} \left(\frac{4(8+9\alpha)}{621\alpha(1+\alpha)^2}\right)^{\textstyle\alpha} \approx 47.7322896460174547. $$

The reason why I say "probably" is that I didn't prove it rigorously, but I'm sure that rigour is routine to add. First identify the largest terms in the sum by looking at the ratio $f(n,k+1)/f(n,k-1)$, where $f(n,k)$ is the term. This ratio is approximately 1 when $k\approx\alpha n$. In this range, the ratio of $f(n+1,\alpha(n+1))/f(n,\alpha n)$ tends to the quantity I have identified as $n\to\infty$.

To add rigour, find which range of terms are required for the asymptotic value of the sum by expanding $f(n,\alpha n+t)$ as a series in $t$. Probably you will find that the shape is Gaussian and $|t|\le n^{1/2+\epsilon}$ will suffice. With $k$ in that range, the ratio $f(n+1,k)/f(n,k)$ might always converge to the limit above as $n\to\infty$. If not, use the Euler-Maclaurin theorem to sum the terms in this range, make a crude bound on the terms outside this range, and you will have the asymptotic value of the sum.

ADDED: The stuff inside the large parens simplifies to 1, and the stuff outside them simplifies to $$ \rho = \frac{6561}{16} - \frac{452709}{64}\alpha - \frac{1358127}{256}\alpha^2,$$ which implies that $\rho$ is the smallest zero of $$ 1048576\rho^3 - 4353564672\rho^2 + 4518872583696\rho - 205891132094649,$$ which also happens to be $3^{10}/2^8$ times the smallest zero of $y^3-18y^2+81y-16$, and I guess that's about as much simplification as possible.

Answer by Brendan McKay for Multivariate expansion in terms of single variate products: what is the name for this?

2013-01-27T09:57:24Z

This paper calls it "separable of rank $n$" if $n$ is the number of terms in the sum. If the sum is an infinite one, the condition is very weak (for example it includes all functions with a convergent Taylor expansion).

Answer by Brendan McKay for The terminology for a node's number of in-links in weighted directed graph

2013-01-27T03:47:22Z

I've seen papers where $m$ is called the in-degree and $k_{in}$ is called something else (such as weighted in-degree). Using in-degree and fan-in as Vel Nias suggests would be fine too. But you need to define it as there isn't universal agreement on how to interpret these names in the weighted graph context.

Answer by Brendan McKay for Resticted number of edges, optimal connected graph

2013-01-22T10:46:00Z

http://en.wikipedia.org/wiki/Degree_diameter_problem

probability of zero subset sum

2013-01-21T12:59:12Z

Almost 17 years ago, I asked the following question on USENET, motivated by a method in numerology (I kid you not).

Pick integers $n \ge 2$, $k \ge 1$. Toss $n$ $k$-sided dice. The sides of each die are numbered $0,1,\ldots,k-1$. The dice are unbiased and the tosses are independent.

What is the probability $P(n,k)$ that no non-empty subset of the dice adds to a multiple of $k$?

One can get answers with inclusion-exclusion, but it becomes rapidly more difficult as $n$ increases. Simple cases are $$k P(1,k) = k-1,$$ $$k^2 P(2,k) = (k-1)(k-2).$$ David desJardins found that $$ k^3 P(3,k) = k^3 - 7 k^2 + 15 k - 9 - d_2(k), $$ $$ k^4 P(4,k) = k^4 - 15 k^3 + 80 k^2 - 170 k + 104 - (10 k - 40) d_2(k) + 10 d_3(k),$$ where $$ d_2(k) = 1 \text{ if $k$ is even, 0 otherwise},$$ $$ d_3(k) = 1 \text{ if $k$ is 0 mod 3, otherwise}.$$ David also found the leading terms as $k\to\infty$ for fixed $n$, starting with $$ P(n,k) = 1 - (2^n - 1)/k + 1/2 (4^n - 3^n - 2^n + 1)/k^2 + \cdots .$$

However, nobody found an exact formula, recursion, or generating function, or in fact any method for rapid computation when $n$ is large. That's my question.

Comment by Brendan McKay

2013-05-22T09:49:30Z

@Algemon: You are right, gulp. $B_1$ and $B_2$ are independent when conditioned on the ball distribution, but not globally.

Comment by Brendan McKay

2013-05-22T02:34:07Z

Incidentally, Erdős and Rényi did not define this type of random graph in the seminal paper that everyone thinks is the origin of the concept. We really should call them Gilbert random graphs after the guy who did define them (in the same year, 1959).

Comment by Brendan McKay

2013-05-22T02:30:27Z

I think the maximum degree is a red herring. For example, when $c<1$ is constant you can easily check that the probability of having two edge-disjoint paths from 1 to 2 goes to zero, whereas the probability of one of them having degree 0 or 1 does not go to 1. So with high probability they can be separated by removing one edge even though there is some non-zero probability both have degree 2. The same holds for $c=1$, but larger $c$ is harder. I'm pretty sure this has all been worked out, but I'm too lazy to search.

Comment by Brendan McKay

2013-05-22T02:07:09Z

I think Dustin is correct: the events $B_i=1$ are independent. Even conditional on a given distribution of balls they are independent ($i$ is the index of a draw, not the index of a bin). Also, the formula for $E[X_p]$ is elementary and doesn't need a recurrence: $(1-1/m)^p$ is the probability that a particular bin is empty after $p$ balls are thrown in.

Comment by Brendan McKay

2013-05-21T14:22:30Z

@pnaky: Gjergji's answer is close to the best you can do. If $d$ is a divisor of $n$, it is exactly the best you can do. Just set all the $d_i$s equal to $d$.

Comment by Brendan McKay

2013-05-21T14:16:40Z

I'm not sure if you have "with high probability" in the right place. You want that the disconnecting edges exist with high probability, not that 1 and 2 are disconnected with high probability, right?

Comment by Brendan McKay

2013-05-16T11:46:58Z

This is a question about enumerating bipartite graphs with given degree sequences, under a weak condition that two vertices on one side can't have the same neighbours on the other side. Under reasonable conditions the number of solutions will grow faster than exponentially as $m,n\to\infty$.

Comment by Brendan McKay

2013-05-14T04:52:37Z

Is $p$ constant, or can it increase with the graph size? The answer surely depends on it.

Comment by Brendan McKay

2013-05-13T18:01:16Z

I think it is polynomial. To get from $k+1$ colours to $k$ colours, choose an existing colour and monitor the number of balls with that colour. It goes up or down (with equal probability) at least 1 in $n$ turns and is a standard random walk so it hits either 0 or n in polynomial expected time.

Comment by Brendan McKay

2013-05-10T06:01:38Z

Any chance that $b_{n,k}$ is an inclusion-exclusion summation?

Comment by Brendan McKay

2013-05-10T05:54:19Z

I think this is a hard problem even asymptotically for some values of the parameters.

Comment by Brendan McKay

2013-05-10T05:30:59Z

@Gerhard: Agreed, and it shouldn't be too hard to identify the boundary exactly.

Comment by Brendan McKay

2013-05-10T00:08:06Z

Experimentally the error falls exponentially, but proving it might not be so easy. The individual terms in the E-M expansion fall rapidly, but the error term is trickier. I'll stop working on it now.

Comment by Brendan McKay

2013-05-09T12:05:46Z

And the error term is exponentially small. The Euler-Maclaurin formula will show it.

Comment by Brendan McKay

2013-05-09T11:58:19Z

I'm pretty sure the power of $4\ln n$ should be $n+1$ and not $n$.