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

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.

• 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. – Misha Lavrov Oct 26 '17 at 17:39
• 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. – Misha Lavrov Oct 26 '17 at 20:55
• Oh right, don't know what I was thinking, the graph is obviously not dense. – nikhil_vyas Oct 26 '17 at 20:57
• 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$). – Misha Lavrov Oct 26 '17 at 21:03

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.