• JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
  • JoomlaWorks Simple Image Rotator
 
  Bookmark and Share
 
 
Master's Dissertation
DOI
https://doi.org/10.11606/D.100.2020.tde-07022020-121851
Document
Author
Full name
Luis Amato Neto
E-mail
Institute/School/College
Knowledge Area
Date of Defense
Published
São Paulo, 2020
Supervisor
Committee
Mendonça, José Ricardo Gonçalves de (President)
Camargo, Raphael Yokoingawa de
Freire, Alexandre da Silva
Rodrigues Neto, Camilo
Title in Portuguese
Coincidências: Problema dos aniversários e polinômios cromáticos
Keywords in Portuguese
Coincidências
Polinômios cromáticos
Problema dos aniversários
Abstract in Portuguese
Como discutido em Diaconis e Mosteller (1989), o problema dos aniversários é um ponto importante de partida no estudo de coincidências. Uma definição de coincidência é adotada, seguida de uma breve apresentação dos seus principais aspectos: entre eles a subjetividade e a surpresa. Na literatura são encontradas as principais variações do problema dos aniversários, que analisadas, fornecem as bases para um estudo do aspecto probabilístico das coincidências. Neste trabalho os eventos são associados a variáveis aleatórias independentes e igualmente distribuídas, ou seja, os problema são estudados por técnicas de contagem. Desta forma o problema clássico dos aniversários pode ser associado à coloração dos vértices de um grafo completo, assim como o problema do aniversariante pode ser associado à coloração dos vértices de um grafo estrela. A partir destas observações, é proposta a formulação de problema dos aniversários sujeito a restrições de uma rede de relacionamentos, que equivale a um problema da coloração própria dos vértices de um grafo simples, cuja topologia modela as restrições do problema original. O objetivo do trabalho é aplicar o conhecimento desenvolvido sobre polinômios cromáticos no estudo das coincidências associadas a problemas dos aniversários sujeito a restrições, Um resumo sobre teoria dos grafos e os principais resultados referentes a polinômios cromáticos são apresentados com o objetivo de dar clareza e consistência entre definições adotadas, teoremas utilizados e sua aplicação nos casos de árvores de Cayley, grafos Bollobas-Chung e redes sociais simples. A análise das coincidências se concentra na determinação do polinômio cromático e suas representações em diferentes bases, entre elas as formas: de potência, fatorial e de árvore. A decisão se um grafo pode ou não ser colorido de maneira própria com k > 2 cores é um problema de decisão NP-completo, portanto um objetivo secundário é analisar as limitações dos algoritmos existentes e dos sistemas disponíveis para de calculo de polinômios cromáticos, que possuem coeficientes inteiros e podem alcançar centenas de dígitos. Os cálculos e as simulações foram realizadas no Sage Mathematics Software (Linux Version 8.8). A conclusão demonstra que o conhecimento e as técnicas de polinômios cromáticos contribuem com a solução da generalização proposta do problema dos aniversários, sendo analisadas as limitações atuais quanto à eficácia dos algoritmos disponíveis e a capacidade computacional demandada pela topologia do grafo associado ao problema original
Title in English
Coincidences: birthday problem and chromatic polynomials
Keywords in English
Birthday problem
Chromatic polynomials
Coincidences
Abstract in English
As discussed in Diaconis e Mosteller (1989), the birthday problem is an important starting point in the study of coincidences. A definition of coincidence is adopted, followed by a brief presentation of its main aspects: subjectivity and surprise among them. In the literature, the main variations of the birthday problem are found, which analyzed, provide the basis for a study of the probabilistic aspect of coincidences. In this work the events are associated with independent and equally distributed random variables, that is, the problems are studied by counting techniques. Thus the classical birthday problem can be associated with the coloring of vertices of a complete graph, just as the birthmate problem can be associated with the coloring of the vertices of a star graph. From these observations, it is proposed a formulation of the birthday problem, subject to constraints of a relationships network, which is equivalent to a problem of proper coloring of the vertices of a simple graph, whose topology shapes the constraints of the original problem. The objective of this work is to apply the knowledge developed about chromatic polynomials in the study of coincidences associated with restricted birthday problems. A summary of graph theory and the main results concerning chromatic polynomials are presented with the purpose of providing clarity and consistency between adopted definitions, used theorems and their application in the case of Cayley trees, Bollobas-Chung graphs and simple social networks. The analysis of coincidences focuses on the determination of the chromatic polynomial and its representations in different bases, among them the power, factorial and tree bases. Whether or not a graph can be properly colored with k > 2 colors is an NP-complete decision problem, so a secondary objective is to analyze the limitations of existing algorithms and available systems for calculating chromatic polynomials, which have integer coefficients and can reach hundreds of digits. Calculations and simulations were performed in Sage Mathematics Software (Linux Version 8.8). The conclusion demonstrates that the knowledge and techniques of chromatic polynomials contribute to the solution of the proposed generalization of the birthdays problem, it is also analyzed the current limitations regarding the effectiveness of available algorithms and the computational capacity demanded by the graph topology associated with the original problem
 
WARNING - Viewing this document is conditioned on your acceptance of the following terms of use:
This document is only for private use for research and teaching activities. Reproduction for commercial use is forbidden. This rights cover the whole data about this document as well as its contents. Any uses or copies of this document in whole or in part must include the author's name.
Publishing Date
2020-02-14
 
WARNING: Learn what derived works are clicking here.
All rights of the thesis/dissertation are from the authors
CeTI-SC/STI
Digital Library of Theses and Dissertations of USP. Copyright © 2001-2020. All rights reserved.