Timeline for Find large "induced" bipartite graph in a dense graph?
Current License: CC BY-SA 4.0
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 15, 2019 at 14:55 | vote | accept | Connor | ||
| Mar 15, 2019 at 9:59 | answer | added | Louis Esperet | timeline score: 2 | |
| Mar 15, 2019 at 9:30 | comment | added | Louis Esperet | Ok I finally understood your question. | |
| Mar 14, 2019 at 13:28 | comment | added | Connor | @LouisEsperet Yes, but how do you guarantee the requirement $e_G(A,B)=e_H(A,B)$? | |
| Mar 14, 2019 at 13:24 | comment | added | Louis Esperet | In $G$ the minimum degree is at least $cn$ so there are at least $cn/2$ edges. | |
| Mar 13, 2019 at 17:31 | comment | added | Connor | @LouisEsperet But how if some edges between $A$ and $B$ are removed? | |
| Mar 13, 2019 at 17:26 | comment | added | Louis Esperet | If you place each vertex of $G$ in $A$ or $B$ independently at random then $A$ and $B$ are linear in $n$ and the number of edges of $G$ (or $H$) between $A$ and $B$ is at least $cn^2/4$ in expectation. | |
| Mar 13, 2019 at 0:24 | review | Suggested edits | |||
| Mar 13, 2019 at 7:49 | |||||
| Mar 13, 2019 at 0:12 | history | edited | Connor | CC BY-SA 4.0 |
added 289 characters in body
|
| Mar 13, 2019 at 0:02 | comment | added | Connor | It reflects on $e_G(A,B)=e_H(A,B)$. | |
| Mar 12, 2019 at 20:04 | history | edited | Connor | CC BY-SA 4.0 |
added 8 characters in body
|
| Mar 12, 2019 at 20:00 | comment | added | Mike | OK but I didn't get that from the way you worded your question originally. You really ought to consider editting it. | |
| Mar 12, 2019 at 19:56 | comment | added | Connor | Yes, but also with requirement that the edges between $A$ and $B$ in $G$ are same as those of $H$. | |
| Mar 12, 2019 at 19:53 | comment | added | Mike | This question is very hard to follow as written. This is how I took what you written. So you want to know if there is a dense graph $H$ that satisfies the following: Let $G$ be any subgraph of $H$ with high minimum degree, then there are two disjoint subsets $A$ and $B$ of $VG)$ such that the number of edges between $A$ and $B$ in $G$ is large. Am I correct? | |
| Mar 12, 2019 at 19:35 | history | asked | Connor | CC BY-SA 4.0 |