Dense triangle free graphs with paths of length 3 between every pair of vertices

220 Views Asked by At

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.

1

There are 1 best solutions below

0
On BEST ANSWER

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.