dc.contributor.supervisor 
Gunderson, David (Mathematics) 
en_US 
dc.contributor.author 
Tsaturian, Sergei


dc.date.accessioned 
20190411T19:38:00Z 

dc.date.available 
20190411T19:38:00Z 

dc.date.issued 
2019 
en_US 
dc.date.submitted 
20190329T20:19:06Z 
en 
dc.identifier.uri 
http://hdl.handle.net/1993/33849 

dc.description.abstract 
This thesis addresses problems of three types.
The first type is finding extremal numbers for unions of graphs, each with a colourcritical edge (joint work with V. Nikiforov). In 1968, Simonovits found extremal numbers $ex(n,H)$ for graphs with a colourcritical edge for large $n$ (without specifying how large). A similar result for unions of graphs, each with a colourcritical edge, can be deduced from Simonovits' 1974 work. Nikiforov and I improved this result, giving a precise bound for $n$.
The second type of problem considered is maximizing the number of cycles in a graph (joint work with A. Arman and D. Gunderson). It is proved that for sufficiently many vertices, the complete balanced bipartite graph is the unique trianglefree graph with the maximum number of cycles, thus answering a conjecture posed by Durocher et al. Other results include upper and lower bounds on the maximum number of cycles in graphs and multigraphs with a given number of edges, or with a given number of vertices and edges. The lower bounds in some cases come from random graphs; the asymptotics for the expected number of cycles in the random graph $G(n,m)$ is found for all possible relations between $n$ and $m$.
The final chapter is dedicated to Euclidean Ramsey theory. Two results about twocolouring of Euclidean spaces are given. One of the results answers in the affirmative a question asked in 1973 by Erd\H{o}s and others: if the Euclidean plane is coloured in red and blue, are there either two red points at distance one or five blue points on a line with distance one between consecutive points? The second result (joint work with A. Arman) answers the similar question for six points in 3dimensional space. 
en_US 
dc.rights 
info:eurepo/semantics/openAccess 

dc.subject 
Mathematics 
en_US 
dc.subject 
Combinatorics 
en_US 
dc.subject 
Graph theory 
en_US 
dc.subject 
Discrete geometry 
en_US 
dc.title 
Problems in extremal graph theory and Euclidean Ramsey theory 
en_US 
dc.type 
info:eurepo/semantics/doctoralThesis 

dc.degree.discipline 
Mathematics 
en_US 
dc.contributor.examiningcommittee 
Craigen, Robert (Mathematics)
Li, Ben (Computer Science)
Solymosi, Jozsef (University of British Columbia) 
en_US 
dc.degree.level 
Doctor of Philosophy (Ph.D.) 
en_US 
dc.description.note 
May 2019 
en_US 