Denso triángulo gráficos gratuitos con caminos de longitud 3 entre cada par de vértices

Question

¿Existe una familia infinita de denso (es decir, #bordes = $m = O(n^2)$) de los gráficos, que son el triángulo libre y tener un camino de longitud exactamente 3 entre cada par de vértices?

Mejor límite inferior(de los bordes) que se me ocurre es de la familia de Mycielskian gráficos que tienen en torno a $n^{log_2(3)} \approx n^{1.585}$ bordes en el límite.

Editar Como Misha Lavrov señaló en los comentarios de la Kneser gráfico KG(3k-1, k) en el límite da un grafo con aristas $n^{log_{27/4}(27)} \approx n^{1.726 }$ bordes.

Editar La generalizada Kneser gráfico KG(6k-1, 3k, k) en el límite de $n^{log_{8}(54)} \approx n^{1.918}$ bordes. Esto le da una mejor cota inferior, pero todavía no densa. Tenga en cuenta que no generalizada Kneser gráfico que es el triángulo de la libre voluntad de dar una densa gráfico.

Tenga en cuenta que podemos tomar los gráficos al máximo triángulo, lo que implica que son mínimos los gráficos de diámetro 2 es decir, la eliminación de cualquier borde aumenta el diámetro de 2 a 3.

Answer 1

Tomar el grafo con vértices $\{0,1,2\}\times(\mathbb Z/3d\mathbb Z)$ y los bordes:

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

Este tiene una densidad de alrededor de $\tfrac 2 9.$ Tenga en cuenta que hay una simetría envío de $(0,j),(1,j),(2,j)$ $(1,j),(2,j),(0,j+1)$respectivamente.

A partir de $(0,0),$ caminos de longitud $3$ puede llegar al menos a los vértices $(1,j+j'-j'')$ $j'\neq j''$ $j,j',j''$ $\{0,\dots,d-3,d-2,d\}.$ lo que le permite llegar a cualquier vértice de la forma $(1,j).$ Por la simetría de dos vértices cuya primera coordinar es diferente están conectados por un camino de longitud $3.$

Para$(0,0)$, hasta alcanzar un vértice de la forma $(0,i)$ por un camino de longitud $3$ tiene que ir todo el camino alrededor de la primera coordinar, terminando en $(0,j+j'+j''+1)$$j,j',j''$$\{0,\dots,d-3,d-2,d\}.$, lo que le permite llegar exactamente a $(0,1)$ $(0,3d-1).$Por simetría, cualquiera de las dos diferentes vértices con el mismo primer coordinar están conectados por un camino de longitud tres, y no hay triángulos.