# Brendan McKay

 9,120 Reputation 2286 views

## Registered User

 Name Brendan McKay Member for 2 years Seen 3 hours ago Website Location Australia Age
Professor of Computer Science Australian National University Specialties: combinatorics, algorithms
 1d comment Probability $k$ bins are non-empty.@Algemon: You are right, gulp. $B_1$ and $B_2$ are independent when conditioned on the ball distribution, but not globally. 2d comment Removing edges from Erdős–Rényi graph to make two nodes disconnectedIncidentally, 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). 2d comment Removing edges from Erdős–Rényi graph to make two nodes disconnectedI 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. 2d comment Probability $k$ bins are non-empty.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. 2d comment How many Perfect Matchings in a regular bipartite Graph@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$. 2d comment Removing edges from Erdős–Rényi graph to make two nodes disconnectedI'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? May16 comment An interesting version of the problem “balls into bins”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$. May14 comment Number of edges in graph in terms of reliabilityIs $p$ constant, or can it increase with the graph size? The answer surely depends on it. May13 comment Another colored balls puzzleI 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. May10 comment positive expressionAny chance that $b_{n,k}$ is an inclusion-exclusion summation? May10 comment probability calculationI think this is a hard problem even asymptotically for some values of the parameters. May10 comment Bounding a sum of binomial coefficients in terms of ‘the next one’@Gerhard: Agreed, and it shouldn't be too hard to identify the boundary exactly. May10 comment Asymptotics of a functionExperimentally 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. May9 comment Asymptotics of a functionAnd the error term is exponentially small. The Euler-Maclaurin formula will show it. May9 comment Asymptotics of a functionI'm pretty sure the power of $4\ln n$ should be $n+1$ and not $n$. May9 revised Asymptotics of a functionwithdraw answer May8 answered Asymptotics of a function May3 comment Random graphs nonisomorphic to unit distance graphsCan we identify some class of non-unit-distance graphs that are almost surely contained in such a random graph? May2 comment Counting matchings in a bipartite matching-covered graphSince a perfect matching can lie along an ear in two different ways, it seems that the recursion provided by an ear decomposition would have exponential complexity. But I'd love to be proved wrong.... May2 accepted Counting matchings in a bipartite matching-covered graph May2 comment Random graphs nonisomorphic to unit distance graphsIs this homework? May2 answered Counting matchings in a bipartite matching-covered graph May1 comment How quickly can we test if a graph is distance-regular?@Tony: Thanks. They compute the matrix of distances then apply the definition of distance regularity to that, taking at least $n^3$ time. May1 asked How quickly can we test if a graph is distance-regular? Apr30 comment Computing a large permanent(Ran out of characters) There is another method where you act like you are generating the whole search tree, but toss a coin at each node to decide whether or not to make its children. The bias of the coin, perhaps different at each level, is adjusted in advance so that what remains is not too large but still has a fair number of leaves. I've made some spot-on predictions using this method, but I've never seen it analyzed. I don't think it is equivalent to Knuth's method. Apr30 comment Computing a large permanentYes, I've seen that happen too, but I've also had some successes. One thing that I've found to help a lot is to collapse some number of lower levels in the tree into one level (so when you get to that level you perform an exhaustive search). That takes care of the situation where most paths die out just before the end. Another modification that should help here would be to define the tree to exclude all useless branches (using a flow algorithm for example) so that no paths die out at all. It will be much slower but also much less skewed I think. Apr30 comment Computing a large permanentA general estimation method that I think would work here starts by defining any backtrack program that counts the matchings in this bipartite graph. Then estimate the number of nodes at the right level of the search tree by using Knuth's method that involves tracing random paths. This gives an unbiased estimator, though it can be hard to get a reliable estimate of the precision. Apr29 comment Computing a large permanentIf the matrix is extremely sparse it could be possible. It is much bigger than problems usually solvable. Apr26 awarded ● Civic Duty Apr25 comment Is Ryser’s conjecture on permanent minimizers still open?@Gerhard: Yuichiro is correct. Only row and column sums need to be $k$. Apr22 comment smallest number of comparisons needed@Douglas: Can you expand please? Apr22 comment How many distinct eigenvalues does a random graph have?Pretty sure it isn't known, though most people would conjecture the even stronger result that the characteristic polynomial is usually irreducible. Chris Godsil will give us an authoritative answer shortly. Apr22 answered How dense is the set of asymmetric graphs? Apr21 comment 3-coloring of specific planar graphsGraphs made like this are called Halin graphs Apr19 comment Solutions to $\binom{n}{5} = 2 \binom{m}{5}$Any solutions have $n=\lfloor 2^{1/5} m\rfloor$, so there are no further solutions for $m\le 10,000,000$. Apr15 answered Minimize diameter of a tree Apr12 comment Inequality of Partial Taylor SeriesThe upper limit of the sum should be $n-1$ I believe. Apr12 comment Inequality of Partial Taylor SeriesYou won't find an exact answer. However, the difference between the left side and $e^x$ is the tail of the Taylor series so can be expressed in many ways including as an integral. Bounding that integral will give you bounds on $x$. Apr4 answered Rapid evaluation of multivariate normal integral Mar30 revised Enumerating 0-1 finite boxes without null rays.deleted 129 characters in body Mar30 revised Enumerating 0-1 finite boxes without null rays.added 177 characters in body Mar30 revised Enumerating 0-1 finite boxes without null rays.added 212 characters in body; added 74 characters in body Mar30 revised Enumerating 0-1 finite boxes without null rays.added 1 characters in body; edited body Mar30 revised Enumerating 0-1 finite boxes without null rays.added 594 characters in body Mar30 answered Enumerating 0-1 finite boxes without null rays. Mar29 awarded ● Nice Answer Mar24 answered how rare random bipartite graphs in all random regular graphs Mar22 accepted asymptotic or approximate formula for a combination expression Mar21 accepted “Non-oriented” vs “undirected” graph Mar19 awarded ● Popular Question