¿Cuántos nodos en el grafo $k$-denso más pequeño?

Question

Consideremos un grafo dirigido $k$-denso si:

• Cada nodo tiene exactamente dos hijos (vecinos salientes);
• Cada par de nodos tiene al menos tres hijos diferentes (además de ellos mismos);
• Cada tres nodos tienen al menos cuatro hijos diferentes (además de ellos mismos);
• ...
• Cada $k$ nodos tienen al menos $k+1$ hijos diferentes (además de ellos mismos);

¿Cuál es el número más pequeño de nodos requerido para un grafo $k$-denso?

Aquí hay algunos casos especiales.

Para $k=1$, el número más pequeño de nodos es $3$:

1->[2,3],   2->[3,1],   3->[1,2]

Para $k=2$, el número más pequeño de nodos es $7$. Para ver esto, podemos construir el grafo avariciosamente basándonos en la siguiente restricción: el hijo de un nodo debe ser diferente a su padre y hermano(s). ¿Por qué? Porque un nodo y su padre deben tener tres hijos además de ellos mismos.

• $1$ tiene dos hijos: llámelos $2$ y $3$.
• $2$ debe tener dos hijos diferentes a su padre ($1$) y hermano ($3$): llámelos $4$ y $5$.
• $3$ debe tener dos hijos diferentes a su padre ($1$) y hermano ($2$). El primero puede ser $4$. Ahora, $3$ y $2$ juntos solo tienen dos hijos además de ellos mismos ($4$ y $5$), por lo que $3$ debe tener otro hijo diferente - llámelo $6$.
• $4$ debe tener dos hijos diferentes a sus padres ($2$ y $3$) y hermanos ($5$ y $6$). El primero puede ser $1$ y el segundo debe ser nuevo - llámelo $7$.
• $5$ debe tener dos hijos diferentes a su padre ($2$) y hermano ($4$). El primero puede ser $1$. El segundo no puede ser uno de los hijos de $1$ ($2$ y $3$) o hermanos ($7$) por lo que debe ser $6$.
• $6$ debe tener dos hijos diferentes a sus padres ($3$ y $5$) y hermanos ($4$ y $1$). Estos deben ser $2$ y $7$.
• $7$ debe tener dos hijos diferentes a sus padres ($4$ y $6$) y hermanos ($2$ y $1$). Estos deben ser $3$ y $5$.

En total, tenemos el siguiente grafo $2$-denso con $n=7$ nodos:

1->[2,3]  2->[4,5]  3->[4,6]  4->[1,7]  5->[1,6]  6->[2,7]  7->[3,5]

Para $k=3$, usé un algoritmo avaricioso similar (con más restricciones) para construir el siguiente grafo:

 1->[2,3]    2->[4,5]    3->[6,7]    4->[6,8]     5->[7,9]
 6->[10,11]  7->[12,13]  8->[1,9]    9->[10,14]  10->[2,12]  
11->[1,13]  12->[8,15]  13->[4,14]  14->[3,15]   15->[5,11]

Utilicé un programa de computadora para verificar todas las posibilidades con un máximo de $14$ nodos y no encontré ninguna, por lo que (asumiendo que mi programa es correcto) $n=15$ es el número mínimo requerido para $k=3$.

Esto sugiere que el número mínimo de nodos en un grafo $k$-denso debería ser: $2^{k+1}-1$. ¿Es esto cierto?

¿Cuál es el número más pequeño de nodos requerido para $k$ en general?

ACTUALIZACIÓN 1: Acabo de aprender sobre la expansión de vértices. Parece estar relacionado, pero aún no estoy seguro de cómo exactamente.

Answer 1

Teorema. Un grafo $k$-denso tiene al menos $2^{k+1}-1$ vértices.

Prueba. Sea $L$ una copia del conjunto de vértices $V$, con elementos $l_v$ para $v\in V$. Sea $M$ el grafo bipartito en el conjunto de vértices $V\cup L$, con aristas $wl_v$ siempre que $w=v$ o $w$ sea un hijo de $v$. La condición $k$-densa implica que para cualquier $L'\subseteq L$ con $|L'|\leq k$, el conjunto de vecinos $\Gamma(L')=\{v\in V\mid (\exists l_w\in L').vl_w\in E(M)\}$ tiene un orden de al menos $2|L'|+1$. Esto implica que $M$ no tiene ningún ciclo $C$ de longitud $2k$ o menos: tomar $L'=C\cap L$ daría $|L'|\leq k$ y $|\Gamma(L')|\leq 2|L'|$. Así que $M$ tiene una circunferencia de al menos $2(k+1)$, y ambas partes de $M$ tienen un grado promedio de $3$. El límite de Hoory [1] (prueba alternativa en [2]) da $|V|\geq 1+2+4+\dots+2^k=2^{k+1}-1$. $\Box$

Observación. Sospecho, pero no he comprobado, que el límite de Hoory solo es exacto para grafos regulares. El teorema de Feit-Higman dice que los únicos grafos regulares que alcanzan el límite anterior tienen una circunferencia de $5,6,8$ o $12$, lo que significa que solo podría haber grafos $k$-densos de orden $2^{k+1}-1$ para $k=2,3,5$ (y $k=1$). Creo que se puede construir un grafo $k$-denso a partir de una jaula $(3,2k+2)$ (por ejemplo, la jaula Tutte 12) quite fácilmente tomándola como "M" y usando un emparejamiento perfecto para elegir qué vértices en $L$ deben etiquetarse como $l_v$.

[1] Tamaño de Grafos Bipartitos con una Circunferencia Dada, Shlomo Hoory, https://www.sciencedirect.com/science/article/pii/S0095895602921234

[2] Una prueba basada en la entropía del límite de Moore para grafos irregulares, S. Ajesh Babu, Jaikumar Radhakrishnan, https://arxiv.org/abs/1011.1058