Problems in extremal graph theory and Euclidean Ramsey theory
| dc.contributor.author | Tsaturian, Sergei | |
| dc.contributor.examiningcommittee | Craigen, Robert (Mathematics) Li, Ben (Computer Science) Solymosi, Jozsef (University of British Columbia) | en_US |
| dc.contributor.supervisor | Gunderson, David (Mathematics) | en_US |
| 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.degree.discipline | Mathematics | en_US |
| dc.degree.level | Doctor of Philosophy (Ph.D.) | en_US |
| 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.description.note | May 2019 | en_US |
| dc.identifier.uri | http://hdl.handle.net/1993/33849 | |
| dc.language.iso | eng | en_US |
| dc.rights | open access | en_US |
| 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 | doctoral thesis | en_US |