Home

# Problems in extremal graph theory and Euclidean Ramsey theory

 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. en_US 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. 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) en_US Li, Ben (Computer Science) Solymosi, Jozsef (University of British Columbia) dc.degree.level Doctor of Philosophy (Ph.D.) en_US dc.description.note May 2019 en_US
﻿