Independence in groups, graphs and the integers
Lead Research Organisation:
University of Birmingham
Department Name: School of Mathematics
Abstract
A fundamental aim in mathematics is to develop techniques that apply to a range of problems across different topics. One of the most exciting recent developments in this direction has been the emergence of 'independence' as a unifying concept. Indeed, many fundamental results and open problems in algebra, combinatorics and number theory can be rephrased in terms of independent sets in hypergraphs. For example, the famous Szemerédi theorem on arithmetic progressions in the integers can be phrased in the language of independent sets.
Novel approaches developed in the last few years have led to the resolution of many seemingly unrelated classical open problems in this area. This has led to a drive for techniques that are universal to the theory. The underlying goal of the proposal is to develop such techniques. These methods will be applied to tackle a range of challenging problems at the interface of algebra, combinatorics, number theory and probability theory.
The research in the project consists of three interconnected themes. Firstly, the project will investigate solution-free sets of integers; this unifying notion encapsulates a range of major topics in number theory such as arithmetic progressions, Sidon sets and sum-free sets. Secondly, the project will explore the interplay between counting sum-free sets in abelian groups and the size of the largest such set. Another major aspect of the project is to investigate how 'robust' a combinatorial property is. This part of the project will be studied from a probabilistic point of view. In particular, we will seek a deeper understanding of sharp threshold phenomena in the evolution of random graphs, an area which has close ties to measure theory and statistical physics.
In the past, many problems in algebra and number theory related to this proposal have been tackled via Fourier analytical methods. One long-term aim of this proposal is to provide additional combinatorial approaches that are beneficial for these research communities. For example, one key component of this project is to develop so-called container results which provide information on the distribution of independent sets; such tools have proven vital in the study of a number of 'counting' problems. Another crucial element of the proposal is to develop a better understanding of the structure of independent sets in given algebraic objects.
Novel approaches developed in the last few years have led to the resolution of many seemingly unrelated classical open problems in this area. This has led to a drive for techniques that are universal to the theory. The underlying goal of the proposal is to develop such techniques. These methods will be applied to tackle a range of challenging problems at the interface of algebra, combinatorics, number theory and probability theory.
The research in the project consists of three interconnected themes. Firstly, the project will investigate solution-free sets of integers; this unifying notion encapsulates a range of major topics in number theory such as arithmetic progressions, Sidon sets and sum-free sets. Secondly, the project will explore the interplay between counting sum-free sets in abelian groups and the size of the largest such set. Another major aspect of the project is to investigate how 'robust' a combinatorial property is. This part of the project will be studied from a probabilistic point of view. In particular, we will seek a deeper understanding of sharp threshold phenomena in the evolution of random graphs, an area which has close ties to measure theory and statistical physics.
In the past, many problems in algebra and number theory related to this proposal have been tackled via Fourier analytical methods. One long-term aim of this proposal is to provide additional combinatorial approaches that are beneficial for these research communities. For example, one key component of this project is to develop so-called container results which provide information on the distribution of independent sets; such tools have proven vital in the study of a number of 'counting' problems. Another crucial element of the proposal is to develop a better understanding of the structure of independent sets in given algebraic objects.
Planned Impact
The main impact of this project will be to the academic community working at the interface of algebra, combinatorics, number theory and probability theory. In particular, a broad range of problems arising from these areas can be stated in terms of 'independent sets': the primary aim of the project is to develop novel combinatorial methods for solving such independent set problems. The development of these tools will have a strong impact on an area of intradisciplinary research that has been identified as of significant importance by EPSRC and the 2010 IRMS. Indeed, the latter stated that "Discrete mathematics and combinatorics are inherently cross-disciplinary" and that "new UK-led developments in additive combinatorics... involve and energise combinatorics".
One central aim of the proposal is to develop so-called 'refined container theorems'. Container theorems have recently proven to be powerful tools to attack independent set problems. However, so far this method typically cannot be used to prove 'exact' results. I aim to overcome this significant hurdle by developing refined approaches that exploit the structural information about a problem.
Success here will have important ramifications. Firstly, these tools will enable me to resolve a number of major open problems at the interface of algebra, combinatorics, number theory and probability theory. For instance, several of the objectives relate to questions on sum-free sets that have been extensively investigated by eminent researchers such as Alon, Cameron, Erdös, Gowers and Green. Another goal is to characterise the 'sharp threshold' phenomena for Ramsey properties in random graphs: 'sharp thresholds' is an area that interacts with statistical physics and theoretical computer science. Secondly, the aim is that the methods developed will have applications far beyond the remit of the proposal. In particular, in the 'Academic beneficiaries' summary I have outlined a number of open problems that researchers may be able to attack using the methods developed in the project.
An important route to maintaining and enhancing the strength of UK research is to develop stronger links with international research centres of excellence. The University of Birmingham has identified the strategic alliance with the University of Illinois at Urbana-Champaign as a platform to achieve this. Through collaborative research visits I will help develop this partnership.
Another pathway to enhance the impact of this project is by nurturing young research talent. The PhD students that will work on some of the topics of the proposal will gain expertise in an area of intradisciplinary research of significant importance to the UK research landscape. I will also interact extensively with members of other research communities. For example, I will organise a one-day workshop on the themes of the proposal to help stimulate interactions between the algebra, combinatorics and number theory research communities.
A workforce highly skilled in the mathematical sciences is crucial to the health of the economy. For example, a Deloitte report estimated that the contribution of the mathematical sciences to the UK economy in 2010 was around £208 billion in terms of Gross Value Added. However, a recent International Survey of Adult Skills led the OECD to conclude that "The talent pool of highly skilled adults in England and Northern Ireland is likely to shrink relative to that of other countries". Through the outreach activities associated with the proposal I aim to inspire young people to study mathematics further and ultimately have careers that make use of their mathematical skills. For example, I will organise master classes for 14-18 year old students focusing on the broad themes of the proposal and as well as giving a 'Birmingham Popular Maths Lecture' on this exciting area of mathematics.
One central aim of the proposal is to develop so-called 'refined container theorems'. Container theorems have recently proven to be powerful tools to attack independent set problems. However, so far this method typically cannot be used to prove 'exact' results. I aim to overcome this significant hurdle by developing refined approaches that exploit the structural information about a problem.
Success here will have important ramifications. Firstly, these tools will enable me to resolve a number of major open problems at the interface of algebra, combinatorics, number theory and probability theory. For instance, several of the objectives relate to questions on sum-free sets that have been extensively investigated by eminent researchers such as Alon, Cameron, Erdös, Gowers and Green. Another goal is to characterise the 'sharp threshold' phenomena for Ramsey properties in random graphs: 'sharp thresholds' is an area that interacts with statistical physics and theoretical computer science. Secondly, the aim is that the methods developed will have applications far beyond the remit of the proposal. In particular, in the 'Academic beneficiaries' summary I have outlined a number of open problems that researchers may be able to attack using the methods developed in the project.
An important route to maintaining and enhancing the strength of UK research is to develop stronger links with international research centres of excellence. The University of Birmingham has identified the strategic alliance with the University of Illinois at Urbana-Champaign as a platform to achieve this. Through collaborative research visits I will help develop this partnership.
Another pathway to enhance the impact of this project is by nurturing young research talent. The PhD students that will work on some of the topics of the proposal will gain expertise in an area of intradisciplinary research of significant importance to the UK research landscape. I will also interact extensively with members of other research communities. For example, I will organise a one-day workshop on the themes of the proposal to help stimulate interactions between the algebra, combinatorics and number theory research communities.
A workforce highly skilled in the mathematical sciences is crucial to the health of the economy. For example, a Deloitte report estimated that the contribution of the mathematical sciences to the UK economy in 2010 was around £208 billion in terms of Gross Value Added. However, a recent International Survey of Adult Skills led the OECD to conclude that "The talent pool of highly skilled adults in England and Northern Ireland is likely to shrink relative to that of other countries". Through the outreach activities associated with the proposal I aim to inspire young people to study mathematics further and ultimately have careers that make use of their mathematical skills. For example, I will organise master classes for 14-18 year old students focusing on the broad themes of the proposal and as well as giving a 'Birmingham Popular Maths Lecture' on this exciting area of mathematics.
People |
ORCID iD |
| Andrew Treglown (Principal Investigator / Fellow) |
Publications
Treglown A
(2017)
On solution-free sets of integers II
in Acta Arithmetica
Balogh J
(2017)
An improved lower bound for Folkman's theorem
in Bulletin of the London Mathematical Society
BALOGH J
(2018)
Tilings in Randomly Perturbed Dense Graphs
in Combinatorics, Probability and Computing
HAN J
(2017)
Exact Minimum Codegree Threshold for K - 4 -Factors
in Combinatorics, Probability and Computing
Das S
(2020)
Ramsey properties of randomly perturbed graphs: cliques and cycles
in Combinatorics, Probability and Computing
Meeks K
(2018)
On the complexity of finding and counting solution-free sets of integers
in Discrete Applied Mathematics
Hancock R
(2016)
Enumerating solution-free sets in the integers
in Electronic Notes in Discrete Mathematics
Hancock R
(2017)
On solution-free sets of integers
in European Journal of Combinatorics
Staden K
(2020)
The bandwidth theorem for locally dense graphs
in Forum of Mathematics, Sigma
CZYGRINOW A
(2018)
TILING DIRECTED GRAPHS WITH TOURNAMENTS
in Forum of Mathematics, Sigma
| Description | I have now completed the fellowship. During the fellowship there had been success in completing many of the objectives from the project. Further, some of the research goes beyond the original aims of the proposal. So far the project has resulted in 13 published papers. Further, so far there have been 4 other papers produced during the project (still in the refereeing process). One of the key aims of the project was to gain a better understanding of sets of numbers that do not have any solution to a given equation. For example, sets of odd numbers have no solution to x+y=z (because two odds always add up to an even number!). If a set of numbers has no solution to x+y=z we call it sum-free. In "Sharp bound on the number of maximal sum-free subsets of integers" we give a precise count on the number of so-called maximal sum-free sets of integers. Building on this work, we have also investigated the size and number of sets of integers that do not have solutions to other linear equations (such as 2x+2y=z). For example, in "On solution-free sets of integers" we show that the number of so-called maximal solution-free sets can vary widely depending on the equation under consideration. In "On the complexity of finding and counting solution-free sets of integers" we study the problem of deciding whether one can efficiently determine the size of the largest solution-free subset of a given set of integers. One vital technique used in some of the aforementioned work is to translate the problems into one about so-called independent sets in "networks". This approach has also been used to tackle other goals in the project. Indeed, in "Applications of graph containers in the Boolean lattice" we give a number of applications of this approach, including to a problem concerning codes: Coding theory plays an important role in the modern world. Unfortunately, when submitting a message across a communication channel, errors can occur. It is therefore of interest to encode messages in a way that ensures the message can be understood even if a certain number of errors occur. Such codes are called error-correcting codes. In this project we have given an asymptotic formula for the total number of error-correcting codes with certain parameters (this answers a question raised more than 10 years ago by Sapozhenko). Related to the aforementioned work on sum-free sets, there has been interest in related questions in a branch of mathematics called Ramsey theory. For example, one result in the area is Schur's theorem which states whenever you colour the numbers 1,2,3, with two colours (say red and blue), there is a red solution to x+y=z or a blue solution to x+y=z. In "An improved lower bound for Folkman's Theorem" we significantly improved a lower bound on Folkman's theorem, which is a famous generalisation of Schur's theorem. In "Independent sets in hypergraphs and Ramsey properties of graphs and the integers" we use the container method to prove "resilient random" versions of many classical results in Ramsey theory, including Schur's theorem. This strengthened many important results in the area, including work of Conlon, Gowers and Schacht. Matching problems arise in a number of situations. For example, a company may wish to match employees to individual jobs. Such problems can be modelled in terms of graphs: A graph is a collection of points (called vertices) some pairs of which are joined together by lines (called edges). More complicated matching problems can be modelled using so-called hypergraphs. For example, we may have a collection of employees, jobs and cities and seek a matching of each employee to a specific job in a given city. Whilst graph matchings are well understood, much less is known about hypergraph matchings. In "A note on perfect matchings in uniform hypergraphs" we give a condition which guarantees a hypergraph contains a "perfect" matching. The study of perfect matchings has links also to theoretical Computer Science. Indeed, in general it is believed that one cannot efficiently determine whether a given hypergraph has a perfect matching. In "The complexity of perfect matchings and packings in dense hypergraphs" we develop a tool for obtaining classes of hypergraphs where one can actually determine efficiently whether we have a perfect matching. Then using this new tool, we answered a 10 year old question of Yuster, and partially resolved a conjecture of Knox, Keevash and Mycroft. |
| Exploitation Route | One of the most exciting recent developments in combinatorics and related areas has been the emergence of 'independence' as a unifying concept. This notion has transformed the study of many topics in algebra, combinatorics and number theory. Indeed, many mathematical problems can be rephrased in the language of counting independent sets in hypergraphs. This is useful because in recent years techniques such as the "container method" have emerged to tackle such independent set problems. One of the goals of the project is to refine the current container methods and there has been success here. Indeed, one of the weaknesses of the standard container method is that there is natural "over counting" arising. In "Sharp bound on the number of maximal sum-free subsets of integers" we refined this method so that the over counting could be avoided (therefore giving a very exact result). I therefore believe the "refined" container method of this paper could be of particular interest to other mathematicians. |
| Sectors | Digital/Communication/Information Technologies (including Software) |
| URL | http://web.mat.bham.ac.uk/~treglowa/pubat.html |