EPSRC Reference: 
EP/V038168/1 
Title: 
Substructures in large graphs and hypergraphs 
Principal Investigator: 
Pehova, Dr Y 
Other Investigators: 

Researcher CoInvestigators: 

Project Partners: 

Department: 
Mathematics 
Organisation: 
London School of Economics & Pol Sci 
Scheme: 
EPSRC Fellowship 
Starts: 
01 September 2022 
Ends: 
31 August 2024 
Value (£): 
208,494

EPSRC Research Topic Classifications: 

EPSRC Industrial Sector Classifications: 
No relevance to Underpinning Sectors 


Related Grants: 

Panel History: 

Summary on Grant Application Form 
In this project, we seek to understand the fundamental mathematical properties of discrete structures. In particular, we study graphs, which are collections of vertices, together with a set of unordered pairs of vertices called edges. Graphs are used to model transportation networks, social networks, large data sets, and more, and as such, a deeper understanding of their fundamental properties is beneficial to a wide variety of their applications.
This project falls within the area of Extremal Graph Theory, in which one major direction concerns the minima and maxima of graph parameters among graphs avoiding a certain substructure. This project considers this type of problems, where the substructure is a large set of edgedisjoint or vertexdisjoint copies of a prescribed small or sparse graph; these are known in the area as packing and tiling problems, respectively. For example, part of this project seeks to understand what is the maximum number of triangles which can be packed edgedisjointly in a graph with a given density of edges.
A second part of this project concerns a wellknown conjecture of Jackson (c. 1980) on packing Hamilton cycles in bipartite oriented graphs. An oriented graph is obtained from a graph by specifying an orientation for each edge, and a Hamilton cycle is a cyclic ordering of the vertices such that every two consecutive vertices are connected by an edge. It was recently shown that every regular orientation of the complete graph can be decomposed into such Hamilton cycles. We seek to prove Jackson's conjecture, which is a natural bipartite analogue of this result, as well as investigate a related conjecture of Kuhn and Osthus on tripartite graphs.
Finally, a significant portion of this project is dedicated to investigating the maximum edgedensity in a uniformly dense hypergraph which avoids a fixed subhypergraph. Hypegraphs are a natural generalisation of graphs, which allows for the modelling of relationships among more than two objects. In particular, their edge set consists of subsets of vertices whose size is not necessarily two. We seek to understand, in a certain family of pseudorandom hypegraphs, what edge density forces the emergence of a given subhypergraph.

Key Findings 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk

Potential use in nonacademic contexts 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk

Impacts 
Description 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk 
Summary 

Date Materialised 


Sectors submitted by the Researcher 
This information can now be found on Gateway to Research (GtR) http://gtr.rcuk.ac.uk

Project URL: 

Further Information: 

Organisation Website: 
http://www.lse.ac.uk 