Project acronym DISCONV
Project DISCRETE AND CONVEX GEOMETRY: CHALLENGES, METHODS, APPLICATIONS
Researcher (PI) Imre Barany
Host Institution (HI) MAGYAR TUDOMANYOS AKADEMIA RENYI ALFRED MATEMATIKAI KUTATOINTEZET
Call Details Advanced Grant (AdG), PE1, ERC-2010-AdG_20100224
Summary Title: Discrete and convex geometry: challenges, methods, applications
Abstract: Research in discrete and convex geometry, using tools from combinatorics, algebraic
topology, probability theory, number theory, and algebra, with applications in theoretical
computer science, integer programming, and operations research. Algorithmic aspects are
emphasized and often serve as motivation or simply dictate the questions. The proposed
problems can be grouped into three main areas: (1) Geometric transversal, selection, and
incidence problems, including algorithmic complexity of Tverberg's theorem, weak
epsilon-nets, the k-set problem, and algebraic approaches to the Erdos unit distance problem.
(2) Topological methods and questions, in particular topological Tverberg-type theorems,
algorithmic complexity of the existence of equivariant maps, mass partition problems, and the
generalized HeX lemma for the k-coloured d-dimensional grid. (3) Lattice polytopes and random
polytopes, including Arnold's question on the number of convex lattice polytopes, limit
shapes of lattice polytopes in dimension 3 and higher, comparison of random polytopes and
lattice polytopes, the integer convex hull and its randomized version.
Summary
Title: Discrete and convex geometry: challenges, methods, applications
Abstract: Research in discrete and convex geometry, using tools from combinatorics, algebraic
topology, probability theory, number theory, and algebra, with applications in theoretical
computer science, integer programming, and operations research. Algorithmic aspects are
emphasized and often serve as motivation or simply dictate the questions. The proposed
problems can be grouped into three main areas: (1) Geometric transversal, selection, and
incidence problems, including algorithmic complexity of Tverberg's theorem, weak
epsilon-nets, the k-set problem, and algebraic approaches to the Erdos unit distance problem.
(2) Topological methods and questions, in particular topological Tverberg-type theorems,
algorithmic complexity of the existence of equivariant maps, mass partition problems, and the
generalized HeX lemma for the k-coloured d-dimensional grid. (3) Lattice polytopes and random
polytopes, including Arnold's question on the number of convex lattice polytopes, limit
shapes of lattice polytopes in dimension 3 and higher, comparison of random polytopes and
lattice polytopes, the integer convex hull and its randomized version.
Max ERC Funding
1 298 012 €
Duration
Start date: 2011-04-01, End date: 2017-03-31
Project acronym DISCRETECONT
Project From discrete to contimuous: understanding discrete structures through continuous approximation
Researcher (PI) László Lovász
Host Institution (HI) EOTVOS LORAND TUDOMANYEGYETEM
Call Details Advanced Grant (AdG), PE1, ERC-2008-AdG
Summary Important methods and results in discrete mathematics arise from the interaction between discrete mathematics and ``continuous'' areas like analysis or geometry. Classical examples of this include topological methods, linear and semidefinite optimization generating functions and more. More recent areas stressing this connection are the theory of limit objects of growing sequences of finite structures (graphs, hypergraphs, sequences), differential equations on networks, geometric representations of graphs. Perhaps most promising is the study of limits of growing graph and hypergraph sequences. In resent work by the Proposer and his collaborators, this area has found highly nontrivial connections with extremal graph theory, the theory of property testing in computer science, to additive number theory, the theory of random graphs, and measure theory as well as geometric representations of graphs. This proposal's goal is to explore these interactions, with the participation of a number of researchers from different areas of mathematics.
Summary
Important methods and results in discrete mathematics arise from the interaction between discrete mathematics and ``continuous'' areas like analysis or geometry. Classical examples of this include topological methods, linear and semidefinite optimization generating functions and more. More recent areas stressing this connection are the theory of limit objects of growing sequences of finite structures (graphs, hypergraphs, sequences), differential equations on networks, geometric representations of graphs. Perhaps most promising is the study of limits of growing graph and hypergraph sequences. In resent work by the Proposer and his collaborators, this area has found highly nontrivial connections with extremal graph theory, the theory of property testing in computer science, to additive number theory, the theory of random graphs, and measure theory as well as geometric representations of graphs. This proposal's goal is to explore these interactions, with the participation of a number of researchers from different areas of mathematics.
Max ERC Funding
739 671 €
Duration
Start date: 2009-01-01, End date: 2014-06-30
Project acronym GROGandGIN
Project Growth in Groups and Graph Isomorphism Now
Researcher (PI) Laszlo Pyber
Host Institution (HI) MAGYAR TUDOMANYOS AKADEMIA RENYI ALFRED MATEMATIKAI KUTATOINTEZET
Call Details Advanced Grant (AdG), PE1, ERC-2016-ADG
Summary "In recent years there has been spectacular progress in studying growth in groups. A central result in this new area, obtained by Pyber-Szabo' (with a similar result proved by Breuillard-Green-Tao), shows that powers of generating subsets of finite simple groups of ""bounded dimension"" grow fast. Extending this Product Theorem Szabo' and the PI also proved a weaker version of a conjecture of Helfgott-Lindenstrauss. The Product Theorem has deep consequences in the study of groups, number theory and random walks. A central open question of the area is to remove the dependence on dimension in our Product Theorem. The PI formulated a new Conjecture, as a step forward. The way to further progress is via combining techniques from asymptotic group theory and probability theory. It is from this perspective that the current GROGandGIN proposal addresses issues concerning random walks. We examine how recent probabilistic arguments for random walks in the symmetric group may be transferred to matrix groups. While the first results in the subject of growth concern matrix groups we see an evolving theory of growth in permutation groups. This relies on earlier work of Babai and the PI which aims at finding proofs which do not use the Classification of Finite Simple Groups (CFSG). Similarly, Babai's famous Quasipolynomial Graph Isomorphism Algorithm builds on ideas from CFSG-free proofs due to him. The PI has recently removed CFSG from the analysis of Babai's algorithm. Our method goes ""halfway"" towards removing CFSG from proofs of growth results for permutation groups, currently a major open problem. The GROGandGIN initiative plans to improve various other parts of Babai's paper, working with several people who look at it from different angles, with an eye towards obtaining a Polynomial Graph Isomorphism algorithm. The GROGandGIN team will also study growth in Lie groups since the theory of random walks in Lie groups has been revitalised using analogues of our Product Theorem."
Summary
"In recent years there has been spectacular progress in studying growth in groups. A central result in this new area, obtained by Pyber-Szabo' (with a similar result proved by Breuillard-Green-Tao), shows that powers of generating subsets of finite simple groups of ""bounded dimension"" grow fast. Extending this Product Theorem Szabo' and the PI also proved a weaker version of a conjecture of Helfgott-Lindenstrauss. The Product Theorem has deep consequences in the study of groups, number theory and random walks. A central open question of the area is to remove the dependence on dimension in our Product Theorem. The PI formulated a new Conjecture, as a step forward. The way to further progress is via combining techniques from asymptotic group theory and probability theory. It is from this perspective that the current GROGandGIN proposal addresses issues concerning random walks. We examine how recent probabilistic arguments for random walks in the symmetric group may be transferred to matrix groups. While the first results in the subject of growth concern matrix groups we see an evolving theory of growth in permutation groups. This relies on earlier work of Babai and the PI which aims at finding proofs which do not use the Classification of Finite Simple Groups (CFSG). Similarly, Babai's famous Quasipolynomial Graph Isomorphism Algorithm builds on ideas from CFSG-free proofs due to him. The PI has recently removed CFSG from the analysis of Babai's algorithm. Our method goes ""halfway"" towards removing CFSG from proofs of growth results for permutation groups, currently a major open problem. The GROGandGIN initiative plans to improve various other parts of Babai's paper, working with several people who look at it from different angles, with an eye towards obtaining a Polynomial Graph Isomorphism algorithm. The GROGandGIN team will also study growth in Lie groups since the theory of random walks in Lie groups has been revitalised using analogues of our Product Theorem."
Max ERC Funding
1 965 340 €
Duration
Start date: 2017-08-01, End date: 2022-07-31
Project acronym LTDBud
Project Low Dimensional Topology in Budapest
Researcher (PI) Andras Istvan Stipsicz
Host Institution (HI) MAGYAR TUDOMANYOS AKADEMIA RENYI ALFRED MATEMATIKAI KUTATOINTEZET
Call Details Advanced Grant (AdG), PE1, ERC-2011-ADG_20110209
Summary "Heegaard Floer theory. In this project (in collaboration with P. Ozsváth and Z. Szabó) we plan to extend our earlier results computing various versions of Heegaard Floer homologies purely combinatorially. We also plan to find combinatorial definitions of these invariants (as graded groups). Such results will potentially lead to a combinatorial description of 4-dimensional Heegaard Floer (mixed) invariants, conjecturally equivalent to Seiberg-Witten invariants of smooth 4-manifolds. In particular, we hope to find a combinatorial proof of Donaldson’s diagonalizability theorem, and find relations between the Heegaard Floer and the fundamental groups of a 3-manifold.
Contact topology. Using Heegaard Floer theory and contact surgery, a systematic study of existence of tight contact structures on 3-manifolds is planned. Similar techniques also apply in studying Legendrian and transverse knots in contact 3-manifolds. In particular, the verification of the existence of tight structures on 3-manifolds given by surgery on a knot (with high enough framing) in the 3-sphere is proposed. Using the Legendrian invariant of knots, Legendrian and transverse simplicity can be conveniently studied. The ideas detailed in this part are planned to be carried out partly in collaboration with Paolo Lisca, Vera Vértesi and Hansjörg Geiges.
Exotic 4-manifolds. Extending our previous results, we plan to investigate the existence of exotic smooth structures on 4-manifolds with small Euler characteristics, such as the complex projective plane CP2, its blow-up CP2#CP2-bar, the product of two complex projective lines CP1×CP1 and ultimately the 4-dimensional sphere S4. We plan to investigate the effect of the Gluck transformation. Possible extensions of the rational blow down procedure (successful in producing exotic structures) will be also studied. We plan collaborations with Zoltán Szabó, Daniel Nash and Mohan Bhupal in these questions."
Summary
"Heegaard Floer theory. In this project (in collaboration with P. Ozsváth and Z. Szabó) we plan to extend our earlier results computing various versions of Heegaard Floer homologies purely combinatorially. We also plan to find combinatorial definitions of these invariants (as graded groups). Such results will potentially lead to a combinatorial description of 4-dimensional Heegaard Floer (mixed) invariants, conjecturally equivalent to Seiberg-Witten invariants of smooth 4-manifolds. In particular, we hope to find a combinatorial proof of Donaldson’s diagonalizability theorem, and find relations between the Heegaard Floer and the fundamental groups of a 3-manifold.
Contact topology. Using Heegaard Floer theory and contact surgery, a systematic study of existence of tight contact structures on 3-manifolds is planned. Similar techniques also apply in studying Legendrian and transverse knots in contact 3-manifolds. In particular, the verification of the existence of tight structures on 3-manifolds given by surgery on a knot (with high enough framing) in the 3-sphere is proposed. Using the Legendrian invariant of knots, Legendrian and transverse simplicity can be conveniently studied. The ideas detailed in this part are planned to be carried out partly in collaboration with Paolo Lisca, Vera Vértesi and Hansjörg Geiges.
Exotic 4-manifolds. Extending our previous results, we plan to investigate the existence of exotic smooth structures on 4-manifolds with small Euler characteristics, such as the complex projective plane CP2, its blow-up CP2#CP2-bar, the product of two complex projective lines CP1×CP1 and ultimately the 4-dimensional sphere S4. We plan to investigate the effect of the Gluck transformation. Possible extensions of the rational blow down procedure (successful in producing exotic structures) will be also studied. We plan collaborations with Zoltán Szabó, Daniel Nash and Mohan Bhupal in these questions."
Max ERC Funding
1 208 980 €
Duration
Start date: 2012-04-01, End date: 2017-03-31
Project acronym POTENTIALTHEORY
Project Potential theoretic methods in approximation and orthogonal polynomials
Researcher (PI) Vilmos Totik
Host Institution (HI) SZEGEDI TUDOMANYEGYETEM
Call Details Advanced Grant (AdG), PE1, ERC-2010-AdG_20100224
Summary The project is aimed at systematic applications of potential theoretical
methods in approximation theory and in the theory of orthogonal polynomials.
Various open problems are proposed in different fields which
can be attacked with tools that have been developed in the
near past or are to be developed within the project.
The main areas are asymptotic behavior of Christoffel functions on the
real line and on curves, the universality problem in random matrices,
orthogonal polynomials and their zeros, polynomial inequalities, approximation
by homogeneous polynomials and some
questions in numerical analysis. The research problems and areas
discussed in the proposal are intensively investigated in current research. As has been the
case in the past, PhD students will be actively involved in the project.
Summary
The project is aimed at systematic applications of potential theoretical
methods in approximation theory and in the theory of orthogonal polynomials.
Various open problems are proposed in different fields which
can be attacked with tools that have been developed in the
near past or are to be developed within the project.
The main areas are asymptotic behavior of Christoffel functions on the
real line and on curves, the universality problem in random matrices,
orthogonal polynomials and their zeros, polynomial inequalities, approximation
by homogeneous polynomials and some
questions in numerical analysis. The research problems and areas
discussed in the proposal are intensively investigated in current research. As has been the
case in the past, PhD students will be actively involved in the project.
Max ERC Funding
402 000 €
Duration
Start date: 2011-01-01, End date: 2016-12-31
Project acronym PRIMEGAPS
Project Gaps between primes and almost primes. Patterns in primes and almost primes. Approximations to the twin prime and Goldbach conjectures
Researcher (PI) Janos Pintz
Host Institution (HI) MAGYAR TUDOMANYOS AKADEMIA RENYI ALFRED MATEMATIKAI KUTATOINTEZET
Call Details Advanced Grant (AdG), PE1, ERC-2008-AdG
Summary The twin prime conjecture, that n and n+2 are infinitely often primes simultaneously, is probably the oldest unsolved problem in mathematics. De Polignac (1849) conjectured that for every even value of h, n and n+h are infinitely often primes simultaneously. These are the most basic problems on gaps and patterns in primes. Another one is the conjecture of Waring (1770), stating that there are arbitrarily long arithmetic progressions (AP) of primes. For the newest developments we cite Granville (Bull. AMS 43 (2006), p.93): ): Despite much research of excellent quality, there have been few breakthroughs on the most natural questions about the distribution of prime numbers in the last few decades. That situation has recently changed dramatically with two extraordinary breakthroughs, each on questions that the experts had held out little hope for in the foreseeable future. Green and Tao proved that there are infinitely many k-term arithmetic progressions of primes using methods that are mostly far removed from mainstream analytic number theory. Indeed, their work centers around a brilliant development of recent results in ergodic theory and harmonic analysis. Their proof is finished, in a natural way, by an adaptation of the proof of the other fantastic new result in this area, Goldston, Pintz and Yildirim s proof that there are small gaps between primes. The proposal's aim is to study these types of patterns in primes with possible combination of the two theories. We quote 3 of the main problems, the first one being the most important. 1) Bounded Gap Conjecture. Are there infinitely many bounded gaps between primes? 2) Suppose that primes have a level of distribution larger than 1/2. Does a fixed h exists such that for every k there is a k-term AP of generalised twin prime pairs (p, p+h)? 3) Erdôs' conjecture for k=3. Suppose A is a sequence of natural numbers, such that the sum of their reciprocals is unbounded. Does A contain infinitely many 3-term AP's?
Summary
The twin prime conjecture, that n and n+2 are infinitely often primes simultaneously, is probably the oldest unsolved problem in mathematics. De Polignac (1849) conjectured that for every even value of h, n and n+h are infinitely often primes simultaneously. These are the most basic problems on gaps and patterns in primes. Another one is the conjecture of Waring (1770), stating that there are arbitrarily long arithmetic progressions (AP) of primes. For the newest developments we cite Granville (Bull. AMS 43 (2006), p.93): ): Despite much research of excellent quality, there have been few breakthroughs on the most natural questions about the distribution of prime numbers in the last few decades. That situation has recently changed dramatically with two extraordinary breakthroughs, each on questions that the experts had held out little hope for in the foreseeable future. Green and Tao proved that there are infinitely many k-term arithmetic progressions of primes using methods that are mostly far removed from mainstream analytic number theory. Indeed, their work centers around a brilliant development of recent results in ergodic theory and harmonic analysis. Their proof is finished, in a natural way, by an adaptation of the proof of the other fantastic new result in this area, Goldston, Pintz and Yildirim s proof that there are small gaps between primes. The proposal's aim is to study these types of patterns in primes with possible combination of the two theories. We quote 3 of the main problems, the first one being the most important. 1) Bounded Gap Conjecture. Are there infinitely many bounded gaps between primes? 2) Suppose that primes have a level of distribution larger than 1/2. Does a fixed h exists such that for every k there is a k-term AP of generalised twin prime pairs (p, p+h)? 3) Erdôs' conjecture for k=3. Suppose A is a sequence of natural numbers, such that the sum of their reciprocals is unbounded. Does A contain infinitely many 3-term AP's?
Max ERC Funding
1 376 400 €
Duration
Start date: 2008-11-01, End date: 2013-10-31
Project acronym REGULARITY
Project Regularity and Irregularity in Combinatorics and Number Theory
Researcher (PI) Endre Szemeredi
Host Institution (HI) MAGYAR TUDOMANYOS AKADEMIA RENYI ALFRED MATEMATIKAI KUTATOINTEZET
Call Details Advanced Grant (AdG), PE1, ERC-2012-ADG_20120216
Summary "Regularity and irregularity plays a central role in mathematics. In the present research proposal we will select problems from combinatorics and number theory (including additive combinatorics), where regularity and irregularity appear. In some cases we have to deal, e.g., with arbitrary finite or infinite subsets of natural numbers, where the only information we have is their cardinality, namely, that they are of positive (lower asymptotic) density within the set of all natural numbers or within the interval [1,N] for a large N. In other cases we consider an arbitrary distribution of n points within the unit square, where all we know is the density of our point set. The goal is often to show that certain configurations appear within the arbitrary set of numbers or points. These configurations definitely appear in a random set of numbers or points, but we have to show this for an arbitrary set of numbers or points with certain general properties. In order to reach our goal one can use two well-known methods. The first one is deterministic, often some kind of greedy algorithm. The second is the probabilistic method of Erdős, which shows that almost all arrangements of the given points or numbers (or graphs) fulfill the wanted property. A third method, the so called pseudorandom method, was initiated by the PI (together with M. Ajtai and J. Komlós), uses a combination of these. In other cases we have a deterministic set of numbers with certain quasi-random properties, for example, the primes. Randomness was the key idea in the recent breakthrough of Green and Tao, in proving that primes contain arbitrarily long arithmetic progressions. We will deal with 6 groups of problems: (i) finite or infinite sequences of integers, (ii) difference sets and Fourier analysis, (iii) graph and hypergraph embedding theorems, (iv) Ramsey theory, (v) distribution of points in the plane and in the unit square, (vi) regularities and irregularities in the distribution of primes."
Summary
"Regularity and irregularity plays a central role in mathematics. In the present research proposal we will select problems from combinatorics and number theory (including additive combinatorics), where regularity and irregularity appear. In some cases we have to deal, e.g., with arbitrary finite or infinite subsets of natural numbers, where the only information we have is their cardinality, namely, that they are of positive (lower asymptotic) density within the set of all natural numbers or within the interval [1,N] for a large N. In other cases we consider an arbitrary distribution of n points within the unit square, where all we know is the density of our point set. The goal is often to show that certain configurations appear within the arbitrary set of numbers or points. These configurations definitely appear in a random set of numbers or points, but we have to show this for an arbitrary set of numbers or points with certain general properties. In order to reach our goal one can use two well-known methods. The first one is deterministic, often some kind of greedy algorithm. The second is the probabilistic method of Erdős, which shows that almost all arrangements of the given points or numbers (or graphs) fulfill the wanted property. A third method, the so called pseudorandom method, was initiated by the PI (together with M. Ajtai and J. Komlós), uses a combination of these. In other cases we have a deterministic set of numbers with certain quasi-random properties, for example, the primes. Randomness was the key idea in the recent breakthrough of Green and Tao, in proving that primes contain arbitrarily long arithmetic progressions. We will deal with 6 groups of problems: (i) finite or infinite sequences of integers, (ii) difference sets and Fourier analysis, (iii) graph and hypergraph embedding theorems, (iv) Ramsey theory, (v) distribution of points in the plane and in the unit square, (vi) regularities and irregularities in the distribution of primes."
Max ERC Funding
1 776 000 €
Duration
Start date: 2013-03-01, End date: 2018-02-28
