Timeline for The number of chains of chordal graphs
Current License: CC BY-SA 4.0
21 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 6, 2021 at 3:47 | comment | added | Brendan McKay | Gil, define $c(n)$ by the number of split chains is $n^{c(n)n^2}$. The value is steadily rising and by $n=14$ has passed $\frac12$. I believe that a lower bound $\liminf c(n) \ge \frac12+o(1)$ follows by recursive application of your idea. I'm guessing that $c(n)$ converges to a number around $0.8$, which is pretty high considering that $\binom{n}{2}! = n^{(1+o(1))n^2}$. | |
| S Jun 5, 2021 at 7:27 | history | bounty ended | Gil Kalai | ||
| S Jun 5, 2021 at 7:27 | history | notice removed | Gil Kalai | ||
| Jun 4, 2021 at 15:17 | comment | added | Gil Kalai | Brendan, would it be easy now by your program to have a similar table for $n \le 12$ for the case of chains of split graphs? | |
| Jun 4, 2021 at 13:32 | comment | added | Brendan McKay | Of course, even if the total number of graphs is asymptotically equal, it doesn't follow that the number of chains is asymptotically equal. There are more ways for a chordal chain to get started and this advantage will remain no matter how many vertices there are. | |
| Jun 4, 2021 at 13:03 | comment | added | Brendan McKay | I remember, and just checked, that "almost all chordal graphs are split graphs" is one of those asymptotic facts that are in no hurry to happen. Up as far as the number of labelled chordal graphs is known ($n=13$), the ratio is still heading towards 0 at an apparently exponential rate. Similarly the number of chordal chains is growing faster than the number of split chains by an extra factor of 4 at each step. For $n=12$ there are 6458 times as many chordal chains as split chains. All this emphasises the danger of the law of small numbers. | |
| Jun 4, 2021 at 9:39 | comment | added | Gil Kalai | @NathanLindzey In any case the reference to split graph shows that the asymptotic behavior is $\exp (c n^2 \log n)$ since once you added the edges of a clique of size $n/2$ you can next add the edges between its vertices and the other vertices in an arbitrary order. | |
| Jun 4, 2021 at 6:23 | comment | added | Gil Kalai | Many thanks, Nathan. I forgot that split graphs are precisely chordal graphs whose complements are chordal. Certainly this gives more motivation (and hope) for b). | |
| Jun 3, 2021 at 23:44 | comment | added | Nathan Lindzey | Just a comment: the chordal graphs whose complements are also chordal are the split graphs, i.e., its vertices can be partitioned into two classes where one is clique and the other is an independent set. Understanding the question for split graphs might be useful for answering question b) since almost all chordal graphs are split graphs, see doi.org/10.1017/S1446788700023077. If this is what motivated Variation b) in the first place, then my apologies for stating the obvious. | |
| S Jun 3, 2021 at 16:40 | history | bounty started | Gil Kalai | ||
| S Jun 3, 2021 at 16:40 | history | notice added | Gil Kalai | Reward existing answer | |
| Jun 1, 2021 at 12:58 | comment | added | Brendan McKay | I couldn't resist, see my answer. | |
| Jun 1, 2021 at 12:58 | answer | added | Brendan McKay | timeline score: 13 | |
| May 31, 2021 at 21:30 | comment | added | Gil Kalai | Dear @BrendanMcKay, I waited since the early 80s so anything which is little -o of 40 years can be considered as "near future" :) Thanks, Sam. I vaugely remember that the guess $(n!)^{n−2}$ based on $n=3,4$, did not come through, but maybe it reflects a weighted enumeration of some kind. | |
| May 31, 2021 at 18:39 | history | edited | Gil Kalai | CC BY-SA 4.0 |
edited body
|
| May 31, 2021 at 13:45 | comment | added | Brendan McKay | It could be computed up to about f(12) fairly easily, using the isomorph-invariance of chordalness (choldality?) Alas I can't do it in the near future. | |
| May 31, 2021 at 13:28 | comment | added | Sam Spiro | I think the g(3) in your remark should be f(3). | |
| May 31, 2021 at 5:11 | history | edited | Gil Kalai | CC BY-SA 4.0 |
added 483 characters in body
|
| May 30, 2021 at 15:59 | comment | added | Fedor Petrov | It is at most $c^{n^2}m!$ for certain $c<1$: we may choose $\Omega(n^2)$ edge-disjoint complete graphs on 4 vertices, and each of them have several forbidden orders of edges appearance. These events are independent. | |
| May 30, 2021 at 14:01 | comment | added | Sam Hopkins | Not an answer to your question, but if you look instead at "chains of connected graphs" (or really, connected graph plus isolated vertices, depending on how you look at it) then you're counting shellings of the complete graph, and this question was asked (a couple times) on MO previously: mathoverflow.net/questions/297411/… | |
| May 30, 2021 at 13:58 | history | asked | Gil Kalai | CC BY-SA 4.0 |