Timeline for An optimization involving (random) graphs
Current License: CC BY-SA 3.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 31, 2013 at 12:41 | vote | accept | passerby51 | ||
| May 14, 2012 at 14:07 | comment | added | passerby51 | You are right, they originally considered the model you mentioned. However, it seems easier for me to consider G(n,p) where you pick each potential edge out of 2-subsets of [n] with probability p. | |
| May 13, 2012 at 15:39 | answer | added | Anthony Quas | timeline score: 1 | |
| May 13, 2012 at 15:17 | history | edited | Pietro Majer | CC BY-SA 3.0 |
spelling
|
| May 13, 2012 at 15:05 | comment | added | Anthony Quas | My comment was that (as I understand it) ER didn't consider random graphs where each edge shows up with probability $p$; but rather where you are told the exact number of edges to put down uniformly at random. It is not so surprising that the behaviour of these two models (putting down $pn(n-1)/2$ edges at random and putting in each edge with probability $p$) has very similar behaviour. | |
| May 13, 2012 at 6:04 | comment | added | passerby51 | @Anthony: Thanks. Yes, I am primarily interested in an Erdos-Renyi (ER) graph. I stated the problem more generally, in case it is related to a known problem. You can assume an ER graph with p = a/n, where maybe a = O(log n). Also, you can assume s/n < 1/2 and maybe $ s/n \to \gamma (0,1/2)$ as $n \to \infty$. It would be interesting to show that (max N)/n is strictly less than $\gamma$ as $n \to \infty$ with high probability. | |
| May 13, 2012 at 5:47 | comment | added | Anthony Quas | I'm guessing if you're asking for Erdos-Renyi, you're probably fine with random graphs with probability $p$ of having an edge. You should tell us what sort of values of $p$ and $s$ you're thinking about in terms of $n$. | |
| May 13, 2012 at 4:57 | history | asked | passerby51 | CC BY-SA 3.0 |