User louigi addario-berry - MathOverflow

Answer by Louigi Addario-Berry for Number of Geodesic Paths Passing Through a Vertex in an Expander Graph

2012-02-19T01:58:59Z

My short answer: I think not much is known. But: here is the state of the art on related problems, as far as I am aware.

Aldous and Bhamidi consider the following model. Place independent exponential edge weights on the edges of the complete graph $K_n$; we view the weights as edge lengths. Then, for each pair $u,v$ of vertices, place a constant flow between them on the shortest path from $u$ to $v$. For each edge $e$, write $F_n(e)$ for the total flow along edge $e$ in the resulting network. Then for each fixed $z > 0$, as $n \to \infty$, \[ \frac{1}{n} \#\{e: F_n(e) > z\log n\} \to \int_0^{\infty}\mathbb{P}(W_1W_2e^{-u} > z)~du, \] where $W_1$ and $W_2$ are independent exponentials. (In fact, the paper proves a more detailed distributional convergence result.) In particular, typical edge congestion is $O(\log n)$; but the paper does not address maximum edge congestion. The paper also addresses vertex congestion (more directly linked to your question), showing a similar convergence result but with a more complicated term on the right-hand side of the convergence. As in the edge case, however, maximum vertex congestion is not treated, only typical congestion.

What follows is less relevant as it relates to global strategies for minimizing congestion, rather than greedy routing between nodes. I'm posting it anyway in case it's useful.

Alan Frieze has a survey on disjoint paths in expander graphs which may be of interest. Theorems 4 and 5 of that survey are results of Broder, Frieze and Upfal, which imply that in an expander, any set of at most $c n/\log^2 n$ pairs of vertices can be connected by disjoint paths, and that every pair can be connected by a path in such a way that the total congestion is $O(n \log n)$.

Finally, for a particular class of random expanders, something can be said about a fractional version (flows rather than paths; again, this allows global optimization). Given a connected, undirected graph $G=(V,E)$, a uniform flow of volume $\phi$ on $G$ is a collection $F$ of flows, one for each ordered pair $(v,w)$ of vertices of $G$, each having volume $\phi$. Given $f \in F$ and $e \in E$, write $f(e)$ for the flow through edge $e$ in $f$ (ignore direction so this is always non-negative). Then write \[ \chi(F)=\max_{e \in E} \sum_{f \in F} f(e) \] for the maximum flow across any edge of $G$, when all flows of $F$ are simultaneously active

Aldous, Mcdiarmid, and Scott have proved the following. Fix a non-negative random variable $C$ with $\mathbb{E}(C) < \infty$, and take G_n to be the complete graph $K_n$ each of whose edges $e$ is weighted with an independent copy $C_e$ of $C$. Let $\phi_n$ be the largest value such that there exists a uniform flow $F$ of volume $\phi_n$ on $G$ such that \[ \sum_{f \in F} f(e) \le C_e \] for all $e \in E(K_n)$. Then there is a positive constant $\phi_*$ such that $\phi_n \to \phi_*$ in probability.

Note that if $C$ takes some fixed value $M$ with probability $p$, and is $0$ with probability $1-p$, this is equivalent to requiring maximum congestion $\le M$ on the random graph $G_{n,p}$. Thus, this setting includes (edge) congestion-type bounds on at least some expander-like graphs.

Answer by Louigi Addario-Berry for Cover time and intersection time of random walks

2012-05-23T11:00:45Z

In Proposition 5 of Chapter 14 of the unpublished book on Markov chains by Aldous and Fill, they show that for continuous time reversible Markov chains, \[ I \le \max\{ \mathbb{E}_i T_j, i,j \in V\}, \] where $\mathbb{E}_i T_j$ is the expected time, starting from state i, until state j is visited. The preceding maximum is clearly bounded from above by $C$, so it follows that $I \le C$. This includes the case of continuous time simple random walk on a connected graph $G$, and a similar argument can be used to to establish the bound for lazy simple random walk on $G$ (in fact, the martingale argument used in the proof is originally described in Chapter 3 of the same book for the case of discrete time walks).

Answer by Louigi Addario-Berry for Does graph asymmetry imply all eigenvalues of the graph Laplacian are simple?

2012-02-21T15:04:11Z

Take two asymmetric $d$-regular graphs $H_1,H_2$, and let $G$ be their disjoint union. Then $d$ will be a repeated eigenvalue.

If you want $G$ connected, take the complement of the graph obtained by the above construction. Graph complements preserve asymmetry and repeated eigenvalues.

Answer by Louigi Addario-Berry for Asymptotic Geodesic Flow on Planar Graphs

2012-02-20T00:51:23Z

You can't do better. Lipton and Tarjan's planar separator theorem says that any $n$-node planar graph $G=(V,E)$ contains a set $S$ of $O(\sqrt{n})$ vertices whose removal separates the graph into components all of which have size at most $2n/3$. We can then partition $V \setminus S$ into sets $X,Y$ each containing at least $(1/3-o(1))n$ vertices; there are order $n^2$ pairs $(u,v) \in X \times Y$, and any path between such a pair $(u,v)$ contains a vertex of $S$. Since $|S|=O(\sqrt{n})$, by the pigeonhole principle it follows that some element of $S$ is in order $n^{3/2}$ paths. between $X$ and $Y$.

Answer by Louigi Addario-Berry for The critical value of percolation on Cayley graphs.

2012-02-09T02:52:14Z

In a paper called Critical Percolation on any Nonamenable Group Has no Infinite Clusters, Benjamini, Lyons, Peres, and Schramm show that ... critical percolation on any nonamenable group has no infinite clusters.

More precisely, if $G$ is a Cayley of any finitely generated non-amenable group, then $\theta(p_c)=0$. This immediately implies that $p_c(G) < 1$.

The paper also shows that for any invariant bond percolation $P$ on $G$ (invariant means its distribution is unchanged by the action of the group), if in $P$ the expected number of neighbours of the origin $o$ is at least \[ d_G(o) - \kappa(G), \] then with probability one there is percolation. (Here $d_G(o)$ is the number of neighbours of the origin in $G$, and $\kappa(G)$ is the Cheeger constant of $G$, which is positive since the group is non-amenable.) This gives that \[ p_c(G) \le 1-\kappa(G)/d_G(o), \] which is weaker than the bound in Vincent Beffara and Asaf Nachmias' answers, but applies to a broader range of percolation models.

Answer by Louigi Addario-Berry for Distribution of big component of set partitions

2012-01-09T17:18:22Z

I haven't managed to find the answer to precisely your question but here are a couple of references that might be useful.

Vershik and Yakubovich have a paper on The limit shape and fluctuations of random partitions of naturals with a fixed number of summands. It addresses partitions of $n$ with around $\sqrt{n}$ summands, but doesn't seem to have exactly the result you're asking about.

If you haven't already looked at it, Chapter 1 of Pitman's Combinatorial stochastic processes seems quite relevant to your question. In particular he states something which he calls "Kolchin's representation of Gibbs partitions". For the special case of uniformly random partitions, this can be stated as follows, I think. Fix a positive parameter $\xi$ and let $X_1,X_2,\ldots$ be iid with distribution Poisson$(\xi)$ (Added on edit: the $X_i$ should be conditioned to be strictly positive). Also, let $K$ be Poisson$(e^{\xi}-1)$ and independent of the $X_i$.

Then for any $n$, conditional on the event that $X_1+\ldots+X_K=n$, the vector $(X_1,\ldots,X_K)$ is distributed as the vector of sizes of the parts of a uniformly random partition of $\{1,\ldots,n\}$ , listed in exchangeable random order.

You could then try conditioning both on $X_1+\ldots+X_K=n$ and on $K=k$, and playing with the parameter $\xi$, to read off information about partitions of $\{1,\ldots,n\}$ into $k$ parts.

Answer by Louigi Addario-Berry for Length of the last edge when visiting points by nearest neighbor order

2011-11-01T08:09:26Z

This is closely related to a nice open problem of David Aldous, from the list of open problems on his web site, some version of which in fact has quite a long history in the combinatorial optimization community. At the above link Aldous has references to existing knowledge about the problem. The state of the art is that the sum of all edge lengths is $O(n^{1/2})$ in expectation.

Answer by Louigi Addario-Berry for Did Joseph Doob prove that random sequences don't exist?

2011-07-09T13:39:20Z

There is an excellent article by Sérgio B. Volchan in the American Mathematical Monthly, titled What Is a Random Sequence, which discusses how the von Mises-Wald-Church model of randomness is unsatisfactory. He goes on to explain the proposed candidate for a definition of a random sequence due to Martin-Löf, that of typicality, or "randomness with respect to effective statistical tests". Here randomness is defined with respect to a given measure $\mu$ on infinite binary strings; it turns out to coincide with a natural notion of incompressibility of the sequence.

Anyway, in short: there are other natural candidates for what it should mean for a sequence to be random, that turn out to work pretty well (and are beautiful), and Volchan's paper is a good place to learn about them.

Counting subtrees of a random tree ("random Catalan numbers")

2011-05-31T21:57:34Z

Given a rooted tree $T$ and an integer $k \geq 1$, let $N_k(T)$ be the number of subtrees of $T$ containing the root and having exactly $k$ nodes (take $N_k(T)=0$ if $T$ has less than $k$ nodes).

Next, fix an integer $d \geq 2$, and let $T_d$ be the infinite $d$-ary rooted tree (every node has $d$ children). It is well-known (see, e.g. Stanley's enumerative combinatorics, Thm 5.3.10) that \[ N_k(T_d) = \frac{1}{k}{dk \choose k-1} < (ed)^{k-1}. \] When $d=2$, these are simply the Catalan numbers.

Now suppose that $\mathcal{T}$ is a Galton--Watson tree with offspring distribution $B$ and $\mathbb{E}(B)=\mu \in (1,\infty)$.

What can be said about the behavior of $N_k(\mathcal{T})$, either in probability or in expectation, when the branching distribution $B$ may be unbounded?

In particular, it seems likely that under suitable assumptions on $B$, $N_k$ again grows exponentially in $k$. Is it the case, for example, that $N_k/(2e\mu)^{k-1} \to 0$ in expectation (or in probability), perhaps assuming that $B$ has sufficiently large exponential moments?

Perhaps the problem is more combinatorially tractable if one assumes that $B$ has a Poisson distribution? This special case is interesting to me.

Answer by Louigi Addario-Berry for Properties of Some Random Graphs

2011-04-02T19:07:24Z

Yes, this model has been studied. You should look at Chapter 9 of Janson, Luczak and Rucinski's Random Graphs book, and in particular at Corollary 9.44. This corollary is in fact a rather well-known theorem, which I'll now explain.

Let $H_n(d)$ be the distribution you describe (Edit: more accurately, $H_n(d)$ is the distribution of the union of $d$ independent and uniformly random cycles, conditioned on the result being a simple graph), and let $G_n(2d)$ be the distribution of a uniformly random $2d$-regular (all nodes having degree exactly $2d$) simple graph. Then Corollary 9.44 states that for any fixed $d$, $H_n(d)$ and $G_n(2d)$ are contiguous, which means that for any graph property $A$, \[ \mathbb{P}(H_n(d) \in A) \to 1~\mbox{as}~n\to\infty \] if and only if \[ \mathbb{P}(G_n(2d) \in A) \to 1~\mbox{as}~n\to\infty. \] In other words, if you are only interested in studying whether things hold asymptotically almost surely, these two models are equivalent.

In particular, its isoperimetric constant is $(1/2+o(1)) d$, its diameter is $(1+o(1)) \log_{d-1} (n)$, and all eigenvalues except for the largest are $\sqrt{2(d-1)}+o(1)$.

Answer by Louigi Addario-Berry for Coin flipping and a recurrence relation

2011-02-16T16:30:48Z

I think you can get the precise value (well, within an additive error of one) by a sort of limiting argument. Rather than a sequence of coins, for each $i=1,\ldots,n$ let $P_i$ be a Poisson process with rate $\ln(2)$ so that the probability there is at least one point in an interval of length $1$ is $1-e^{-\ln(2)} = 1/2$. Now let $T$ be the first time $t$ that in each of the Poisson processes, at least one point has fallen. then $\lceil T \rceil$ has the same distribution as the time you are looking for.

Furthermore, $T$ is distributed as the maximum of $n$ exponential random variables with mean $1/\ln(2)$, or in other words as $1/\ln(2)$ times the maximum of $n$ standard exponentials. Next, note that you can find such a maximum by first considering the minimum, which is exponentially distributed with mean $1/n$, then considering the maximum remaining time for the remaining $n-1$ exponentials and using the memoryless property. It follows that $T$ is distributed as a sum $E_1+\ldots+E_n$, where the $E_i$ are independent and $E_i$ has mean $1/i$.

It follows that $T$ is has mean $H_n/\ln 2$, and so $f(n) = \mathbb{E}(\lceil T\rceil)$ has mean in $[H_n/\ln(2),H_n/\ln(2)+1]$.

Answer by Louigi Addario-Berry for Random permutations of Z_n

2011-02-02T15:26:32Z

I emailed Noga to ask him; here is his response (touched up slightly for MO; any errors in what I post are probably mine rather than Noga's). The only details not present are the required applications of Stirling's formula.

As far as I recall the argument I had in mind was as follows (I am not trying to optimize the error term). Let $k$ be an even integer, much smaller than $n$ but much bigger than $\log n$, I guess $k=n^{0.01}$ or so should be ok. Split the set of vertices $[n]$ of the cyclic tournament to $k$ blocks of consecutive vertices, each of size $n/k$. Call the blocks $B_1,..,B_k$. We will count only Hamilton cycles in the tournament in which all edges go between distinct blocks, say from $B_i$ to $B_j$, with $j \lt i+k/2$ for each such edge, and with exactly $n/(k(k-2)/2)$ edges between each such pair of blocks.

To count those you use the so called BEST theorem to count the number of Euler circuits in the digraph on the $k$ vertices $B_1,\ldots,B_k$ with $n/(k(k-2)/2)$ directed edges from $B_i$ to $B_j$ for $i \neq j$, $j\lt i+(k-2)/2$ (and divide by $([n/(k(k-2)/2)]!)^{n/(k(k-2)/2)}$ to make sure all edges from B_i to B_j are considered the same.)

In the BEST theorem ignore the determinant corresponding to the number of arborecences, which is not needed here (we are anyway only proving a lower bound) and is negligible. This gives $[(n/k-1)!]^{k}$ divided by the term above. Now this has to be multiplied by $[(n/k)!]^k$, because inside each block B_i we can decide on the order in which we take the $n/k$ vertices (we enter the block represented by a vertex $(n/k)$ times, so we can decide which vertex we enter in each such step). Now take the resulting product, use Stirling and choose the optimal $k$: this should give the claim (not sure with which error term). It may well be that some stronger lower bounds are known, and in fact I think that a similar bound holds for any regular tournament (I believe there is a paper by Bill Cuckler about that in CPC 2007). Hope this makes sense, please feel free to mention whatever you see fit in Mathoverflow.

Answer by Louigi Addario-Berry for Differences of near diagonal Ramsey numbers.

2010-10-20T13:02:06Z

Edit: Erdős got three things wrong. First of all, it wasn't Faudree, Shelp, and Rousseau, it was Faudree, Shelp, and Burr. Second, it wasn't "recently", it was in the future (with respect to the quote you provide)! Third, they didn't prove that $(R(n+1,n)-R(n,n))/n \to \infty$, but only that $R(n+1,n)-R(n,n) \geq 2n-3$.

The relevant paper is On the difference between consecutive Ramsey Numbers, published in 1989. The proof is not long. On a (somewhat cursory) search I wasn't able to find any papers citing this one that address the same question, so it seems likely that this bound is still the best known.

Old answer.

For your first question: thanks to Miklos Simonovits and others, all of Erdős' papers are available from this site. I scanned through the papers by Erdős, Faudree, Rousseau and Schelp from up to 1982 but didn't see such a result. There are 12 papers with precisely these four coauthors, and another several that also have Burr as a coauthor, so it may take some time to find (especially if it isn't explicitly stated as a lemma but is embedded in a proof somewhere). But: if they published it, then you'll be able to find your result by scanning through the papers on that site.

Answer by Louigi Addario-Berry for Proving that every graph is an induced subgraph of an r-regular graph

2011-01-18T03:12:18Z

Use induction on $r-\delta$, where $\delta=\delta(G)$ is the smallest degree of any vertex in $G$.

If $r-\delta=0$, then you are done.

If $r-\delta > 0$ then create two disjoint copies of $G$, say $G_1$ and $G_2$. For any vertex $v$ in $G$ of degree less than $r$, add an edge between the corresponding vertices $v_1$ in $G_1$, $v_2$ in $G_2$. Call the resulting graph $G'$. Then $G'$ contains $G$ as an induced subgraph, and $r-\delta(G')=r-\delta(G)-1$.

Has the technique of "sprinkling" been used in studying random matrices?

2011-01-10T18:13:05Z

In 1982, while studying the component sizes of random subgraphs of a hypercube, Ajtai, Komlós, and Szemerédi introduced a technique that came to be known as sprinkling. In this technique, the edges of the random graph are exposed in rounds. To explain it, suppose that each edge $e$ is independently assigned a random Uniform$[0,1]$ variable $U_e$. Eventually, all edges with $U_e \leq p$ will be included in the graph. In the first round, however, for some subset of the edges, we only check whether $U_e \leq p-\epsilon$. In the second round, for the remaining edges for which we know $U_e > p-\epsilon$, we check whether $U_e \leq p$. (The last few edges are the ones being "sprinkled" on at the end.) The idea is that this additional, last-minute randomization can be used to ensure (or at least make it very likely) that some desirable graph property holds. A similar technique has also been used by percolation theorists.

Has the technique of sprinkling been used in the study of random Bernoulli matrices? Can you give me references?

Answer by Louigi Addario-Berry for Cutting convex sets

2010-12-03T17:31:29Z

There is a generalization of this question, where "area" and "circumference" are replaced by arbitrary "nice" measures (for the purpose of this answer, say absolutely continuous measures) $\mu$ and $\nu$ on $\mathbb{R}^2$. Bárány and Matoušek have a nice paper on the subject.

Even more generally, fix nice probability measures $\mu_1,\ldots,\mu_i$ on $\mathbb{R}^2$. A $k$-fan in $\mathbb{R}^2$ consists of $k$ rays (semi-infinite lines) $r_1,\ldots,r_k$ emanating from a point, listed in some clockwise order. (In fact $k$-fans are also allowed to emanate from the point at infinity, i.e., a set of $k$ parallel lines is considered to be a $k$-fan.) Write $C_k$ for the region proceeding $r_k$ in the clockwise order.

Given a vector $\alpha=(\alpha_1,\ldots,\alpha_k)$ with non-negative entries summing to one, say that $\mu_1,\ldots,\mu_r$ can be simultaneously $\alpha$-partitioned if there exists a $k$-fan such that $\mu_i(C_j)=\alpha_j$ for each $i=1,\ldots,r$ and $j=1,\ldots,k$. (If $\alpha_1=\ldots=\alpha_k=1/k$ say that the measures can be simultaneously equipartitioned. This case, with $k=2$, is closest to the original )

Bárány and Matoušek have a whole host of results about when such partitions exist and do not exist. Here are just a couple:

For any $k \geq 5$ and any $\alpha$, there are two measures that can not be simultaneously $\alpha$-partitioned.
For any $\alpha=(\alpha_1,\alpha_2)$, any two measures can be simultaneously $\alpha$-partitioned, even if the center of the fan is specified in advance.

~~No one knows, for example, if any two measures can be simultaneously equipartitioned into four parts.~~ Karasev seems to have a paper where he proves that any two measures can be simultaneously equipartitioned into $q$ convex parts, whenever the number of parts is a prime power. (This was first achieved for three parts -- this is the result by Bárány et al that Joseph O'Rourke mentioned.) I am unclear on the relation between this and the result of Hubard and Aronov, mentioned by Joseph O'Rourke in his answer.

Higher-dimensional versions have also been considered but much is open. For example, for any three measures in $\mathbb{R}^3$ can one always find a convex $3$-partition of space so that each measure has measure $1/3$ on each part? (I heard Bárány say in a seminar that the version with $3$ replaced by a power of $2$, is known to be true; but I didn't note down a reference.)

Answer by Louigi Addario-Berry for $E(X_1 | X_1 + X_2)$, where $X_i$ are (integrable) independent infinitely divisible rv's "of the same type"

2010-11-24T16:41:17Z

I think the right way to phrase this discussion is as follows. Let $(X_s)_{0 \leq s \leq t}$ be a real stochastic process with cyclically exchangeable increments: for all $u \in [0,t]$, the process $(X'_s)_{0\leq s \leq t}$ obtained by a cyclic shift by $u$, has the same distribution as the original process.

Suppose that $X_0=X_t=0$ with probability one. Then for all $s$, $\mathbb{E}(X_s)=0$. (As in Ori's argument, for this step a continuity argument is needed, which you may not like. On the other hand, this kind of continuity argument is bog-standard -- it is a basic procedure when you study infinitely divisible distributions via their characteristic functions.)

Edit: Here is an argument to replace the continuity argument but which requires an additional assumption. Suppose for simplicity that $t=1$. The additional assumption is that $\sup_{s \in (0,1)} |\mathbb{E}(X_s)| < \infty$. Suppose there is $s$ s.t. $\mathbb{E}(X_s) = z > 0$. Then by cyclic exchangeability, $\mathbb{E}(X_{1-s}) = -z$. Again by cyclic exchangeability, $|\mathbb{E}(X_{|2s-1|})| = 2z$, the sign depending on the sign of $2s-1$.

By repeating this argument, it follows that if there is any point $s$ with $\mathbb{E}(X_s) \neq 0$ then there are points $s$ for which $|\mathbb{E}(X_s)|$ is arbitrarily large. In fact, since by cyclic exchangeability, $\mathbb{E}(X_{s/n})=\mathbb{E}(X_s)/n$, it then follows that there are points arbitrarily close to zero for which $|\mathbb{E}(X_s)|$ is arbitrarily large.

Edit: (This is an expansion of the argument I sketched in the comments.) Note that for any stochastic proces $(X_t)=(X_t)_{0 \leq t \leq 1}$ if $U$ is a uniform $[0,1]$ random variable, independent of $(X_t)$, then the process $(X_t')$ obtained from $(X_t)$ by cyclically shifting $(X_t)$ by $U$, has cyclically exchangeable increments. Furthermore, if $(X_t)$ itself has cyclically exchangeable increments, then $(X_t)$ and $(X_t')$ have the same distribution.

Now let $(Z_s)=(Z_s)_{0 \leq s \leq 1}$ be a Lévy process. Let $U$ be uniform on $[0,1]$ and independent of $(Z_s)$, and let $(Y_s)=(Y_s)_{0 \leq s \leq 1}$ be the process you get by cyclically shifting $(Z_s)$ by U. Then $Y_1=Z_1$, and $(Y_s)$ has the same distribution as $(Z_s)$.

Conditional upon $Z_1$ (which equals $Y_1$), we don't automatically know the distribution of $(Z_s)$. However, we know the following facts.

Conditional on $Z_1$, $(Y_s)$ is distributed as a uniformly random cyclic shift of the conditioned process $(Z_s)$ (conditioned on $Z_1$), so still has has cyclically exchangeable increments.
Since $Z_1=Y_1$, $(Y_s)$ conditioned on $Z_1$ is the same as $(Y_s)$ conditioned on $Y_1$. But $(Y_s)$ and $(Z_s)$ have the same distribution so $(Y_s)$ conditioned on $Y_1$ is distributed as $(Z_s)$ conditioned on $Z_1$.

Putting these facts together, we see that conditional on $Z_1$, $(Z_s)$ still has cyclically exchangeable increments, and thus (still conditional on $Z_1$) $(Z_s - sZ_1)$ does as well. But then $(Z_s - sZ_1)$ is a process with c.e. increments and equal to zero at $s=0$, $s=1$. By the first three paragraphs of my answer, it follows that if $\sup_{0 \leq s \leq 1} |\mathbb{E}(Z_s -sZ_1 | Z_1)|$ is almost surely finite, then almost surely $\mathbb{E}(Z_s|Z_1)=sZ_1$.

But $\mathbb{E}(Z_s -sZ_1 | Z_1) = \mathbb{E}(Z_s|Z_1)+sZ_1$ so the requirement boils down to $\sup_{0 \leq s \leq 1} |\mathbb{E}(Z_s|Z_1)|$ almost surely finite. Using the tower law, this holds as long as $\mathbb{E}(\sup_{0 \leq s \leq 1} |Z_s|)$ is almost surely finite. I think this is equivalent to requiring that $\mathbb{E}|Z_1| < \infty$ but I still haven't checked.

Are Penrose tilings universal? Do aperiodic universal tilings exist?

2010-11-23T18:47:57Z

Consider a tiling of the plane using tiles of at least two types (e.g, a Penrose tiling such as that shown at the bottom of this question, which tiles the plane with two types of tiles). List the tile types as $t_1,\ldots,t_k$. Say that an {\em animal} using tiles $t_1,\ldots,t_k$ is a connected subset of the plane that can be obtained by gluing a finite number of tiles together along their edges; identify congruent subsets. If there is only one type, this is often called a polyomino; here are some pictures of polyominoes in the square lattice (which has only one type of tile and is not in fact an interesting lattice from the point of view of this question).

Say that a tiling of the plane using (distinct) tiles $t_1,\ldots,t_k$ is universal if it contains every possible lattice animal using tiles $t_1,\ldots,t_k$. To explain what I mean by "possible", suppose that $k=2$, that $t_1$ is the "thin diamond" from the Penrose tiling and that $t_2$ is the "thick diamond. By gluing together four copies of $t_1$ one can obtain the following "animal".

This animal can't be contained within any tiling (Penrose or otherwise) using $t_1$ and $t_2$. So it makes sense to restrict to animals which, for example, are contained within some tiling of the plane with the given tiles.

My question is: are there $k \geq 2$ for which (aperiodic -- adjective added in edit) universal tilings exist?

Edit: when I first posted the question I omitted the adjective aperiodic above. As pointed out in comments, in this case the answer is obviously yes, which is good to have had pointed out.

We can also restrict the allowed animals. For example, we could restrict to animals which exhibit some form of symmetry.

One could then ask: do aperiodic tilings exist which are universal for animals in a (non-trivial) restricted class? Are there any interesting results along these lines? Is the Penrose tiling itself known to be universal for some interesting class of animals?

Covering a random graph with spanning trees.

2010-11-10T20:54:17Z

Let $G=(V,E)$ be a connected graph, say $V=\{1,\ldots,n\}$ . Let $F=(V,E')$ be a uniformly random forest in $G$. (In other words, $E'$ is a subset of edges $E$ not containing a cycle, and it is uniformly chosen over all such sets.)

Associated to the random forest $F$ are marginals $\{p_e:e \in E\}$ , where $p_e = \mathbb{P}(e \in E')$. Now let $E^*$ be a random subset of $E$, chosen by independently including each edge $e \in E$ with probability $p_e$.

Finally, let $N$ be the (random) smallest number of spanning trees of $G$ whose union contains $E^*$.

What is known about the distribution of $N$? How does $\sup_{G} \mathbb{E}(N)$, the largest expected value of $N$ over all $n$-vertex graphs, grow? Is it $O(\log n)$? Is it $O(1)$?

Edit: is it $O(\sqrt{\log n})$? Fedor has a nice example showing that it is not $O(1)$. I believe optimizing Fedor's example yields a lower bound of order $(\log n/\log\log n)^{1/2}$.

Note: the question also makes sense if $E'$ is the edge set of a uniformly random spanning tree, and Fedor's example applies in either case.

Answer by Louigi Addario-Berry for Brownian bridge interpreted as Brownian motion on the circle

2010-11-22T21:21:24Z

Aldous and Pitman have a paper on "Brownian bridge asymptotics for random mappings", which describes a setting in which Brownian bridge shows up as a limit object and is most naturally thought of as indexed by a circle rather than by an interval. There are two follow-up papers (one, two) by Aldous, Miermont and Pitman, the first of which "give[s] a conceptually straightforward argument which both proves convergence and more directly identifies the limit" (as well as extending the results to more general kinds of random mappings).

The basic idea is that mapping, i.e. a function $f$ from $[n] = \{1,\ldots,n\}$ to $[n]$ can be represented in terms of "basins of attraction". Create a digraph by joining $i$ to $j$ if $f(i)=j$. In this digraph, each connected component will contain a unique directed cycle, and each vertex $i$ of the cycle will be the root of a tree all of whose edges are oriented towards $i$. It is then possible to code the structure of the cycle-plus-trees in terms of a lattice path, with height corresponding to distance from the cycle.

When the underlying mapping $f$ is a uniformly random mapping, the resulting lattice path, suitably interpreted and after rescaling, converges to (the absolute value of) Brownian bridge.

Answer by Louigi Addario-Berry for Obstructions for planar graphs on surfaces of genus g

2010-11-19T17:40:21Z

Yes. Wagner's Conjecture/Robertson and Seymour's Theorem says that any graph family closed under taking minors can be defined by specifying a finite list of forbidden minors. For any surface $S$, the graphs embeddable $S$ without crossing edges forms a family closed under taking minors.

I haven't looked carefully at it but Jim Belk's introduction to graph minor theory seems good. On the linked page he mentions the following facts: the projective plane has 35 forbidden minors, the number for the torus is in the ~~hundreds~~ thousands (at least, the precise number/collection is not known), and in general the number of forbidden minors grows exponentially with the genus.

Notation for bilinear form $y^t M z$, where $M$ is a matrix and $y,z$ are vectors.

2010-11-19T15:29:48Z

I'm working on a problem where I need to consider a bilinear form of the form $y^t M z$ where $M$ is an $n$-by-$n$ real symmetric matrix and $y,z \in \mathbb{R}^n$ are vectors. I also need to consider restricted forms of such a product, of the form $$ \sum_{i,j=1}^n y_i m_{ij} z_j \mathbf{I}_{(y_i,z_j) \in E}, $$ where $E$ is some subset of $\mathbb{R}^2$. We recover $y^t M z$ by taking $E=\mathbb{R}^2$. I want a common notation for $y^t M z$ and for these restricted sums, so I have been writing $y^t M z = \langle y,z\rangle_M$, and writing $\langle y,z\rangle_{M,E}$ for the restricted sum above.

I see nothing wrong with the notation I'm using. However, if there's a standard notation for such things that I am unaware of, I would like to know about it. Is there? If you know of another notation, can you give me a reference?

Answer by Louigi Addario-Berry for Strongly correlated? Terminology question

2010-11-09T21:03:14Z

This is along the lines of Tom's answer. $X$ induces a partial order on $\Omega$. In fact, it induces a total order on a partition of $\Omega$ into sets $X^{-1}(x)$, $x \in \mathbb{R}$); simply say $X^{-1}(x) < X^{-1}(y)$ if $x < y$.

By your property, there is then some non-decreasing function $y:\mathbb{R} \to \mathbb{R}$ such that for $x \in \mathbb{R}$, if $\omega_1, \omega_2 \in X^{-1}(x)$ then $Y(\omega_1)=Y(\omega_2)=y(x)$.

But then we can write $Y(\omega)=y(X(\omega))$. In other words, $Y$ is just a non-decreasing (measurable) function of $X$.

Answer by Louigi Addario-Berry for Planar layouts of bipartite graphs

2010-11-07T22:07:06Z

Edit: When I posted this I was assuming you also wanted a straight-line drawing, which I now realize you did not say. The below relates only to straight-line drawings.

This is not possible. The $3$-cube is already a counterexample. Viewing the cube as the Hamming cube, up to symmetries there is only one way to place the middle two layers in the manner you suggest -- one must take ${100,010,001}\subset B$, ${110,011} \subset A_1$ and ${101}\subset A_2$. But then it is impossible to put $111$ in either $A_1$ or $A_2$ without creating crossing edges.

More generally, a counting argument should quite straightforwardly show that for large $n$, the proportion of planar graphs that satisfy your criteria is asymptotically small. (Using the fact that the number of labeled planar graphs on $n$ vertices is asymptotically $n! \cdot (27.22687\ldots)^n$ times lower order terms, which is a result of Gimenez and Noy.)

Answer by Louigi Addario-Berry for When do 3D random walks return to their origin?

2010-11-07T14:58:59Z

For a fairly robust intuitive argument, think of a random walk in $\mathbb{R}^d$ as the "product" of $d$ one-dimensional walks in $\mathbb{R}^1$. For a (finite variance) random walk in $\mathbb{R}^1$, the probability the random walk is within $O(1)$ of the origin after $n$ steps scales like $n^{-1/2}$. If the $d$-dimensional random walk were to literally just be the independent product of $d$ one-dimensional walks, this would mean that in $\mathbb{R}^d$ the probability the random walk is near the origin after $n$ steps would be about $n^{-d/2}$, and indeed, this answer is correct. Roughly speaking, then, the reason random walk changes behavior between $d=2$ and $d=3$ is that this is when $\sum_n n^{-d/2}$ switches from divergent to convergent.

This intuition suggests that if your walk is "truly" at least $(2+\epsilon)$-dimensional for some $\epsilon > 0$, then it should be transient (if you're willing to accept this intuition of $n^{-d/2}$ behavior for fractional $d$). Terry Lyons has derived a necessary and sufficient condition for the transience of a reversible Markov chain which I think formalizes and extends this intuition. He in particular uses it to prove a necessary and sufficient condition for the transience of simple random walk on "wedges" in $\mathbb{Z}^d$. Specializing his result even further, he mentions that, letting $\Omega$ be the subgraph of $\mathbb{Z}^3$ with $$ \Omega=\{(x,y,z) \in \mathbb{Z}^3, y \leq x, x \leq (\log(z+1))^{\alpha}\} $$ then the simple random walk on $\Omega$ is transient whenever $\alpha > 1$. (The same would be true for any finite variance random walk constrained to lie in $\Omega$, though I'm not sure Terry Lyons' theorem will prove this in full generality.) The graph $\Omega$ is just a very slight "fattening" of part of $\mathbb{Z}^2$, and the walk is already transient. In a sense, random walks in $\mathbb{Z}^2$ only "just" fail to be transient, and if you go above $\mathbb{Z}^2$ in any way you will immediately be transient.

Answer by Louigi Addario-Berry for Most memorable titles

2010-11-01T12:45:05Z

Here is a list of papers in Theoretical Computer Science with cute titles. Some that I like from the list (aside from "Mick gets some" which is good enough to deserve its own answer anyway).

A Smaller Sleeping Bag for a Baby Snake
The Art of Pointless Thinking: a Student's Guide to the Category of Locales
Scott is not always sober

Also: Mangoes and Blueberries.

And in a similar vein, a quote from "Quotients homophone des groupes libres - Homophonic quotients of free groups," that appears on the first linked page page: "Ah, la recherche! Du temps perdu."

Answer by Louigi Addario-Berry for The conditions in the definition of Poisson process (and a Lévy process generalization)

2010-10-25T14:56:06Z

Based on the comments to this answer, I no longer believe what I initially wrote (still appearing at the bottom of the answer). It seems to me a construction should be possible. It is at least possible in the case of a Binomial point process.

Let $\{X_i\}_{i \in \mathbb{N},i\neq 4}$ be independent Bernoulli$(1/2)$ random variables. Let $X_4'$ be Bernoulli$(1/2)$ and independent of the $X_i$. Then define $X_4$ as follows:

$X_4 = 1$ if $(X_1,X_2,X_3)$ is either $(0,0,1)$ or $(1,1,0)$,
$X_3 = 0$ if $(X_1,X_2,X_3)$ is either $(0,1,0)$ or $(1,0,1)$,
$X_4=X_4'$ otherwise.

Then for all $j \geq 0$, $n \geq 1$, $X_{j+1}+\ldots+X_{j+n}$ has Binomial$(n,1/2)$ distribution but the family $(X_n)_{n \in \mathbb{N}}$ are not iid.

What appears below (where I suggested such a construction was impossible) is false.

For a standard Poisson process, this won't be possible. (See this question and its answer.)

Edit: Given the comments perhaps I should provide more detail.

With probability one, for every pair $0 < p < q$, $p,q$ rationals, $X(q)−X(p)$ is a non-negative integer. Since X is cadlag the same property must hold for every real pair $0 < s < t$, i.e. $X$ is increasing and integer-valued.

Let us also show that $X$ has no jumps of size more than one: with probability one, for all $x > 0$, $X(x^-) := \lim_{y \uparrow x} X(y) \geq X(x)-1$. If this failed to hold then there would be $\epsilon > 0$ and $t < \infty$ so that $$ \mathbb{P}(\exists x \in [0,t), X(x)-X(x^-) \geq 2) > \epsilon/2. $$ But since $X$ is increasing, for any positive integer $n$ we can bound this probability from above by $$ \sum_{1 \leq i < 2n} \mathbb{P}(X((i+1)t/2n)-X((i-1)t/2n) \geq 2) $$ the point being that these intervals are chosen to overlap so that a jump of size $\geq 2$ must fall in at least one of them. Each of the differences above is distributed as Poisson$(t/n)$, so the associated probability is $o(n^{-1})$ as $n \to \infty$ and thus the whole sum tends to zero as $n \to \infty$.

We then know that a process $X$ such as you describe must be increasing and integer valued, with all jumps of size $1$. In other words, $X$ is a point process on $[0,\infty)$. Now the answer from the other thread implies that $X$ must be a rate one Poisson process.

Answer by Louigi Addario-Berry for Basic results with three or more hypotheses

2010-10-22T18:10:34Z

Here is another one: a finite irreducible aperiodic Markov chain is ergodic.

Answer by Louigi Addario-Berry for Basic results with three or more hypotheses

2010-10-22T12:31:36Z

The central limit theorem: if random variables $\{X_n\}_{n \in \mathbb{N}}$ are (A) Independent, (B) Identically distributed, and (C) have finite variance then (D) $(\sum_1^n X_i - n\mu)/\sqrt{\sigma^2 n} \to N(0,1)$.

Answer by Louigi Addario-Berry for is there an interpretation to the inverse of $I-M$ in multitype branching process, where $M$ is the mean matrix?

2010-10-17T15:00:01Z

In general, if $M$ was the transition matrix (infinitesimal generator) of a Markov chain , this functional would be called called the resolvent. Perhaps you already knew this; if not, you could look at James Norris' Markov Chains for a nice introduction; it may well contain enough information for you.

Comment by Louigi Addario-Berry

2013-03-11T13:23:19Z

Dear Timothy, I have a small bone to pick with this answer. While graph minor theory is indeed a grand project, the proof of the strong perfect graph conjecture and the characterization of the structure of claw-free graphs are not part of graph minor theory. Both are concerned with forbidden induced subgraphs, rather than forbidden minors. The tools used in studying forbidden induced subgraphs are rather different, as witnessed by the fact that the paper containing the proof of the strong perfect graph conjecture does not reference a single paper from the graph minors sequence.

Comment by Louigi Addario-Berry

2013-01-25T13:28:52Z

(First paragraph, I mean.)

Comment by Louigi Addario-Berry

2013-01-25T13:28:32Z

Aldous points out in the first line of this article (stat-www.berkeley.edu/~aldous/Papers/me49.pdf) that the distribution is not the uniform distribution.

Comment by Louigi Addario-Berry

2012-12-03T19:59:25Z

I checked the Moon Moser paper, that is indeed your reference. I've emailed you a somewhat crappy but legible scan of the paper.

Comment by Louigi Addario-Berry

2012-03-12T14:09:42Z

There are results of Alon (tinyurl.com/nogapaper) and of Bollobas and Sarkar (myweb.facstaff.wwu.edu/sarkara/four.ps) on maximizing the number of copies of P_4 over graphs with a fixed number of edges. Not posting as an answer since the word "induced", and fixing the number of edges rather than of vertices, makes a pretty big difference. As a historical curiosity, this seems to be Noga Alon's first paper, according to the publication list on his web site.

Comment by Louigi Addario-Berry

2012-01-10T02:08:52Z

Thanks for the comment, Brendan. Pitman has this right; I didn't in my first version of my answer. I'll correct.

Comment by Louigi Addario-Berry

2011-11-01T23:29:06Z

Sorry, you're right. That's what I get for commenting before my first coffee. I've corrected my response. Welcome to MO.

Comment by Louigi Addario-Berry

2011-07-28T02:28:04Z

Nice argument, Andrew.

Comment by Louigi Addario-Berry

2011-06-10T00:14:53Z

Sorry, Ori. No way to edit comments either! My error will live for all time.

Comment by Louigi Addario-Berry

2011-06-09T13:00:48Z

For Uri's argument to work you need to be doing the walk on a regular graph, otherwise there is another factor which is the ratio of the degrees of $x$ and $y$.

Comment by Louigi Addario-Berry

2011-06-07T17:56:09Z

This looks like it should work in fair generality, whenever $Q(z)$ behaves reasonably. Vertex weights might make the computations a little simpler than edge weights, I'll see. Thanks for the suggestion, Omer -- when I get around to working out some details I'll post an update.

Comment by Louigi Addario-Berry

2011-05-10T23:28:18Z

What about in four dimensions?

Comment by Louigi Addario-Berry

2011-05-09T15:54:03Z

Not an answer, just an observation. If you instead write $S_n=\epsilon+\sum_{i=1}^n X_i$ then for irrational $\alpha$ I expect that $\mathcal{P}_{\epsilon}(\alpha)$ will be everywhere discontinuous as a function of $\epsilon$. This gives me some doubt that there will be a nice, closed-form answer, since in any recurrence-relation type approach to the problem you will end up having to consider terms like $\mathcal{P}_{\epsilon}(\alpha)$ You might find something of use in the literature on combinatorics on words, but I don't know this literature very well at all so I'm not sure.

Comment by Louigi Addario-Berry

2011-04-20T15:45:31Z

This actually looks amazingly good. First online LaTeX editor I can actually imagine using.

Comment by Louigi Addario-Berry

2011-04-17T13:33:14Z

James, George, yes, James' observation reduces this to an assignment-level exercise. I will delete the question. Thanks for the comments all three of you.