User brendan mckay - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T05:53:40Z http://mathoverflow.net/feeds/user/9025 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/130071/asymptotics-of-a-function/130086#130086 Answer by Brendan McKay for Asymptotics of a function Brendan McKay 2013-05-08T15:05:50Z 2013-05-09T04:43:11Z <p>$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.</p> <p><strong>Apologies</strong>. I misread the question exact as Benoît suggests.</p> http://mathoverflow.net/questions/129432/counting-matchings-in-a-bipartite-matching-covered-graph/129434#129434 Answer by Brendan McKay for Counting matchings in a bipartite matching-covered graph Brendan McKay 2013-05-02T15:43:27Z 2013-05-02T15:43:27Z <p>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.</p> http://mathoverflow.net/questions/129290/how-quickly-can-we-test-if-a-graph-is-distance-regular How quickly can we test if a graph is distance-regular? Brendan McKay 2013-05-01T07:48:52Z 2013-05-01T07:48:52Z <p>A (simple, finite, connected) graph $G$ is <em>distance regular</em> 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.</p> <p><strong>My question is:</strong> given a graph $G$ with $n$ vertices and $m$ edges, how quickly can we test if $G$ is distance-regular?</p> <p>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).</p> <p>Can it be done quicker?</p> http://mathoverflow.net/questions/128233/how-dense-is-the-set-of-asymmetric-graphs/128308#128308 Answer by Brendan McKay for How dense is the set of asymmetric graphs? Brendan McKay 2013-04-22T04:12:01Z 2013-04-22T04:12:01Z <p>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$.</p> http://mathoverflow.net/questions/127602/minimize-diameter-of-a-tree/127635#127635 Answer by Brendan McKay for Minimize diameter of a tree Brendan McKay 2013-04-15T15:39:53Z 2013-04-15T15:39:53Z <p>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.</p> http://mathoverflow.net/questions/109269/partly-obscured-rubiks-cube partly obscured Rubik's cube Brendan McKay 2012-10-10T03:12:17Z 2013-04-10T19:54:08Z <p>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?</p> http://mathoverflow.net/questions/126460/rapid-evaluation-of-multivariate-normal-integral/126503#126503 Answer by Brendan McKay for Rapid evaluation of multivariate normal integral Brendan McKay 2013-04-04T12:08:13Z 2013-04-04T12:08:13Z <p>I suggest you try <a href="http://en.wikipedia.org/wiki/Gauss%E2%80%93Hermite_quadrature" rel="nofollow">Gauss-Hermite</a> integration. You can guess the precision by increasing the number of abscissae. Tables of abscissae and weights are <a href="http://www.efunda.com/math/num_integration/findgausshermite.cfm" rel="nofollow">here</a>. </p> http://mathoverflow.net/questions/125919/enumerating-0-1-finite-boxes-without-null-rays/125983#125983 Answer by Brendan McKay for Enumerating 0-1 finite boxes without null rays. Brendan McKay 2013-03-30T06:33:25Z 2013-03-30T07:55:04Z <p>Define $$N(m,r,s) = \begin{cases} 0 &amp; \text{if } r+s\gt m, \text{ otherwise} \\ 3^m-2 &amp; \text{if } r=s=0 \\ 3^{m-s}-1 &amp; \text{if } r=0,s\gt 0, \\ 3^{m-r}-1 &amp; \text{if } r\gt 0,s=0, \\ 3^{m-r-s} &amp; \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.$$</p> <p>For $M(n,n,2)$ I get 1, 35, 12757, 35420099, 780742441861, 145246791109197875, ...</p> <p>Not in OEIS (and shouldn't be put there without checking).</p> <p>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.</p> <p>The asymptotic number is $$N(n,n,2) \sim 3^{n^2},$$ which is easy to prove.</p> <p>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$.</p> http://mathoverflow.net/questions/125392/how-rare-random-bipartite-graphs-in-all-random-regular-graphs/125413#125413 Answer by Brendan McKay for how rare random bipartite graphs in all random regular graphs Brendan McKay 2013-03-24T00:31:16Z 2013-03-24T00:31:16Z <p>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 <a href="http://www.math.uwaterloo.ca/~nwormald/papers/regsurveyfull.pdf" rel="nofollow">such as this paper of Wormald</a>. </p> http://mathoverflow.net/questions/103442/6-regular-bipartite-graphs-with-no-8-cycles 6-regular bipartite graphs with no 8-cycles Brendan McKay 2012-07-29T10:55:38Z 2013-03-16T04:59:31Z <p>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.</p> http://mathoverflow.net/questions/123681/invertibility-of-a-certain-matrix-indexed-by-the-hamming-cube/123865#123865 Answer by Brendan McKay for Invertibility of a certain matrix indexed by the Hamming cube Brendan McKay 2013-03-07T12:50:35Z 2013-03-09T02:02:40Z <p>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.</p> <p>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}$.</p> <p>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.</p> <p>This is easy to prove by induction using Benjamin's recursive formula for the inverse.</p> http://mathoverflow.net/questions/123744/formal-writing-numbers-under-10/123749#123749 Answer by Brendan McKay for Formal writing: numbers under 10 Brendan McKay 2013-03-06T12:30:46Z 2013-03-06T12:30:46Z <p>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.</p> <p>However ordinals like in "Section 4" and "Lemma 2" are always written with digits. "There are three results in Theorem 3."</p> http://mathoverflow.net/questions/123333/non-oriented-vs-undirected-graph/123389#123389 Answer by Brendan McKay for "Non-oriented" vs "undirected" graph Brendan McKay 2013-03-02T03:57:31Z 2013-03-02T03:57:31Z <p>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".</p> <p>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".</p> http://mathoverflow.net/questions/123318/minimum-number-of-edges-directed-graph-with-given-sums-of-weights/123320#123320 Answer by Brendan McKay for Minimum number of edges - directed graph with given sums of weights Brendan McKay 2013-03-01T12:17:23Z 2013-03-01T12:17:23Z <p>First, divide the vertex weights into a maximum number of portions that each sum to 0 and handle them separately.</p> <p>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.</p> <p>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.</p> http://mathoverflow.net/questions/42512/awfully-sophisticated-proof-for-simple-facts/122787#122787 Answer by Brendan McKay for Awfully sophisticated proof for simple facts Brendan McKay 2013-02-24T07:35:39Z 2013-02-24T22:22:49Z <p>The sum of the degrees of the vertices of a graph is even.</p> <p>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$.</p> http://mathoverflow.net/questions/122304/many-expected-streaks-imply-high-probability-for-a-streak/122363#122363 Answer by Brendan McKay for many expected streaks imply high probability for a streak Brendan McKay 2013-02-20T00:17:09Z 2013-02-20T00:17:09Z <p>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.</p> http://mathoverflow.net/questions/72832/overlapping-gershgorin-disks Overlapping Gershgorin disks Brendan McKay 2011-08-13T13:38:05Z 2013-02-18T14:29:11Z <p>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 <code>$$D_i = \Bigl\{ z : |z-a_{ii}|\le \sum_{j\ne i} |a_{ij}|\Bigr\}.$$</code> 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.</p> <p>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$?</p> <p>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?</p> <p>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.</p> http://mathoverflow.net/questions/121754/semimagic-squares-and-partitions/121848#121848 Answer by Brendan McKay for Semimagic Squares and Partitions Brendan McKay 2013-02-14T23:03:01Z 2013-02-14T23:03:01Z <p>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.</p> http://mathoverflow.net/questions/121171/which-finite-group-is-not-the-automorphism-group-of-some-rooted-finite-trees/121176#121176 Answer by Brendan McKay for Which finite group is not the automorphism group of some rooted finite trees Brendan McKay 2013-02-08T11:42:41Z 2013-02-08T13:46:04Z <p>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.</p> <p>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. </p> <p>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 <a href="http://oeis.org/A001013" rel="nofollow">Jordan-Polya numbers</a>.</p> <p>For homework, which groups have one of the allowed orders but still aren't groups of trees?</p> http://mathoverflow.net/questions/121190/are-all-variables-in-a-set-of-random-variables-independent-if-all-pairs-are-indep/121194#121194 Answer by Brendan McKay for Are all variables in a set of random variables independent if all pairs are independent? Brendan McKay 2013-02-08T13:26:42Z 2013-02-08T13:26:42Z <p>Steven's example is indeed the simplest. See chapter 3 of <a href="http://tocs.ulb.tu-darmstadt.de/12587850.pdf" rel="nofollow">this book</a> for counterexamples to lots of similar possibilities.</p> http://mathoverflow.net/questions/121025/expected-number-of-cycles-in-a-random-bipartite-directed-graph/121059#121059 Answer by Brendan McKay for expected number of cycles in a "random" bipartite directed graph Brendan McKay 2013-02-07T12:11:04Z 2013-02-07T23:15:58Z <p>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.</p> http://mathoverflow.net/questions/120879/mathematical-techniques-to-reduce-the-amount-of-storage-memory/120919#120919 Answer by Brendan McKay for Mathematical techniques to reduce the amount of storage memory Brendan McKay 2013-02-06T00:09:04Z 2013-02-06T00:09:04Z <p>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.</p> <p>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.</p> <p>Clearly you can tune parameters, and even have more than two levels if you want.</p> <p>By the way, this is all very very standard data-base methodology. </p> http://mathoverflow.net/questions/120820/finding-a-vertex-equidistant-from-two-given-vertices-in-a-digraph/120850#120850 Answer by Brendan McKay for Finding a vertex equidistant from two given vertices in a digraph Brendan McKay 2013-02-05T10:19:25Z 2013-02-05T10:19:25Z <p>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.</p> <p>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$.</p> http://mathoverflow.net/questions/120734/who-invented-the-expression-pairwise-different-and-what-is-its-advantage-over/120739#120739 Answer by Brendan McKay for Who invented the expression "pairwise different" and what is its advantage over "different" Brendan McKay 2013-02-04T09:09:41Z 2013-02-04T09:09:41Z <p>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".</p> <p>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".</p> <p>The earliest appearance I found <a href="http://www.jstor.org/discover/10.2307/2235951?uid=3737536&amp;uid=2&amp;uid=4&amp;sid=21101755524487" rel="nofollow">this 1941 paper of von Neumann</a>, but I bet someone will find it in German much earlier. MathSciNet has 168 uses starting in 1949.</p> http://mathoverflow.net/questions/120220/asymptotic-or-approximate-formula-for-a-combination-expression/120398#120398 Answer by Brendan McKay for asymptotic or approximate formula for a combination expression Brendan McKay 2013-01-31T10:39:59Z 2013-01-31T10:39:59Z <p>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.</p> http://mathoverflow.net/questions/120254/growth-constant-limit-for-sum-of-products-of-two-binomial-coefficients/120284#120284 Answer by Brendan McKay for Growth constant limit for sum of products of two binomial coefficients Brendan McKay 2013-01-30T06:34:08Z 2013-01-30T08:35:52Z <p>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.$$ </p> <p>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$.</p> <p>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.</p> <p>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.</p> http://mathoverflow.net/questions/119895/multivariate-expansion-in-terms-of-single-variate-products-what-is-the-name-for/120003#120003 Answer by Brendan McKay for Multivariate expansion in terms of single variate products: what is the name for this? Brendan McKay 2013-01-27T09:57:24Z 2013-01-27T09:57:24Z <p><a href="http://www.jstor.org/discover/10.2307/2688535?uid=3737536&amp;uid=2129&amp;uid=2&amp;uid=70&amp;uid=4&amp;sid=21101713553267" rel="nofollow">This paper</a> 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).</p> http://mathoverflow.net/questions/119965/the-terminology-for-a-nodes-number-of-in-links-in-weighted-directed-graph/119988#119988 Answer by Brendan McKay for The terminology for a node's number of in-links in weighted directed graph Brendan McKay 2013-01-27T03:47:22Z 2013-01-27T03:47:22Z <p>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.</p> http://mathoverflow.net/questions/119547/resticted-number-of-edges-optimal-connected-graph/119553#119553 Answer by Brendan McKay for Resticted number of edges, optimal connected graph Brendan McKay 2013-01-22T10:46:00Z 2013-01-22T10:46:00Z <p><a href="http://en.wikipedia.org/wiki/Degree_diameter_problem" rel="nofollow">http://en.wikipedia.org/wiki/Degree_diameter_problem</a></p> http://mathoverflow.net/questions/119464/probability-of-zero-subset-sum probability of zero subset sum Brendan McKay 2013-01-21T12:59:12Z 2013-01-21T12:59:12Z <p>Almost 17 years ago, I asked the following question on USENET, motivated by a method in numerology (I kid you not).</p> <p>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. </p> <p><strong>What is the probability $P(n,k)$ that no non-empty subset of the dice adds to a multiple of $k$?</strong> </p> <p>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 .$$</p> <p>However, nobody found an exact formula, recursion, or generating function, or in fact any method for rapid computation when $n$ is large. <strong>That's my question.</strong></p> http://mathoverflow.net/questions/131324/probability-k-bins-are-non-empty/131393#131393 Comment by Brendan McKay Brendan McKay 2013-05-22T09:49:30Z 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. http://mathoverflow.net/questions/131310/removing-edges-from-erdsrenyi-graph-to-make-two-nodes-disconnected Comment by Brendan McKay Brendan McKay 2013-05-22T02:34:07Z 2013-05-22T02:34:07Z Incidentally, Erdős and R&#233;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). http://mathoverflow.net/questions/131310/removing-edges-from-erdsrenyi-graph-to-make-two-nodes-disconnected Comment by Brendan McKay Brendan McKay 2013-05-22T02:30:27Z 2013-05-22T02:30:27Z I think the maximum degree is a red herring. For example, when $c&lt;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. http://mathoverflow.net/questions/131324/probability-k-bins-are-non-empty/131393#131393 Comment by Brendan McKay Brendan McKay 2013-05-22T02:07:09Z 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. http://mathoverflow.net/questions/131279/how-many-perfect-matchings-in-a-regular-bipartite-graph/131285#131285 Comment by Brendan McKay Brendan McKay 2013-05-21T14:22:30Z 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$. http://mathoverflow.net/questions/131310/removing-edges-from-erdsrenyi-graph-to-make-two-nodes-disconnected Comment by Brendan McKay Brendan McKay 2013-05-21T14:16:40Z 2013-05-21T14:16:40Z I'm not sure if you have &quot;with high probability&quot; 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? http://mathoverflow.net/questions/130800/an-interesting-version-of-the-problem-balls-into-bins Comment by Brendan McKay Brendan McKay 2013-05-16T11:46:58Z 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$. http://mathoverflow.net/questions/130521/number-of-edges-in-graph-in-terms-of-reliability Comment by Brendan McKay Brendan McKay 2013-05-14T04:52:37Z 2013-05-14T04:52:37Z Is $p$ constant, or can it increase with the graph size? The answer surely depends on it. http://mathoverflow.net/questions/130489/another-colored-balls-puzzle Comment by Brendan McKay Brendan McKay 2013-05-13T18:01:16Z 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. http://mathoverflow.net/questions/129974/positive-expression Comment by Brendan McKay Brendan McKay 2013-05-10T06:01:38Z 2013-05-10T06:01:38Z Any chance that $b_{n,k}$ is an inclusion-exclusion summation? http://mathoverflow.net/questions/130115/probability-calculation Comment by Brendan McKay Brendan McKay 2013-05-10T05:54:19Z 2013-05-10T05:54:19Z I think this is a hard problem even asymptotically for some values of the parameters. http://mathoverflow.net/questions/130173/bounding-a-sum-of-binomial-coefficients-in-terms-of-the-next-one Comment by Brendan McKay Brendan McKay 2013-05-10T05:30:59Z 2013-05-10T05:30:59Z @Gerhard: Agreed, and it shouldn't be too hard to identify the boundary exactly. http://mathoverflow.net/questions/130071/asymptotics-of-a-function/130145#130145 Comment by Brendan McKay Brendan McKay 2013-05-10T00:08:06Z 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. http://mathoverflow.net/questions/130071/asymptotics-of-a-function/130145#130145 Comment by Brendan McKay Brendan McKay 2013-05-09T12:05:46Z 2013-05-09T12:05:46Z And the error term is exponentially small. The Euler-Maclaurin formula will show it. http://mathoverflow.net/questions/130071/asymptotics-of-a-function/130145#130145 Comment by Brendan McKay Brendan McKay 2013-05-09T11:58:19Z 2013-05-09T11:58:19Z I'm pretty sure the power of $4\ln n$ should be $n+1$ and not $n$.