4
$\begingroup$

Does there exist an infinite family of dense (i.e. #edges = $m = O(n^2)$) graphs such that they are triangle-free and have a path of length exactly 3 between every pair of vertices?

Best lower bound(of edges) that I can come up with is from the family of Mycielskian graphs which have around $n^{log_2(3)} \approx n^{1.585}$ edges in the limit.

Edit As Misha Lavrov pointed out in the comments the Kneser graph KG(3k-1, k) in limit gives a graph with edges $n^{log_{27/4}(27)} \approx n^{1.726 }$ edges.

Edit The generalized Kneser graph KG(6k-1, 3k, k) in limit has $n^{log_{8}(54)} \approx n^{1.918}$ edges. This gives an even better lower bound but still not dense. Note that no generalized Kneser graph which is triangle-free will give a dense graph.

Note that we can take the graphs to maximally triangle-free which implies that they are minimal graphs of diameter 2 i.e. removing any edge increases the diameter from 2 to 3.

$\endgroup$
  • 1
    $\begingroup$ The Kneser graph $KG(3k-1,k)$ is a better lower bound, with $\mathcal O(n^\alpha)$ edges for $\alpha = \log_{27/4} 27 \approx 1.726$, but still not as good as you'd like. $\endgroup$ – Misha Lavrov Oct 26 '17 at 17:39
  • $\begingroup$ Well, you've just found a better example. I don't think $KG(6k-1,3k,k)$ is dense either, though: my calculations say that the number of edges is $n^{\log_8 54} \approx n^{1.918}$ in the limit. (I may have made a calculation error.) Possibly a different generalized Kneser graph would do it. $\endgroup$ – Misha Lavrov Oct 26 '17 at 20:55
  • $\begingroup$ Oh right, don't know what I was thinking, the graph is obviously not dense. $\endgroup$ – nikhil_vyas Oct 26 '17 at 20:57
  • 1
    $\begingroup$ Playing with the parameters, it doesn't look like there's a denser generalized Kneser which is triangle-free. But it would be surprising if $n^{1.918}$ were possible and not at least $n^{2-o(1)}$ (if not exactly $C n^2$). $\endgroup$ – Misha Lavrov Oct 26 '17 at 21:03
3
+50
$\begingroup$

Take the graph with vertices $\{0,1,2\}\times(\mathbb Z/3d\mathbb Z)$ and edges:

  • $(0,i)\sim (1,i+j)$ for $0\leq j\leq d-2$ or $j=d$
  • $(1,i)\sim (2,i+j)$ for $0\leq j\leq d-2$ or $j=d$
  • $(2,i)\sim (0,i+j+1)$ for $0\leq j\leq d-2$ or $j=d$

This has density about $\tfrac 2 9.$ Note there is a symmetry sending $(0,j),(1,j),(2,j)$ to $(1,j),(2,j),(0,j+1)$ respectively.

Starting from $(0,0),$ paths of length $3$ can reach at least the vertices $(1,j+j'-j'')$ with $j'\neq j''$ and $j,j',j''$ each in $\{0,\dots,d-3,d-2,d\}.$ This lets it reach any vertex of the form $(1,j).$ By symmetry any two vertices whose first co-ordinate is different are connected by a path of length $3.$

For $(0,0)$ to reach a vertex of the form $(0,i)$ by a path of length $3$ it has to go all the way around the first co-ordinate, ending up at $(0,j+j'+j''+1)$ with $j,j',j''$ in $\{0,\dots,d-3,d-2,d\}.$ which lets it reach exactly $(0,1)$ to $(0,3d-1).$ By symmetry, any two different vertices with the same first co-ordinate are connected by a path of length three, and there are no triangles.

$\endgroup$

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.