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.
Organisations
People |
ORCID iD |
| I Leader (Primary Supervisor) | |
| Eero-Pekka Johannes Räty (Student) |
Publications
Leader I
(2018)
A Note on Intervals in the Hales-Jewett Theorem
in The Electronic Journal of Combinatorics
Räty E
(2020)
Uniqueness in Harper's vertex-isoperimetric theorem
in Discrete Mathematics
Räty E
(2020)
Induced saturation of P 6
in Discrete Mathematics
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 |