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.

Publications

10 25 50
publication icon
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