Powered by OpenAIRE graph
Found an issue? Give us feedback
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/ MSpace at the Univer...arrow_drop_down
image/svg+xml art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos Open Access logo, converted into svg, designed by PLoS. This version with transparent background. http://commons.wikimedia.org/wiki/File:Open_Access_logo_PLoS_white.svg art designer at PLoS, modified by Wikipedia users Nina, Beao, JakobVoss, and AnonMoos http://www.plos.org/
addClaim

This Research product is the result of merged Research products in OpenAIRE.

You have already added 0 works in your ORCID record related to the merged Research product.

Problems in extremal graph theory and Euclidean Ramsey theory

Authors: Tsaturian, Sergei;

Problems in extremal graph theory and Euclidean Ramsey theory

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.

Related Organizations
Keywords

Graph theory, Combinatorics, Discrete geometry, Mathematics

  • BIP!
    Impact byBIP!
    selected citations
    These citations are derived from selected sources.
    This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    0
    popularity
    This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
    Average
    influence
    This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
    Average
    impulse
    This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
    Average
Powered by OpenAIRE graph
Found an issue? Give us feedback
selected citations
These citations are derived from selected sources.
This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Citations provided by BIP!
popularity
This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.
BIP!Popularity provided by BIP!
influence
This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).
BIP!Influence provided by BIP!
impulse
This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.
BIP!Impulse provided by BIP!
0
Average
Average
Average
Green