¿Cuál es la prueba de este lema de Hajnal sobre la complejidad de la consulta aleatoria de las propiedades de gráficos monótonos?

En este documento , Hajnal establece el siguiente lema:

Sea el conjunto de todos los gráficos bipartitos con n vértices en la parte izquierda ym vértices en la parte derecha. Suponga que P ⊆ G n , m es no trivial, monótono e invariante con respecto a los isomorfismos de gráficos bipartitos. Ordene el conjunto de gráficos mínimos con propiedad P lexicográficamente de acuerdo con la lista ordenada de grados de vértices izquierdos, y deje que G sea ​​el primer gráfico mínimo con propiedad P de acuerdo con este orden. Entonces, la complejidad de la consulta aleatoria de error cero de P es Ω ( Δ $\mathscr{G}_{n, m}$$n$$m$$\mathscr{P} \subseteq \mathscr{G}_{n, m}$$\mathscr{P}$$G$$\mathscr{P}$$\mathscr{P}$, dondeΔL(G)es el grado máximo de cualquier vértice en el lado izquierdo deGyδL(G)es el grado medio de los vértices en el lado izquierdo deG.$\Omega(\frac{\Delta_L(G)}{\delta_L(G)} n)$$\Delta_L(G)$$G$$\delta_L(G)$$G$

(De hecho, Hajnal en realidad usa una ligera extensión del lema anterior.) Gröger también usa el mismo lema en este otro documento y Chakrabarti y Khot en este otro documento . Pero no puedo entender la prueba del lema de Hajnal. Hajnal atribuye el lema a Yao y cita este artículo . Pero el artículo de Yao en realidad no afirma ese lema en esa forma.

El artículo de Yao demuestra un lema estrechamente relacionado. (Lema 5 en el documento de Yao, o equivalentemente Lema 6 en esta versión de diario del documento de Yao .) Al adaptar la prueba del lema en el documento de Yao, veo cómo probar el lema de Hajnal bajo el supuesto adicional de que . Tengo problemas con el caso de que δ L ( G ) es subconstante.$\delta_L(G) \geq \Omega(1)$$\delta_L(G)$

$\lambda(n)$$\delta_L(G)$$\mu(n)$$\Delta_L(G)$$\frac{\Delta_L(G) - 4\delta_L(G)}{\lceil 4 \delta_L(G) \rceil} \cdot \frac{n}{2}$

$\delta_L(G)$$O(\Delta_L(G) n)$$\frac{\Delta_L(G)}{\delta_L(G)} n$$T_i'$

¿Cómo se puede reparar la prueba?

$\Omega(\frac{\Delta_L(G)}{\lceil \delta_L(G) \rceil} n)$