9
$\begingroup$

Consider a saturated chain $G_0 \subset G_1 \subset \cdots \subset G_m$ of graphs on $n$ labelled vertices, where $G_i$ has $i$ edges, and $m = {{n}\choose {2}}$. Altogether there are $m!$ such chains of graphs (they are also known as "graph processes") and they form an interesting topic of study.

Recall that $G$ is chordal if all induced cycles in $G$ are 3-gons.

The question

Let $f(n)$ be the number of such chains where all graphs $G_i$ are chordal. What is the value of $f(n)$? a) for small values of $n$? b) what is its asymptotic behaviour? c) Is there an exact formula?

Of course $f(n) \le {{n} \choose {2}}!$, and it is easy to see that $f(n) \ge \prod_{k=1}^{n-1} k!$.

Variations: We can also ask about a) saturated chains of perfect graphs, b) saturated chains of chordal graphs whose complement is also chordal.

Motivation

For a saturated chain of graphs $G_0 \subset G_1 \subset \cdots \subset G_m$ we can look at the vector $(v_0,v_1,...,v_{n-1})$ where $v_k$ is the number of indices $j$ where $G_{j+1}$ has $k$ additional triangles compared to $G_j$. Such vectors introduced by Beus in 1970 (in the context of sorting algorithms) are interesting parameters of saturated chains of graphs and the case of chordal graphs is precisely the case where the vector is $(n-1,n-2,\dots,1)$.

Remark:

$f(3)=6$, and $f(4)=576$. I am curious to know the values of $f(5)$ and $f(6)$.

$\endgroup$
13
  • 2
    $\begingroup$ 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/… $\endgroup$ – Sam Hopkins May 30 at 14:01
  • 1
    $\begingroup$ 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. $\endgroup$ – Fedor Petrov May 30 at 15:59
  • 1
    $\begingroup$ I think the g(3) in your remark should be f(3). $\endgroup$ – Sam May 31 at 13:28
  • 1
    $\begingroup$ 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. $\endgroup$ – Brendan McKay May 31 at 13:45
  • 1
    $\begingroup$ 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. $\endgroup$ – Gil Kalai May 31 at 21:30
12
+350
$\begingroup$

This is not a general answer but the big numbers don't fit properly into a comment.

f(1) = 1
f(2) = 1
f(3) = 6
f(4) = 576
f(5) = 1416960
f(6) = 120678543360
f(7) = 455010170456862720
f(8) = 95371866538619173904056320
f(9) = 1383866987105877308750365304858542080
f(10) = 1716187027583005555045945024371317843956845772800
f(11) = 221917018834976627508152930913765491170568412125060985539788800
f(12) = 3598055237740601485367382153175891099609454479883844294426214728495086488780800
f(13) = 8665460290021468438320782226358244848272843476236433280013965605190231652374443764439998581964800

The last two took about 10 minutes and 5 hours.

For a graph $G$ let $g(G)$ be 0 if $G$ is not chordal and equal to the number of chordal chains back to the empty graph otherwise.

Set $g({\rm empty})=1$ and for one member $G$ of each isomorphism class of nonempty chordal graph in non-decreasing order of the number of edges, do $$ g(G) := \sum_{e\in E(G)} g(G-e). $$ The answer is $g(K_n)$. No adjustment for automorphism group size is needed. The only technical requirement is recognising $G-e$ as isomorphic to a previous graph.

The program can handle any class of graphs closed under isomorphism provided they all fit into memory at once.

On request, here is the corresponding table for split graphs.

s(1) = 1
s(2) = 1
s(3) = 6
s(4) = 480
s(5) = 719040
s(6) = 28111985280
s(7) = 39667596799259520
s(8) = 2716101119587792215121920
s(9) = 11750142295253741381979240922398720
s(10) = 4059370170952132363824590307446791630779187200
s(11) = 138004666315436722628999805261994204164032807656029840998400
s(12) = 557103455087735168484078548670473120844063643381325957791547628642631680000
s(13) = 316753104615638650562235298836069531430557783996203420700809420563227053308369342951115980800
s(14) = 29665849491651526562732309913886504922801500810240504259322068041948739753073885726711112718885233432115281920000
$\endgroup$
3
  • $\begingroup$ Dear Brendan, wonderful! thanks a lot. $\endgroup$ – Gil Kalai Jun 1 at 15:38
  • $\begingroup$ I suppose that asymptotically we can wonder if it is $e^{cn^2}$ or $e^{cn^2 \log n}$ or something else. $\endgroup$ – Gil Kalai Jun 1 at 18:17
  • $\begingroup$ It is $e^{c n^2 \log n}$ already for chains of split graphs. (See comments for the question.) $\endgroup$ – Gil Kalai Jun 4 at 9:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.