Topics in extremal combinatorics

Lead Research Organisation: UNIVERSITY OF CAMBRIDGE
Department Name: Pure Maths and Mathematical Statistics

Abstract

Abstracts are not currently available in GtR for all funded research. This is normally because the abstract was not required at the time of proposal submission, but may be because it included sensitive information such as personal details.

Publications

10 25 50
publication icon
Leader I (2018) A Note on Intervals in the Hales-Jewett Theorem in The Electronic Journal of Combinatorics

publication icon
Räty E (2020) Uniqueness in Harper's vertex-isoperimetric theorem in Discrete Mathematics

publication icon
Räty E (2020) Induced saturation of P 6 in Discrete Mathematics

publication icon
Räty E (2019) Coordinate Deletion of Zeroes in The Electronic Journal of Combinatorics

Studentship Projects

Project Reference Relationship Related To Start End Student Name
EP/N509620/1 30/09/2016 29/09/2022
1951100 Studentship EP/N509620/1 30/09/2017 29/09/2020 Eero-Pekka Johannes Räty
 
Description During the funding period, I have worked on problems in the area of Extremal Combinatorics. As a result, I have achieved four accepted publications which are listed in the Publications-section. The contents of two of these papers, "Uniqueness in Harper's vertex-isoperimetric theorem" and "Coordinate deletion of zeroes" are briefly described in the award abstract already. The other two papers are "A Note on Intervals in the Hales-Jewett Theorem" and "Induced Saturation of P6", and the first one of these is joint work with my supervisor Prof. Imre Leader.

The Hales-Jewett Theorem states that if the vertices of the cube {1,,m}^d are coloured with c colours, then for any sufficiently large d there exists a monochromatic line. Any such line has a set of active coordinates, and it is natural to ask what is the least number of intervals l (for given m and c) so that for any c-colouring one can always find a monochromatic line whose active set of coordinates is an union of at most l intervals. Conlon and Kamcev considered this question when m=3 and c is odd integer. Together with Imre Leader we proved that when m=3 and c=2, one can always find a monochromatic line whose active set of coordinates is an interval (i.e. only one interval is required), answering a question of Conlon and Kamcev.

A graph G is said to be H induced saturated if G does not contain H as an induced subgraph, but changing any edge of G to non-edge or any non-edge of G to an edge gives an induced copy of H. In the latter paper, I came up with a construction which proves that there is a graph that is P6 induced saturated.

I also have another four papers that are submitted and are currently under review by the journals. One of these papers, "Inequalities on Projected Volumes", is joint work with Imre Leader and Zarko Randelovic, and the other papers are "An Achievement Game on a Cycle", "A grid generalisation of the Kruskal-Katona theorem" and "The Toucher-Isolator Game on Trees".

"The papers Achievement Game on a Cycle" and "The Toucher-Isolator Game on Trees" are work related to a certain game on graph which was introduced by Dowden, Kang, Mikalacki and Stojakovic. In the game the two players, Toucher and Isolator claim edges of a given graph in alternating turns. Toucher is aiming to touch as many vertices as possible with the edges he claimed, and Isolator is aiming to isolate as many vertices as possible. In these two papers I found the optimal strategy for paths and cycles, and also prove that among trees, the paths are 'best' for Isolator.
Exploitation Route The are some open questions related to the problems I was considering, and some of these findings have already been taken forward by other researches working in the area. For example, there has been subsequent research related to the papers A Note on Intervals in the Hales-Jewett Theorem by Kamcev and Spiegel, and to Induced Saturation of P6 by Cho, Choi and Park.
Sectors Other