Skip to content
printicon

Extremal problems for codegree and discrepancy

Research project This project focuses on two main areas in extremal combinatorics: (I) graph and hypergraph discrepancy, and (II) extremal codegree problems for hypergraphs.

This project focusses on two areas within extremal combinatorics. 1. First of all, graph discrepancy (local variations in density) is studied from the perspective of extremal graph theory. The main questions there are: what do graphs which have no dense clusters look like? How do we identify dense communities or clusters within a large network? The aim is to characterise for a fixed edge density the graphs with minimum positive discrepancy, and thereby to establish links between extremal graph theory and graph discrepancy. 2. Secondly, some extremal problems for 3-uniform hypergraphs (3-graphs) are investigated. Suppose we have a 3-graph G on n vertices in which every pair of vertices is contained in at least d triples. Let F be a fixed 3-graph. How large does d need to be to force G to contain a copy of F? How large does d need to be to guarantee we can cover the vertices of G with vertex-disjoint copies of F? The work in this project will use a mixture of tools from extremal and probabilistic combinatorics, in particular dependent random choice, correlation inequalities, large deviation inequalities, hypergraph regularity, absorption, flag algebra, and the theory of graph limits.

Head of project

Victor Falgas Ravry
Associate professor
E-mail
Email

Project overview

Project period

2017-01-01 2021-12-31

Research subject

Mathematics

External funding

Swedish Research Council

External funding