User michal kotowski - MathOverflow

Spectral gap for random bipartite regular graphs

2011-05-16T19:18:48Z

For a graph $G$, let its Laplacian be $\Delta = I - D^{-1/2}AD^{-1/2}$, where $A$ is the adjacency matrix, $I$ is the identity matrix and $D$ is the diagonal matrix with vertex degrees. I'm interested in the spectral gap of $G$, i.e. the first nonzero eigenvalue of $\Delta$, denoted by $\lambda_{1}(G)$.

Is it true that a randomly chosen (with uniform distribution) $d$-regular bipartite graph on $(n, n)$ vertices (with multiple edges allowed) has, with probability approaching $1$ as $n \to \infty$, $\lambda_1$ arbitrarily close to $1$ (i.e. we can make arbitrarily close by taking $d$ large enough)?

If yes, is there a reference for this fact?

Proofs of expanding properties for random regular graphs which I have found in the literature usually give the probability only bounded from below by a constant, i. e. $1/2$, although I imagine that actually almost all random graphs have good spectral gap.

Note: by $d$-regular bipartite graph I mean a graph in which each vertex (on the left and on the right) has degree $d$.

Unexpected applications of Dvoretzky's theorem

2010-11-16T20:00:41Z

Dvoretzky's theorem is a classic of convex geometry. Recently at a conference in quantum information I learned (from Patrick Hayden's talk) about a nontrivial application of the theorem to a problem in quantum cryptography (which was solved previously, but using more complicated tools). What are the unexpected applications of Dvoretzky's theorem that you have heard of, if any?

(by "unexpected" I mean applying it to a problem which is not directly connected to convex geometry, functional analysis etc. or perhaps is connected, but requires phrasing the problem in a different language in a non-obvious way)

Answer by Michal Kotowski for Simple uses for the Entropy bound on the volume of a Hamming ball

2012-08-01T20:16:04Z

A nice application is showing that every Cayley graph of an Abelian group with a set of generators of logarithmic size has also logarithmic diameter.

More precisely, let $G$ be an Abelian group and let $S$ be a symmetric generating set for $G$ of size $d = c_{0} \log n$ (where $n = |G|$ and $c_{0} > 0$ is a constant. Then for any $c_{1} > 0$ such that: $$ (c_{0} + c_{1})H(\frac{c_{1}}{c_{0} + c_{1}}) < 1 $$

we have $diam(G) \geq c_{1} \log n$, where $diam(G)$ is the diameter of the Cayley graph of $G$ with generating set $S$.

The proof uses a simple observation that the number of distinct pairs of endpoints of paths of length $l$ is at most $\binom{d+l}{l}$, since to determine an element of $G$ as a word in generators we only need to specify which generator appears how many times (because of commutativity the order is unimportant). So we have: $$ \sum\limits_{l=0}^{c_{1} \log n} \binom{c_{0}\log n + l}{l} \leq 2^{(c_{0} + c_{1})H(\frac{c_{1}}{c_{0} + c_{1}}) \log n} < n $$ so the number of vertices reachable from a fixed vertex by a path of length $l \leq c_{1}\log n$ is strictly smaller than $n$. This implies that $diam(G) \geq c_{1}\log n$.

This fact is used by Newman and Rabinovich in "Hard Metrics From Cayley Graphs Of Abelian Groups" to give a simple example of an $n$-point metric space which requires distortion $\Omega(\log n)$ to embed it into $\ell_{2}$.

Inequality for the first Fourier level of a Boolean function

2012-02-22T00:12:09Z

In the study of Boolean functions, the hypercontractive inequality enables one to bound from above the norm of $Tf$ by some norm of $f$, where $T$ is the noise operator depending on the noise parameter. This can be written in terms of the Fourier transform of $f$ as (in a special case of $q=2$):

$\left( \sum\limits_{S \subseteq [n]} (p - 1)^{|S|} \widehat{f}(S)^2 \right)^{1/2} \leq \left( \frac{1}{2^n} \sum\limits_{x \in (0,1)^n} |f(x)|^p \right)^{1/p}$

However, this involves all Fourier levels of $f$. In the application I have in mind, I'm interested only in bounding the norm of the first level of $f$, i.e. restricting the sum on the left to $|S| = 1$. Is it possible to give any inequality of this kind, probably with a different right hand side (but still involving some information about the norm of $f$) and some additional assumptions on $f$? If it's impossible for some trivial reasons, let me know anyway.

Here I'd be mostly interested in matrix-valued Boolean functions (see for example http://arxiv.org/abs/0705.3806), although any answer would be appreciated.

Inner products and Gaussian integration over intersection of halfspaces

2012-08-06T03:06:39Z

Let $v$ be a unit vector in $\mathbb{R}^{n}$ and consider arbitrary unit vectors $w_1, w_2, \ldots, w_k$ also in $\mathbb{R}^n$. Let $g$ be a standard Gaussian random vector in $\mathbb{R}^n$. I'm interested in finding a formula for

$$ \mathbb{E_g} \left( \langle g, v \rangle f(\arg \max_{i} \langle g, w_i \rangle) \right)$$

where the expectation is with respect to $g$ and $f(j)$ is equal to $1$ if $j=1$ and $-\frac{1}{k-1}$ otherwise (so $f$ chooses $w_i$ which is closest to the random vector).

Ideally I'd like to express this quantity in terms of inner products $\langle v_1, w_i \rangle$. Sorry if the anser is easy, but here we are essentially integrating a Gaussian variable over sets defined by intersections of halfspaces (as $\arg \max_{i} \langle g, w_i \rangle) = j$ means that $\langle g, w_j \rangle \geq \langle g, w_i\rangle$ for $i \neq j$) and it doesn't seem trivial to me.

Note that it is possible to calculate a somewhat similar integral in a simpler case: for any unit vectors $u,v$ we have: $$ \mathbb{E_g}\left(\langle g, u \rangle sgn(\langle g, v \rangle) \right) = C\langle u, v\rangle $$ for an explicit constant $C$ (this is a simple exercise in Gaussian integration).

Set of unitaries with "spread-like" properties

2012-07-06T18:53:31Z

I'm interested in finding two sets of $N$ unitary $N \times N$ matrices $U_{1}, \ldots, U_{N}$, $V_{1}, \ldots, V_{N}$ such that:

$ \sup\limits_{X, Y}\sum\limits_{j,k = 1}^{N} |\mathrm{Tr}(YU_{j}XV_{k}^{\ast})|^2 \ll N$

where the sup is over all Hermitian traceless matrices with Frobenius norm $1$ nad $\ll$ means that the sum is asymptotically smaller than $N$.

The motivation comes from a problem in quantum information theory. An explicit construction of such sets of $U_{j}$ and $V_{k}$ would be the most desirable result, although pseudorandom constructions would also be very interesting. This statement is true if instead of taking unitaries we take matrices with independent Gaussian entries (rescaled properly so that on average each column has norm 1 etc.); however, I don't know how to show that random unitaries satisfy this property, so a hint for such a proof would also be welcome.

I would like to think of such unitaries as having some sort of "spread" property similar to objects showing up in the study of pseudorandomness like mutually unbiased bases, randomness extractors etc. However, I'm not sure if there is any definite connection to those notions.

Concentration of functions of random unitary matrices

2012-05-19T23:23:47Z

Suppose $U$ and $V$ are $n \times n$ random unitary matrices, chosen independently from the Haar measure. Is there any kind of concentration inequality which would be applicable to polynomials $p(U,V)$ in entries of $U$ and $V$? More specifically, I am interested in polynomials of the form:

$ \sum U_{ij}V_{i'j'} X_{ii'}Y_{jj'}$

$ |\sum U_{ij}V_{i'j'} X_{ii'}Y_{jj'}|^2$

where $X$ and $Y$ are some arbitrary matrices and the sum is over all indices. For matrices with i.i.d. Gaussian entries there are well-known concentration bounds for this kind of expressions, I would like to know if there is anything similar for unitary matrices (for this case or for $U=V$).

Tensors with low spectral norm

2012-05-16T20:03:03Z

Consider a tensor $T$ with six indices, $T_{(ii')(jj')(kk')}$, where each index goes from $1$ to $n$. We can think of $T$ as a linear map from $\mathbb{R}^n \otimes \mathbb{R}^n \otimes \mathbb{R}^n$ to itself and consider its spectral norm:

$ \Vert T \Vert_{\infty} = \sup \vert \sum T_{(ii')(jj')(kk')} x_{ijk}y_{i'j'k'}\vert $

where the supremum is taken over all unit vectors $x,y \in \mathbb{R}^n \otimes \mathbb{R}^n \otimes \mathbb{R}^n$.

On the other hand $T$ can also be viewed as trilinear form on $n$-dimensional matrices, so we can define a norm:

$ \Vert T \Vert_{2,2,2} = \sup \vert \sum T_{(ii')(jj')(kk')} X_{ii'} Y_{jj'}Z_{kk'}\vert $

where the supremum is over all matrices $X,Y,Z$ of Frobenius norm $1$.

What are the examples of tensors which have high (as $n \to \infty$) spectral norm as linear maps, but low norm as trilinear forms?

Since the question is admittedly rather general, let's specialize to tensors of a more special form, namely $T_{(ii')(jj')(kk')} = g_{ijk}h_{i'j'k'}$, where $g,h \in \mathbb{R}^n \otimes \mathbb{R}^n \otimes \mathbb{R}^n$, so that $T = gh^{T}$ as a linear map. Then its spectral norm is simply $\Vert g\Vert \cdot \Vert h\Vert$. Taking $g$ and $h$, say, to be unit vectors, how should we choose them to get a low trilinear norm:

$\Vert T \Vert_{2,2,2} = \sup \vert \sum g_{ijk}h_{i'j'k'} X_{ii'} Y_{jj'}Z_{kk'}\vert $ ?

It can be shown that randomly chosen $g, h$ will have the desired property, but I'm interested in more explicit examples. Because there is no direct analog of the spectral decomposition for tensors, the intuition that the "mass" of $T$ should be "spread out" roughly in all directions (as in the case of matrices with low spectral norm, but high Frobenius norm) on the $\mathbb{R}^{n^2}$ components of the tensor product is not easy to formalize.

Derandomizing random matrices

2012-02-06T19:48:56Z

My question is rather general - what is known about derandomization of results in random matrix theory, high-dimensional geometry, Banach spaces etc. using probabilistic constructions (like estimates of eigenvalues, Dvoretzky's theorem, metric embeddings)? Here I'm interested both in fully explicit counterparts of random constructions as well as "pseudorandom" (in some sense) examples, using "less" randomness than, say, filling every entry of a matrix with a random variable etc. For example - suppose we know that for a fixed norm an n x n matrix with IID standard gaussian entries has "large" norm with high probability. How to find an explicit infinite family of such matrices?

My question is rather vague, of course I have a specific application of this kind of results in mind, but at this moment I am more interested in general methodology of constructing "derandomized" examples, where to start looking for such objects etc. My only contact so far with pseudorandomness has been in the context of spectral graph theory, expander graphs, property (T) etc., I'm not sure if this perspective is relevant for high-dimensional geometry.

I'd be grateful for any hints, references or advice on who may know this kind of things.

Casual tours around proofs

2011-11-09T04:33:58Z

(this is basically the same question, only in math, as Alessandro Cossentino asked about theoretical computer science at TCS.SE: http://cstheory.stackexchange.com/questions/8869/casual-tours-around-proofs; if a question similar to this one already exists at MO, feel free to close this)

Recently Ryan Williams published (see http://arxiv.org/abs/1111.1261) a more "pedagogical" version of his proof in complexity theory concerning NEXP and ACC - in his own words, "the proof will be described from the perspective of someone trying to discover it". The paper discusses more intuition, failed attempts at solving the problem etc. much more extensively than a typical journal paper.

Personally I find such efforts extremely valuable, because they give you an opportunity to learn how somebody thinks about mathematics and not only verify the formal correctness of some abstract reasoning.

What other examples of such approach are you aware of?

Vector bundles on graphs

2011-10-29T17:58:32Z

Vector bundles over manifolds have fundamental importance in differential geometry, algebraic topology etc. Are there any applications of this concept (or some variation of it) for graphs (finite or infinite)?

The only place I have seen something like this is in a paper on spanning forests by Kenyon, where the application seems somewhat specialized.

Random versions of deterministic problems

2011-05-20T16:08:17Z

What are the examples of situations where "randomizing" a problem (or some part of it) and analyzing it using probabilistic techniques yields some insight into its deterministic version?

An example of what I have in mind: it is a well-known conjecture that the Hausdorff dimension of the graph of Weierstrass function (everywhere continuous, nowhere differentiable) is given by a certain simple formula, depending on the amplitudes and phases of the cosines in the series. This is still open; however, in the paper "The Hausdorff Dimension of Graphs of Weierstrass Functions" Hunt proved that if you add a uniformly distributed independent random "noise" to each phase, the conjectured formula holds with probability 1. So while the "randomized" approach does not solve the original problem, it somehow lends credibility to the original conjecture and thus gives us some insight about the problem.

Random bipartite graphs

2011-09-23T18:14:57Z

Consider the following situation: I have a set $A$ of $n$ vertices and a set $B$ of $N = n^2$vertices. I consider the bipartite graph $(A, B)$ and put at random $M = n^{1 + \varepsilon}$ edges (or I could put each edge independently with probability $p$ such that $pnN = M$, this shouldn't make a big difference). Then I remove the isolated vertices from $B$, so effectively I get vertex sets of size $n$ and $\Theta(n^{1 + \varepsilon})$.

Are there any references on how in general such bipartite random graphs look like (their degree sequence, connectivity etc.)? The model considered above is rather specific, however, I'd be happy with any references on bipartite graphs on $(n, N)$ vertices, where $N$ depends on $n$ (or information on how can one tackle them with techniques similar to ordinary random graphs; in this context it isn't clear to me whether we should treat the graph as a "sparse" or a "dense" one).
Ultimately I'm interested in spectral properties of such a graph (or rather a slight modification of it). What can be said about the second largest eigenvalue of its adjacency matrix or Laplacian? Now suppose that we take a union of this graph and a "good" graph (possibly also random) on the set $A$ only (by "good" I mean it has good spectral properties, I'm not trying to be very specific here). What can be said about eigenvalues of this graph?

Eigenfunctions of random graphs

2011-09-13T17:44:24Z

Consider a random $d$-regular graph on $n$ vertices. What can be said about its nontrivial (i.e. orthogonal to the constant) eigenfunctions? For example, I'm interested whether there are "nodal zones", i.e. if the graph can be divided into groups such that the eigenfunction has the same sign on every vertex of the same groups. Are there any results of this kind?

Another question - suppose I divide the graph arbitrarily into $k$ groups of vertices ($k$ may depend on $n$); is it possible to say something about how large the sum of eigenfunction's values on one group typically is?

Answer by Michal Kotowski for Interesting and Accessible Topics in Graph Theory

2011-05-10T09:25:42Z

I think that presenting the connection between random walks and electrical networks (like in the classic text "Random walks and electric networks" by Doyle and Snell) is an interesting and feasible idea. Just a week ago I taught a 6-day course about this to talented high schoolers and it worked out very nicely. It's a good opportunity to show them interesting applications of probability and give a flavour of a vibrant field of mathematics. Plus, there is a quite a lot of room for digressions on Markov chains, spectral graph theory etc.

Path integrals outside QFT

2010-04-05T17:43:10Z

The main application of Feynman path integrals (and the primary motivation behind them) is in Quantum Field Theory - currently this is something standard for physicists, if even the mathematical theory of functional integration is not (yet) rigorous.

My question is: what are the applications of path integrals outside QFT? By "outside QFT" I mean non-QFT physics as well as various branches of mathematics.

(a similar question is http://mathoverflow.net/questions/19490/doing-geometry-using-feynman-path-integral, but it concerns only one possible application)

Answer by Michal Kotowski for Why semigroups could be important?

2011-02-18T19:03:57Z

An important application of semigroups and monoids is algebraic theory of formal languages, like regular languages of finite and infinite words or trees (one could argue this is more theoretical computer science than mathematics, but essentialy TCS is mathematics).

For example, regular languages can be characterized using finite state automata, but can also be described by homomorphisms into finite monoids. The algebraic approach simplifies many proofs (like determinization of Buchi automata for infinite words or proving that FO = LTL) and gives deeper insight into the structure of languages.

Liouville property in Z^d

2011-01-13T12:34:52Z

It is well known that $\mathbb{Z}^d$ has Liouville property, i. e. every bounded harmonic function on this graph is constant.

(harmonic means that the value of $f$ in a point $x$ is equal to the average of $f$ over neighbours of $x$ in the lattice $\mathbb{Z}^d$).

What are the nicest/shortest/most ingenious proofs of this fact that you know?

Answer by Michal Kotowski for Computer Science for Mathematicians

2011-01-05T18:05:02Z

"Computational Complexity"by Christos Papadimitriou - very good introduction to logic/theory of computation (Turing machines etc.) and computational complexity. One of the best textbooks IMHO.

Spectrum of the Laplacian on G(n, p) and G(n, M)

2010-11-29T19:31:52Z

A random graph in $G(n, p)$ model is a graph on $n$ vertices in which for each of the $n\choose{2}$ edges we independently flip a coin, then take the edge with probability $p$ or remove it with $1 - p$.

A random graph in $G(n, m)$ model is a graph on $n$ vertices in which a subset of edges of a fixed size $m$ is chosen at random.

We expect $G(n, p)$ and $G(n, m)$ for $m = p {n\choose{2}}$ to look asymptotically the same, because the number of edges in $G(n, p)$ is highly concentrated around the mean.

The (normalized) Laplacian $L$ on a graph is an operator (matrix) which has entries:

$L(v, v) = 1$

$L(v, w) = - \frac{1}{\sqrt{deg(v)deg(w)}}$

where $v \neq w$ are vertices of the the graph.

We are interested in $\lambda_{2}$, that is, the smallest nonzero eigenvalue of $L$. Suppose we know that, for $p = p(n)$ growing sufficiently fast (papers by Chung et al. show that, for example, $p \geq \frac{\log^2 n}{n}$), $\lambda_{2}$ for a random graph in $G(n, p)$ model is close to 1 with high probability (i. e. approaching 1).

Does it follow immediately that also in $G(n, m)$ we have $\lambda_{2} \to 1$ with high probability? It is known in random graph theory that such implications hold for monotone properties (that is, properties which still hold after adding an edge to the graph), however, the second eigenvalue is not monotone (although it is probably "monotone on average", so I expect the statement above is true for $G(n, m)$).

Applications of classical field theory

2010-07-07T13:13:02Z

What are the applications (physical and mathematical) of classical field theory beyond electrodynamics and gravity?

By such applications, I mean that either the field theory viewpoint adds some genuinely new insight into the underlying physics or that it gives rise to interesting mathematical problems. So I'm not thinking about:

-field-theoretical description of something that is very well understood with other tools (for example, describing classical electrodynamics in language of fibre bundles, differential forms etc. is very nice and elegant, but doesn't add much to physics)

-quantum field theory (in QFT you always write down the classical lagrangian and then turn the fields into operators, but there is not much actual classical field theory here)

Of course, you can always write some lagrangian like phi^34 + 14*phi^8 + ..., and study the resulting PDE (existence and uniqueness of solutions etc.), but I guess that lacks real motivation.

Geometric group theory and analysis

2010-03-14T12:47:12Z

Geometric group theory is mainly concerned with topological and geometric properties of groups, spaces on which they act etc., so the ideas employed in GGT are mainly algebraic/geometric/topological. Is there any subfield of GGT where methods from analysis find applications? I once heard that analytical tools, e. g. geodesic flows, are used in studying ends of groups, but that's all I know.

Automatic groups - recent progress

2010-01-07T09:36:47Z

Epstein's (et al.) "Word Processing in Groups" is a quite comprehensive monograph on automatic groups, finite automata in geometric group theory, specific examples like braid groups, fundamental groups of 3-dim manifolds etc. However, the book is from 1992, so much of the material summarizes research done by Cannon, Thurston, Holt etc. back in the '80s. I'm interested in how the theory of automatic groups (and, more generally, applications of formal languages in group theory) has progressed since then - have there been any significant new results, open problems, novel ideas, examples?

Comment by Michal Kotowski

2013-04-14T23:58:26Z

You are right, the question is trivial, I'll delete it.

Comment by Michal Kotowski

2012-10-20T21:22:42Z

I second that, a very nice notion :). I think I know what fedja is referring to, but it'd still be great to get some more explanation.

Comment by Michal Kotowski

2012-07-29T22:07:55Z

A very appropriate comment for this sort of question.

Comment by Michal Kotowski

2012-07-13T16:10:26Z

Thanks! I will read the answer more carefully later, but it seems that it solves the the question about random unitaries. Can you provide a reference for "by standard random matrix/free probability facts"? I know a little about random matrix theory, though not that much, and hardly anything about free probability.

Comment by Michal Kotowski

2012-06-14T16:49:59Z

I think you are overestimating the difficulty of its proof. While it is not trivial, it is something standard and covered without any problem in a functional analysis course. If the proof is overlooked, that's probably usually because of, well, oversight, not because it is too complicated to be understood by the ordinary analyst.

Comment by Michal Kotowski

2012-06-01T19:12:46Z

@Agol: which result from Żuk's paper are you referring to?

Comment by Michal Kotowski

2012-02-07T16:20:32Z

@Mark: thanks! Are there such constructions for other properties of random matrices apart from RIP (and stuff related to compressed sensing)?

Comment by Michal Kotowski

2012-02-06T20:34:25Z

@Bill Johnson: if you have any suggestions for references or substantive comments, please consider putting them in an answer - that would be helpful!

Comment by Michal Kotowski

2011-11-17T02:00:39Z

IMHO titles like "A note on ..." should be avoided, unless the title is long enough to make completely unambiguous what specific problem (conjecture etc.) is the topic of the paper. I guess everybody would be hard pressed to say what e.g. "A note on a problem of Erdos" is really about. One should aim to make the title as informative as possible.

Comment by Michal Kotowski

2011-10-29T19:38:41Z

@Charlie Frohman: any reference?

Comment by Michal Kotowski

2011-07-31T20:18:14Z

I can't help but add a comment - while the question is probably meant to be read by experts in string theory, it never hurts to formulate it so that a layman (i.e. a mathematician from other field) can at least have a clue about what's going on...

Comment by Michal Kotowski

2011-05-15T20:56:55Z

This attitude has a downside, namely it leads to proliferation of references to papers which have gaps, errors, are incomplete etc. I don't want to use specific names, but it certainly happens that a widely cited paper has gaps in the proofs or is faulty in some way, which those citing it may not be aware of (because they haven't read it and, well, if so many people have cited it before, it "has" to be correct...).

Comment by Michal Kotowski

2011-05-15T20:50:24Z

Could you maybe provide some background on the problem, or at least relevant definitions etc.?

Comment by Michal Kotowski

2011-05-10T15:33:33Z

Of course you can't treat this topic extensively, but mentioning expanders, the fact that their geometric properties are connected to the mixing rate of the random walk and can be analyzed algebraically is surely doable as a digression (as well as things like PageRank or random graphs).

Comment by Michal Kotowski

2011-05-03T08:11:11Z

It has already been mentioned (and it appeared on the Arxiv some time ago).