Show simple item record

dc.contributor.supervisor Gunderson, David (Mathematics) en_US
dc.contributor.author Tsaturian, Sergei
dc.date.accessioned 2019-04-11T19:38:00Z
dc.date.available 2019-04-11T19:38:00Z
dc.date.issued 2019 en_US
dc.date.submitted 2019-03-29T20: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 colour-critical edge (joint work with V. Nikiforov). In 1968, Simonovits found extremal numbers $ex(n,H)$ for graphs with a colour-critical edge for large $n$ (without specifying how large). A similar result for unions of graphs, each with a colour-critical 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 triangle-free 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 two-colouring 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 3-dimensional space. en_US
dc.rights info:eu-repo/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:eu-repo/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


Files in this item

This item appears in the following Collection(s)

Show simple item record

View Statistics