Modern theory of extremal structures  Page description

Help  Print 
Back »
 

Details of project

  
Identifier
101536
Type K
Principal investigator Simonovits, Miklós
Title in Hungarian Extremális struktúrák modern elmélete
Title in English Modern theory of extremal structures
Keywords in Hungarian véges struktúrák; véletlen struktúrák; kvázi véletlen struktúrák; gráf limeszek
Keywords in English finite strucutures; random structures; quasirandom structures; graph limits
Discipline
Mathematics (Council of Physical Sciences)100 %
Ortelius classification: Combinatorial analysis
Panel Mathematics and Computing Science
Department or equivalent Alfréd Rényi Institute of Mathematics
Participants Abért, Miklós
Elek, Gábor
Füredi, Zoltán
Gyori, Ervin
Sali, Attila
Szemerédi, Endre
T. Sós, Vera
Starting date 2012-01-01
Closing date 2016-06-30
Funding (in million HUF) 12.929
FTE (full time equivalent) 12.23
state closed project
Summary in Hungarian
Jelen pályázatunkban azt vizsgálnánk meg
-- különbözõ kombinatorikus struktúrákban
-- hogy mi a kapcsolat a struktúrák lokális és globális tulajdonágai között.
A diszkrét matematika legklasszikusabb ágai között szerepelnek az Extrém Gráfelmélet, Ramsey elmélet, és a véletlen gráfok elmélete.
Ezek szorosan kapcsolódnak egymáshoz is.

Az utóbbi évek egy gyorsan növõ kutatási területe a gráflimeszek elmélete.
Szorosan kapcsolódik a fenti területekhez és rámutat az Analizis és ezen területek kapcsolatára.

Emellett mindezek kapcsolatban vannak a híres Szemerédi Regularitási lemmával is, mely az egyik legfontosabb eszköz a kvázivéletlenstruktúrák vizsgálatában is, és fontos a limesz-elméletben is.

Korábbi kutatásainkat folytatva/kiterjesztve kutatnánk több extremális problémát, beleértve az Erdős-Sós fa-sejtést, a Komlós - Sós sejtést, hipergráf-problémákat, Ramsey problémákat. Eszközök szempontjából kiemelten a Regularitási Lemma alkalmazásait. Megvizsgálnánk bizonyos kombinatorikus számelméleti problémákat is.

Emellett a gráf-limesz elméletet kutatnánk, bizonyos eredmények kiterjesztését a jobb-konvergenciára, alkalmazásokat a csoportelméletben, a algebrai invariánsok és a gráflimesz kapcsolatát (korlátos fokú gráfoknál.)
Summary
We plan to study how -- in different combinatorial structures -- local and global properties affect each other. Some of the most classical parts of Discrete Mathematics are the Theory of Extremal Graphs, Ramsey Theory and the Theory of Random Graphs. They are strongly related to each other. A fairly new area is the Theory of Convergence and Limit of Graph Sequences. It is strongly related to the above fields, but also indicates that these classical fields are related to Analysis as well.

These are strongly connected to the Szemerédi Regularity Lemma, a key tool in the investigation of quasi-random graphs, playing important role in the theory of Limits of Graph Sequences.

Our research extends some of our earlier research to extremal graph problems connected with trees, including questions related to the Erdõs-Sós conjecture. Komlós-Sós conjecture, and to applications of the Regularity Lemma.

We also investigate new type extremal problems, for graphs, hypergraphs and other structures. We would investigate some problems in Combinatorial Number Theory, too.

Further, we investigate, how can results in the graph limit theory be extended from left-convergence to rightüconvergence. We investigate the connection of algebraic invariants and limits of graph sequences of bounded degrees.




 

Final report

  
Results in Hungarian
A munkánk jelentős része korábbi kutatásainkat folytatta, és Extremális Gráfelmélethez kapcsolódott. Jelentős része vonatkozott a megfelelő kombinatorikai területek kapcsolódásaira a matematika egyéb területeivel, pl. folytonos struktúrákhoz, kombinatorikus számelmélethez, kombinatorikus geometriához. Az extremális gráfelméleten belül sokat foglalkoztunk az Erdõs-Sós fákra vonatkozó sejtéssel (az ehhez kapcsolódó Loebl-Komlós-Sós sejtéssel, illetve az eredeti bizonyításunk bizonyos részleteivel). Számtalan bizonyításunk használja a Szemerédi regularitási lemmát. Sok eredményünk van hipergráf extremális problémákról. Újszerű eredményeket értünk el pl. a lineáris hipergráfokkal kapcsolatban, hipergráfok köreivel kapcsolatban, illetve nemlineáris hipergráfok lineáris részhipergráfjaival kapcsolatban. Sok eredményt értünk el a Gráf limeszekkel kapcsolatban is, mind a sűrű, mind a ritka gráfok esetében. Fontosak az algebrai, pl. a csoportelméleti kapcsolatokra vonatkozó publikációink. Sokan voltunk meghívva számos konferenciára, vagy más megtisztelő előadástartásra, különböző egyetemekre, főelőadóknak, több mint 40-szer.
Results in English
Large part of our work is a direct continuation of our earlier research. Some of the work is connected to embedding trees into large graphs, like the solution of the Erdős-Sós conjecture on trees, or the solution of the Loebl-Komlós-Sós conjecture. Several of our results are connected to the applications of Szemerédi regularity lemma. We also solved problems in connection with graph-coloring (and choosability) and in connection with applications of combinatorics in coding theory. We proved deep results on Turán type extremal problems for very sparse excluded hypergraphs, connected to the Ruzsa-Szemeredi theorem and to the Erdős-Gallai theorem. Some of our results are on linear hypergraph cycles. Many of other results connect extremal graph theory to other fields. e.g., to Graph limits. This area has two parts: the dense and the sparse case. We proved some new types of results about the "weak limit", on quasirandom properties, on graph coloring, on the statistics of the densities of monochromatic copies of fixed graphs, and also we proved some results on the sparse case. We have several results on groups, on the distribution of roots of graph polynomials, on applications of algebraic methods in combinatorial geometry, some results are related with combinatorial number theory, some others with combinatorial geometry. We were invited as conference invited speakers or colloquium speakers at various universities, more than 40 times.
Full text https://www.otka-palyazat.hu/download.php?type=zarobeszamolo&projektid=101536
Decision
Yes





 

List of publications

  
Miklós Abért, Péter Csikvári, Tamás Hubai: Matching measure, Benjamini-Schramm convergence and the monomer-dimer free energy, arXiv:1405.6740 (18 pages), 2016
Miklos Abért, Péter Csikvári, Péter Frenkel, Gábor Kun: Matchings in Benjamini-Schramm convergent graph sequences, arXiv:1405.3271, 2016
Miklós Abért, Tamás Hubai: Benjamini-Schramm convergence and the distribution of chromatic roots for sparse graphs, arXiv:1201.3861, 2016
Miklos Abert, Yair Glasner: Generic groups acting on regular trees, arXiv:math/0702736, 2016
Miklos Abert, Nikolay Nikolov: Rank gradient, cost of groups and the rank versus Heegaard genus problem, arXiv:math/0701361, 2016
Beka Ergemlidze, Ervin Győri, Abhishek Methuku:: 3-uniform hypergraphs and linear cycles, arXiv:1609.03934, 2016
Ervin Győri, Tamás Róbert Mezei: Partitioning orthogonal polygons into at most 8-vertex pieces, with application to an art gallery theorem, arXiv:1509.05227, 2016
Lucas Colucci, Péter L. Erdős, Ervin Győri, Tamás Róbert Mezei: Terminal-Pairability in Complete Bipartite Graphs, arXiv:1702.04313, 2016
Csilla Bujtás, Akbar Davoodi, Ervin Győri, Zsolt Tuza: Clique Coverings and Claw-free Graphs, arXiv:1608.07686, 2016
Ervin Györi, Tamás Róbert Mezei, Gábor Mészáros: Note on Terminal-Pairability in Complete Grid Graphs, arXiv:1606.06826, 2016
Akbar Davoodi, Ervin Győri, Abhishek Methuku, Casey Tompkins: An Erdős-Gallai type theorem for hypergraphs, arXiv:1608.03241, 2016
Ervin Győri, Gyula Y. Katona, László F. Papp, Casey Tompkins: The Optimal Pebbling Number of Staircase Graphs, arXiv:1611.09686, 2016
Zoltán Füredi, Zeinab Maleki: The minimum number of triangular edges and a symmetrization method for multiple graphs, arXiv:1411.0771, 2016
Zoltán Füredi: A proof of the stability of extremal graphs, Simonovits' stability from Szemerédi's regularity, arXiv:1501.03129, 2016
Zoltán Füredi, Lale Özkahya: On 3-uniform hypergraphs without a cycle of a given length, arXiv:1412.8083, 2016
Zoltán Füredi, Alexandr Kostochka, Ruth Luo: A stability version for a theorem of Erdős on nonhamiltonian graphs, arXiv:1608.05741, 2016
Zoltán Füredi, Alexandr Kostochka, Jacques Verstraëte: Stability in the Erdos--Gallai Theorem on cycles and paths, arXiv:1507.05338, 2016
Zoltán Füredi, Tao Jiang: Turán numbers of hypergraph trees, arXiv:1505.03210, 2016
Zoltan Furedi, Tao Jiang: Hypergraph Turan numbers of linear cycles, arXiv:1302.2387, 2016
Paul Balister, Béla Bollobás, Zoltán Füredi, Imre Leader, Mark Walters: Subtended Angles, arXiv:1502.07869, 2016
Bela Bollobas, Zoltan Furedi, Ida Kantor, G. O. H. Katona, Imre Leader: A coding problem for pairs of subsets, arXiv:1403.3847, 2016
Zoltan Füredi, David S. Gunderson: Extremal numbers for odd cycles, arXiv:1310.6766, 2016
Zoltán Füredi: On a theorem of Erdős and Simonovits on graphs not containing the cube, arXiv:1307.1062, 2016
Paul Balister, Béla Bollobás, Zoltán Füredi, John Thompson: Minimal symmetric differences of lines in projective planes, arXiv:1303.4117, 2016
Zoltán Füredi, Dániel Gerbner, Máté Vizer: A discrete isodiametric result: the Erdős-Ko-Rado theorem for multisets, arXiv:1212.1071, 2016
Vojtěch Rödl, Andrzej Ruciński, Mathias Schacht, Endre Szemerédi: On the Hamiltonicity of triple systems with high minimum degree, arXiv:1605.00773, 2016
Jan Hladký, János Komlós, Diana Piguet, Miklós Simonovits, Maya J. Stein, Endre Szemerédi: The approximate Loebl-Komlós-Sós Conjecture II: The rough structure of LKS graphs, arXiv:1408.3871, 2016
Jan Hladký, János Komlós, Diana Piguet, Miklós Simonovits, Maya J. Stein, Endre Szemerédi: The approximate Loebl-Komlós-Sós Conjecture IV: Embedding techniques and the proof of the main result, arXiv:1408.3870 (81 pages), 2016
Jan Hladký, János Komlós, Diana Piguet, Miklós Simonovits, Maya J. Stein, Endre Szemerédi: The Approximate Loebl-Komlós-Sós Conjecture III: The finer structure of LKS graphs, arXiv:1408.3866, 2016
Jan Hladký, János Komlós, Diana Piguet, Miklós Simonovits, Maya J. Stein, Endre Szemerédi: The approximate Loebl-Komlós-Sós Conjecture I: The sparse decomposition, arXiv:1408.3858, 2016
Jan Hladký, János Komlós, Diana Piguet, Miklós Simonovits, Maya Stein, Endre Szemerédi: The approximate Loebl-Komlós-Sós Conjecture, arXiv:1211.3050, 2016
Gabor Elek: Infinite dimensional representations of finite dimensional algebras and amenability, arXiv:1512.03959, 2016
Gabor Elek: Convergence and limits of linear representations of finite groups, arXiv:1406.5032, 2016
Z. Füredi, Jiang T; Seiver R: Exact solution of the hypergraph Turán problem for k-uniform linear paths, COMBINATORICA (ISSN: 0209-9683) (eISSN: 1439-6912) 34: (3) pp. 299-322. (2014), 2014
Gabor Elek, Balazs Szegedy: A measure-theory approach to the theory of dense hypergraphs, Advances in Mathematics, 231, 3-4, 1731-1772, 2012
Elek, Gábor: Lamplighter groups and von Neumann's continuous regular ring, Proc. Amer. Math. Soc. 144 (2016), no. 7, 2871–2883, 2016
Elek, Gábor: Convergence and limits of linear representations of finite groups, J. Algebra 450 (2016), 588–615., 2016
Elek, Gábor: Full groups and soficity, Proc. Amer. Math. Soc. 143 (2015), no. 5, 1943–1950., 2015
Abért, Miklós; Glasner, Yair; Virág, Bálint: The measurable Kesten theorem., Ann. Probab. 44 (2016), no. 3, 1601–1646., 2016
Abért, Miklós; Csikvári, Péter; Frenkel, Péter E.; Kun, Gábor: Matchings in Benjamini-Schramm convergent graph sequences, Trans. Amer. Math. Soc. 368 (2016), no. 6, 4197–4218., 2016
Abért, Miklós; Csikvári, Péter; Hubai, Tamás: Matching measure, Benjamini-Schramm convergence and the monomer-dimer free energy, J. Stat. Phys. 161 (2015), no. 1, 16–34., 2015
Abért, Miklós; Hubai, Tamás: Benjamini-Schramm convergence and the distribution of chromatic roots for sparse graphs, Combinatorica 35 (2015), no. 2, 127–151., 2015
Abért, Miklós; Glasner, Yair; Virág, Bálint: Kesten's theorem for invariant random subgroups, Duke Math. J. 163 (2014), no. 3, 465–488., 2014
Abért, Miklós; Weiss, Benjamin: Bernoulli actions are weakly contained in any free action, Ergodic Theory Dynam. Systems 33 (2013), no. 2, 323–333., 2013
Anstee, R. P.; Sali, Attila: Large forbidden configurations and design theory, Studia Sci. Math. Hungar. 53 (2016), no. 2, 157–166, 2016
Rácz, Gábor; Sali, Attila; Schewe, Klaus-Dieter: Semantic matching strategies for job recruitment: a comparison of new and known approaches., Foundations of information and knowledge systems, 149–168, Lecture Notes in Comput. Sci., 9616,, 2016
Gyárfás, András; Győri, Ervin; Simonovits, Miklós: On 3-uniform hypergraphs without linear cycles, J. Comb. 7 (2016), no. 1, 205–216., 2016
Hladký, Jan; Piguet, Diana; Simonovits, Miklós; Stein, Maya; Szemerédi, Endre: The approximate Loebl-Komlós-Sós conjecture and embedding trees in sparse graphs, Electron. Res. Announc. Math. Sci. 22 (2015), 1–11., 2015
Balogh, József; Hu, Ping; Simonovits, Miklós: Phase transitions in Ramsey-Turán theory, J. Combin. Theory Ser. B 114 (2015), 148–169., 2015
Simonovits, Miklós: Paul Erdős in the 21st century, Eur. Math. Soc. Newsl. No. 91 (2014), 23–29, 2014
Janson, Svante; Sós, Vera T.: More on quasi-random graphs, subgraph counts and graph limits, European J. Combin. 46 (2015), 134–160., 2015
Szemerédi, Endre: Structural approach to subset sum problems, Found. Comput. Math. 16 (2016), no. 6, 1737–1749, 2016
Szemerédi, Endre: Erdős's unit distance problem, Open problems in mathematics, 459–477, Springer, [Chapter], 2016
Szemerédi, Endre: Arithmetic progressions, different regularity lemmas and removal lemmas, Commun. Math. Stat. 3 (2015), no. 3, 315–328., 2015
Szemerédi, Endre: Is laziness paying off? ("Absorbing'' method), Colloquium De Giorgi 2010–2012, 17–34, Colloquia, 4, Ed. Norm., Pisa, 2013., 2013
Barát J. Z. Füredi, I. Kantor, Younjin Kim, B. Patkós: Large Bd -free and union-free subfamilies, SIAM J. Disc. Math. 26 (2012), 71–76., 2012
Z. Füredi; Y Kim: Cycle-Saturated Graphs with Minimum Number of Edges, JOURNAL OF GRAPH THEORY (ISSN: 0364-9024) 73: (2) pp. 203-215. (2013), 2013
C Bíró; Z Füredi; S Jabanbekam: Large Chromatic Number and Ramsey Graphs, GRAPHS AND COMBINATORICS (ISSN: 0911-0119) 29: (5) pp. 1183-1191. (2013), 2013
Z. Füredi;M Ruszinkó: Uniform hypergraphs containing no grids, ADVANCES IN MATHEMATICS (ISSN: 0001-8708) 240: pp. 302-324. (2013), 2013
Z. Füredi: Linear trees in uniform hypergraphs, EUROPEAN JOURNAL OF COMBINATORICS (ISSN: 0195-6698) 35: pp. 264-272. (2013), 2013
Z. Füredi; Kostochka A; Kumbhat M: Choosability with Separation of Complete Multipartite Graphs and Hypergraphs, JOURNAL OF GRAPH THEORY (ISSN: 0364-9024) &: p. &. (2013), 2013
Z. Füredi: Intersection representations of the complete bipartite graph, In: R L Graham;J Nesetril (szerk.) The Mathematics of Paul Erdős,. New York: Springer Verlag, 2013. pp. 127-134., 2013
E. Győri; J. Nesetril; A Sali: Preface: Selected Papers of EuroComb'11, EUROPEAN JOURNAL OF COMBINATORICS (ISSN: 0195-6698) 35: p. 1. (2014), 2014
A. Sárközy; V. T: Sós: On additive representation functions, n: R L Graham; J Nesetril (szerk.) The Mathematics of Paul Erdős,. New York: Springer Verlag, 2013. pp. 233-262., 2013
Ervin Gyori; Hao Li: 2-factors of k cycles in Hamiltonian graphs, International Conference on Cycles in Graphs, 2012
Elek G; Monod N: On the topological full group of a minimal cantor Z2-system, PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY (ISSN: 0002-9939) 141: (10) pp. 3549-3552. (2013), 2013
Abért Miklós; Weiss Benjamin: Bernoulli actions are weakly contained in any free action, ERGODIC THEORY AND DYNAMICAL SYSTEMS (Published online: 07 February 2012), 2012
Abért M; Elek G: Dynamical properties of profinite actions, ERGODIC THEORY AND DYNAMICAL SYSTEMS (ISSN: 0143-3857) 32: (6) pp. 1805-1835, 2012
Abért M; Nikolov N: Rank gradient, cost of groups and the rank versus Heegaard genus problem, JOURNAL OF THE EUROPEAN MATHEMATICAL SOCIETY (ISSN: 1435-9855) 14: (5) pp. 1657-1677., 2012
Abért M; Elek G: Hyperfinite actions on countable sets and probability measure spaces, Dynamical systems and group actions. 270 p.; Contemporary mathematics; 567., 2012
Elek G: Finite graphs and amenability, JOURNAL OF FUNCTIONAL ANALYSIS (ISSN: 0022-1236) 263: (9) pp. 2593-2614., 2012
Elek G; Szegedy B: A measure-theoretic approach to the theory of dense hypergraphs, ADVANCES IN MATHEMATICS (ISSN: 0001-8708) 231: (3-4) pp. 1731-1772, 2012
Füredi Z; Kim Y: The structure of the typical graphs of given diameter, DISCRETE MATHEMATICS (ISSN: 0012-365X) 313: (2) pp. 155-163., 2013
Füredi Zoltán; Ruszinkó Miklós: Uniform hypergraphs containing no grids, ADVANCES IN MATHEMATICS (ISSN: 0001-8708) (online), 2013
Füredi Z; Sali A: Optimal multivalued shattering, SIAM JOURNAL ON DISCRETE MATHEMATICS (ISSN: 0895-4801) 26: (2) pp. 737-744., 2012
Füredi Z; Kim Y: Cycle-Saturated Graphs with Minimum Number of Edges, JOURNAL OF GRAPH THEORY (ISSN: 0364-9024) (online), 2012
Frankl P; Füredi Z: A new short proof of the EKR theorem, JOURNAL OF COMBINATORIAL THEORY SERIES A (ISSN: 0097-3165) 119: (6) pp. 1388-1390., 2012
Füredi Z; Sali A: Some new bounds on partition critical hypergraphs, EUROPEAN JOURNAL OF COMBINATORICS (ISSN: 0195-6698) 33: (5) pp. 844-852., 2012
Biró C; Füredi Z; Jahanbekam S: Large Chromatic Number and Ramsey Graphs, GRAPHS AND COMBINATORICS (ISSN: 0911-0119) &: pp. 1-9., 2012
Füredi Z: 2-cancellative hypergraphs and codes, COMBINATORICS PROBABILITY AND COMPUTING (ISSN: 0963-5483) 21: (1-2) pp. 159-177., 2012
Győri E; Li H: The Maximum Number of Triangles in C2k+1-Free Graphs, COMBINATORICS PROBABILITY AND COMPUTING (ISSN: 0963-5483) 21: (1-22) pp. 187-191, 2012
Alberto Apostolico; Péter L Erdős; Ervin Győri; Zsuzsanna Lipták; Cinzia Pizzi: Efficient algorithms for the periodic subgraphs mining problem, JOURNAL OF DISCRETE ALGORITHMS (ISSN: 1570-8667) 17: pp. 24-30., 2012
Ervin Gyori; Hao Li: 2-factors of k cycles in Hamiltonian graphs, International Conference on Cycles in Graphs, 2012
ERVIN GYŐRI; NATHAN LEMONS: Hypergraphs with No Cycle of a Given Length, COMBINATORICS PROBABILITY AND COMPUTING (ISSN: 0963-5483) 21: (1-2) pp. 193-201., 2012
ERVIN GYŐRI; NATHAN LEMONS: 3-uniform hypergraphs avoiding a given odd cycle, COMBINATORICA (ISSN: 0209-9683) 32: (2) pp. 187-203., 2012
ERVIN GYŐRI; NATHAN LEMONS: Hypergraphs with no cycle of length 4, DISCRETE MATHEMATICS (ISSN: 0012-365X) 312: (9) pp. 1518-1520., 2012
Borgs C; Chayes JT; Lovász L; Sós VT; Vesztergombi K: Convergent sequences of dense graphs II. Multiway cuts and statistical physics, ANNALS OF MATHEMATICS (ISSN: 0003-486X) 176: (1) pp. 151-219., 2012
Tomasz Luczak; Miklós Simonovits; Jozef Skokan: On the multi-colored Ramsey numbers of cycles, JOURNAL OF GRAPH THEORY (ISSN: 0364-9024) 69: (2) pp. 169-175., 2012
Z. Füredi; M. Simonovits: The history of degenerate (bipartite) extremal graph problems, In: Lovász L; Ruzsa I; Sós V T; Palvolgyi D (szerk.) Erdős Centennial. 730 p. Konferencia helye, ideje: Budapest, Magyarország, 2013.07.01-2013.07.05. Berlin; Budapest:, 2013
M. Simonovits,s: Paul Turan's influence in Combinatorics, Number Theory, Analysis and Combinatorics: Proceedings of the Paul Turan memorial conference held August 22-26, 2011, in Budapest. Konferencia helye, ideje: Budapest, Mag, 2013
Elk G; Monod N: On the topological full group of a minimal cantor Z2-system, PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY (ISSN: 0002-9939) 141: (10) pp. 3549-3552. (2013), 2013
Elek G: Connes embeddings and von neumann regular closures of amenable group algebras, TRANSACTIONS OF THE AMERICAN MATHEMATICAL SOCIETY (ISSN: 0002-9947) 365: (6) pp. 3019-3039. (2013), 2013
M Abért; B Virág: Kestens theorem for invariant random subgroups, DUKE MATHEMATICAL JOURNAL (ISSN: 0012-7094) &: p. &. (2014) online, 2014
M. Abért; T Hubai: Benjamini-Schramm convergence and the distribution of chromatic roots for sparse graphs, COMBINATORICA (ISSN: 0209-9683) &: p. &. (2014) online, 2014
M. Abért; B Weiss: Bernoulli actions are weakly contained in any free action, ERGODIC THEORY AND DYNAMICAL SYSTEMS (ISSN: 0143-3857) 33: (2) pp. 323-333. (2013), 2013




 

Events of the project

  
2015-04-20 10:39:06
Résztvevők változása



Back »