Qual é a prova desse lema de Hajnal sobre a complexidade da consulta aleatória das propriedades do gráfico monótono?

No presente trabalho , Hajnal afirma o seguinte lema:

Seja o conjunto de todos os gráficos bipartidos com vértices na parte esquerda e vértices na parte direita. Suponha que seja não trivial, monótono e invariável em relação aos isomorfismos dos gráficos bipartidos. Ordene o conjunto de gráficos mínimos com a propriedade lexicograficamente de acordo com a lista ordenada de graus de vértices esquerdos e deixe ser o primeiro gráfico mínimo com a propriedade acordo com esta ordem. A complexidade da consulta aleatória com erro zero de é , em que$\mathscr{G}_{n, m}$m P ⊆ G n , m P G P P Ω ( Δ L ( G $n$$m$$\mathscr{P} \subseteq \mathscr{G}_{n, m}$$\mathscr{P}$$G$$\mathscr{P}$$\mathscr{P}$ΔL(G$\Omega(\frac{\Delta_L(G)}{\delta_L(G)} n)$$\Delta_L(G)$ é o grau máximo de qualquer vértice no lado esquerdo e é o grau médio dos vértices do lado esquerdo .δ L ( G ) $G$$\delta_L(G)$$G$

(De fato, Hajnal realmente usa uma ligeira extensão do lema acima.) O mesmo lema também é usado por Gröger neste outro artigo e por Chakrabarti e Khot neste outro artigo . Mas não consigo descobrir a prova do lema de Hajnal. Hajnal atribui o lema a Yao e cita este artigo . Mas o artigo de Yao na verdade não reivindica esse lema dessa forma.

O artigo de Yao é um lema intimamente relacionado. (Lema 5 no artigo de Yao, ou equivalente 6 nesta versão do jornal de Yao .) Adaptando a prova do lema no artigo de Yao, vejo como provar o lema de Hajnal sob a suposição extra de que . Estou tendo problemas com o caso é subconstante.δ L ( G $\delta_L(G) \geq \Omega(1)$$\delta_L(G)$

(Agora vou assumir que o leitor está familiarizado com a prova de Yao.) Meu entendimento é que, para provar o lema de Hajnal, a idéia é modificar a prova de Yao, basicamente substituindo por e com todos os lugares. Em um nível alto, com essas modificações, o raciocínio de Yao ainda faz sentido e mostra que, para "descobrir arestas ausentes suficientes", o algoritmo de consulta precisará fazer pelo menos cerca de consultas.δ L ( G ) μ ( n ) Δ L ( G ) Δ L ( G ) - 4 δ 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}$

O problema é que, quando é subconstante, devido à operação de teto, esse limite inferior é apenas , que é muito menor que o limite que aparece no lema de Hajnal. (Concretamente, o problema é que cada conjunto precisa ter um número inteiro de vértices.)O ( Δ L ( G ) n ) Δ L ( G $\delta_L(G)$$O(\Delta_L(G) n)$T ′ $\frac{\Delta_L(G)}{\delta_L(G)} n$$T_i'$

Como a prova pode ser corrigida?

Enviei um email para Péter Hajnal, e ele gentilmente confirmou que o limite no lema deveria ser .$\Omega(\frac{\Delta_L(G)}{\lceil \delta_L(G) \rceil} n)$