10
$\begingroup$

This question is posted from StackExchange since it received no answer there.

Let $f(n, e)$ be the number of triangle-free graphs on $n$ vertices and $e$ edges. From empirical evidence, I am motivated to make the following conjecture.

Conjecture: $f(n,e)$ is unimodal in $e$. In other words, for each $n$ there exists a mode $m = m(n)$ such that $f(n, e) \leq f(n, e + 1)$ if $e < m$, and $f(n, e) \geq f(n, e + 1)$ if $e \geq m$.

I am wondering if this conjecture has been mentioned in literature before since it is natural for such sequences to display some unimodality.

Here's another way to phrase the question.

Conjecture: Let $G$ be the $3$-uniform linear hypergraph whose vertex set is $\binom{[n]}{2}$, and whose edge set is $\{\{i,j\},\{j, k\}, \{k, i\}\}$ for distinct $i,j,k\in [n]$. Then the independence polynomial $Z_G(x)$ is unimodal.

It is known that if we instead consider the $2$-uniform graph with the same vertex set and edge set $\{\{i,j\},\{j, k\}\}$, then $Z_G(x)$ is equal to the matching polynomial $m_G(x)$ of $K_n$, which is unimodal and log-concave.

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Are you counting labelled graphs or unlabelled graphs? $\endgroup$
    – Brendan McKay
    Dec 5, 2022 at 8:56
  • $\begingroup$ Labeled graphs. $\endgroup$
    – abacaba
    Dec 5, 2022 at 16:51
  • $\begingroup$ I wonder if this general problem is true: Let $G$ be a group and $E$ be a finite G-set, $S$ be a subset of $E$, a $S$-free subset of $E$ is a set with no subset is $gS$ for some $g\in G$, let $f(G,e)$ be the number of $S$-free set with $e$ element, is $f(G,e)$ unimodal? $\endgroup$
    – Veronica Phan
    Jan 13, 2023 at 14:00

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.