Propriedades globais de classes hereditárias?

15

Uma classe hereditária de estruturas (por exemplo, gráficos) é aquela que é fechada sob subestruturas induzidas, ou equivalente, é fechada sob remoção de vértices.

Classes de gráficos que excluem um menor têm boas propriedades que não dependem do menor excluído específico. Martin Grohe mostrou que para classes de gráfico excluindo um menor existe um algoritmo polinomial para isomorfismo, e lógica de ponto fixo com contagem captura o tempo polinomial para essas classes de gráfico. (Grohe, Definibilidade de ponto fixo e tempo polinomial em gráficos com menores excluídos , LICS, 2010.) Eles podem ser considerados propriedades "globais".

Existem propriedades "globais" semelhantes conhecidas para classes hereditárias (gráficos ou estruturas mais gerais)?

Seria bom ver cada resposta focada em apenas uma propriedade específica.

András Salamon
fonte

Respostas:

13

Propriedades hereditárias são muito "robustas" no sentido a seguir.

Noga Alon e Asaf Shapira mostrou que para qualquer propriedade hereditária , se um gráfico G necessita de mais do que £ n 2 bordas para ser adicionado ou removido de modo a satisfazer P , então há uma subgráfico em L , do tamanho, no máximo, f P ( ε ) , o qual não satisfaz P . Aqui, a função f depende apenas da propriedade P (e não do tamanho do gráfico G , por exemplo). Erdős fez tal conjetura apenas sobre a propriedade da colorabilidade k .PGϵn2PGfP(ϵ)PfPGk

De fato, Alon e Shapira provam o seguinte fato mais forte: dado , para qualquer ϵ em ( 0 , 1 ) , existem N ( ϵ ) , h ( ϵ ) e δ ( ϵ ) tal que se um gráfico G tiver pelo menos N vértices e precisa de pelo menos ϵ n 2 arestas adicionadas / removidas para satisfazer P ; então, para pelo menos δ fração de subgráficos induzidos em h vértices, o subgrafo induzido violaPϵ(0,1)N(ϵ)h(ϵ)δ(ϵ)GNϵn2Pδh . Assim, se ϵ e a propriedade P são fixas, a fim de testar se um gráfico de entrada satisfaz P ou é far - longe de satisfazer P , então é necessário apenas consultar as arestas de um subgrafo induzido aleatoriamente de tamanho constante no gráfico e verifique se satisfaz a propriedade ou não. Esse testador sempre aceitaria gráficos satisfazendo P e rejeitaria gráficos ϵ - além de satisfazê-lo com probabilidade constante. Além disso, qualquer propriedade que seja testável por um lado nesse sentido é uma propriedade hereditária! Veja o artigo de Alon e Shapira para obter detalhes.PϵPPϵPPϵ

arnab
fonte
Houve uma boa palestra plenária de Czumaj ( springerlink.com/content/9rw586wx50656412 ) sobre testes de propriedades há dois dias. Para mais informações sobre o assunto, há um post de Terry Tao ( terrytao.wordpress.com/2007/10/31/… ) ou uma pesquisa de Goldreich ( eccc.uni-trier.de/report/2010/082 ).
RJK
A testabilidade é uma grande propriedade global. Obrigado pelo bom resumo.
András Salamon
8

Isso pode não ser exatamente o que você tinha em mente, mas existem restrições conhecidas sobre quantos gráficos em vértices podem existir em uma classe hereditária de gráficos. Por exemplo, não há classe hereditária de gráficos que tenha entre 2 Ω ( n ) e 2 o ( n log n ) em n vértices.n2Ω(n)2o(nlogn)n

Referência: E. Scheinerman, J. Zito, Sobre o tamanho das classes hereditárias de gráficos, Journal of Combinatorial Theory Series B

Serviço Travis
fonte
Essas propriedades certamente se qualificam: acho que a quantidade a que você se refere se chama "velocidade".
András Salamon
8

Isso está relacionado à resposta de Travis. De fato, poderia ser considerada uma versão mais forte.

Um papel por Bollob \ 'como e Thomason (Combinatorica, 2000) mostra que em Erd \ H {O} sR \' enyi gráficos aleatórios (com p alguma constante fixa), cada propriedade hereditária podem ser aproximadas por que eles chame uma propriedade básica . Básico quase significa gráficos cujos conjuntos de vértices são uniões de classes r , s dos quais abrangem cliques e r - s dos quais abrangem conjuntos independentes, mas não completamente. Essa aproximação é usada para caracterizar o tamanho de um maior conjunto de P , bem como o número cromático de P de G n ,Gn,pprsr-sPP , onde P é alguma propriedade hereditária fixa. Seppuder variar, o comportamento não será bem compreendido.Gn,pPp

Para obter mais informações sobre esse e outros trabalhos relacionados, há uma pesquisa realizada por Bollob \ 'as (Proceedings of ICM 1998), que também fornece uma conjectura atraente ao longo dessas linhas, exceto para hipergráficos.

Acho a conexão profunda entre propriedades hereditárias e o lema da regularidade de Szem \ 'eredi muito intrigante, pois foi usada aqui e no resultado de Alon e Shapira.

RJK
fonte
Obrigado Ross. O link que você destaca entre propriedades hereditárias e o lema da regularidade faria algumas perguntas interessantes.
András Salamon
7

A resposta de Suresh sobre a conjectura do AKR me fez pensar na mesma conjectura para propriedades hereditárias. Eu acho que (a menos que eu cometi um erro) eu posso mostrar que todas as propriedades não-trivial hereditárias têm (randomizados e determinista) complexidade árvore de decisão , que estabelece a conjectura AKR para tais propriedades (até constantes).Θ(n2)

Tentei pesquisar na literatura para ver se isso foi mostrado em algum lugar, mas não consegui encontrar uma referência. Então, ou eu não consegui encontrá-lo, mas ele existe, ou o teorema é desinteressante, ou cometi um erro.

Portanto, este é outro exemplo de propriedade global de todas as propriedades hereditárias do gráfico.

Robin Kothari
fonte
Eu ficaria muito interessado em ler um rascunho com seus resultados.
András Salamon
Avisarei quando for escrever. Também estou razoavelmente confiante de que isso deve seguir alguns limites mais conhecidos nessa área. Infelizmente, não conheço nenhum especialista nesta área que eu possa perguntar.
Robin Kothari
6

Ω(nc)c>0 0

David Eppstein
fonte
2
Este é um exemplo potencialmente muito interessante, mas alguns excelentes teóricos de gráficos estruturais que conheço acreditam que é falso!
RJK
4

Essa é a direção "reversa", mas a conjectura bem conhecida de Aanderaa-Rosenberg-Karp se aplica a propriedades gráficas monótonas para cima (ou seja, se G satisfaz a propriedade, o mesmo ocorre com qualquer gráfico nos mesmos nós cujo conjunto de arestas contém E (G )).

Suresh Venkat
fonte
4
A conjectura do AKR se aplica igualmente a propriedades monótonas para baixo, porque o complemento de uma propriedade monótona para cima é uma propriedade monótona para baixo e a complexidade da árvore de decisão de uma propriedade e seu complemento é a mesma. No entanto, a noção de monotonicidade na conjectura do AKR é com relação à remoção de borda, enquanto a pergunta do OP é sobre monotonicidade com relação à remoção de vértices. Eles definem duas classes diferentes de propriedades.
Robin Kothari
2
Pode ser interessante fazer uma nova pergunta para classes fechadas por subestrutura.
András Salamon