The Library
Packings and tilings in dense graphs
Tools
Pehova, Yanitsa (2020) Packings and tilings in dense graphs. PhD thesis, University of Warwick.
|
PDF
WRAP_Theses_Pehova_2020.pdf - Submitted Version - Requires a PDF viewer. Download (941Kb) | Preview |
Official URL: http://webcat.warwick.ac.uk/record=b3519971~S15
Abstract
In this thesis we present results on selected problems from extremal graph theory,
and discuss both known and new methods used to solve them.
In Chapter 1, we give an introductory overview of the regularity method, the flag
algebra framework, and some probabilistic tools, which we use to prove our results
in subsequent chapters.
In Chapter 2 we prove a new result on the packing density of triangles in graphs
with given edge density. In doing so, we settle a few conjectures of Gyori and Tuza
on decompositions and coverings of graphs with cliques of bounded size.
In Chapter 3 we show that a famous conjecture on Hamilton decompositions of
bipartite tournaments due to Jackson holds approximately, providing the first
intermediate result towards a full proof of the conjecture.
In Chapter 4, we introduce a novel absorbing paradigm for graph tilings, which we
apply in a few different settings to obtain new results. Using this method, we are
able to extend a result on triangle-tilings in graphs with high minimum degree and
sublinear independence number to clique-tilings of arbitrary size. We also strengthen
an existing result on tilings in randomly perturbed graphs.
Finally, in Chapter 5, we consider a problem on quasi-randomness in permutations.
We obtain simple density conditions for a sequence of permutations to be quasirandom,
and give a full characterisation of all conditions of the same type that force quasi-randomness in the same way.
Item Type: | Thesis (PhD) | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||
Library of Congress Subject Headings (LCSH): | Graph theory, Combinatorial designs and configurations, Bipartite graphs, Permutations, Geometry, Algebraic, Combinatorial analysis | ||||
Official Date: | September 2020 | ||||
Dates: |
|
||||
Institution: | University of Warwick | ||||
Theses Department: | Mathematics Institute | ||||
Thesis Type: | PhD | ||||
Publication Status: | Unpublished | ||||
Supervisor(s)/Advisor: | Král', Daniel | ||||
Extent: | v, 110 leaves | ||||
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