Nick B.
Reputation
Next privilege 100 Rep.
Edit community wikis
 Sep 24 awarded Autobiographer Jul 2 awarded Curious Jan 24 revised Decomposition of projectors: A generalized format edited tags; edited title Jan 20 asked Decomposition of projectors: A generalized format Dec 7 awarded Commentator Dec 6 comment Existence of (Cut-Based) pseudorandom graphs beating the random graph 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? Dec 6 comment Existence of (Cut-Based) pseudorandom graphs beating the random graph We wouldn't be done with the reduction yet because the "cut" 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 Dec 6 comment Existence of (Cut-Based) pseudorandom graphs beating the random graph 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. Dec 5 comment Existence of (Cut-Based) pseudorandom graphs beating the random graph 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. Dec 5 revised Existence of (Cut-Based) pseudorandom graphs beating the random graph added 1 characters in body; edited title Dec 5 asked Existence of (Cut-Based) pseudorandom graphs beating the random graph Dec 4 comment The minimum size of Max-Cut for graphs of half density 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. Dec 4 accepted The minimum size of Max-Cut for graphs of half density Dec 3 revised The minimum size of Max-Cut for graphs of half density edited title Dec 3 revised The minimum size of Max-Cut for graphs of half density added 2 characters in body; added 34 characters in body; added 127 characters in body Dec 3 awarded Editor Dec 3 revised The minimum size of Max-Cut for graphs of half density edited tags; edited title Dec 3 asked The minimum size of Max-Cut for graphs of half density Nov 16 comment A simple stopping time problem. please do, Ori ! Nov 16 comment A simple stopping time problem. 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 ?