Título: | A CHARACTERIZATION OF TESTABLE GRAPH PROPERTIES IN THE DENSE GRAPH MODEL | ||||||||||||
Autor: |
FELIPE DE OLIVEIRA |
||||||||||||
Colaborador(es): |
SIMON RICHARD GRIFFITHS - Orientador |
||||||||||||
Catalogação: | 19/JUN/2023 | Língua(s): | ENGLISH - UNITED STATES |
||||||||||
Tipo: | TEXT | Subtipo: | THESIS | ||||||||||
Notas: |
[pt] Todos os dados constantes dos documentos são de inteira responsabilidade de seus autores. Os dados utilizados nas descrições dos documentos estão em conformidade com os sistemas da administração da PUC-Rio. [en] All data contained in the documents are the sole responsibility of the authors. The data used in the descriptions of the documents are in conformity with the systems of the administration of PUC-Rio. |
||||||||||||
Referência(s): |
[pt] https://www.maxwell.vrac.puc-rio.br/projetosEspeciais/ETDs/consultas/conteudo.php?strSecao=resultado&nrSeq=62907&idi=1 [en] https://www.maxwell.vrac.puc-rio.br/projetosEspeciais/ETDs/consultas/conteudo.php?strSecao=resultado&nrSeq=62907&idi=2 |
||||||||||||
DOI: | https://doi.org/10.17771/PUCRio.acad.62907 | ||||||||||||
Resumo: | |||||||||||||
We consider, in this thesis, the question of determining if a graph has a
property P such as G is triangle-free or G is 4-colorable. In particular,
we consider for which properties P there exists a random algorithm with
constant error probabilities that accept graphs that satisfy P and reject graphs
that are epsilon-far from any graph that satisfies it. If, in addition, the algorithm
has complexity independent of the size of the graph, the property is called
testable. We will discuss the results of Alon, Fischer, Newman, and Shapira
that obtained a combinatorial characterization of testable graph properties,
solving an open problem raised in 1996. This characterization informally says
that a graph property P is testable if and only if testing P can be reduced to
testing the property of satisfying one of finitely many Szemerédi-partitions.
|
|||||||||||||
|