User louigi addario-berry - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T13:33:03Z http://mathoverflow.net/feeds/user/3401 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/83154/number-of-geodesic-paths-passing-through-a-vertex-in-an-expander-graph/88878#88878 Answer by Louigi Addario-Berry for Number of Geodesic Paths Passing Through a Vertex in an Expander Graph Louigi Addario-Berry 2012-02-19T01:58:59Z 2012-07-04T14:24:05Z <p>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. </p> <p><a href="http://arxiv.org/pdf/0708.0555v1.pdf" rel="nofollow">Aldous and Bhamidi</a> 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$, <code>$\frac{1}{n} \#\{e: F_n(e) &gt; z\log n\} \to \int_0^{\infty}\mathbb{P}(W_1W_2e^{-u} &gt; z)~du,$</code> where $W_1$ and $W_2$ are independent exponentials. (In fact, the paper proves a more detailed distributional convergence result.) In particular, <em>typical</em> edge congestion is $O(\log n)$; but the paper does not address <em>maximum</em> 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. </p> <blockquote> <p>What follows is less relevant as it relates to <em>global</em> strategies for minimizing congestion, rather than greedy routing between nodes. I'm posting it anyway in case it's useful. </p> </blockquote> <p>Alan Frieze has <a href="http://math.cmu.edu/~af1p/Texfiles/R98.pdf" rel="nofollow">a survey on disjoint paths in expander graphs</a> 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)$. </p> <p>Finally, for a particular class of <em>random</em> 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 <em>uniform flow of volume $\phi$</em> 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 <code>$\chi(F)=\max_{e \in E} \sum_{f \in F} f(e)$</code> for the maximum flow across any edge of $G$, when all flows of $F$ are simultaneously active </p> <p><a href="http://www.stat.berkeley.edu/~aldous/Papers/me122.pdf" rel="nofollow">Aldous, Mcdiarmid, and Scott</a> have proved the following. Fix a non-negative random variable $C$ with $\mathbb{E}(C) &lt; \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 <code>$\sum_{f \in F} f(e) \le C_e$</code> for all $e \in E(K_n)$. Then there is a positive constant $\phi_*$ such that $\phi_n \to \phi_*$ in probability. </p> <p>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. </p> http://mathoverflow.net/questions/97698/cover-time-and-intersection-time-of-random-walks/97744#97744 Answer by Louigi Addario-Berry for Cover time and intersection time of random walks Louigi Addario-Berry 2012-05-23T11:00:45Z 2012-05-23T11:00:45Z <p>In Proposition 5 of <a href="http://www.stat.berkeley.edu/~aldous/RWG/Chap14.pdf" rel="nofollow">Chapter 14</a> of the unpublished book on Markov chains by Aldous and Fill, they show that for continuous time reversible Markov chains, <code>$I \le \max\{ \mathbb{E}_i T_j, i,j \in V\},$</code> 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). </p> http://mathoverflow.net/questions/89096/does-graph-asymmetry-imply-all-eigenvalues-of-the-graph-laplacian-are-simple/89113#89113 Answer by Louigi Addario-Berry for Does graph asymmetry imply all eigenvalues of the graph Laplacian are simple? Louigi Addario-Berry 2012-02-21T15:04:11Z 2012-02-21T15:04:11Z <p>Take two asymmetric $d$-regular graphs $H_1,H_2$, and let $G$ be their disjoint union. Then $d$ will be a repeated eigenvalue. </p> <p>If you want $G$ connected, take the complement of the graph obtained by the above construction. Graph complements preserve asymmetry and repeated eigenvalues. </p> http://mathoverflow.net/questions/88719/asymptotic-geodesic-flow-on-planar-graphs/88982#88982 Answer by Louigi Addario-Berry for Asymptotic Geodesic Flow on Planar Graphs Louigi Addario-Berry 2012-02-20T00:51:23Z 2012-02-20T00:51:23Z <p>You can't do better. Lipton and Tarjan's <a href="http://en.wikipedia.org/wiki/Planar_separator_theorem" rel="nofollow">planar separator theorem</a> 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$. </p> http://mathoverflow.net/questions/87788/the-critical-value-of-percolation-on-cayley-graphs/87954#87954 Answer by Louigi Addario-Berry for The critical value of percolation on Cayley graphs. Louigi Addario-Berry 2012-02-09T02:52:14Z 2012-02-09T15:49:52Z <p>In a paper called <a href="http://www.math.bme.hu/~balint/oktatas/perkolacio/percolation_papers/benjamini_lyons_peres_schramm_nonamen.pdf" rel="nofollow">Critical Percolation on any Nonamenable Group Has no Infinite Clusters</a>, Benjamini, Lyons, Peres, and Schramm show that ... critical percolation on any nonamenable group has no infinite clusters. </p> <p>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) &lt; 1$. </p> <p>The paper also shows that for any invariant bond percolation $P$&nbsp; on $G$ (invariant means its distribution is unchanged by the action of the group), if in $P$&nbsp; the expected number of neighbours of the origin $o$ is at least <code>$d_G(o) - \kappa(G),$</code> 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 <code>$p_c(G) \le 1-\kappa(G)/d_G(o),$</code> which is weaker than the bound in Vincent Beffara and Asaf Nachmias' answers, but applies to a broader range of percolation models. </p> http://mathoverflow.net/questions/85196/distribution-of-big-component-of-set-partitions/85270#85270 Answer by Louigi Addario-Berry for Distribution of big component of set partitions Louigi Addario-Berry 2012-01-09T17:18:22Z 2012-01-10T02:10:56Z <p>I haven't managed to find the answer to precisely your question but here are a couple of references that might be useful.</p> <p>Vershik and Yakubovich have a paper on <a href="http://www.ams.org/distribution/mmj/vol1-3-2001/vershik.pdf" rel="nofollow"><em>The limit shape and fluctuations of random partitions of naturals with a fixed number of summands</em></a>. It addresses partitions of $n$ with around $\sqrt{n}$ summands, but doesn't seem to have exactly the result you're asking about. </p> <p>If you haven't already looked at it, Chapter 1 of Pitman's <a href="http://works.bepress.com/cgi/viewcontent.cgi?article=1000&amp;context=jim_pitman" rel="nofollow"><em>Combinatorial stochastic processes</em></a> 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)$ (<b>Added on edit</b>: <em>the</em> $X_i$ <em>should be conditioned to be strictly positive</em>). Also, let $K$ be Poisson$(e^{\xi}-1)$ and independent of the $X_i$. </p> <p>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 <code>$\{1,\ldots,n\}$</code>, listed in exchangeable random order.</p> <p>You could then try conditioning both on $X_1+\ldots+X_K=n$ <em>and</em> on $K=k$, and playing with the parameter $\xi$, to read off information about partitions of <code>$\{1,\ldots,n\}$</code> into $k$ parts.</p> http://mathoverflow.net/questions/79534/length-of-the-last-edge-when-visiting-points-by-nearest-neighbor-order/79687#79687 Answer by Louigi Addario-Berry for Length of the last edge when visiting points by nearest neighbor order Louigi Addario-Berry 2011-11-01T08:09:26Z 2011-11-01T23:28:02Z <p>This is closely related to a nice <a href="http://www.stat.berkeley.edu/~aldous/Research/OP/greedy_tour.html" rel="nofollow">open problem of David Aldous</a>, 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. </p> http://mathoverflow.net/questions/69773/did-joseph-doob-prove-that-random-sequences-dont-exist/69874#69874 Answer by Louigi Addario-Berry for Did Joseph Doob prove that random sequences don't exist? Louigi Addario-Berry 2011-07-09T13:39:20Z 2011-07-09T13:39:20Z <p>There is an excellent article by Sérgio B. Volchan in the American Mathematical Monthly, titled <a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.102.671&amp;rep=rep1&amp;type=pdf" rel="nofollow">What Is a Random Sequence</a>, 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 <em>typicality</em>, 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 <em>incompressibility</em> of the sequence. </p> <p>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. </p> http://mathoverflow.net/questions/66595/counting-subtrees-of-a-random-tree-random-catalan-numbers Counting subtrees of a random tree ("random Catalan numbers") Louigi Addario-Berry 2011-05-31T21:57:34Z 2011-06-06T18:15:28Z <p>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). </p> <p>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 <code>$N_k(T_d) = \frac{1}{k}{dk \choose k-1} &lt; (ed)^{k-1}.$</code> When $d=2$, these are simply the Catalan numbers.</p> <p>Now suppose that $\mathcal{T}$ is a Galton--Watson tree with offspring distribution $B$ and $\mathbb{E}(B)=\mu \in (1,\infty)$. </p> <blockquote> <p>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? </p> </blockquote> <p>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? </p> <p>Perhaps the problem is more combinatorially tractable if one assumes that $B$ has a Poisson distribution? This special case is interesting to me. </p> http://mathoverflow.net/questions/60371/properties-of-some-random-graphs/60377#60377 Answer by Louigi Addario-Berry for Properties of Some Random Graphs Louigi Addario-Berry 2011-04-02T19:07:24Z 2011-04-04T20:09:20Z <p>Yes, this model has been studied. You should look at Chapter 9 of Janson, Luczak and Rucinski's <a href="http://www.amazon.com/Random-Graphs-Svante-Janson/dp/0471175412" rel="nofollow">Random Graphs book</a>, and in particular at Corollary 9.44. This corollary is in fact a rather well-known theorem, which I'll now explain.</p> <p>Let $H_n(d)$ be the distribution you describe (<b>Edit:</b> 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 <i>contiguous</i>, which means that for any graph property $A$, <code>$\mathbb{P}(H_n(d) \in A) \to 1~\mbox{as}~n\to\infty$</code> if and only if <code>$\mathbb{P}(G_n(2d) \in A) \to 1~\mbox{as}~n\to\infty.$</code> In other words, if you are only interested in studying whether things hold asymptotically almost surely, these two models are equivalent. </p> <p>In particular, its <a href="ftp://ftp-sop.inria.fr/mascotte/personnel/Stephane.Perennes/Bol88.pdf" rel="nofollow">isoperimetric constant</a> is $(1/2+o(1)) d$, its <a href="http://www.stanford.edu/class/msande337/notes/the%20diameter%20of%20random%20regular%20graphs.pdf" rel="nofollow">diameter</a> is $(1+o(1)) \log_{d-1} (n)$, and <a href="http://www.math.ubc.ca/~jf/pubs/web_stuff/alon.html" rel="nofollow">all eigenvalues except for the largest</a> are $\sqrt{2(d-1)}+o(1)$. </p> http://mathoverflow.net/questions/55625/coin-flipping-and-a-recurrence-relation/55636#55636 Answer by Louigi Addario-Berry for Coin flipping and a recurrence relation Louigi Addario-Berry 2011-02-16T16:30:48Z 2011-02-17T10:19:12Z <p>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. </p> <p>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 <em>minimum</em>, 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$. </p> <p>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]$. </p> http://mathoverflow.net/questions/54051/random-permutations-of-z-n/54103#54103 Answer by Louigi Addario-Berry for Random permutations of Z_n Louigi Addario-Berry 2011-02-02T15:26:32Z 2011-02-03T14:45:55Z <p>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.</p> <blockquote> <p>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.</p> <p>To count those you use the so called <a href="http://en.wikipedia.org/wiki/BEST_theorem" rel="nofollow">BEST theorem</a> 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.)</p> <p>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 <a href="http://journals.cambridge.org/action/displayAbstract?fromPage=online&amp;aid=721448" rel="nofollow">paper by Bill Cuckler about that</a> in CPC 2007). Hope this makes sense, please feel free to mention whatever you see fit in Mathoverflow.</p> </blockquote> http://mathoverflow.net/questions/39823/differences-of-near-diagonal-ramsey-numbers/42893#42893 Answer by Louigi Addario-Berry for Differences of near diagonal Ramsey numbers. Louigi Addario-Berry 2010-10-20T13:02:06Z 2011-01-30T14:12:29Z <blockquote> <p><b>Edit</b>: 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$. </p> </blockquote> <p>The relevant paper is <a href="http://www.renyi.hu/~p_erdos/1989-21.pdf" rel="nofollow">On the difference between consecutive Ramsey Numbers</a>, 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. </p> <hr> <p><b>Old answer.</b></p> <p>For your first question: thanks to Miklos Simonovits and others, all of Erdős' papers are available from <a href="http://www.renyi.hu/~p_erdos/Erdos.html" rel="nofollow">this site</a>. 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.</p> http://mathoverflow.net/questions/52333/proving-that-every-graph-is-an-induced-subgraph-of-an-r-regular-graph/52375#52375 Answer by Louigi Addario-Berry for Proving that every graph is an induced subgraph of an r-regular graph Louigi Addario-Berry 2011-01-18T03:12:18Z 2011-01-18T03:12:18Z <p>Use induction on $r-\delta$, where $\delta=\delta(G)$ is the smallest degree of any vertex in $G$. </p> <p>If $r-\delta=0$, then you are done. </p> <p>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$.</p> http://mathoverflow.net/questions/51677/has-the-technique-of-sprinkling-been-used-in-studying-random-matrices Has the technique of "sprinkling" been used in studying random matrices? Louigi Addario-Berry 2011-01-10T18:13:05Z 2011-01-10T18:13:05Z <p>In 1982, while studying the component sizes of random subgraphs of a hypercube, <a href="http://www.springerlink.com/content/pw8u247117244054/fulltext.pdf" rel="nofollow">Ajtai, Komlós, and Szemerédi</a> introduced a technique that came to be known as <em>sprinkling</em>. 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.</p> <blockquote> <p>Has the technique of sprinkling been used in the study of random Bernoulli matrices? Can you give me references? </p> </blockquote> http://mathoverflow.net/questions/24352/cutting-convex-sets/48198#48198 Answer by Louigi Addario-Berry for Cutting convex sets Louigi Addario-Berry 2010-12-03T17:31:29Z 2010-12-03T17:39:45Z <p>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&#353;ek have a <a href="http://www.renyi.hu/~barany/cikkek/equipp.ps" rel="nofollow">nice paper on the subject</a>. </p> <p>Even more generally, fix nice probability measures $\mu_1,\ldots,\mu_i$ on $\mathbb{R}^2$. A <em>$k$-fan</em> 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. </p> <p>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 <em>simultaneously $\alpha$-partitioned</em> 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 <em>simultaneously equipartitioned</em>. This case, with $k=2$, is closest to the original )</p> <p>Bárány and Matou&#353;ek have a whole host of results about when such partitions exist and do not exist. Here are just a couple: </p> <ul> <li>For any $k \geq 5$ and any $\alpha$, there are two measures that can not be simultaneously $\alpha$-partitioned. </li> <li>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. </li> </ul> <p><strike>No one knows, for example, if any two measures can be simultaneously equipartitioned into four parts.</strike> Karasev seems to have <a href="http://arxiv.org/abs/1011.4762v2" rel="nofollow">a paper</a> where he proves that any two measures can be simultaneously equipartitioned into $q$ <em>convex</em> 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.</p> <p>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.) </p> http://mathoverflow.net/questions/47168/ex-1-x-1-x-2-where-x-i-are-integrable-independent-infinitely-divisib/47247#47247 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" Louigi Addario-Berry 2010-11-24T16:41:17Z 2010-11-25T20:12:28Z <p>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 <code>$(X'_s)_{0\leq s \leq t}$</code> obtained by a cyclic shift by $u$, has the same distribution as the original process.</p> <p>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.)</p> <p><b>Edit</b>: 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)| &lt; \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$. </p> <p>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. </p> <p><b>Edit:</b> (This is an expansion of the argument I sketched in the comments.) Note that for <em>any</em> 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.</p> <p>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)$. </p> <p>Conditional upon $Z_1$ (which equals $Y_1$), we don't automatically know the distribution of $(Z_s)$. However, we know the following facts.</p> <ol> <li><p>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. </p></li> <li><p>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$. </p></li> </ol> <p>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$. </p> <p>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| &lt; \infty$ but I still haven't checked.</p> http://mathoverflow.net/questions/47131/are-penrose-tilings-universal-do-aperiodic-universal-tilings-exist Are Penrose tilings universal? Do aperiodic universal tilings exist? Louigi Addario-Berry 2010-11-23T18:47:57Z 2010-11-24T04:29:59Z <p>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 <i>polyomino</i>; 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). </p> <p><img src="http://mathworld.wolfram.com/images/eps-gif/Polyominoes_1300.gif" width="400"> </p> <p>Say that a tiling of the plane using (distinct) tiles $t_1,\ldots,t_k$ is <i>universal</i> 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". </p> <p><img src="http://www.math.mcgill.ca/louigi/images/penroseexample.jpg"></p> <p>This animal can't be contained within <em>any</em> tiling (Penrose or otherwise) using $t_1$ and $t_2$. So it makes sense to restrict to animals which, for example, are contained within <em>some</em> tiling of the plane with the given tiles. </p> <blockquote> <p>My question is: are there $k \geq 2$ for which (aperiodic -- adjective added in edit) universal tilings exist? </p> <p><b>Edit:</b> 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. </p> </blockquote> <p>We can also restrict the allowed animals. For example, we could restrict to animals which exhibit some form of symmetry. </p> <blockquote> <p>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? </p> </blockquote> <p><img src="http://upload.wikimedia.org/wikipedia/commons/1/1a/Penrose_Tiling_(Rhombi).svg"></p> http://mathoverflow.net/questions/45599/covering-a-random-graph-with-spanning-trees Covering a random graph with spanning trees. Louigi Addario-Berry 2010-11-10T20:54:17Z 2010-11-23T01:21:01Z <p>Let $G=(V,E)$ be a connected graph, say <code>$V=\{1,\ldots,n\}$</code>. 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.) </p> <p>Associated to the random forest $F$ are <em>marginals</em> <code>$\{p_e:e \in E\}$</code>, 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$. </p> <p>Finally, let $N$ be the (random) smallest number of spanning trees of $G$ whose union contains $E^*$. </p> <blockquote> <p>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)$?</p> </blockquote> <p><b>Edit</b>: 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}$.</p> <p><b>Note:</b> 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.</p> http://mathoverflow.net/questions/46991/brownian-bridge-interpreted-as-brownian-motion-on-the-circle/47004#47004 Answer by Louigi Addario-Berry for Brownian bridge interpreted as Brownian motion on the circle Louigi Addario-Berry 2010-11-22T21:21:24Z 2010-11-22T21:47:46Z <p><a href="http://www3.interscience.wiley.com/journal/113393695/abstract" rel="nofollow">Aldous and Pitman</a> 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 (<a href="http://www.math.washington.edu/~ejpecp/viewarticle.php?id=1429&amp;layout=abstract" rel="nofollow">one</a>, <a href="http://www.springerlink.com/content/g8134863lt734607/?p=ed2ec1d76a7f4250990539b6c19a321c&amp;pi=4" rel="nofollow">two</a>) 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). </p> <p>The basic idea is that mapping, i.e. a function $f$ from <code>$[n] = \{1,\ldots,n\}$</code> 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.</p> <p>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. </p> http://mathoverflow.net/questions/46655/obstructions-for-planar-graphs-on-surfaces-of-genus-g/46656#46656 Answer by Louigi Addario-Berry for Obstructions for planar graphs on surfaces of genus g Louigi Addario-Berry 2010-11-19T17:40:21Z 2010-11-19T18:23:55Z <p>Yes. <a href="http://en.wikipedia.org/wiki/Robertson%E2%80%93Seymour_theorem" rel="nofollow">Wagner's Conjecture/Robertson and Seymour's Theorem</a> 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. </p> <p>I haven't looked carefully at it but <a href="http://cornellmath.wordpress.com/2007/07/04/graph-minor-theory-part-3/" rel="nofollow">Jim Belk's introduction to graph minor theory</a> 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 <strike>hundreds</strike> thousands (at least, the precise number/collection is not known), and in general the number of forbidden minors grows exponentially with the genus. </p> http://mathoverflow.net/questions/46641/notation-for-bilinear-form-yt-m-z-where-m-is-a-matrix-and-y-z-are-vectors Notation for bilinear form $y^t M z$, where $M$ is a matrix and $y,z$ are vectors. Louigi Addario-Berry 2010-11-19T15:29:48Z 2010-11-19T18:05:00Z <p>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 <code>$y,z \in \mathbb{R}^n$</code> 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. </p> <p>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?</p> http://mathoverflow.net/questions/45474/strongly-correlated-terminology-question/45484#45484 Answer by Louigi Addario-Berry for Strongly correlated? Terminology question Louigi Addario-Berry 2010-11-09T21:03:14Z 2010-11-09T21:03:14Z <p>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) &lt; X^{-1}(y)$ if $x &lt; y$. </p> <p>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)$. </p> <p>But then we can write $Y(\omega)=y(X(\omega))$. In other words, $Y$ is just a non-decreasing (measurable) function of $X$. </p> http://mathoverflow.net/questions/45211/planar-layouts-of-bipartite-graphs/45222#45222 Answer by Louigi Addario-Berry for Planar layouts of bipartite graphs Louigi Addario-Berry 2010-11-07T22:07:06Z 2010-11-07T22:12:50Z <p><b>Edit:</b> 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. </p> <hr> <p>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. </p> <p>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.)</p> http://mathoverflow.net/questions/45098/when-do-3d-random-walks-return-to-their-origin/45174#45174 Answer by Louigi Addario-Berry for When do 3D random walks return to their origin? Louigi Addario-Berry 2010-11-07T14:58:59Z 2010-11-07T14:58:59Z <p>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. </p> <p>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$). <a href="http://projecteuclid.org/DPubS?service=UI&amp;version=1.0&amp;verb=Display&amp;handle=euclid.aop/1176993604" rel="nofollow">Terry Lyons has derived</a> 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 <code>$$\Omega=\{(x,y,z) \in \mathbb{Z}^3, y \leq x, x \leq (\log(z+1))^{\alpha}\}$$</code> 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. </p> http://mathoverflow.net/questions/44326/most-memorable-titles/44436#44436 Answer by Louigi Addario-Berry for Most memorable titles Louigi Addario-Berry 2010-11-01T12:45:05Z 2010-11-01T12:45:05Z <p>Here is <a href="http://www2.tcs.ifi.lmu.de/~jjohanns/cute.html" rel="nofollow">a list of papers in Theoretical Computer Science with cute titles</a>. Some that I like from the list (aside from "Mick gets some" which is good enough to deserve its own answer anyway). </p> <ul> <li>A Smaller Sleeping Bag for a Baby Snake</li> <li>The Art of Pointless Thinking: a Student's Guide to the Category of Locales</li> <li>Scott is not always sober</li> </ul> <p>Also: <a href="http://www.springerlink.com/content/dybau01uabebcxry/" rel="nofollow">Mangoes and Blueberries</a>.</p> <p>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: <i>"Ah, la recherche! Du temps perdu."</i></p> http://mathoverflow.net/questions/43481/the-conditions-in-the-definition-of-poisson-process-and-a-levy-process-generaliz/43528#43528 Answer by Louigi Addario-Berry for The conditions in the definition of Poisson process (and a Lévy process generalization) Louigi Addario-Berry 2010-10-25T14:56:06Z 2010-10-26T01:31:10Z <p>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. </p> <p>Let <code>$\{X_i\}_{i \in \mathbb{N},i\neq 4}$</code> 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: </p> <ul> <li>$X_4 = 1$ if $(X_1,X_2,X_3)$ is either $(0,0,1)$ or $(1,1,0)$,</li> <li>$X_3 = 0$ if $(X_1,X_2,X_3)$ is either $(0,1,0)$ or $(1,0,1)$, </li> <li>$X_4=X_4'$ otherwise. </li> </ul> <p>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. </p> <hr> <p>What appears below (where I suggested such a construction was impossible) is false.</p> <hr> <p>For a standard Poisson process, this won't be possible. (See <a href="http://mathoverflow.net/questions/39491/a-point-process-is-characterized-by-its-void-probabilities" rel="nofollow">this question</a> and its answer.) </p> <p><b>Edit</b>: Given the comments perhaps I should provide more detail. </p> <p>With probability one, for every pair $0 &lt; p &lt; 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 &lt; s &lt; t$, i.e. $X$ is increasing and integer-valued. </p> <p>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 &lt; \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 &lt; 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$. </p> <p>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.</p> http://mathoverflow.net/questions/43148/basic-results-with-three-or-more-hypotheses/43214#43214 Answer by Louigi Addario-Berry for Basic results with three or more hypotheses Louigi Addario-Berry 2010-10-22T18:10:34Z 2010-10-22T18:10:34Z <p>Here is another one: a finite irreducible aperiodic Markov chain is ergodic. </p> http://mathoverflow.net/questions/43148/basic-results-with-three-or-more-hypotheses/43169#43169 Answer by Louigi Addario-Berry for Basic results with three or more hypotheses Louigi Addario-Berry 2010-10-22T12:31:36Z 2010-10-22T12:31:36Z <p>The central limit theorem: if random variables <code>$\{X_n\}_{n \in \mathbb{N}}$</code> 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)$.</p> http://mathoverflow.net/questions/42505/is-there-an-interpretation-to-the-inverse-of-i-m-in-multitype-branching-process/42509#42509 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? Louigi Addario-Berry 2010-10-17T15:00:01Z 2010-10-17T15:00:01Z <p>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' <a href="http://www.statslab.cam.ac.uk/~james/Markov/" rel="nofollow">Markov Chains</a> for a nice introduction; it may well contain enough information for you.</p> http://mathoverflow.net/questions/117668/new-grand-projects-in-contemporary-math/117997#117997 Comment by Louigi Addario-Berry Louigi Addario-Berry 2013-03-11T13:23:19Z 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 <i>induced</i> 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. http://mathoverflow.net/questions/119797/how-random-are-random-spanning-trees/119804#119804 Comment by Louigi Addario-Berry Louigi Addario-Berry 2013-01-25T13:28:52Z 2013-01-25T13:28:52Z (First paragraph, I mean.) http://mathoverflow.net/questions/119797/how-random-are-random-spanning-trees/119804#119804 Comment by Louigi Addario-Berry Louigi Addario-Berry 2013-01-25T13:28:32Z 2013-01-25T13:28:32Z Aldous points out in the first line of this article (<a href="http://stat-www.berkeley.edu/~aldous/Papers/me49.pdf" rel="nofollow">stat-www.berkeley.edu/~aldous/Papers/me49.pdf</a>) that the distribution is not the uniform distribution. http://mathoverflow.net/questions/115276/reference-for-almost-all-graphs-have-diameter-2/115296#115296 Comment by Louigi Addario-Berry Louigi Addario-Berry 2012-12-03T19:59:25Z 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. http://mathoverflow.net/questions/90953/induced-paths-of-order-4 Comment by Louigi Addario-Berry Louigi Addario-Berry 2012-03-12T14:09:42Z 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 &quot;induced&quot;, 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. http://mathoverflow.net/questions/85196/distribution-of-big-component-of-set-partitions/85270#85270 Comment by Louigi Addario-Berry Louigi Addario-Berry 2012-01-10T02:08:52Z 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. http://mathoverflow.net/questions/79534/length-of-the-last-edge-when-visiting-points-by-nearest-neighbor-order/79687#79687 Comment by Louigi Addario-Berry Louigi Addario-Berry 2011-11-01T23:29:06Z 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. http://mathoverflow.net/questions/71393/can-you-prove-that-hypergraphs-with-n-1-edges-are-partially-2-colorable/71401#71401 Comment by Louigi Addario-Berry Louigi Addario-Berry 2011-07-28T02:28:04Z 2011-07-28T02:28:04Z Nice argument, Andrew. http://mathoverflow.net/questions/67192/exactly-simulating-a-random-walk-from-infinity/67215#67215 Comment by Louigi Addario-Berry Louigi Addario-Berry 2011-06-10T00:14:53Z 2011-06-10T00:14:53Z Sorry, Ori. No way to edit comments either! My error will live for all time. http://mathoverflow.net/questions/67192/exactly-simulating-a-random-walk-from-infinity/67215#67215 Comment by Louigi Addario-Berry Louigi Addario-Berry 2011-06-09T13:00:48Z 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$. http://mathoverflow.net/questions/66595/counting-subtrees-of-a-random-tree-random-catalan-numbers/66883#66883 Comment by Louigi Addario-Berry Louigi Addario-Berry 2011-06-07T17:56:09Z 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. http://mathoverflow.net/questions/64396/blocking-visibility-with-cylinders Comment by Louigi Addario-Berry Louigi Addario-Berry 2011-05-10T23:28:18Z 2011-05-10T23:28:18Z What about in four dimensions? http://mathoverflow.net/questions/63789/probability-of-a-random-walk-crossing-a-straight-line Comment by Louigi Addario-Berry Louigi Addario-Berry 2011-05-09T15:54:03Z 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. http://mathoverflow.net/questions/3044/tools-for-collaborative-paper-writing/62397#62397 Comment by Louigi Addario-Berry Louigi Addario-Berry 2011-04-20T15:45:31Z 2011-04-20T15:45:31Z This actually looks amazingly good. First online LaTeX editor I can actually imagine using. http://mathoverflow.net/questions/62017/guessing-the-mean-of-a-drifted-brownian-motion Comment by Louigi Addario-Berry Louigi Addario-Berry 2011-04-17T13:33:14Z 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.