Topics in extremal combinatorics
Lead Research Organisation:
University of Cambridge
Department Name: Pure Maths and Mathematical Statistics
Abstract
The aim of the project is to answer certain questions in the area of extremal combinatorics. In the next paragraphs I will discuss few of these questions in details.
One of these questions is related to the isoperimetric inequality in the hypercube. In vague sense, isoperimetric inequalities answer the following question: Given a set with fixed volume, how small can the boundary of the set be? To make the question more interesting, further constrains are usually added. For example, one may ask this question for subsets of three-dimensional space, subsets of surface of the sphere, etc. My aim is to study a problem related to an isoperimetric inequality type of question for subsets of the discrete hypercube, i.e. the set of all {0,1} sequences with some fixed number of entries.
For subsets of the hypercube, there already exists an isoperimetric inequality result called Harper's inequality. It states that for sets of given size, there always exists a set of certain nice form that has minimal size of boundary. However, for some certain sizes there are plenty of sets A which has minimal size of boundary. The aim of my research is to find which subsets of the hypercube of given size have minimal boundary and whose complement also have minimal boundary. Hence, in some sense the aim is to classify all subsets A of the hypercube for which the boundary of both A and the complement of A is small. The approach that I used to analyse such sets A is to analyse certain compression operators. They are operators that modifies a given set in some systematic way in order to obtain a new set with preferable structure. It turns out that the sets A which have small boundary and whose complements have small boundary can be classified quite efficiently. On the other hand, this task is non-trivial as there are some interesting examples of such sets as well (that is, there are other sets satisfying these properties than just those described by the Harper's inequality).
Another two questions I am working on are related to shadows of sequences. Let A be a subset containing sequences with n coordinates, all of which are 0 or 1. A classical way of defining the shadow of A is to take the set of those sequences obtained from any element x in A by flipping one of the 1-entries of x to 0. There are various ways to generalise or modify this problem, but the main question is always to ask how to choose a set A of sequences of given size, so that the size of the shadow of A is minimal.
One of the generalisations I am considering is to extend the notion of shadow to sequences whose coordinates are in {0,...,m} instead of {0,1}. In this set-up, we define the shadow of a set A to be the set of those sequences obtained from any element x in A by flipping one of the entries of x that is in {1,...,m} to 0.
Another way to generalise this question is to delete coordinates instead of changing their values. Let A be a collection of sequences of length n whose coordinates are in {0,...,m}. Then the shadow of A is given by taking all sequences obtained from any x in A by removing one coordinate of x which equals zero.
With both problems, it is easy to get started with similar approach that was used in the isoperimetric problem: the aim is to modify a given set in some systematic way without increasing the size of the shadow so that the resulting set has nice structure. However, in both cases these compression operators will give a quite large class of sets which potentially could have minimal size of the shadow. Hence in both cases I had to come up with some further techniques to find out which of those candidate sets have minimal size of the shadow, but eventually I was able to prove that for any size, there is a certain nice set of sequences of that size which has minimal size of the shadow.
The research in the project is contained under the EPSRC's "Logic and combinatorics" area.
One of these questions is related to the isoperimetric inequality in the hypercube. In vague sense, isoperimetric inequalities answer the following question: Given a set with fixed volume, how small can the boundary of the set be? To make the question more interesting, further constrains are usually added. For example, one may ask this question for subsets of three-dimensional space, subsets of surface of the sphere, etc. My aim is to study a problem related to an isoperimetric inequality type of question for subsets of the discrete hypercube, i.e. the set of all {0,1} sequences with some fixed number of entries.
For subsets of the hypercube, there already exists an isoperimetric inequality result called Harper's inequality. It states that for sets of given size, there always exists a set of certain nice form that has minimal size of boundary. However, for some certain sizes there are plenty of sets A which has minimal size of boundary. The aim of my research is to find which subsets of the hypercube of given size have minimal boundary and whose complement also have minimal boundary. Hence, in some sense the aim is to classify all subsets A of the hypercube for which the boundary of both A and the complement of A is small. The approach that I used to analyse such sets A is to analyse certain compression operators. They are operators that modifies a given set in some systematic way in order to obtain a new set with preferable structure. It turns out that the sets A which have small boundary and whose complements have small boundary can be classified quite efficiently. On the other hand, this task is non-trivial as there are some interesting examples of such sets as well (that is, there are other sets satisfying these properties than just those described by the Harper's inequality).
Another two questions I am working on are related to shadows of sequences. Let A be a subset containing sequences with n coordinates, all of which are 0 or 1. A classical way of defining the shadow of A is to take the set of those sequences obtained from any element x in A by flipping one of the 1-entries of x to 0. There are various ways to generalise or modify this problem, but the main question is always to ask how to choose a set A of sequences of given size, so that the size of the shadow of A is minimal.
One of the generalisations I am considering is to extend the notion of shadow to sequences whose coordinates are in {0,...,m} instead of {0,1}. In this set-up, we define the shadow of a set A to be the set of those sequences obtained from any element x in A by flipping one of the entries of x that is in {1,...,m} to 0.
Another way to generalise this question is to delete coordinates instead of changing their values. Let A be a collection of sequences of length n whose coordinates are in {0,...,m}. Then the shadow of A is given by taking all sequences obtained from any x in A by removing one coordinate of x which equals zero.
With both problems, it is easy to get started with similar approach that was used in the isoperimetric problem: the aim is to modify a given set in some systematic way without increasing the size of the shadow so that the resulting set has nice structure. However, in both cases these compression operators will give a quite large class of sets which potentially could have minimal size of the shadow. Hence in both cases I had to come up with some further techniques to find out which of those candidate sets have minimal size of the shadow, but eventually I was able to prove that for any size, there is a certain nice set of sequences of that size which has minimal size of the shadow.
The research in the project is contained under the EPSRC's "Logic and combinatorics" area.
Organisations
People |
ORCID iD |
| I Leader (Primary Supervisor) | |
| Eero-Pekka Johannes Räty (Student) |
Studentship Projects
| Project Reference | Relationship | Related To | Start | End | Student Name |
|---|---|---|---|---|---|
| EP/N509620/1 | 01/10/2016 | 30/09/2022 | |||
| 1951100 | Studentship | EP/N509620/1 | 01/10/2017 | 30/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 |