Project acronym ANAMULTISCALE
Project Analysis of Multiscale Systems Driven by Functionals
Researcher (PI) Alexander Mielke
Host Institution (HI) FORSCHUNGSVERBUND BERLIN EV
Call Details Advanced Grant (AdG), PE1, ERC-2010-AdG_20100224
Summary Many complex phenomena in the sciences are described by nonlinear partial differential equations, the solutions of which exhibit oscillations and concentration effects on multiple temporal or spatial scales. Our aim is to use methods from applied analysis to contribute to the understanding of the interplay of effects on different scales. The central question is to determine those quantities on the microscale which are needed to for the correct description of the macroscopic evolution.
We aim to develop a mathematical framework for analyzing and modeling coupled systems with multiple scales. This will include Hamiltonian dynamics as well as different types of dissipation like gradient flows or rate-independent dynamics. The choice of models will be guided by specific applications in material modeling (e.g., thermoplasticity, pattern formation, porous media) and optoelectronics (pulse interaction, Maxwell-Bloch systems, semiconductors, quantum mechanics). The research will address mathematically fundamental issues like existence and stability of solutions but will mainly be devoted to the modeling of multiscale phenomena in evolution systems. We will focus on systems with geometric structures, where the dynamics is driven by functionals. Thus, we can go much beyond the classical theory of homogenization and singular perturbations. The novel features of our approach are
- the combination of different dynamical effects in one framework,
- the use of geometric and metric structures for coupled partial differential equations,
- the exploitation of Gamma-convergence for evolution systems driven by functionals.
Summary
Many complex phenomena in the sciences are described by nonlinear partial differential equations, the solutions of which exhibit oscillations and concentration effects on multiple temporal or spatial scales. Our aim is to use methods from applied analysis to contribute to the understanding of the interplay of effects on different scales. The central question is to determine those quantities on the microscale which are needed to for the correct description of the macroscopic evolution.
We aim to develop a mathematical framework for analyzing and modeling coupled systems with multiple scales. This will include Hamiltonian dynamics as well as different types of dissipation like gradient flows or rate-independent dynamics. The choice of models will be guided by specific applications in material modeling (e.g., thermoplasticity, pattern formation, porous media) and optoelectronics (pulse interaction, Maxwell-Bloch systems, semiconductors, quantum mechanics). The research will address mathematically fundamental issues like existence and stability of solutions but will mainly be devoted to the modeling of multiscale phenomena in evolution systems. We will focus on systems with geometric structures, where the dynamics is driven by functionals. Thus, we can go much beyond the classical theory of homogenization and singular perturbations. The novel features of our approach are
- the combination of different dynamical effects in one framework,
- the use of geometric and metric structures for coupled partial differential equations,
- the exploitation of Gamma-convergence for evolution systems driven by functionals.
Max ERC Funding
1 390 000 €
Duration
Start date: 2011-04-01, End date: 2017-03-31
Project acronym ANOPTSETCON
Project Analysis of optimal sets and optimal constants: old questions and new results
Researcher (PI) Aldo Pratelli
Host Institution (HI) FRIEDRICH-ALEXANDER-UNIVERSITAET ERLANGEN NUERNBERG
Call Details Starting Grant (StG), PE1, ERC-2010-StG_20091028
Summary The analysis of geometric and functional inequalities naturally leads to consider the extremal cases, thus
looking for optimal sets, or optimal functions, or optimal constants. The most classical examples are the (different versions of the) isoperimetric inequality and the Sobolev-like inequalities. Much is known about equality cases and best constants, but there are still many questions which seem quite natural but yet have no answer. For instance, it is not known, even in the 2-dimensional space, the answer of a question by Brezis: which set,
among those with a given volume, has the biggest Sobolev-Poincaré constant for p=1? This is a very natural problem, and it appears reasonable that the optimal set should be the ball, but this has never been proved. The interest in problems like this relies not only in the extreme simplicity of the questions and in their classical flavour, but also in the new ideas and techniques which are needed to provide the answers.
The main techniques that we aim to use are fine arguments of symmetrization, geometric constructions and tools from mass transportation (which is well known to be deeply connected with functional inequalities). These are the basic tools that we already used to reach, in last years, many results in a specific direction, namely the search of sharp quantitative inequalities. Our first result, together with Fusco and Maggi, showed what follows. Everybody knows that the set which minimizes the perimeter with given volume is the ball.
But is it true that a set which almost minimizes the perimeter must be close to a ball? The question had been posed in the 1920's and many partial result appeared in the years. In our paper (Ann. of Math., 2007) we proved the sharp result. Many other results of this kind were obtained in last two years.
Summary
The analysis of geometric and functional inequalities naturally leads to consider the extremal cases, thus
looking for optimal sets, or optimal functions, or optimal constants. The most classical examples are the (different versions of the) isoperimetric inequality and the Sobolev-like inequalities. Much is known about equality cases and best constants, but there are still many questions which seem quite natural but yet have no answer. For instance, it is not known, even in the 2-dimensional space, the answer of a question by Brezis: which set,
among those with a given volume, has the biggest Sobolev-Poincaré constant for p=1? This is a very natural problem, and it appears reasonable that the optimal set should be the ball, but this has never been proved. The interest in problems like this relies not only in the extreme simplicity of the questions and in their classical flavour, but also in the new ideas and techniques which are needed to provide the answers.
The main techniques that we aim to use are fine arguments of symmetrization, geometric constructions and tools from mass transportation (which is well known to be deeply connected with functional inequalities). These are the basic tools that we already used to reach, in last years, many results in a specific direction, namely the search of sharp quantitative inequalities. Our first result, together with Fusco and Maggi, showed what follows. Everybody knows that the set which minimizes the perimeter with given volume is the ball.
But is it true that a set which almost minimizes the perimeter must be close to a ball? The question had been posed in the 1920's and many partial result appeared in the years. In our paper (Ann. of Math., 2007) we proved the sharp result. Many other results of this kind were obtained in last two years.
Max ERC Funding
540 000 €
Duration
Start date: 2010-08-01, End date: 2015-07-31
Project acronym ANTHOS
Project Analytic Number Theory: Higher Order Structures
Researcher (PI) Valentin Blomer
Host Institution (HI) GEORG-AUGUST-UNIVERSITAT GOTTINGENSTIFTUNG OFFENTLICHEN RECHTS
Call Details Starting Grant (StG), PE1, ERC-2010-StG_20091028
Summary This is a proposal for research at the interface of analytic number theory, automorphic forms and algebraic geometry. Motivated by fundamental conjectures in number theory, classical problems will be investigated in higher order situations: general number fields, automorphic forms on higher rank groups, the arithmetic of algebraic varieties of higher degree. In particular, I want to focus on
- computation of moments of L-function of degree 3 and higher with applications to subconvexity and/or non-vanishing, as well as subconvexity for multiple L-functions;
- bounds for sup-norms of cusp forms on various spaces and equidistribution of Hecke correspondences;
- automorphic forms on higher rank groups and general number fields, in particular new bounds towards the Ramanujan conjecture;
- a proof of Manin's conjecture for a certain class of singular algebraic varieties.
The underlying methods are closely related; for example, rational points on algebraic varieties
will be counted by a multiple L-series technique.
Summary
This is a proposal for research at the interface of analytic number theory, automorphic forms and algebraic geometry. Motivated by fundamental conjectures in number theory, classical problems will be investigated in higher order situations: general number fields, automorphic forms on higher rank groups, the arithmetic of algebraic varieties of higher degree. In particular, I want to focus on
- computation of moments of L-function of degree 3 and higher with applications to subconvexity and/or non-vanishing, as well as subconvexity for multiple L-functions;
- bounds for sup-norms of cusp forms on various spaces and equidistribution of Hecke correspondences;
- automorphic forms on higher rank groups and general number fields, in particular new bounds towards the Ramanujan conjecture;
- a proof of Manin's conjecture for a certain class of singular algebraic varieties.
The underlying methods are closely related; for example, rational points on algebraic varieties
will be counted by a multiple L-series technique.
Max ERC Funding
1 004 000 €
Duration
Start date: 2010-10-01, End date: 2015-09-30
Project acronym COCAN
Project Complexity and Condition in Algebra and Numerics
Researcher (PI) Peter BÜRGISSER
Host Institution (HI) TECHNISCHE UNIVERSITAT BERLIN
Call Details Advanced Grant (AdG), PE1, ERC-2017-ADG
Summary "This proposal connects three areas that are considered distant from each other: computational complexity, algebraic geometry, and numerics. In the last decade, it became clear that the fundamental questions of computational complexity (P vs NP) should be studied in algebraic settings, linking them to problems in algebraic geometry. Recent progress on this challenging and very difficult questions led to surprising progress in computational invariant theory, which we want to explore thoroughly. We expect this to lead to solutions of computational problems in invariant theory that currently are considered infeasible. The complexity of Hilbert's null cone (the set of ""singular objects'') appears of paramount importance here. These investigations will also shed new light on the foundational questions of algebraic complexity theory. As an essential new ingredient to achieve this, we will tackle the arising algebraic computational problems by means of approximate numeric computations, taking into account the concept of numerical condition.
A related goal of the proposal is to develop a theory of efficient and numerically stable algorithms in algebraic geometry that reflects the properties of structured systems of polynomial equations, possibly with singularities. While there are various heuristics, a satisfactory theory so far only exists for unstructured systems over the complex numbers (recent solution of Smale's 17th problem), which seriously limits its range of applications. In this framework, the quality of numerical algorithms is gauged by a probabilistic analysis that shows small average (or smoothed) running time. One of the main challenges here consists of a probabilistic study of random structured polynomial systems. We will also develop and analyze numerical algorithms for finding or describing the set of real solutions, e.g., in terms of their homology.
"
Summary
"This proposal connects three areas that are considered distant from each other: computational complexity, algebraic geometry, and numerics. In the last decade, it became clear that the fundamental questions of computational complexity (P vs NP) should be studied in algebraic settings, linking them to problems in algebraic geometry. Recent progress on this challenging and very difficult questions led to surprising progress in computational invariant theory, which we want to explore thoroughly. We expect this to lead to solutions of computational problems in invariant theory that currently are considered infeasible. The complexity of Hilbert's null cone (the set of ""singular objects'') appears of paramount importance here. These investigations will also shed new light on the foundational questions of algebraic complexity theory. As an essential new ingredient to achieve this, we will tackle the arising algebraic computational problems by means of approximate numeric computations, taking into account the concept of numerical condition.
A related goal of the proposal is to develop a theory of efficient and numerically stable algorithms in algebraic geometry that reflects the properties of structured systems of polynomial equations, possibly with singularities. While there are various heuristics, a satisfactory theory so far only exists for unstructured systems over the complex numbers (recent solution of Smale's 17th problem), which seriously limits its range of applications. In this framework, the quality of numerical algorithms is gauged by a probabilistic analysis that shows small average (or smoothed) running time. One of the main challenges here consists of a probabilistic study of random structured polynomial systems. We will also develop and analyze numerical algorithms for finding or describing the set of real solutions, e.g., in terms of their homology.
"
Max ERC Funding
2 297 163 €
Duration
Start date: 2019-01-01, End date: 2023-12-31
Project acronym DIFFINCL
Project Differential Inclusions and Fluid Mechanics
Researcher (PI) Laszlo SZEKELYHIDI
Host Institution (HI) UNIVERSITAET LEIPZIG
Call Details Consolidator Grant (CoG), PE1, ERC-2016-COG
Summary Important problems in science often involve structures on several distinct length scales. Two typical examples are fine phase mixtures in solid-solid phase transitions and the complex mixing patterns in turbulent or multiphase flows. The microstructures in such situations influence in a crucial way the macroscopic behavior of the system, and understanding the formation, interaction and overall effect of these structures is a great scientific challenge. Although there is a large variety of models and descriptions for such phenomena, a recurring issue in the mathematical analysis is that one has to deal with very complex and highly non-smooth structures in solutions of the associated partial differential equations.
A common ground is provided by the analysis of differential inclusions, a theory whose development was strongly influenced by the influx of ideas from the work of Gromov on partial differential relations, building on celebrated constructions of Nash for isometric immersions, and the work of Tartar in the study of oscillation phenomena in nonlinear partial differential equations. A recent success of this approach is provided by my work on the h-principle in fluid mechanics and Onsager's conjecture. Against this background my aim in this project is to go significantly beyond the state of the art, both in terms of the methods and in terms of applications of differential inclusions. One part of the project is to continue my work on fluid mechanics with the ultimate goal to address important challenges in the field: providing an analytic foundation for the K41 statistical theory of turbulence and for the behavior of turbulent flows near instabilities and boundaries. A further aim is to explore rigidity phenomena and to attack several outstanding open problems in the context of differential inclusions, most prominently Morrey's conjecture on quasiconvexity and rank-one convexity.
Summary
Important problems in science often involve structures on several distinct length scales. Two typical examples are fine phase mixtures in solid-solid phase transitions and the complex mixing patterns in turbulent or multiphase flows. The microstructures in such situations influence in a crucial way the macroscopic behavior of the system, and understanding the formation, interaction and overall effect of these structures is a great scientific challenge. Although there is a large variety of models and descriptions for such phenomena, a recurring issue in the mathematical analysis is that one has to deal with very complex and highly non-smooth structures in solutions of the associated partial differential equations.
A common ground is provided by the analysis of differential inclusions, a theory whose development was strongly influenced by the influx of ideas from the work of Gromov on partial differential relations, building on celebrated constructions of Nash for isometric immersions, and the work of Tartar in the study of oscillation phenomena in nonlinear partial differential equations. A recent success of this approach is provided by my work on the h-principle in fluid mechanics and Onsager's conjecture. Against this background my aim in this project is to go significantly beyond the state of the art, both in terms of the methods and in terms of applications of differential inclusions. One part of the project is to continue my work on fluid mechanics with the ultimate goal to address important challenges in the field: providing an analytic foundation for the K41 statistical theory of turbulence and for the behavior of turbulent flows near instabilities and boundaries. A further aim is to explore rigidity phenomena and to attack several outstanding open problems in the context of differential inclusions, most prominently Morrey's conjecture on quasiconvexity and rank-one convexity.
Max ERC Funding
1 860 875 €
Duration
Start date: 2017-04-01, End date: 2022-03-31
Project acronym FLAT SURFACES
Project SL(2,R)-action on flat surfaces and geometry of extremal subvarieties of moduli spaces
Researcher (PI) Martin Moeller
Host Institution (HI) JOHANN WOLFGANG GOETHE-UNIVERSITATFRANKFURT AM MAIN
Call Details Starting Grant (StG), PE1, ERC-2010-StG_20091028
Summary Dynamics on polygonal billiard tables is best understood by unfolding the table and studying the resulting flat surface. The moduli space of flat surfaces carries a natural action of SL(2,R) and all the questions about Lie group actions on homogeneous spaces reappear in this
non-homogeneous setting in an even more interesting way.
Closed SL(2,R)-orbits give rise to totally geodesic
subvarieties of the moduli space of curves, called
Teichmueller curves. Their classifcation is a major goal over the coming years. The applicant's algebraic characterization of Teichmueller curves plus the comprehension of the Deligne-Mumford compactification of Hilbert modular varities
make this goal feasible.
on polygonal billiard tables is best understood
unfolding the table and studying the resulting
surface. The moduli space of flat surfaces carries
action of SL(2,R) and all the questions about
group actions on homogeneous spaces reappear in this homogeneous setting in an even more interesting way.
SL(2,R)-orbits give rise to totally geodesic
of the moduli space of curves, called
curves. Their classifcation is a major goal
the coming years. The applicant's algebraic characterization Teichmueller curves plus the comprehension of the Mumford compactification of Hilbert modular varities this goal feasible.
Summary
Dynamics on polygonal billiard tables is best understood by unfolding the table and studying the resulting flat surface. The moduli space of flat surfaces carries a natural action of SL(2,R) and all the questions about Lie group actions on homogeneous spaces reappear in this
non-homogeneous setting in an even more interesting way.
Closed SL(2,R)-orbits give rise to totally geodesic
subvarieties of the moduli space of curves, called
Teichmueller curves. Their classifcation is a major goal over the coming years. The applicant's algebraic characterization of Teichmueller curves plus the comprehension of the Deligne-Mumford compactification of Hilbert modular varities
make this goal feasible.
on polygonal billiard tables is best understood
unfolding the table and studying the resulting
surface. The moduli space of flat surfaces carries
action of SL(2,R) and all the questions about
group actions on homogeneous spaces reappear in this homogeneous setting in an even more interesting way.
SL(2,R)-orbits give rise to totally geodesic
of the moduli space of curves, called
curves. Their classifcation is a major goal
the coming years. The applicant's algebraic characterization Teichmueller curves plus the comprehension of the Mumford compactification of Hilbert modular varities this goal feasible.
Max ERC Funding
1 005 600 €
Duration
Start date: 2010-10-01, End date: 2015-09-30
Project acronym MODSIMCONMP
Project Modeling, Simulation and Control of Multi-Physics Systems
Researcher (PI) Volker Mehrmann
Host Institution (HI) TECHNISCHE UNIVERSITAT BERLIN
Call Details Advanced Grant (AdG), PE1, ERC-2010-AdG_20100224
Summary This proposal is aimed at developing and analyzing a fundamentally new interdisciplinary approach for the modeling, simulation, control and optimization of multi-physics, multi-scale dynamical systems. The new innovative feature is to generate models via a network of modularized uni-physics components, where each component incorporates a mathematical model for the dynamical behavior as well as a model for the uncertainties, e.g. due to modeling, discretization or finite precision computation errors. Based on this new modeling concept also new numerical simulation, control, and optimization techniques will be developed and incorporated, that allow a systematic adaptive error control (including the appropriate treatment of different scales,and the uncertainties) for the components as well as for the whole multi-physics model. In order to cope with the differential-algebraic and multi-scale character of the systems we will develop and analyze remodeling techniques for the components as well as for the whole network including the uncertainties and special structures. The new remodeled systems will be designed such that they allow an efficient and accurate dynamical simulation with high order numerical integration techniques as well as efficient methods for model reduction and open and closed loop control.
In an interdisciplinary corporation with colleagues from computer science and engineering we will extend the modeling language MODELICA to be able to incorporate the new features (in particular the uncertainties and modeling errors) and we also plan to implement the complete approach as a new software platform.
Summary
This proposal is aimed at developing and analyzing a fundamentally new interdisciplinary approach for the modeling, simulation, control and optimization of multi-physics, multi-scale dynamical systems. The new innovative feature is to generate models via a network of modularized uni-physics components, where each component incorporates a mathematical model for the dynamical behavior as well as a model for the uncertainties, e.g. due to modeling, discretization or finite precision computation errors. Based on this new modeling concept also new numerical simulation, control, and optimization techniques will be developed and incorporated, that allow a systematic adaptive error control (including the appropriate treatment of different scales,and the uncertainties) for the components as well as for the whole multi-physics model. In order to cope with the differential-algebraic and multi-scale character of the systems we will develop and analyze remodeling techniques for the components as well as for the whole network including the uncertainties and special structures. The new remodeled systems will be designed such that they allow an efficient and accurate dynamical simulation with high order numerical integration techniques as well as efficient methods for model reduction and open and closed loop control.
In an interdisciplinary corporation with colleagues from computer science and engineering we will extend the modeling language MODELICA to be able to incorporate the new features (in particular the uncertainties and modeling errors) and we also plan to implement the complete approach as a new software platform.
Max ERC Funding
1 899 924 €
Duration
Start date: 2011-04-01, End date: 2016-03-31
Project acronym NewtonStrat
Project Newton strata - geometry and representations
Researcher (PI) Eva VIEHMANN
Host Institution (HI) TECHNISCHE UNIVERSITAET MUENCHEN
Call Details Consolidator Grant (CoG), PE1, ERC-2017-COG
Summary The Langlands programme is a far-reaching web of conjectural or proven correspondences joining the fields of representation theory and of number theory. It is one of the centerpieces of arithmetic geometry, and
has in the past decades produced many spectacular breakthroughs, for example the proof of Fermat’s Last Theorem by Taylor and Wiles.
The most successful approach to prove instances of Langlands’ conjectures is via algebraic geometry, by studying suitable moduli spaces such as Shimura varieties. Their cohomology carries actions both of a linear algebraic group (such as GLn) and a Galois group associated with the number field one is studying. A central tool in the study of the arithmetic properties of these moduli spaces is the Newton stratification, a natural decomposition based on the moduli description of the space. Recently the theory of Newton strata has seen two major new developments: Representation-theoretic methods and results have been successfully established to describe their geometry and cohomology. Furthermore, an adic version of the Newton stratification has been defined and is already of prime importance in new approaches within the Langlands programme.
This project aims at uniting these two novel developments to obtain new results in both contexts with direct applications to the Langlands programme, as well as a close relationship and dictionary between the classical and the adic stratifications. It is subdivided into three parts which mutually benefit from each other: Firstly we investigate the geometry of Newton strata in loop groups and Shimura varieties, and representations in their cohomology. Secondly, we study corresponding geometric and cohomological properties of adic Newton strata. Finally, we establish closer ties between the two contexts. Here we want to obtain analogues to results on one side for the other, but more importantly aim at a direct comparison that explains the similar behaviour directly.
Summary
The Langlands programme is a far-reaching web of conjectural or proven correspondences joining the fields of representation theory and of number theory. It is one of the centerpieces of arithmetic geometry, and
has in the past decades produced many spectacular breakthroughs, for example the proof of Fermat’s Last Theorem by Taylor and Wiles.
The most successful approach to prove instances of Langlands’ conjectures is via algebraic geometry, by studying suitable moduli spaces such as Shimura varieties. Their cohomology carries actions both of a linear algebraic group (such as GLn) and a Galois group associated with the number field one is studying. A central tool in the study of the arithmetic properties of these moduli spaces is the Newton stratification, a natural decomposition based on the moduli description of the space. Recently the theory of Newton strata has seen two major new developments: Representation-theoretic methods and results have been successfully established to describe their geometry and cohomology. Furthermore, an adic version of the Newton stratification has been defined and is already of prime importance in new approaches within the Langlands programme.
This project aims at uniting these two novel developments to obtain new results in both contexts with direct applications to the Langlands programme, as well as a close relationship and dictionary between the classical and the adic stratifications. It is subdivided into three parts which mutually benefit from each other: Firstly we investigate the geometry of Newton strata in loop groups and Shimura varieties, and representations in their cohomology. Secondly, we study corresponding geometric and cohomological properties of adic Newton strata. Finally, we establish closer ties between the two contexts. Here we want to obtain analogues to results on one side for the other, but more importantly aim at a direct comparison that explains the similar behaviour directly.
Max ERC Funding
1 202 500 €
Duration
Start date: 2018-06-01, End date: 2023-05-31
Project acronym PEPCo
Project Problems in Extremal and Probabilistic Combinatorics
Researcher (PI) Mathias DR. SCHACHT
Host Institution (HI) UNIVERSITAET HAMBURG
Call Details Consolidator Grant (CoG), PE1, ERC-2016-COG
Summary Extremal and probabilistic combinatorics is a central and currently maybe the most active and fastest growing area in discrete mathematics. The field can be traced back to the work of Turán and it was established by Erdős through his fundamental contributions and his uncounted guiding questions. Since then it has grown into an important discipline with strong ties to other mathematical areas such as theoretical computer science, number theory, and ergodic theory.
The PI proposes a variety of extremal problems for hypergraphs and for sparse random and pseudorandom graphs. The work for hypergraphs is motivated by Turán’s problem, maybe the most prominent open problem in the area. After solving an analogous question for graphs, Turán asked to determine the maximum cardinality of a set E of three-element subsets of a given n-element set V such that for any 4 elements of V at least one triple is missing in E. This innocent looking problem seems to be out of reach by our current methods and despite a great deal of effort over the last 70 years, our knowledge is still very limited.
We suggest a variant of the problem by imposing additional restrictions on the distribution of the three-element subsets in E. These additional assumptions yield a finer control over the corresponding extremal problem. In fact, this leads to many interesting and hopefully more manageable subproblems, some of which were already considered by Erdős and Sós. We suggest a unifying framework for these problems and one of the main goals would be the development of new techniques for this type of problems. These additional assumptions on the hyperedge distribution are closely related to the theory of quasirandom discrete structures, which was pioneered by Szemerédi and became a central theme in the field. In fact, the hypergraph extension by Gowers and by Rödl et al. of the regularity lemma provide essential tools for this line of research.
Summary
Extremal and probabilistic combinatorics is a central and currently maybe the most active and fastest growing area in discrete mathematics. The field can be traced back to the work of Turán and it was established by Erdős through his fundamental contributions and his uncounted guiding questions. Since then it has grown into an important discipline with strong ties to other mathematical areas such as theoretical computer science, number theory, and ergodic theory.
The PI proposes a variety of extremal problems for hypergraphs and for sparse random and pseudorandom graphs. The work for hypergraphs is motivated by Turán’s problem, maybe the most prominent open problem in the area. After solving an analogous question for graphs, Turán asked to determine the maximum cardinality of a set E of three-element subsets of a given n-element set V such that for any 4 elements of V at least one triple is missing in E. This innocent looking problem seems to be out of reach by our current methods and despite a great deal of effort over the last 70 years, our knowledge is still very limited.
We suggest a variant of the problem by imposing additional restrictions on the distribution of the three-element subsets in E. These additional assumptions yield a finer control over the corresponding extremal problem. In fact, this leads to many interesting and hopefully more manageable subproblems, some of which were already considered by Erdős and Sós. We suggest a unifying framework for these problems and one of the main goals would be the development of new techniques for this type of problems. These additional assumptions on the hyperedge distribution are closely related to the theory of quasirandom discrete structures, which was pioneered by Szemerédi and became a central theme in the field. In fact, the hypergraph extension by Gowers and by Rödl et al. of the regularity lemma provide essential tools for this line of research.
Max ERC Funding
1 800 000 €
Duration
Start date: 2017-10-01, End date: 2022-09-30
Project acronym PTRCSP
Project Phase Transitions in Random Constraint Satisfaction Problems
Researcher (PI) Konstantinos PANAGIOTOU
Host Institution (HI) LUDWIG-MAXIMILIANS-UNIVERSITAET MUENCHEN
Call Details Consolidator Grant (CoG), PE1, ERC-2017-COG
Summary The systematic investigation of random discrete structures and processes was initiated by Erdős and Rényi in a seminal paper about random graphs in 1960. Since then the study of such objects has become an important topic that has remarkable applications not only in combinatorics, but also in computer science and statistical physics.
Random discrete objects have two striking characteristics. First, they often exhibit phase transitions, meaning that only small changes in some typically local control parameter result in dramatic changes of the global structure. Second, several statistics of the models concentrate, that is, although the support of the underlying distribution is large, the random variables usually take values in a small set only. A central topic is the investigation of the fine behaviour, namely the determination of the limiting distribution.
Although the current knowledge about random discrete structures is broad, there are many fundamental and long-standing questions with respect to the two key characteristics. In particular, up to a small number of notable exceptions, several well-studied models undoubtedly exhibit phase transitions, but we are not able to understand them from a mathematical viewpoint nor to investigate their fine properties. The goal of the proposed project is to study some prominent open problems whose solution will improve significantly our general understanding of phase transitions and of the fine behaviour in random discrete structures. The objectives include the establishment of phase transitions in random constraint satisfaction problems and the analysis of the limiting distribution of central parameters, like the chromatic number in dense random graphs. All these problems are known to be difficult and fundamental, and the results of this project will open up new avenues for the study of random discrete objects, both sparse and dense.
Summary
The systematic investigation of random discrete structures and processes was initiated by Erdős and Rényi in a seminal paper about random graphs in 1960. Since then the study of such objects has become an important topic that has remarkable applications not only in combinatorics, but also in computer science and statistical physics.
Random discrete objects have two striking characteristics. First, they often exhibit phase transitions, meaning that only small changes in some typically local control parameter result in dramatic changes of the global structure. Second, several statistics of the models concentrate, that is, although the support of the underlying distribution is large, the random variables usually take values in a small set only. A central topic is the investigation of the fine behaviour, namely the determination of the limiting distribution.
Although the current knowledge about random discrete structures is broad, there are many fundamental and long-standing questions with respect to the two key characteristics. In particular, up to a small number of notable exceptions, several well-studied models undoubtedly exhibit phase transitions, but we are not able to understand them from a mathematical viewpoint nor to investigate their fine properties. The goal of the proposed project is to study some prominent open problems whose solution will improve significantly our general understanding of phase transitions and of the fine behaviour in random discrete structures. The objectives include the establishment of phase transitions in random constraint satisfaction problems and the analysis of the limiting distribution of central parameters, like the chromatic number in dense random graphs. All these problems are known to be difficult and fundamental, and the results of this project will open up new avenues for the study of random discrete objects, both sparse and dense.
Max ERC Funding
1 219 462 €
Duration
Start date: 2018-04-01, End date: 2023-03-31