Timeline for What is this expander-mixing-type graph property?
Current License: CC BY-SA 3.0
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 31, 2013 at 0:01 | comment | added | Dustin G. Mixon | Wow, you're right. I ignored a log factor in $n$ on the right-hand side, thinking I didn't need it, but I do. For the sake of documentation, I found a lot of useful information by googling "graph discrepancy". | |
| Dec 30, 2013 at 23:15 | comment | added | Terry Tao | Such graphs cannot be arbitrarily large (for fixed $C$), because any sufficiently large graph of a given density will contain a copy of the complete bipartite graph $K_{m,m}$ for any fixed $m$, which will contradict your property for $m$ large enough depending on $C$. (Graphs obeying your property will have density about 1/2.) | |
| Dec 30, 2013 at 15:24 | history | asked | Dustin G. Mixon | CC BY-SA 3.0 |