[en] A CHARACTERIZATION OF TESTABLE GRAPH PROPERTIES IN THE DENSE GRAPH MODEL
Ano de defesa: | 2023 |
---|---|
Autor(a) principal: | |
Orientador(a): | |
Banca de defesa: | |
Tipo de documento: | Tese |
Tipo de acesso: | Acesso aberto |
Idioma: | eng |
Instituição de defesa: |
MAXWELL
|
Programa de Pós-Graduação: |
Não Informado pela instituição
|
Departamento: |
Não Informado pela instituição
|
País: |
Não Informado pela instituição
|
Palavras-chave em Português: | |
Link de acesso: | https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=62907&idi=1 https://www.maxwell.vrac.puc-rio.br/colecao.php?strSecao=resultado&nrSeq=62907&idi=2 http://doi.org/10.17771/PUCRio.acad.62907 |
Resumo: | [pt] Consideramos, nesta dissertação, a questão de determinar se um grafo tem uma propriedade P, tal como G é livre de triângulos ou G é 4- colorível. Em particular, consideramos para quais propriedades P existe um algoritmo aleatório com probabilidades de erro constantes que aceita grafos que satisfazem P e rejeita grafos que são epsilon-longe de qualquer grafo que o satisfaça. Se, além disso, o algoritmo tiver complexidade independente do tamanho do grafo, a propriedade é dita testável. Discutiremos os resultados de Alon, Fischer, Newman e Shapira que obtiveram uma caracterização combinatória de propriedades testáveis de grafos, resolvendo um problema em aberto levantado em 1996. Essa caracterização diz informalmente que uma propriedade P de um grafo é testável se e somente se testar P pode ser reduzido a testar a propriedade de satisfazer uma das finitas partições Szemerédi. |