Timeline for Is it possible to have t triangles in some graph on n vertices?
Current License: CC BY-SA 3.0
19 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Oct 10, 2021 at 0:52 | history | edited | Tony Huynh |
edited tags
|
|
| Sep 27, 2012 at 4:38 | vote | accept | Ben Golub | ||
| Sep 27, 2012 at 2:49 | comment | added | Douglas Zare | The number of triangles sees very little information from the graph of removed edges. By inclusion-exclusion, it sees at most the number of edges, the number of pairs of edges sharing a vertex, and the number of triangles removed completely. To classify all graphs of a given size takes a lot more than 3 polynomially bounded counts. | |
| Sep 26, 2012 at 7:11 | answer | added | Aaron Meyerowitz | timeline score: 3 | |
| Sep 25, 2012 at 5:19 | vote | accept | Ben Golub | ||
| Sep 27, 2012 at 4:38 | |||||
| Sep 25, 2012 at 4:45 | vote | accept | Ben Golub | ||
| Sep 25, 2012 at 4:50 | |||||
| Sep 25, 2012 at 3:26 | answer | added | Brendan McKay | timeline score: 5 | |
| Sep 24, 2012 at 21:07 | comment | added | Gerhard Paseman | In fact, it should be easy to set up a correspondence: 0 edges removed means 0 triangles removed, a path of length 1 means n-2 triangles, 2-path 2n-6, two 1-paths 2n-5, triangle 3n-10, and so on. If you can readily establish a correspondence, I will bow to the suggestion that this problem is much easier than finite graph enumeration. Gerhard "Don't Need No Suggestion Genuflection" Paseman, 2012.09.24 | |
| Sep 24, 2012 at 20:58 | comment | added | Gerhard Paseman | Douglas, looking at the larger values allowed for t, I note that the missing values depend highly on how many edges are removed and in what configurations. For small values of n, you may need to worry only about a few configurations. Until I see a lot of collapsing occur ( with fixed n, having various complements lead to the same number of missing triangles), I assume pessimisticly that every (or almost every) finite graph corresponds to a different number of missing triangles in a much larger graph. Gerhard "Or I'll Be Pleasantly Surprised" Paseman, 2012.09.24 | |
| Sep 24, 2012 at 20:08 | comment | added | Douglas Zare | I'm really surprised at the suggestion that this might be close to as hard as enumerating all finite graphs. | |
| Sep 24, 2012 at 9:14 | answer | added | Aaron Meyerowitz | timeline score: 4 | |
| Sep 24, 2012 at 7:20 | answer | added | arun chandrasekhar | timeline score: 1 | |
| Sep 24, 2012 at 5:34 | answer | added | Tony Huynh | timeline score: 5 | |
| Sep 23, 2012 at 23:56 | comment | added | Ben Golub | Sridhar -- good call, thanks. I added the $n>4$ stipulation. Gerhard -- thanks a lot, that's helpful! | |
| Sep 23, 2012 at 23:56 | history | edited | Ben Golub | CC BY-SA 3.0 |
added 2 characters in body
|
| Sep 23, 2012 at 23:54 | comment | added | Gerhard Paseman | Many simple statements can be made, two of the most useful are that T_n is contained in T_n+1 and removing an edge from a complete graph affects n-2 triangles. Anything finer is likely not much weaker than enumerating finite graphs. Gerhard "Ask Me About System Design" Paseman, 2012.09.23 | |
| Sep 23, 2012 at 23:52 | comment | added | Sridhar Ramesh | It's not clear to me that {1, 2, ..., n} is contained in $T_n$. How do I get 2 or 3 triangles with just 3 vertices? | |
| Sep 23, 2012 at 23:49 | history | edited | Ben Golub | CC BY-SA 3.0 |
added 6 characters in body; deleted 6 characters in body
|
| Sep 23, 2012 at 23:42 | history | asked | Ben Golub | CC BY-SA 3.0 |