most recent 30 from http://mathoverflow.net 2013-06-19T09:06:10Z http://mathoverflow.net/feeds/user/13284 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/119430/decomposition-of-projectors-a-generalized-format Nick B. 2013-01-20T22:24:47Z 2013-01-24T20:12:50Z

<p>Let $V=\mathbb C^n$ be a vector space with (linear) maps $P_1:V\rightarrow V$ and $P_2:V\rightarrow V$ that are projectors , i.e. they satisfy $P_i^2=P_i$.</p> <p>It is not hard to understand the structure of such a pair. One could see that $P_i$'s can be simultaneously block diagonalized with blocks of size $2$. For this see, <a href="http://en.wikipedia.org/wiki/Principal_angles" rel="nofollow">http://en.wikipedia.org/wiki/Principal_angles</a> and also for example paper of Halmos with the title "two subspaces".</p> <p>My question is about a generalization of this to pairs of $P_1, P_2$ where $P_i$'s satisfy a different (simple) algebraic relation say $P_i^3= P_i$.</p> <p>I want to see whether they can be block-digonalized with blocks of size $O(1)$ independent of $n$. </p>

http://mathoverflow.net/questions/115457/existence-of-cut-based-pseudorandom-graphs-beating-the-random-graph Nick B. 2012-12-05T01:16:30Z 2012-12-06T20:50:59Z

<p>The question is simply this: Does there exist a (family of) graph $G=(V,E)$ such that $\max_{S\subset V} |E(S,S^c)- \frac{|S||S^C|}{2}|\leq o(n^{3/2})$. Such graphs would be very pseudorandom as the edge density of all their cuts would be extremely close to the expected value if we had picked each edge with probability a half. </p> <p>Background: As discussed in the following Math-overflow question <a href="http://mathoverflow.net/questions/53389/max-cut-value-in-a-random-graph" rel="nofollow">http://mathoverflow.net/questions/53389/max-cut-value-in-a-random-graph</a>, with high probability a random $G(n,\frac{1}{2})$ graph has a cut $(S,S^c)$ with more than $\frac{n^2}{8}+\Omega(n^{3/2})$ edges. This implies that the following max-deviation lower bound: For almost every $G=(V,E)$ we have,</p> <p>$ \max_{S\subset V} |E(S,S^c)- \frac{|S||S^C|}{2}| = \Omega(n^{3/2})$</p> <p>This lower bound means that simply by taking a random graph you cannot solve the above problem. </p> <p>It could be true that the above for amost every graph result actually holds for every graph and this quantity is always $\Omega(n^{3/2})$. A proof of this would be quite interesting and would give evidence to a conjecture that I have in mind.</p>

http://mathoverflow.net/questions/115245/the-minimum-size-of-max-cut-for-graphs-of-half-density Nick B. 2012-12-03T05:10:12Z 2012-12-03T19:17:15Z

<p>As discussed in the following math overflow question, <a href="http://mathoverflow.net/questions/53389/max-cut-value-in-a-random-graph" rel="nofollow">http://mathoverflow.net/questions/53389/max-cut-value-in-a-random-graph</a>, the max-cut of a random graph $G(n,1/2)$ is $\frac{n^2}{8} + \Theta(n^{3/2})$ with high probability. </p> <p>My question is this: Does there exist a family of graphs with relative density about $\frac{1}{2}$ with max-cut size being $\frac{n^2}{8}+ o(n^{3/2})$? If not, can we show that every graph with $\frac{1}{2}$ relative density has a cut of size $\frac{n^2}{8} + \Omega(n^{3/2})$ ?</p> <p>(It is possible that any of the well-known explicit pseudorandom graphs with $\frac{1}{2}$ relative density,such as Paley graphs and etc, will satisfy this property but I haven't been able to verify whether this is the case or not by looking at a few survey papers.)</p>

http://mathoverflow.net/questions/81012/a-simple-stopping-time-problem Nick B. 2011-11-15T23:01:34Z 2012-04-12T08:48:27Z

<p>This should be rather standard so I hope somebody with a good background in probability theory would give me a quick solution or a reference.</p> <p>We are given a threshold positive integer $T>0$. Let $a_1=1$ and for all $k$ with probability one half set $a_k=3a_{k-1}$ or else $a_k=2a_{k-1}$. We will stop the process at smallest time $\tau$ when $a_{\tau} \geq T$. We would like to compute the constant $c$ defined to be,</p> <p>$ E[ \sum_{i=1}^{\tau} a_i ] = c T + o(T) $</p> <p>Could you estimate $c$ ?</p>

http://mathoverflow.net/questions/56853/deterministic-coupling-of-probability-measures-with-a-constrained-support-conditi Nick B. 2011-02-27T21:56:22Z 2011-02-27T21:56:22Z

<p>The following question has come up while working on my senior thesis: Assume $\mu$ and $\nu$ are regular probability measures on $\mathbf{R}^n$. We are also given a coupling $\gamma$ of $\mu$ and $\nu$ such that if $(x,y)\in Supp(\gamma)$ then $|x-y| \leq 1$. So basically given random variable $X$ based on $\mu$ and another one $Y$ based on $\nu$ we know $|X-Y|\leq 1$ with probability $1$. </p> <p>Now additionally assume $\mu$ is absolutely continuous with respect to Lebesgue measure. Show that there is a deterministic coupling of $\mu$ and $\nu$, i.e. a Borel mapping $s:\mathbf{R}^n \rightarrow \mathbf{R}^n$ such that $s$ pushes $\mu$ forward to $\nu$.</p> <p>Note that this is true in dimension $1$ by taking monotone measure preserving map.</p>

http://mathoverflow.net/questions/115457/existence-of-cut-based-pseudorandom-graphs-beating-the-random-graph/115641#115641 Nick B. 2012-12-06T23:50:11Z 2012-12-06T23:50:11Z

Second comment: I don't see why your argument resolves the general case. I might be making a silly mistake but consider the following: Let $G$ be (a family) of counterexample to above,i.e. $|E(S,S^c)-|S||S^c|/2|\leq o(n^{3/2})$ .Then use your above construction to take $E(S,T)\geq 1/2 |S||T|+ \Omega(n^{3/2})$ .Let $U=(S\cup T)^c$. Apply the assumptions above to the cuts $(S, U\cup T)$ and $(T,S \cup U)$. This will imply that $E(S,U)≤\frac{|S||U|}{2}−\Omega(n^{3/2})$ and similarly for $(S,T)$. But this would imply a large deviation in the cut $(S\cup T,U)$. Doesn't it?

http://mathoverflow.net/questions/115457/existence-of-cut-based-pseudorandom-graphs-beating-the-random-graph/115641#115641 Nick B. 2012-12-06T22:53:04Z 2012-12-06T22:53:04Z

We wouldn't be done with the reduction yet because the &quot;cut&quot; that we get in $G$ might be in the form $(S,T)$ such that $S\cap T\neq \emptyset$. But I think in that case if $S\cap T$ is large enough to be annoying, you should be able to still get the desired result by taking the intersection $S\cap T$ and taking a random cut across it. You basically reduce to the case that if a graph has relative density bounded away from 1/2 the above result is easy by taking random cuts. I hope the hand-wavy argument above actually goes through

http://mathoverflow.net/questions/115457/existence-of-cut-based-pseudorandom-graphs-beating-the-random-graph/115641#115641 Nick B. 2012-12-06T22:22:13Z 2012-12-06T22:22:13Z

This is really interesting. I have two comments: First of all, Can't you deduce the general statement of your weak form a reduction: Let G=(V,E) be our graph and Take G1 and G2 to be two copies of G. Take G′=$G_1\cup G_2$ and now connect $v\in G_1$ with $u\in G_2$ if their preimage in G were not connected. Now the relative degree of each vertex would be 1/2 in G′. Now any cut ,or weak-cut, deviation in G′ will manifest itself with deviation in G losing a factor of 1/4 in the reduction.

http://mathoverflow.net/questions/115457/existence-of-cut-based-pseudorandom-graphs-beating-the-random-graph Nick B. 2012-12-05T18:20:58Z 2012-12-05T18:20:58Z

The approach of taking a random partition and analyzing higher moments would probably not be sufficiently strong to prove this. But one approach could be to use the fact that we know this for random graphs, and hence for graphs $O(n^{3/2})$ close to random graphs. And given a graph G we have to see what this non-randomness can give us. Maybe in graphs far away from random one can use a random partition to achieve this. (indeed if the relative density is bounded away from 1/2 this works)Also some have suggested that maybe \emph{discrepancy theory} is the keyword in this problem.

http://mathoverflow.net/questions/115245/the-minimum-size-of-max-cut-for-graphs-of-half-density/115326#115326 Nick B. 2012-12-04T03:01:06Z 2012-12-04T03:01:06Z

Thanks! I don't know how I didn't see that myself! But for the application that I had in mind what is really necessary is that a graph $G=(V,E)$ such that for any $S\subset V$ we have $|E(S,S^c)-\frac{|S||S^c|}{2}|\leq o(n^{3/2})$. Maybe I ask about the existence of such graphs in another question.

http://mathoverflow.net/questions/81012/a-simple-stopping-time-problem/81019#81019 Nick B. 2011-11-16T05:52:03Z 2011-11-16T05:52:03Z

please do, Ori !

http://mathoverflow.net/questions/81012/a-simple-stopping-time-problem/81019#81019 Nick B. 2011-11-16T01:31:37Z 2011-11-16T01:31:37Z

yes I think that is not a $1$ ; rather it is a $\frac{1}{s+1}$ but beside that I don't any possible trivial calculation problem. do you ?

http://mathoverflow.net/questions/81012/a-simple-stopping-time-problem/81019#81019 Nick B. 2011-11-16T00:57:04Z 2011-11-16T00:57:04Z

Could you comment on how you would establish the existence of the limit ?

http://mathoverflow.net/questions/56853/deterministic-coupling-of-probability-measures-with-a-constrained-support-conditi Nick B. 2011-02-27T23:05:34Z 2011-02-27T23:05:34Z

The other approach is just to look at extremal points of space of all such couplings of $\mu$ and $\nu$ and somehow show that the extremal points of this space, which exist I think by Krein_Milman, must be deterministic couplings. But I couldn't make that work either.

http://mathoverflow.net/questions/56853/deterministic-coupling-of-probability-measures-with-a-constrained-support-conditi Nick B. 2011-02-27T22:47:42Z 2011-02-27T22:47:42Z

Well, I tried the natural thing and I didn't see it working out for me. I tried approximating the costs by strictly convex costs converging to this cost and my attempt failed at multiple levels because of non-compactness of space of deterministic Borel couplings with respect to wk-* topology.(i.e. a sequence of mappings can go to a random coupling in the limit.) you can try approximate the cost in the other way, from left as opposed to right, and then your measures might not decompose in the way that is necessary for existence of mappings.