User kevin p. costello - MathOverflow

Answer by Kevin P. Costello for Discrete disjoint covering of integer lattices

2013-05-08T19:11:04Z

Let $S$ be the set of integer points $(x_1,x_2,\dots,x_n)$ satisfying

$$x_1+2x_2+3x_3+\dots+nx_n \equiv 0 \mod n+1,$$

and $T$ be the basis-and-origin simplex as described in Ben's comment.

Then translates of $T$ by $S$ disjointly cover $\mathbb{Z}^n$ (since decreasing the $x_i$ coordinate by $1$ changes the left hand side of the above relation by $i$, for any point not in $S$ there's exactly one direction we can move in to reach $S$).

Answer by Kevin P. Costello for Average size of determinants of integer matrices?

2013-04-14T07:43:01Z

As noted in Will's comment above, it's easy to compute the expected square of the determinant. More precisely, we have $$E(\det M^2)=n! \prod \frac{k_i (k_i+1)}{3}.$$

Let $M'$ be formed from $M$ by dividing each row by $\left(\frac{k_i(k_i+1)}{3}\right)^{1/2}$. Now each entry has mean $0$ and variance $1$, and furthermore the entries are bounded. The determinants of such matrices as the size of the matrix tends to infinity have been well studied, by Girko, Tao and Vu, and Nguyen and Vu, among others.

For example, it follows from Theorem 1.1 in the Nguyen and Vu paper linked above that $\log |det(M')|$ is asymptotically normal with mean $\frac{1}{2} \log((n-1)!)$ and variance $\log n$. Taking this and rescaling back to $M$, we have that with probability tending to $1$ as $n$ tends to infinity that $$ det M^2 = \ n^{-1+o(1)} E(det M^2).$$

In particular, the squared determinant is almost surely concentrated in a short interval which does not contain its expectation!

Answer by Kevin P. Costello for Bounding statistical distance by matching moments

2013-04-12T19:17:48Z

I believe that for total variation distance $k$ needs to be $2n$ regardless of the value of $\epsilon$.

Suppose that we have the first $k$ moments. Then the two distributions $p$ and $q$ must satisfy $Ap=Aq$, where $A$ is the $(k+1) \times (2n+1)$ matrix whose entries have the form $j^i$ (where $j$ runs from $-n$ to $n$ and $i$ from $0$ to $k$). For $k=2n$ this is a Vandermonde matrix, so invertible, and the moments uniquely determine $p$.

Conversely, if $k=2n-1$ there is a non-zero vector $v$ in the nullspace of $A$. Renormalize $v$ so that both the positive entries and the negative entries of $v$ sum to $1$ (the entries of $v$ sum to $0$ thanks to the first row of $A$).

Then define $p(i) = \max(0,v(i))$ and $q(i)=\max(0,-v(i))$. By construction, $p-q=v$, so $p$ and $q$ match their first $2n-1$ moments. On the other hand, the total variation distance between $p$ and $q$ is $2$, the maximum possible.

This doesn't answer your second question, though.

Answer by Kevin P. Costello for Invertibility of a certain matrix indexed by the Hamming cube

2013-03-06T00:01:58Z

This argument is motivated by some of the ideas in this paper of Dowling and Wilson --I think it may also be possible to extract the result directly from that paper somehow.

Let $A'$ be formed by $A$ by adding an additional row and column of $0's$ to represent the empty set, and let $J$ be the $2^n \times 2^n$ matrix of all $1's$. Then $J-A'$ can be thought of as the graph on all $2^n$ vertices where we connect two sets if they are disjoint. We have $$det(J-A')=\sum_{\sigma} (-1)^{sgn(\sigma)},$$ where the sum is taken over all permutations such that $\sigma(I) \cap I=0$ for all subsets $I$. But the only such permutation is the one where $\sigma(I)$ is the complement of $I$ (if you assign the sets from largest cardinality to smallest, at each step there's only one choice for $\sigma(I)$).

Since $J-A'$ has full rank and $J$ has rank $1$, then $A'=J-(J-A')$ has rank at least $2^n-1$. Dropping the row and column of $0's$, we have that $A$ has full rank.

Answer by Kevin P. Costello for Concentration bounds for sums of random variables of permutations

2013-01-29T20:57:02Z

One useful trick that comes in handy sometimes (I originally saw it in this paper of Talagrand, though it may go further back): We can view a random permutation in $S_n$ as being generated as follows: Start with the identity permutation, and successively perform transpositions of the form $(n, a_n)$, then $(n-1, a_{n-1})$, and so on down to $(2, a_2)$, where each $a_j$ is uniformly chosen from the numbers between $1$ and $j$ (with no transposition if $a_j=j$).

The point is that the $a_j$ are now independent. So if we have a situation where each individual $a_j$ has little impact on the sum of the $X_i$ or $Y_i$, then we can apply concentration bounds for independent variables. For example, changing an individual $a_j$ only impacts at most $3$ positions in the final permutation (whereever $j$, the old $a_j$, and the new $a_j$ end up), changing an individual $a_j$ can only change $X_1+\dots+X_n$ by $3$ (or at most $1$, if you're more careful), so McDiarmid's inequality immediately gives exponential concentration on the sum.

Answer by Kevin P. Costello for Completion time of a process on a tree

2013-01-24T22:33:18Z

It seems the $\log D$ is unnecessary. We can model the process as follows:

Let $v_1, \dots, v_j$ be the initial leaves of the tree, and let $p_1, \dots, p_j$ be the paths eminating from the leaves to the root vertex. At each step we perform the following:

-Delete the initial vertex of each $p_i$ independently with probability $1/2$.
-If any $p_j$ is a proper subset of some other $p_k$, delete it. If there are two or more identical paths, delete all but one.

Note that by construction after each step the leading vertex of $p_j$ is eligible (if it were not eligible, $p_j$ would be a proper subset of the path containing its eligible child) and the leading vertices are distinct. Furthermore, every unsuccessful vertex is in at least one path until it becomes successful. So the tree becoming successful is equivalent to all the paths either being deleted or becoming empty.

Now consider an alternative process where we do not perform the second step at all, always just reducing each list by $1$ with probability $1/2$ at each step (now a vertex may be deleted from one list but stay on other lists). This alternative process always takes at least as long to finish as the original process. But now it's easy to analyze. Each path has length at most $D$ initially, so the probability it lasts beyond $2D+c\sqrt{D}$ steps decays exponentially in $c^2$. There's at most $D^2$ paths initially, so if we take $c$ large enough to make this probability smaller than $\frac{\delta}{D^2}$, we'll have the desired probability.

I believe this should get you something like $2D+O(D^{1/2} \log(D/\delta))$, which is pretty much the best you can hope for (consider a tree consisting of $D$ disjoint paths of length $D$ from the root).

Answer by Kevin P. Costello for Existence of (Cut-Based) pseudorandom graphs beating the random graph

2012-12-06T20:50:59Z

This isn't a full solution, just a couple of observations too long to fit into a comment.

First of all, it's worth noting that both of the "one-sided" versions of this statement are false. In the complete bipartite graph $K_{n/2,n/2}$, every cut satisfies $E(S,S^C) \geq \frac{1}{2}|S||S^C|$, and in the union of two disjoint copies of $K_{n/2}$ every cut satisfies $E(S,S^C) \leq \frac{1}{2}|S||S^C|$ (these examples can be modified by adding $O(n)$ edges so that their density is exactly $1/2$ if $n$ is a multiple of $4$). This rules out a number of arguments that attempt to construct (randomly or otherwise) an unusually dense cut.

Secondly, the following weaker statement IS true: If $G$ is an $n/2$-regular graph, then there are disjoint subsets $S$ and $T$ such that $E(S,T) \geq \frac{1}{2}|S| |T| + \Omega(n^{3/2})$. A rough sketch of the argument is to take $S$ to be a random subset of the vertices where each vertex is in $S$ with probability $0.1$, then take $T$ to be all the vertices outside of $S$ having at least $|S|/2+0.01 \sqrt{n}$ neighbors in $S$. This automatically forces $E(S,T) \geq |S||T|/2+0.01 |T| \sqrt{n}$, so we just need to show that $|T|$ is large for some $S$.

Each vertex is in $T$ with positive probability (this is where we need regularity), so the expected number of vertices in $T$ is at least $cn$. This means that some $S$ must have a $T$ at least this large.

Unfortunately, this probably does not extend to an argument giving a cut across the whole graph, since the conclusion is one-sided.

Answer by Kevin P. Costello for The minimum size of Max-Cut for graphs of half density

2012-12-03T19:00:05Z

Let $n=4k$, and let $G$ be a graph consisting of two disjoint copies of $K_{2k}$ along with $k$ additional edges (the $k$ additional edges being there to give $G$ density $1/2$).

Any cut of $G$ cuts at most $k^2$ edges from each of the complete graphs, along with the $n$ additional edges, so the max-cut value is at most $2k^2+k=n^2/8+n/4$.

Answer by Kevin P. Costello for Large Intersecting Subsets of a Set

2012-10-24T17:50:23Z

Note: The original answer here had (as noted in the comments) an incorrect calculation of $(Ax)^T Ax$. I've replaced it by the trivial bound $(Ax)^T Ax \geq 0$, which weakens the bound to it doesn't quite match the Hadamard bound anymore.

Here's something which shows the constructions yielding $2n$ are almost tight.

Let $A$ be the $|U| \times n$ matrix where the entry $a_{ij}$ is equal to $1$ if $i \in S_j$ and $-1$ otherwise, and let $B=A^T A$.

Then $B$ is an $n \times n$ matrix having diagonal entries equal to $|U|$ and off-diagonal entries equal to $$b_{ij}=|U| - 2 (|S_j \cap S_i^C| + |S_i \cap S_j^C|)$$ $$=|U|-4(n- |S_i \cap S_j| ) \leq |U| - 2n.$$

Letting $x$ be the $n \times 1$ vector of $1$'s, this implies
$$(Ax)^T (Ax) = \sum_i \sum_j b_{ij} = n |U| + \sum_{(i,j), i \neq j} b_{ij} \leq n|U| + n(n-1) (|U|-2n).$$

But this must be at least $0$, which implies $|U| \geq 2n-2$.

If $n$ is odd, we can improve this slightly to $2n-1$ by replacing the bound $|S_i \cap S_j| \leq n/2$ by $|S_i \cap S_j| \leq (n-1)/2$.

Answer by Kevin P. Costello for Concentration results for inner products of two independent random gaussian vectors

2012-10-19T15:41:07Z

An alternative method is to exploit the rotational invariance of the Gaussian. You can write $$X^T Y = |X| \left( \left(\frac{X}{|X|}\right)^T Y \right).$$ Because $Y$ is rotationally invariant, the inner product is now independent of $X$, and in fact just has distribution $N(0,1/m)$. Now let $C>1$ be an arbitrary parameter. We can bound the probability $X^T Y > \epsilon$ by the probability one of the following two events occur.

$ \left(\frac{X}{|X|}\right)^T Y \geq \frac{\epsilon}{C}$. Assuming $ \epsilon \sqrt{m}/C$ tends to infinity, this occurs with probability $\Phi (\frac{\epsilon \sqrt{m}}{C})=(1+o(1)) \sqrt{\frac{m}{2 \pi}} \exp(-\frac{\epsilon^2 m}{C^2})$.
$|X| \geq C$. The norm of a Gaussian vector is well studied, and it is standard (see, for example Chapter 2 of these notes, that $|X|$ is tightly concentrated around its expectation. For example, applying Corollary 2.3 of the linked notes gives that the probability this occurs is at most $\exp(-\frac{1}{4} (1-\frac{1}{C^2})^2 m)$

For $\epsilon$ bounded away from $0$ you can choose $C$ to optimize the sum of the two terms getting a bound that is exponential in $m$ but with a non-optimal exponent. If $\epsilon$ is tending to $0$ with $m$, then the first term is dominant. That term remains small so long as $\epsilon$ is much larger than $\sqrt{\frac{\log m}{m}}$.

Answer by Kevin P. Costello for The cycle structure of twisted wires, connected

2012-10-09T20:27:50Z

Here's an alternative way of thinking about the problem and Will's answer in the case where $n$ is even.

If we identify the identically labelled vertices on each side, we're left with a graph on $n$ vertices formed by the union of two matchings: The fixed matching ($(1,2), (3,4), \dots, (n-1,n)$) and a random matching. Now imagine exposing the random matching one edge at a time.

At the start (before the new matching is exposed), we have a set of $n/2$ isolated edges. There's a $\frac{1}{n-1}$ chance that the first exposed edge in the second matching is already in the first matching, leaving us with a closed loop together with $n-1$ isolated edges. Otherwise, we have a single path of length $2$ together with $n-2$ isolated edges.

When the next edge is exposed, its endpoints are chosen uniformly at random from the degree $1$ vertices. It closes a cycle if the two endpoints are from the same path. The key thing here is that there's always $\frac{n}{2}-1$ open paths that can be closed, regardless of what happened in the previous edge. This is true in general: Whether an edge closes an existing path off or connects two paths, it always reduces the number of open paths by exactly $1$. So as the $k^{th}$ edge in the new matching is exposed, there's $\frac{n}{2}+1-k$ open paths and a $\frac{1}{n-2k+1}$ chance of closing one of them.

It follows that the number of cycles can be thought of as $x_1+\dots+x_{n/2}$, where the $x_i$ are independently $1$ with probability $\frac{1}{2i-1}$ and $0$ otherwise. This means that

-The probability that there's exactly one cycle (that $x_2=x_3=\dots=0$) is $$\frac{2}{3} \frac{4}{5} \dots \frac{n-2}{n-1} = \frac{2^n \left(\frac{n}{2}!\right)^2}{n\cdot n!}$$

-The expected number of cycles is $\frac{1}{1}+\frac{1}{3}+\dots+\frac{1}{n-1} \approx \frac{1}{2} \log n$

-The number of cycles is reasonably concentrated around its mean (e.g. by Chernoff's bound we have $$P(|X-E(X)| \geq \frac{1}{2} E(X) ) \leq 2 e^{-E(X)/16} = 2n^{-1/32})$$

Answer by Kevin P. Costello for The latice spanned by $m$ random 0-1 vectors of length $n$

2012-08-31T23:00:37Z

I believe it is possible to use some recent closely related work of Kenneth Maples to get a much better (but probably still not quite tight) bound. Let $C>0$ be a constant to be chosen later. Call an $n \times n$ matrix $A$ good if it satisfies each of the following properties

P1. $A$ is non-singular over $\mathbb{R}$.

P2. $|det(A)|$ has at most $C \log n$ prime factors.

P3. $A$ has rank at least $n-C \log n$ over ${\mathbb F}_p$ for every prime $p$.

Here are two claims which together would imply $n+O(\log n)$ vectors are enough.

Claim 1: A random $n \times n$ $(0,1)$ matrix is good with probability $1-O\left(C^{-1}\right)$.

Claim 2: If $A$ is any fixed good matrix, augmenting $A$ by $5C \log n$ random rows with high probability leads to a matrix whose rows span ${\mathbb Z}^n$.

We first look at claim 1. The probability P1 fails is exponentially small in $n$ (as originally shown by Kahn, Komlos, and Szemeredi).

For P2 and P3, we use the following result of Maples (Corollary 1.3 here): For any prime $p$, the probability that a random $n \times n$ matrix has rank $n-k$ over ${\mathbb F}_p$ is

$$p^{-k^2} \frac{\prod_{\ell=k+1}^{\infty} \left(1-p^{-\ell}\right)}{\prod_{\ell=1}^k \left(1-p^{-\ell}\right)}+O\left(e^{-cn/2}\right),$$ where both $c$ and the constant implicit in $O()$ are independent of $p$. We can actually bound the probability above by $O\left(p^{-k^2} +e^{-cn/2}\right)$, since the ratio of products is at most $\prod_{\ell=1}^{\infty} (1-2^{-\ell})^{-1}$. Summing over all $k$, the probability $A$ is singular over ${\mathbb F}_p$ is $O\left(\frac{1}{p} + e^{-\frac{cn}{2}}\right)$. Summing over all $p$, the expected number of primes less than $e^{cn/4}$ dividing $|det(A)|$ is at most $\log n +O(1)$.

There can be at most $2 \log n/c$ prime factors of $|det(A)|$ larger than $e^{cn/4}$, since otherwise $|det(A)|$ would be larger than $n^{n/2}$ and violate Hadamard's bound. So the total expected number of factors is $O(\log n)$, and the probability P2 fails is $O(1/C)$ by Markov's inequality.

For P3, we again split into small and large primes. Applying Maples' theorem again, the probability P3 fails for a given prime less than $e^{cn/4}$ is at most $O\left(p^{-C^2 \log^2 n}+ e^{-cn/2}\right)$, and by the union bound the probability P3 fails for some small prime is small.

For large primes, we use the observation that $A$ can only have rank less than $n-k$ over ${\mathbb F}_p$ if $p^k$ divides the determinant of $A$ (e.g. because in this case we can row reduce over the integers so $k$ rows have all entries divisible by $p$, at which point we can pull a factor of $p$ out for each row). In particular, if $C$ is sufficiently large we know from Hadamard's bound it is impossible for P1 to succeed and P3 to fail for some prime larger than $e^{cn/4}$. This finishes Claim 1.

We now turn to Claim 2. We first note that the for $m \geq n$ the vectors $v_1, \dots, v_m$ span ${\mathbb Z}^n$ if and only if the matrix with the $v_i$ as rows has full rank over ${\mathbb F}_p$ for every prime $p$ (if the volume of a cell is $V$, then $V$ divides the determinant of every $n \times n$ submatrix). Since $A$ is good, we know that we already are full rank for all but at most $C \log n$ primes. So it is enough to show the augmentation with high probability fixes each of those primes. Fix any one such prime $p$.

We use the following observation (originally due to Odlyzko): Any proper subspace of ${\mathbb F}_p^n$ contains at most half of the $(0,1)$ vectors (e.g. because if you fix a column basis, whichever column is not in the basis is determined by the remaining $n-1$ columns). It follows that so long as $v_1, \dots ,v_j$ do not already span the space, $$P\left(v_{j+1} \notin Span(v_1, \dots v_j) \right) \geq \frac{1}{2}.$$ By assumption P3, $A$ already had rank at least $n-C \log n$ before we added the rows. The only way $A$ can fail to be full rank after the augmentation is if the above event occurred at least $4 C \log n$ times, an event which occurs with probability at most $$\binom{5C \log n}{4 C \log n} 2^{-4C \log n} = 2^{(-0.39+o(1)) C \log n}.$$ Taking the union bound over all $p$ which divide $|det(A)|$, the probability we fail to be of full rank modulo some prime is at most $C \log n 2^{-(0.39+o(1)) C \log n} = Cn^{-0.39C+o(1)}$, proving Claim 2.

This bound is probably still not quite tight, especially in the handling of P3 for large $p$. One annoyance in trying to drop below $\log n$ is that if the last row of $A$ and all the rows added in the augmentation are zero (an event occurring with probability roughly $2^{-n(m-n)}$), the matrix fails to be of full rank modulo every prime. This means just taking the union bound over all the roughly $2^{c n \log n}$ primes less than $n^{n/2}$ won't be enough if $m-n$ is much smaller than $\log n$, unless we could possibly get some handle on the event "$A$ is of full rank over $\mathbb{R}$ but not over ${\mathbb F}_p$" for large $p$.

Answer by Kevin P. Costello for bounding coefficients in the extended Pascal's triangle.

2012-08-05T05:17:57Z

I don't believe any such inequality is possible.

The $x^k$ coefficient of $(1+\dots+x^n)^d$ is $(n+1)^d$ times $P(X_1+\dots+X_d=k)$, where $X_i$ are iid variables uniform on ${0,1,2,\dots,n}$.

If we fix $n$ and let $d$ tend to infinity, then the maximal concentration of $X_1+\dots+X_d$ decays at least as slowly as $C_n d^{-1/2}$ for some constant $C_n$ depending on $n$ (e.g. because by Chebyshev's inequality the sum lies within $-C \sqrt{d}$ and $C\sqrt{d}$ of the mean with probability at least $1/2$ for large $C$, so by pigeonhole some value in that range is likely).

Similarly, the multinomial coefficient $\binom{d}{k_0,\dots,k_n}$ can be thought of as $(n+1)^d$ times $P\left(Y_1+\dots+Y_d=(k_0,k_1,\dots,k_n)\right)$, where the $Y_i$ are iid variables uniform on vectors of the form $(0,\dots,0,1,0,\dots,0)$.

If we fix $n$ and let $d$ tend to infinity, then the maximal concentration of this sum should decay at least as quickly as $c_n d^{-n/2}$. I assume this is well known somewhere, but here's a rough idea for such a bound. It's very unlikely (probability exponentially small in $d$) for any coordinate to be far away from $\frac{d}{n+1}$. So now suppose that all the $k_i$ are near $\frac{d}{n+1}$. Then the probability the first coordinate equals $k_0$, the probability the second coordinate equals $k_1$ given the first coordinate equals $k_0$, and so on up to the probability the second to last coordinate is equal to $k_{n-1}$ given the previous coordinates are all at most $C_n d^{-1/2}$, where $C_n$ is again a constant depending on $n$.

Combining these bounds, the ratio $\frac{M(n,d)}{C(n,d)}$ tends to infinity for fixed $n$ as $d$ tends to infinity.

Answer by Kevin P. Costello for The latice spanned by $m$ random 0-1 vectors of length $n$

2012-07-03T22:01:15Z

I believe (but haven't fully checked) that you can get an upper bound of $m=cn \log^2 n$ using the second moment method. I'm including a sketched argument below.

I will assume WLOG that $m$ is even. I will also (for now) make a parity assumption: I will assume that, modulo $2$, the sum of all $m$ vectors is equal to $(1,0,\dots,0)$.

Consider the $\binom{m}{m/2}$ vectors $$v_A := \sum_{j \in A} v_j - \sum_{j \notin A} v_j,$$ where $A$ is any subset of size $m/2$. For any given $A$, the probability $v_A$ equals $(1,0,\dots 0)$ is $$\frac{\binom{m}{m/2-1}}{2^{m-1}} \left(\frac{\binom{m}{m/2}}{2^{m-1}}\right)^{n-1} = \left(\frac{4}{\pi n}+o(1)\right)^{n/2}$$ by Stirling's approximation (note that I'm dividing by $2^{m-1}$ here due to the parity assumption).

So the expected number of $v_A$ equal to $(1,0,\dots,0)$ is (again using Stirling's approximation) $$\frac{2^m}{\sqrt{\pi m/2}} \left(\frac{2}{\pi n}+o(1)\right)^{n/2}, $$ which tends to infinity for $m=c n \log n$ and sufficiently large $c$. We now look at the second moment.

If $|A \cap B|=k$, then for each coordinate (except the first, which is pretty much the same), the event $v_A(t)=v_B(t)=0$ corresponds (after a bit of rearrangement) to the pair of events $$\sum_{j \in A \cap B} v_j (t) = \sum_{j \in A^C \cap B^C} v_j(t)$$ $$\sum_{j \in A \cap B^C} v_j (t) = \sum_{j \in A^C \cap B} v_j(t).$$ So the probability that both occur equals $$\frac{\binom{2k}{k} \binom{m-2k}{m/2-k}}{2^{m-1}}.$$ We therefore have $$\frac{P(v_A=v_B=0)}{P(v_A=0)^2}=\left( 2^{m-1} \frac{\binom{2k}{k} \binom{m-2k}{m/2-k}}{\left(\binom{m}{m/2}\right)^2} \right)^n$$ Applying Stirling/central binomial asmyptotics again, I get that after some more algebra this becomes $$\left(\frac{m/4}{\sqrt{k(m/2-k)}} \left(1+O(\frac{1}{\min(k,m/2-k)})\right)\right)^n.$$

For $|k-m/4|=t\sqrt{m}$, the first fraction is $1+O\left(\frac{t^2}{m}\right)$ so for $t=o(\sqrt{\log n})$ we have $$\frac{P(v_A=v_B=0)}{P(v_A=0)^2}= \left(1+O(\frac{t^2}{m})\right)^n = 1+o(1).$$ [The parity assumption is necessary to make this work -- otherwise the fact that $v_A=v_B$ modulo $2$ increases the probability by a factor of $2$ for each coordinate]. I believe (but haven't gone through the full details) that it's similarly possible to bound the tails, so by Chebyshev we will almost surely have $(1,0,0,\dots,0)$ by the time we get to $m=c n \log n$, under our parity conditioning.

By another second moment calculation, we know that any subset of size $2m$ vectors almost surely has a subset of size $m$ having the desired sum modulo $2$ (the second moment calculation's actually a lot simpler here -- for any $A \neq B$ the sums of $A$ and $B$ are independent!). So by increasing $m$ to $2cn \log n$, we can remove the parity conditioning and almost surely have a sum equal to $(1,0,\dots,0)$. Taking $\log n$ collections of this size $m$, we can almost surely hit every coordinate vector.

Effectively I lost a $\log$ in this argument when I only considered the $v_A$ instead of more general sums, and another $\log$ in the end when I considered $\log n$ disjoint collections of vectors instead of allowing the collections to interact with each other. Both may be unncessary.

Answer by Kevin P. Costello for A strange sum over bipartite graphs

2012-03-05T18:57:53Z

I'm not sure if this is the right interpretation or not...it may really just be another way of encoding the generating function argument. Let $H$ be a random bipartite graph where every edge appears independently with probability $1/2$. Then the left hand side is $$2^{n^2} E \left(\prod_v f(v) \right),$$ where $f(v)$ is equal to $\sum_u x(u,v)$ and $x(u,v)$ is $1$ if an edge is not present, $-1$ if an edge is present. Expanding out the product and using linearity of expectation, we can write this as

$$2^{n^2} \sum_{\sigma} E \left(\prod_{v} x(v,\sigma(v))\right)$$ Where $\sigma$ consists of all mappings taking each vertex to a vertex on the opposite side.

Any $\sigma$ for which some edge $(v,\sigma(v))$ appears only once has $0$ expectation due to independence. The $\sigma$ for which every edge appears for both of its endpoints correspond to matchings between the left and right side, of which there are $n!$. (This last observation corresponds to the fact that the expected square of the permanent of an $n \times n$ random Bernoulli matrix is $n!$...I think it goes at least back to Turan).

Answer by Kevin P. Costello for spectra of VERY sparse random matrices

2012-01-20T21:50:20Z

Also in the "a little too involved for a comment" class: A matrix that's this sparse is usually going to be a block diagonal matrix with very small blocks.

Let $k$ be any fixed constant, and suppose that your matrix contains no $k+1 \times k+1$ principal submatrix with at least $k$ nonzero entries. Then your matrix has a block decomposition with all blocks having size at most $k+1$ (If you start with a given nonzero entry and "grow" it by adding entries in the same row/column as an entry already added, you'll stop by the time you've reached $k-1$ added entries, and each addition increases the size of your block by at most $1$). In this case we can upper bound the probably a submatrix of this size exists by $$\binom{n}{k+1} \binom{(k+1)^2}{k} p^{k} \leq C_k n^{k+1-k \beta}$$ Which goes to $0$ for any $\beta$ in your range if $k$ sufficiently large.

This means you'll usually see singular vectors with very small support, and that the $\sigma_2$ should be much larger than $\sqrt{np}$ (maybe equal to $\sigma_1$ in most cases?) You might be able to get something more explicit by enumerating all the possible structures of blocks and the expected number of occurrences of each.

Answer by Kevin P. Costello for Equitable Allocation of Individuals to Positions

2012-01-04T21:08:11Z

Here's something which might work. WLOG we may assume that $\sum v_j = \sum b_j=1$.

Our algorithm will proceed in at most $n$ stages. At each stage we will assume that we have a sorted list $b_1 \geq b_2 \geq \dots \geq b_n$ with $\sum b_i=1$.

Consider the assignment scheme where we assign endowments according to this order, breaking ties randomly (so for example, if $b_1=b_2=b_3>b_4$, then individuals $1$ $2$ and $3$ will receive positions $1$, $2$, and $3$ uniformly from the $6$ possible orders). Under this scheme, each individual will receive an expected valuation $y_i$ (By construction the $y_i$ are also sorted, with ties for individuals with equal endowments).

Let $p \leq 1$ be chosen maximal subject to the constraint that for every $i$ we have

$$b_i - p y_i \geq b_{i+1} - p y_{i+1}$$

We follow this assignment scheme with probability $p$. If we do not follow this assignment scheme, we replace each $b_i$ with $b_i-py_i$ and rescale so that the sum of the $b_i$ remains equal to $1$. At each stage one of two things will happen.

-$p$ is strictly less than $1$. In this case the new $b_i$ correspond to the target expected value, given that the algorithm hasn't already chosen an assignment. Furthermore, the number of distinct values of $b$ is reduced by at least $1$. So we can't be in this state indefinitely.

-$p=1$. If this happens because the $b_j$ and the $y_j$ are exactly equal, we are done and have produced the desired assignment probabilities. If this is not the case then (because the $b_i-y_i$ are sorted and sum to $0$), we must have that there is some $i$ such that at this stage we have $b_1 = b_2 = \dots = b_i>b_{i+1}$ and $y_1=y_2=\dots=y_i < b_1$. This means there's no satisfying assignment at our current stage, since the average of the $i$ largest $b$ is strictly larger than the average of the $i$ largest $v$.

But at every stage of our algorithm we assigned as much value as possible to the $b_i$ (since our sorting never changed and $b_i$ was always strictly larger than $b_{i+1}$, we've always assigned the $i$ most valuable positions to the $i$ largest endowments). So the original problem must also have had an average of the $i$ largest $b$ which was too large to be satisfiable.

Edit: One corollary of this algorithm is that an assignment is possible iff $\sum_{j=1}^k b_j \leq \sum_{j=1}^k v_j$ for every $k$. If this doesn't hold, the algorithm might return an assignment before you reach the $p=1$ stage, but the assignment won't have the desired expected values.

Answer by Kevin P. Costello for Problem regarding subsets that sum to 0

2011-12-08T21:17:56Z

As suggested by Christian, you may want to start by looking at the Littlewood-Offord problem. Here's a scaled version of Erdős' result that might be more relevant to your problem:

"If $a_1, \dots a_n$ are all nonzero, then for any $c$ subsums which equal $c$ is at most $\binom{n}{\lfloor n/2\rfloor}$, the bound achieved when all of the $a_i$ are equal to $1$. and $c=\lfloor n/2 \rfloor $".

Assume without loss of generality that all of your $a_i$ are nonzero (any $a_i$ which equal $0$ don't appear in any of your subsets anyway). Then that upper bound still applies in this case, and is roughly $C2^n/\sqrt{n}$ for large $n$.

For a lower bound, we'll use the following construction: Suppose you have a set $S$ of positive integers such that the sum of all the elements in $S$ is $k$ and you have many subsets summing to $c$. Then we let

$$S'=S \cup {-c} \cup {c-k}.$$

For every subset of $S$ summing to $c$ there is a corresponding subset of $S'$ formed by adding in $-c$. This subset has no smaller subset summing to $0$ because $S$ consisted entirely of positive integers.

What this lower bound gives you depends on how you're counting subsets. For example, if $n$ is even the multiset $$[1,1,\dots,1,-\frac{n}{2}, -\frac{n}{2}]$$ with $n-2$ ones has $2\binom{n-2}{n/2-1}$ submultisets of the form $[1,1,\dots,1, -\frac{n}{2}]$ summing to $0$. For large $n$ this is about a factor of $2$ off from the lower bound.

If you consider these subsets to all be identical, then you can instead start with $S={1,2,\dots,n-2}$. You can check that for large $n$ this set has roughly $C\frac{2^{n-2}}{n^{3/2}}$ subsets summing to the same value for some $C$ (the idea is that if you take a random subset the standard deviation of its sum is only order $n^{3/2}$). So you can start with this as your $S$ and get a lower bound which is roughly $2^n n^{-3/2}$ for large $n$.

Answer by Kevin P. Costello for Does an $n$ dimensional subspace intersect the $n$-facets of the unit cube?

2011-12-07T23:16:08Z

Here's a way of thinking about Igor's answer to the first part:

Consider first a "generic" $n-$dimensional subspace defined by a system of $m-n$ equations. For any particular $n-$facet, being on that facet means you only have $n$ free variables. So if $n< m-n$, there isn't really any hope to satisfy all the equations at once.

Conversely, if you have a subspace satisfying $m-n \leq n$, you can imagine the following process. We will refer to a variable as fixed if its value is equal to $1$ or $-1$, and free otherwise.

We start at the point $v=0$, at which point all variables are free. If at any point there are fewer than $m-n$ free variables, then there must be a $w \neq 0$ in the subspace which is equal to $0$ at all fixed variables (here we're using $m-n \leq n$). We can then replace $v$ by $v+\lambda w$, where $\lambda$ is chosen to be as large as possible subject to the constraint that we still lie in the hypercube. This new vector is still in the subspace, and has (at least) one more fixed variable than before.

Answer by Kevin P. Costello for how to cover a set in a grid with as few rectangles as possible

2011-11-11T22:15:44Z

In general, I don't think you can expect a set to be well approximated by such a small number of rectangles.

Let $S$ be a random set formed by including every square with probability $1/2$. Then with high probability $S$ has $r \geq 0.5-\epsilon$ for any $\epsilon$.

Now consider any (fixed) arbitrary set $T$. The error of $T$ from $S$ can be thought of as the sum of $N^2$ Bernoulli trials, each with probability $1/2$. It follows from the Chernoff bound that for any fixed $\epsilon<1/2$ the probability of having error at most $\epsilon N^2$ is at most $c^{n^2}$ for some constant $c<1$ depending only on $\epsilon$.

On the other hand, there are only $4^N$ rectangles (choose whether or not to include each row and column), so at most $4^{Nk}$ unions of $k$ rectangles. Taking the union bound over all such unions, we see that with high probability $S$ is not approximated by any union of $o(N)$ rectangles.

In general, I have a feeling (though I'm not familiar enough with this area to say for certain) that a better way to explain this all is in terms of information theory/entropy -- Specifying that a set has density $r$ still leaves you with approximately $N^2 H(r)$ (where $H$ is the entropy function) bits of entropy. On the other hand, the union of $k$ rectangles has less than $2kN$ such bits. You can't compress the former into the latter if $k$ is much less than $NH(r)$ without incurring a fair amount of error.

Answer by Kevin P. Costello for Bounds on maximal eigenvalue of a k-regular graph

2011-10-13T22:10:16Z

We'll work with $A$, then translate our results to bounds on $L$ at the end. Suppose the eigenvalues of $A$ are $k=\alpha_1 \geq \dots \geq \alpha_n$. Since $A$ has zero trace, we have $$\alpha_1+\alpha_2+\dots+\alpha_n=0.$$ The sum of the squares of the eigenvalues is equal to $Tr(A^2)$, which counts the number of closed walks of length $2$ on $G$. There are $k$ such walks starting at each vertex, so we have $$\alpha_1^2+\alpha_2^2+\dots+\alpha_n^2=kn.$$ Now by assumption we have that every $\alpha_i$ lies in $[\alpha_n, k]$. It follows from the convexity of $x^2$ that $$kn=\alpha_1^2+\dots+\alpha_n^2 \leq n(p*\alpha_n^2+(1-p)*k^2),$$ where $0\leq p\leq1$ is chosen such that $\alpha_n p + (1-p) k=0=\sum \alpha_i$.

Direct computation gives that $p=\frac{k}{k-\alpha_n}$. Plugging this into the above equation and solving for $\alpha_n$ gives $\alpha_n^2 \geq 1$, so $\alpha_n \leq -1$. Translating back to the Laplacian gives $\lambda_n \geq k+1$ independent of $n$.

This is tight for the case where $G$ consists of the union of disjoint copies of $K_{k+1}$. If you have more information on the structure of $G$, you may be able to get a better bound by translating that into a bound on the number of closed walks of length $3$ or $4$ on $G$ (the sum of $\alpha_i^3$ or $\alpha_i^4$).

An alternative argument which might provide better bounds in some cases is to use interlacing: If $H$ is any induced subgraph of $G$, the minimal (adjacency) eigenvalue of $H$ is at least as large as the minimal (adjacency) eigenvalue of $G$. For example, if $G$ contains a vertex not contained in any triangle, then you can take $H$ to be the $k-$star induced by that vertex and its neighborhood to get a $k+\sqrt{k}$ bound on $\lambda_n$.

Answer by Kevin P. Costello for Existence of a nice subset of edges in $k-$regular simple graphs?

2011-05-12T15:38:29Z

It seems like such a subset should always exist.

Consider the bipartite graph on $2|V(G)|$ vertices corresponding to the adjacency matrix of $G$. Since this graph is regular, by Hall's Theorem it has a perfect matching. In terms of the original $G$, this corresponds to a permutation $\sigma$ on $V(G)$ such that $v$ and $\sigma(v)$ are always adjacent. The cycles of $\sigma$ would then give you the desired decomposition.

Answer by Kevin P. Costello for "sparse graphs are locally tree-like"

2011-02-17T18:16:09Z

I don't believe you can say that "most" graphs in this range have small girth, but there is a sense in which you can say they have few short cycles. For example, if you consider the model of random regular graphs of degree $d$ (graphs chosen uniformly from all $d$ regular graphs on $n$ vertices), and let $X_i$ denote the number of cycles of length $i$, then Bollobás and Wormald independently showed that the $X_i$ behaved asymptotically as independent Poisson variables with mean $(d-1)^i/(2i)$.

In other words: There's a positive probability that a graph contains each of $3$-cycles, $4$-cycles, etc. Because these events are asymptotically independent, "most" $d-$regular graphs have bounded girth. On the other hand, the number of cycles of each fixed length on average remains bounded even as the size of the graph tends to infinity. So if I fix a single vertex and look in the neighborhood of that vertex, I have to look at farther and farther distance before I see any cycles at all. (But not too far...as Louigi noted, we can't expect to go much past the $\log n$ diameter of the graph). This is the "locally" part of "locally tree-like".

A similar situation should hold for Erdős–Rényi graphs like the ones mentioned in Louigi's comment.

Answer by Kevin P. Costello for Spectrum of the Laplacian on G(n, p) and G(n, M)

2010-11-30T19:45:22Z

I'm not sure if there's a way to get it directly from the $G(n,p)$ Laplacian results, but I think it's feasible to get there by way of the adjacency matrix and a coupling argument if $m$ is sufficiently large (say at least $n \log^3 n$). I've sketched an argument which should hopefully work below. The key aspect we use is the following lemma.

Lemma: Let $d_n \rightarrow \infty$, and let $G_n$ be a sequence of graphs whose maximum and minimum degree are both $(1+o(1))d_n$. Then $\lambda_2(G_n) \rightarrow 1$ if and only all eigenvalues of the adjacency matrix of $G_n$ but the largest are $o(d_n)$.

This Lemma should be standard (though I don't have a reference), but is not hard to prove: The idea is that $AD^{-1}$ can be written as $\frac{1}{d_n}A(I-(I-\frac{1}{d_n}D))^{-1},$ and by assumption $I-\frac{1}{d_n}D$ has small spectral norm.

Let $m$ and $p$ be related by $m=p\binom{n}{2}$, and let $H_1$ be a random graph from $G(n,p)$ conditioned on having between $m$ and $m+\sqrt{m}$ edges. Let $H_2$ be a random subgraph of $H_1$ having $m$ edges (note that $H_2$ has uniform distribution on $G(n,m)$). Since $m$ is sufficiently large, $H_2$ satisfies the hypothesis of the lemma. So it suffices to bound the second eigenvalue of $H_2$'s adjacency matrix.

By the results of Chung et al. along with the lemma, the second largest eigenvalue of $H_1$ is $o(m/n)$ (since we're conditioning on an event of positive probability, the results of Chung still hold even after conditioning). We're therefore done if we show that the spectral norm of $H_1-H_2$ is also almost surely $o(m/n)$.

For any $1 \leq k \leq \sqrt{m}$, the distribution of $H_1-H_2$ conditioned on $k$ edges being removed is the same as that of $G(n,k)$. We can bound the spectral norm of $G(n,k)$ by its maximum degree (whose distribution should also be well-known, though again I don't have a reference), at which point we may as well take $k=\sqrt{m}$. Using the negative correlation between edges in $G(n,k)$, we see that the probability a vertex has degree at least $d$ is at most $$n \binom{n}{d} \left(\frac{2k}{n^2}\right)^{d} \leq n \left(\frac{2e\sqrt{m}}{dn}\right)^d$$ which tends to $0$ for $d=\frac{m}{n \log n}$ (recall that by assumption $d \geq \log^2 n$).

Answer by Kevin P. Costello for Best lower bound for off-diagonal Ramsey numbers

2010-11-08T14:55:41Z

The best bounds I know of are due to Tom Bohman for $R(k,4)$ and Bohman and Peter Keevash for $R(k,5)$ and beyond. Both rely on using the differential equations method to analyze the following process: Start with the empty graph, and at each step add an edge uniformly at random among all edges which do not create a $K_t$. The bounds they achieve are $$R(k,t) \geq c_t \left( \frac{k}{\log k} \right)^{\frac{t+1}{2}} (\log k)^{\frac{1}{t-2}}$$

The final term in this product corresponds to the improvement over the bounds obtained using the Local Lemma. For $t=3$ it matches Kim's bound up to a constant factor.

Answer by Kevin P. Costello for What are some good examples of non-monotone graph properties?

2010-09-28T01:37:22Z

The property of having a non-singular adjacency matrix is non-monotone. For example, the path on four vertices has a full-rank adjacency matrix, but closing the path into a cycle reduces the rank by $2$ (the two pairs of opposite vertices correspond to equal rows in the adjacency matrix). Conversely, closing the path on three vertices into a triangle converts a singular adjacency matrix into a non-singular one.

This does turn out to have a sharp threshold though, as I showed with Van Vu. The situation is similar to that for the graph becoming connected: The property fails automatically when the graph has isolated vertices, and this turns out to be the main obstruction. The graph becomes connected/the matrix becomes non-singular at $\frac{\log n}{n}$.

A curious consequence of the non-monotonicity here is that there's also (likely) a sharp threshold at the other end of the spectrum. For $p$ exceptionally close to $1$, pairs of equal rows start cropping up again in the adjacency matrix (e.g. when the complement of $G$ contains an isolated edge). However, we don't know whether that's the main source of dependency in this range or if the threshold occurs sooner.

Answer by Kevin P. Costello for Number of invertible {0,1} real matrices?

2010-03-18T22:49:07Z

As Michael noted, the conjectured bound for the probability a random $(0,1)$ matrix is singular is conjectured to be $(1+o(1)) n^2 2^{-n} $. This corresponds to the natural lower bound coming from the observation that if a matrix has two equal rows or columns it is automatically singular.

The best bound currently known for this problem is $(\frac{1}{\sqrt{2}} + o(1) )^n$, and is due to Bourgain, Vu, and Wood. Corollary 3.3 in their paper also gives a bound of $(\frac{1}{\sqrt{q}}+o(1))^n$ in the case where entries are uniformly chosen from ${0, 1, \dots, q-1}$ (here the conjectured bound would be around $n^2 q^{-n})$

Even showing that the determinant is almost surely non-zero is not easy (this was first proven by Komlos in 1967, and the reference is given in Michael's Sloane link).

Answer by Kevin P. Costello for The middle eigenvalues of an undirected graph

2010-03-15T17:28:16Z

If you assume the graph is bipartite (as Cam suggested) and $3-$regular, then I believe the middle eigenvalues are always at most $\sqrt{2}$ in absolute value, with the Heawood graph being the only connected graph with equality.

We know that for any positive integer $k$ the number of closed walks on your graph of length $k$ is equal to $Tr(A^k)=\sum_i \lambda_i^k$. In the case $k=2$, this becomes $$\sum_{i=1}^n \lambda_i^2 = 2 |E| = 3 n,$$ while for $k=4$ we have $$\sum_{i=1}^n \lambda_i^4 \geq 15 n,$$ since there are $9n$ closed walks of the form $x \rightarrow y \rightarrow x \rightarrow z \rightarrow x$ (here $y$ possibly can equal $z$), and $6n$ walks of the form $x \rightarrow y \rightarrow z \rightarrow y \rightarrow x$ where $z \neq x$.

Now suppose that $\lambda_i^2 \in [t, 9]$ for every $i$. It follows from convexity that, subject to the constraint $\sum \lambda_i^2=3n$, the sum of $\lambda_i^4$ is maximized when every $\lambda_i^2$ is either $t$ or $9$, that is to say $$\sum_{i=1}^n \lambda_i^4 \leq (\frac{3-t}{9-t} n) (81) + (\frac{6}{9-t} n) (t^2)=(27-6t)n.$$

Comparing with our lower bound, we see $t \leq 2$. Equality can only hold when there are exactly $n/7$ eigenvalues equal to $3$ in absolute value, and the rest equal to $\sqrt{2}$ in absolute value. This is the spectrum of $n/14$ disjoint copies of the Heawood graph, which is uniquely determined by its spectrum.

It feels like there should be a way of saying that large connected graphs have an eigenvalue much smaller than this, but I don't see how to modify this method to show that (I'm not sure how the connectedness of the graph would show up in path counting). If your graph has many $4$ cycles, you can include them in the $k=4$ lower bound to get a better bound on $t$.

Answer by Kevin P. Costello for Random Alternating Permutations

2010-02-10T06:53:07Z

One observation is that (as mentioned in Stanley's Survey ), the Alternating Permutations satisfy a recurrence $$E_{n+1}=\sum_{\textrm{odd } j \leq n}^n \binom{n}{j} E_j E_{n-j}$$ Here $j$ on the right hand side corresponds to the number of elements appearing before $1$ in the permutation.

This is probably not be the most efficient way, but it seems like you could compute $E_k$ for all $k$ up to $n$ and then build up your permutation recursively by successively choosing where the smallest element goes and dividing the remaining variables into two alternating permutations of the appropriate size based on that.

When does a pointwise CLT hold?

2009-11-16T20:09:22Z

Let $X$ be a random variable with mean $0$ and variance $1$, and let $X_1, X_2, X_3, \dots$ be iid copies of $X$. Under what conditions can we say that the density of $\frac{X_1+\dots+X_n}{\sqrt{n}}$ converges pointwise to $N(0,1)$?

In particular, when can I say that for any sequence $\epsilon_n \rightarrow 0$ we have $$\frac{P(|\frac{X_1+\dots+X_n}{\sqrt{n}}|<\epsilon_n)-P(|N(0,1)|<\epsilon_n)}{\epsilon_n} \rightarrow 0?$$

In flavor this is somewhat similar to what I've seen termed as "local limit theorems", except a little bit stronger; for example if $X$ is a Bernoulli variable the above would not hold (take $\epsilon_n=2^{-n}$). My guess would be that a sufficient condition would be for the usual CLT to hold and $X$ to have bounded density functions, though I haven't seen this cited anywhere.

Comment by Kevin P. Costello

2013-04-27T20:31:56Z

The limit must exist because the expected edit distance is subadditive (we can always edit a string of length $m+n$ by editing each part separately).

Comment by Kevin P. Costello

2013-03-21T21:35:09Z

Do you have any examples in the way of lower bounds?

Comment by Kevin P. Costello

2013-03-21T19:03:45Z

Am I missing something at the end here? It seems like you have $||F||_2^2 \leq \frac{k \epsilon}{k-1}$, not $||F||_2$.

Comment by Kevin P. Costello

2013-03-15T20:50:15Z

If all you care about is showing that the expected distance is less than $1$ for $N=2$, I believe you can dodge most of the computation using by using Jensen's inequality to bound $[E(d)]^2≤E(d^2)=2E((x_1−x_2)^2)=\frac{1}{3}$.

Comment by Kevin P. Costello

2013-03-06T00:35:05Z

In terms of the name, an "intersection graph" is a more general term for a graph formed on a collection of subsets by connecting two subsets if they have non-empty intersection. I'm not sure if there's a special name for the graph in the case where $S$ is all the non-empty subsets of $F$.

Comment by Kevin P. Costello

2013-02-27T22:06:27Z

Shiri Artstein's "Proportional Concentration Phenomena on the Sphere" (tau.ac.il/~shiri/israelj/ISRAJ.pdf ) might be relevant for the geometric interpretation.

Comment by Kevin P. Costello

2013-01-26T01:02:14Z

It only works here if you happen to pick the right vertex of lowest degree to start with -- if you start by picking $5$, you'll only end up with a set of size $3$.

Comment by Kevin P. Costello

2013-01-25T20:22:47Z

The second half of my comment was only referring to the case $n=4$. In that case conditioned on the graph having $5$ (or $6$) edges, there's only one possible graph up to isomorphism. That graph either has exactly half the spanning trees of each type (for $5$ edges), or all of them (for $6$ edges), so the spanning trees appear in the right proportions (one way of thinking about this -- for any $k$ each tree appears in the same number of $k$ edge graphs. If each $k$ edge graph has the same number of spanning trees, that means each tree appears with the same probability given there's $k$ edges

Comment by Kevin P. Costello

2013-01-25T05:55:00Z

Then there's a $1/5$ chance that $G$ is a $4-$cycle (in which case all four spanning trees are paths), and a $4/5$ chance that $G$ is a triangle with one edge added (in which case there are only three spanning trees, one star and two paths). Combining, each of the $12$ paths has a $11/180$ chance of being chosen, while each of the $4$ stars has a $1/15=12/180$ chance.

Comment by Kevin P. Costello

2013-01-25T05:52:04Z

I don't see why each labelled tree is equally likely. Although each tree is a spanning tree for an equal number of graphs, trees which tend to be spanning trees for graphs with fewer spanning trees in total will be more likely to be chosen. Consider for example the case where $n=4$. If we condition on the graph having $3$ edges, all trees are equally likely. The same holds true if we condition on $G$ having $5$ or $6$ edges. But suppose we condition on $G$ having $4$ edges (continued in next comment).

Comment by Kevin P. Costello

2013-01-16T20:27:13Z

Perfect proved a similar result for $\pm 1$ matrices in his "Positive Diagonals of $\pm 1$ Matrices" (he mentions the connection to the permanent in the concluding remarks to his paper). I don't know if his proof carries over or not, but it may be worth looking at.

Comment by Kevin P. Costello

2013-01-10T20:48:31Z

One strange corollary of this: Imagine exposing your matrix minor by minor (so that after step $k$ the $k \times k$ upper left submatrix is exposed). By Sylvester's criterion, $M$ is positive definite iff the determinants of each exposed submatrix are positive. So what this is saying is that the probability the $n^{th}$ determinant is positive, conditioned on the previous determinants being positive, decays exponentially in $n$. I find this counterintuitive, especially given that individual entries have symmetric distribution.

Comment by Kevin P. Costello

2013-01-07T23:01:46Z

A version of this question is also discussed at mathoverflow.net/questions/87923/… (the Thue-Morse sequence mentioned in the original question there corresponds to Stefan's answer). Raff and Zeilberger's "Finite Analogs of Szemeredi's Theorem" (math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/… ) might also be of interest.

Comment by Kevin P. Costello

2012-12-11T00:54:18Z

By "this inequality is independent of the other events $B_i$", do you mean that for any disjoint $S$ and $T$ and any $i \notin S \cup T$ that $$P(B_i \vert B_j \textrm { holds for all } j \in S \textrm{ but does not hold for any } j \in T) \leq x ?$$

Comment by Kevin P. Costello

2012-11-30T22:32:43Z

An alternative viewpoint as to why the bound here is essentially tight: A random set $A$ will have size at least $(\frac{1}{2}+t)N$ with probability at least $\exp(-c_0 t^2 N)$ for some $c_0$. Whenever this happens, the energy is likely to increase by a constant factor as well.