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

8

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 queGn,mm PG n , m P G P P Ω ( Δ L ( G )nmPGn,mPGPPΔL(G)Ω(ΔL(G)δL(G)n)Δ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 ) GGδ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 )δL(G)Ω(1)δ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 )λ(n)δL(G)μ(n)ΔL(G)ΔL(G)4δL(G)4δL(G)n2

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 )δL(G)O(ΔL(G)n)TiΔL(G)δL(G)nTi

Como a prova pode ser corrigida?

William Hoza
fonte
Parece que, nos três trabalhos que mencionei (Hajnal, Gröger e Chakrabarti-Khot), os autores realmente usam apenas o limite mais fraco . Pode haver outros trabalhos que usam esse lema, mas não conheço nenhum. Ω(ΔL(G)δL(G)n)
William Hoza 01/12/16

Respostas:

5

Enviei um email para Péter Hajnal, e ele gentilmente confirmou que o limite no lema deveria ser .Ω(ΔL(G)δL(G)n)

William Hoza
fonte