The Library
Substructure sensities in extremal combinatorics
Tools
Chan, Timothy F. N. (2021) Substructure sensities in extremal combinatorics. PhD thesis, University of Warwick.

PDF
WRAP_Theses_Chan_2021.pdf  Submitted Version  Requires a PDF viewer. Download (1167Kb)  Preview 
Official URL: http://webcat.warwick.ac.uk/record=b3718178
Abstract
One of the primary goals of extremal combinatorics is to understand how an object’s properties are influenced by the presence or multiplicity of a given substructure. Most classical theorems in the area, such as Mantel’s Theorem, are phrased in terms of substructure counts such as the number of edges or the number of triangles in a graph. Gradually, however, it has become more popular to express results in terms of the density of substructures, where the substructure counts are normalised by some natural quantity. This approach has several benefits; results are often more succinctly stated using densities, and it becomes easier to focus on the asymptotic behaviour of objects.
In this thesis, we study three topics concerning density. We begin Chapter 1 by contextualising the study of combinatorial density and justifying its importance within extremal combinatorics. We also introduce the relevant combinatorial objects, results, and questions that are central to the later chapters. Particular attention is paid to developing the theory of graph limits and flag algebras, two modern fields that rely heavily on the notion of density.
In Chapter 2, we investigate the interplay between the densities of cycles of length 3 and 4 in large tournaments. In particular, we prove two cases of a conjecture of Linial and Morgenstern (2016) that the minimum density of 4cycles in a graph with a fixed density of 3cycles is attained by a particular random construction.
In Chapter 3, we explore quasirandom permutations. A permutation is said to be quasirandom if the density of every subpermutation matches the expected density in a random permutation. Our main result is that quasirandomness can be characterised by a property which, on the surface, appears significantly weaker.
Lastly, in Chapter 4, we resolve a problem posed by Bubeck and Linial (2016) on the inducibility of trees. The inducibility of a tree X is defined as the maximum possible density of X in a large tree. We show that there exist nonpath, nonstar trees with positive inducibility, but that all such trees have inducibility bounded away from 1. We also show that there exists a sequence of trees in which every possible subtree appears asymptotically with positive density.
Item Type:  Thesis (PhD)  

Subjects:  Q Science > QA Mathematics  
Library of Congress Subject Headings (LCSH):  Combinatorial geometry, Combinatorial analysis, Extremal problems (Mathematics), Permutations, Trees (Graph theory), Graph theory  
Official Date:  February 2021  
Dates: 


Institution:  University of Warwick  
Theses Department:  Mathematics Institute  
Thesis Type:  PhD  
Publication Status:  Unpublished  
Supervisor(s)/Advisor:  Wood, David R. ; Král', Daniel  
Sponsors:  Australia. Department of Education, Employment, and Workplace Relations  
Format of File:  
Extent:  v, 105 leaves : illustrations  
Language:  eng 
Request changes or add full text files to a record
Repository staff actions (login required)
View Item 
Downloads
Downloads per month over past year