Timeline for almost-bipartite nearly-isolated subgraphs
Current License: CC BY-SA 3.0
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 21, 2012 at 17:53 | answer | added | Ani from Asat forum | timeline score: 2 | |
| May 25, 2012 at 11:22 | history | bounty ended | Felix Goldberg | ||
| May 24, 2012 at 11:29 | history | edited | Felix Goldberg | CC BY-SA 3.0 |
added 62 characters in body
|
| May 22, 2012 at 0:08 | comment | added | Felix Goldberg | A constant fraction will be better, I think. You are probably right about the Paley graphs, I managed to pick like the worst possible example... Any other suggestions perhaps? | |
| May 21, 2012 at 19:05 | comment | added | Kevin P. Costello | What range are you considering here when you say "relatively large"? Do you want $B$ to be a constant fraction of $G$, or $n^{\alpha}$ vertices for some $0<\alpha<1$? If the former, Paley graphs may not be the best bet, as they're quasirandom in the sense of Chung-Graham-Wilson (have large eigenvalue gap; equiv. all large subsets of vertices span about the same number of edges) -- I think if you work through their bounds you get that the Paley graph has no nearly bipartite subgraphs of size larger than $q^{1/2+\epsilon}$ vertices, and you might be able to get better bounds by number theory. | |
| May 21, 2012 at 10:20 | history | edited | Felix Goldberg | CC BY-SA 3.0 |
added 83 characters in body
|
| May 18, 2012 at 13:50 | comment | added | Felix Goldberg | What are 'twisted product graphs'? I found this presentation (math.unl.edu/~adonsig1/SS6A/Wright.pdf) that mentions such a concept but I'm not sure if that's what you meant. | |
| May 18, 2012 at 13:14 | comment | added | Gerhard Paseman | You might consider k-partite graphs with large bipartite compnent or certain mixed product or twisted product graphs. Gerhard "Ask Me About System Design" Paseman, 2012.05.18 | |
| May 18, 2012 at 11:34 | history | edited | Felix Goldberg | CC BY-SA 3.0 |
added 275 characters in body; edited tags
|
| May 18, 2012 at 11:17 | history | bounty started | Felix Goldberg | ||
| May 15, 2012 at 9:17 | history | asked | Felix Goldberg | CC BY-SA 3.0 |