# Nick B.

 175 Reputation 164 views

## Registered User

 Name Nick B. Member for 2 years Seen Apr 14 at 4:44 Website Location Cambridge, MA. Age
Interested in Complexity theory.
 Jan24 revised Decomposition of projectors: A generalized formatedited tags; edited title Jan20 asked Decomposition of projectors: A generalized format Dec7 awarded ● Commentator Dec6 comment Existence of (Cut-Based) pseudorandom graphs beating the random graphSecond 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? Dec6 comment Existence of (Cut-Based) pseudorandom graphs beating the random graphWe 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 Dec6 comment Existence of (Cut-Based) pseudorandom graphs beating the random graphThis 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. Dec5 comment Existence of (Cut-Based) pseudorandom graphs beating the random graphThe 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. Dec5 revised Existence of (Cut-Based) pseudorandom graphs beating the random graphadded 1 characters in body; edited title Dec5 asked Existence of (Cut-Based) pseudorandom graphs beating the random graph Dec4 comment The minimum size of Max-Cut for graphs of half densityThanks! 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. Dec3 revised The minimum size of Max-Cut for graphs of half densityedited title Dec3 revised The minimum size of Max-Cut for graphs of half densityadded 2 characters in body; added 34 characters in body; added 127 characters in body Dec3 awarded ● Editor Dec3 revised The minimum size of Max-Cut for graphs of half densityedited tags; edited title Dec3 asked The minimum size of Max-Cut for graphs of half density