Full text
| |
| Author(s): |
Leonardo Nagami Coregliano
Total Authors: 1
|
| Document type: | Master's Dissertation |
| Press: | São Paulo. |
| Institution: | Universidade de São Paulo (USP). Instituto de Matemática e Estatística (IME/SBI) |
| Defense date: | 2015-08-05 |
| Examining board members: |
Yoshiharu Kohayakawa;
Jie Han;
Carlos Hoppen
|
| Advisor: | Yoshiharu Kohayakawa |
| Abstract | |
Alexander A. Razborov (2007) developed the theory of flag algebras to compute the minimum asymptotic density of triangles in a graph as a function of its edge density. The theory of flag algebras, however, can be used to study the asymptotic density of several combinatorial objects. In this dissertation, we present two original results obtained in the theory of tournaments through application of flag algebra proof techniques. The first result concerns minimization of the asymptotic density of transitive tournaments in a sequence of tournaments, which we prove to occur if and only if the sequence is quasi-random. As a byproduct, we also obtain new quasi-random characterizations and several other flag algebra elements whose density is minimized if and only if the sequence is quasi-random. The second result concerns a class of equivalent properties of a sequence of tournaments that we call quasi-carousel properties and that, in a similar fashion as quasi-random properties, force the sequence to converge to a specific limit homomorphism. Several quasi-carousel properties, when compared to quasi-random properties, suggest that quasi-random sequences and quasi-carousel sequences are the furthest possible from each other within the class of almost balanced sequences. (AU) | |
| FAPESP's process: | 13/23720-9 - The Asymptotic Combinatorics of Permutations and Flag Algebras |
| Grantee: | Leonardo Nagami Coregliano |
| Support Opportunities: | Scholarships in Brazil - Master |