Timeline for Some models for random graphs that I am curious about
Current License: CC BY-SA 2.5
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 6, 2021 at 7:24 | comment | added | Student88 | Following the reference to Lovasz's framework of graphons, I was reading Chatterjee and Varadhan's paper (arxiv.org/pdf/1008.1946.pdf) that derives large deviation results using graphons. I was specifically interested in the result on the upper tail of the triangle count in a graph (section 4), and was wondering if you are familiar with similar results for several subgraphs count? My question is a bit vague I guess, maybe here it is better phrased: math.stackexchange.com/questions/4268673/… | |
| Jul 2, 2010 at 11:25 | history | edited | Gil Kalai |
edited tags
|
|
| Jun 19, 2010 at 13:25 | vote | accept | Gil Kalai | ||
| Jun 19, 2010 at 13:25 | history | bounty ended | Gil Kalai | ||
| Jun 19, 2010 at 13:25 | comment | added | Gil Kalai | All answers are very good. Terry's reference to the graph limit theory developed by Lovasz, Szegedy, Borgs, Chayes, Sos, Freedman, Vesztergombi,... seems indeed very relevant and Bela and Oliver also mentioned it to me. Oliver referred me to a paper by Diaconis and Janson and Svante mentioned, among various other things, a recent talk by Tom Britton on a closely related question. | |
| Jun 13, 2010 at 16:55 | answer | added | Terry Tao | timeline score: 16 | |
| Jun 13, 2010 at 6:34 | history | bounty started | Gil Kalai | ||
| Jun 1, 2010 at 7:14 | comment | added | Gil Kalai | Tim, sure, I will ask Bela, Svante, and Oliver (and perhaps a couple of others). I think that asking via email, or even the old-fashion habit of just thinking about the problem on my own, have still more advantages. But it is exciting to explore new paths. | |
| May 24, 2010 at 6:34 | comment | added | Victor Protsak | I can't help noticing that email is getting old-fashioned... | |
| May 23, 2010 at 21:30 | comment | added | François G. Dorais | I was remembering notes from a colleague along the lines of what Leandro described. I think such models are also widely studied in physics. There is a relevant paper by Park and Newman where they get some precise information on the 2-star case: Phys. Rev. E (3) 70 (2004) - ams.org/mathscinet-getitem?mr=2133810 | |
| May 23, 2010 at 21:25 | comment | added | gowers | Gil, this feels like things that Bela Bollobas, Svante Janson and Oliver Riordan have thought about. If you don't mind using old-fashioned methods, then contacting one of them by email might be a good starting point. | |
| May 23, 2010 at 20:51 | answer | added | David Eppstein | timeline score: 6 | |
| May 23, 2010 at 18:31 | answer | added | Leandro | timeline score: 9 | |
| May 23, 2010 at 17:53 | comment | added | François G. Dorais | Great question! The difficulty for these is that the random variables involved are no longer independent. If I remember correctly, there is a decent way to handle triangles and stars which are useful when studying social networks and epidemiology. I'll try to dig up that reference... | |
| May 23, 2010 at 17:02 | history | asked | Gil Kalai | CC BY-SA 2.5 |