Nick B.
|
Registered User
|
Interested in Complexity theory.
|
|
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 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 |
