Extremal and Probabilistic Combinatorics
Lead Research Organisation:
Queen Mary University of London
Department Name: Sch of Mathematical Sciences
Abstract
I will be working on a number of problems in extremal and probabilistic combinatorics. I will explore a range of areas and questions, including but not necessarily limited to the following:
- the behaviour of geometric random graphs, that is graphs arising from points chosen randomly in n-dimensional space, looking at the connectedness of such graphs depending on the probability distribution and the dimension;
- Saturation in graphs and hypergraphs, focusing on how the saturation number behaves asymptotically as the size of the graph tends to infinity; and
- Perfect and semi-perfect 1-factorizations of various families of graphs, such as complete graphs and discrete cubes.
- the behaviour of geometric random graphs, that is graphs arising from points chosen randomly in n-dimensional space, looking at the connectedness of such graphs depending on the probability distribution and the dimension;
- Saturation in graphs and hypergraphs, focusing on how the saturation number behaves asymptotically as the size of the graph tends to infinity; and
- Perfect and semi-perfect 1-factorizations of various families of graphs, such as complete graphs and discrete cubes.
People |
ORCID iD |
| John Johnson (Primary Supervisor) | |
| Natalie Behague (Student) |
Publications
Behague N
(2019)
Semi-perfect 1-factorizations of the hypercube
in Discrete Mathematics
Studentship Projects
| Project Reference | Relationship | Related To | Start | End | Student Name |
|---|---|---|---|---|---|
| EP/N50953X/1 | 30/09/2016 | 29/09/2021 | |||
| 2100600 | Studentship | EP/N50953X/1 | 30/09/2016 | 30/03/2020 | Natalie Behague |
| Description | I have obtained results on four questions in extremal and probabilistic combinatorics. 1. Tuza's famous conjecture roughly states that there are 'nice asymptotics' for the saturation number of hypergraphs, where the saturation number relates the existence of certain subgraphs to the number of edges of the graph. I answered a question of Pikhurko concerning the asymptotics of the saturation number for families of hypergraphs, proving in particular that there may not be 'nice asymptotics' if we take a family of hypergraphs instead of a single hypergraph. This work resulted in a paper in the Electronic Journal of Combinatorics. 2. The existence or non-existence of 'perfect 1-factorizations' has been studied for various families of graphs, with perhaps the most famous open problem in the area being Kotzig's conjecture which states that the complete graph on an even number of vertices has a perfect 1-factorization. In my work I have focused on another well-studied family of graphs: the hypercubes. I answered almost fully the question of how close (in some particular sense) to perfect a 1-factorization of the hypercube can be. This work resulted in a paper in Discrete Mathematics. 3. The k-nearest-neighbour random geometric graph model puts vertices randomly in a d-dimensional box and joins each vertex to its k nearest neighbours. I found significantly improved upper and lower bounds on the threshold for connectivity for the k-nearest neighbour graph in high dimensions. 4. Cerny's conjecture on the length of the shortest reset word of a synchronizing automaton is arguably the most longstanding open problem in the theory of finite automata. In collaboration with Robert Johnson, I made progress towards this conjecture, bounding the length of a reset word for triples among other things. |
| Exploitation Route | There are several open questions concerning generalisations of and variations of all of the problems I have worked on. For example, Tuza's conjecture, Kotzig's conjecture and Czerny's conjecture as mentioned above are still open, and perhaps my partial progress will be helpful in finding a proof or a counterexample. For the latter two questions in particular, I have improved some bounds but there is room for further improvement to make the upper and lower bounds match and find the true value. |
| Sectors | Other |
| Description | LMS UK-based PhD students' Travel Support |
| Amount | £115 (GBP) |
| Organisation | London Mathematical Society |
| Sector | Academic/University |
| Country | United Kingdom |
| Start | 06/2019 |
| End | 08/2019 |
| Description | Queen Mary Postgraduate Research Fund |
| Amount | £383 (GBP) |
| Organisation | Queen Mary University of London |
| Sector | Academic/University |
| Country | United Kingdom |
| Start | 06/2019 |
| End | 08/2019 |
| Description | Microthesis for LMS newsletter |
| Form Of Engagement Activity | A magazine, newsletter or online publication |
| Part Of Official Scheme? | No |
| Geographic Reach | National |
| Primary Audience | Other audiences |
| Results and Impact | I wrote a microthesis (a two-page summary of some of my research) for the London Mathematical Society's Newsletter. This newsletter is sent to all members of the LMS, who are primarily academic staff, but also include postgraduate students and mathematicians in other occupations who use mathematics in their work. |
| Year(s) Of Engagement Activity | 2019 |
| Description | RI Masterclass |
| Form Of Engagement Activity | Participation in an activity, workshop or similar |
| Part Of Official Scheme? | No |
| Geographic Reach | Local |
| Primary Audience | Schools |
| Results and Impact | In both 2018 and 2019 I lead a Masterclass organised by the Royal Institution and attended by approximately 90 school children. The masterclasses lasted 2.5 hours and were met with positive feedback and engagement, including several students asking for recommendations of resources to find out more about the topic after the class. |
| Year(s) Of Engagement Activity | 2018,2019 |