Combinatorics, algorithms, stochastics  Page description

Help  Print 
Back »
 

Details of project

  
Identifier
76099
Type K
Principal investigator Hajnal, Péter
Title in Hungarian Kombinatorika, algoritmusok, véletlen
Title in English Combinatorics, algorithms, stochastics
Keywords in Hungarian gráfok, geometria, véletlen, agoritmusok
Keywords in English graphs, geometry, stochastics, algorithms
Discipline
Mathematics (Council of Physical Sciences)100 %
Ortelius classification: Combinatorial analysis
Panel Mathematics and Computing Science
Department or equivalent Bolyai Institute (University of Szeged)
Participants Ambrus, Gergely
Balogh, József
Barát, János
Csaba, Béla
Mester, Péter
Mészáros, Viola
Nagy-György, Judit
Pluhár, András Sándor
Timár, Ádám
Starting date 2009-02-01
Closing date 2013-08-31
Funding (in million HUF) 14.000
FTE (full time equivalent) 9.67
state closed project
Summary in Hungarian
A témavezetõ korábbi pályázatához kapcsoló, a szegedi kombinatorikai
csoport kutatásainak folytatása.

Az összes kutatónk az esetleges különbözõ érdeklõdés ellenére
is szorosan kapcsolatot tart, közös szemináriumunkon ismeretjük
ötleteinket, több külföldi elõadó meghívását tervezzük

Gráfelmélet, sztochasztika, geometria, algoritmusok, játékok a
fontos témakörök, amiket vizsgálunk és továbbra is vizsgálni
szeretnénk. Különösen érdeklódéssel ezen témakörök
kapcsolatának vizsgálatára. Ilyen problémák jelenleg is érdeklõdésünk
középpontjában állnak. Ezeket a részletes kutatási tervben vázoljuk.
Summary
This is the contuniation of the leading researcher's
previous projects with the main goal to form, to keep together the combinatorics
group at The University of Szeged.

We have various interests but we keep open eyes on each others
research. The combinatorics seminar at Szeged is an open forum with
many visitors from Budapest and from abroad.

Graph theory, probability theory, geometry, algorithms and
combinatorial game theory are the main topics we have investigated and
we plan to continue to investigate in the future with special regard
to the connections between these branches of combinatorics. Special
problems we plan to investigate are listed in our research plan.




 

Final report

  
Results in Hungarian
A gráfelmélet, kombinatorika központi kérdései egyre több mély módszert igényelnek. Sztochasztikus, geometriai, algoritmikus, játékelméleti módszerek fejlődnek ki. Közben ezen fejezetek is gazdagodnak kombinatorikus problémákkal. Ezen kölcsönhatás egy igen izgalmas, gyorsan fejlődő területét adja a matematikának. Ebben a környezetben kutattunk. Több régi sejtést sikerült megoldanunk, illetve újabb kutatásokba kapcsolódtunk be sikeresen. Több mint 90 publikációnk született. Széleskörű nemzetközi kapcsolatokat építettünk ki. A szegedi kombinatorika szeminárium egy aktív kutató műhely, ahová budapesti és nemzetközi kutatók is szívesen ellátogatnak.
Results in English
The central questions of graph theory and combinatorics requires more and more sophisticated, involved methods. Stochastical, geometrical, algorithmic, game theoretical methods are devised. At the same time these topics are enriched by combinatorial problems. This interaction creates an interesting, fast evolving branch of mathematics. Our research is situated in this circumstances. We have solved some old problems, and we connected to some recent researches. We published over 90 research papers. Our research is based on a local research group and on a broad international connection. The combinatorics seminar at Szeged is an active reseach workshop, where other researchers from Budapest and from abroad are pleased to visit and who are wellcomed.
Full text https://www.otka-palyazat.hu/download.php?type=zarobeszamolo&projektid=76099
Decision
Yes





 

List of publications

  
J. Barát, P. Hajnal, Y. Lin, A. Yang: On the structure of graphs with path-width at most two, Studia Scientiarum Mathematicarum Hungarica, 49 (2012), 211--222, 2012
J. Barát, Z. Füredi, I. Kantor, Y. Kim, B. Patkós: Large $B_d$-free and union-free subfamilies, SIAM J. Discrete Mathematics, 26 (2012), 71--76, 2012
J. Barát, D. Gerbner: Edge-decomposition of graphs into copies of a tree with four edges, The Electronic Journal of Combinatorics, 2013
J. Barát, J. Czap: Vertex coloring of plane graphs with nonrepetitive boundary paths, Journal of Graph Theory, 2013
J. Barát, I.M. Wanless: A cube dismantling problem related to bootstrap percolation, Journal of Statistical Physics, 149 (2012), 754--770, 2012
A. Bóta, M. Krész and A. Pluhár: Approximations of the Generalized Cascade Model, Acta Cybernetica, 21 (2013) 37--51, 2013
A. Csernenszky, C. I. Mándity and A. Pluhár: On Chooser-Picker Positional Games, Discrete Mathematics, 2009
A. Pluhár: Greedy colorings of uniform hypergraphs, Random Structures and Algorithms, 2009
J. Balogh, R. Martin and A. Pluhár: The diameter game, Random Structures and Algorithms, 2009
A. Csernenszky, Gy. Kovács, M. Krész, A. Pluhár and T. Tóth: The use of infection models in accounting and crediting, Challenges for Analysis of the Economy, the Businesses, and Social Progress, 2009
Zs. Gazdag, Sz. Iván, J. Nagy-György: Improved upper bounds on synchronizing nondeterministic automata, Information Processing Letters, 2009
J. Nagy-György: Randomized algorithm for the k-server problem on decomposable spaces, Journal of Discrete Algorithms, 2009
B. Csaba, I. Levitt, J. Nagy-Gyorgy, E. Szemeredi: Tight bounds on embedding bounded degree trees, "Fete of Combinatorics", 2009
J. Balogh, B. Bollobas, and R. Morris: Bootstrap percolation in three dimensions, Annals of Probability, 2009
J. Balogh A. Kostochka, N. Prince, and M. Stiebitz: The Erdos-Lovasz Tihany Conjecture for quasi-line graphs, Discrete Mathematics, 2009
J. Balogh, B. Bollobas, and R. Morris: Majority bootstrap percolation on the hypercube, Combinatorics, Probability and Computing, 2009
N. Alon, J. Balogh, A. Kostochka, and W. Samotij: Sizes of induced subgraphs of Ramsey graphs, Random Structures and Algorithms, 2009
J. Balogh, T. Bohman and D. Mubayi: Erdos-Ko-Rado in Random Hypergraphs, Combinatorics, Probability and Computing, 2009
J. Balogh, Bollobas and Simonovits: The typical structure of graphs without given excluded subgraphs, Random Structures and Algorithms, 2009
J. Balogh and R. Martin: On Avoider-Enforcergames, SIAM Journal on Discrete Mathematics, 2009
J. Balogh, B. Bollobas, M. Saks, and V. T. Sos: On the diversity function of a hereditary graph property, Journal of Combinatorial Theory, 2009
Barát J, Hajnal P.: Saturated tilings with dominoes and 2x2 squares, 6th Japanese-Hungarian Symposium on Discrete Mathematics, 2009
J. Cibulka, J. Kyncl, V. Meszaros, R. Stolar and P. Valtr: Hamiltonian alternating paths on bicolored double-chains, Graph Drawing 2008, Lecture Notes in Computer Science 5417, 181-192, Springer, Berlin, 2009, 2009
J. Cibulka, J. Kyncl, V. Meszaros, R. Stolar and P. Valtr: Solution of Peter Winkler's pizza problem, Fete of Combinatorics, 2009
P. Hajnal. G. Nagy: Simply sequentially additive labelings of 2-regular graphs, Discrete Mathematics, 2009
J. Nagy-György: Online coloring graphs with high girth and high odd girth, Operations Research Letters, 2010
J. Balogh, B. Csaba, M. Pei and W. Samotij: Large Bounded Degree Trees in Expanding Graphs, Electronic Journal of Combinatorics, 2010
J. Balogh and W. Samotij: Almost all $C_4$-free graphs have less than $(1-\varepsilon)\ex(n,C_4)$ edges, SIAM J. Discrete Mathematics, 2010
J. Balogh and J. Butterfield: Online Ramsey Games for Triangles in Random Graphs, Discrete Mathematics, 2010
J. Balogh, B. Bollobas, and R. Morris: Bootstrap percolation in high dimensions, Combinatorics, Probability and Computing, 2010
J. Balogh and J. Butterfield: Excluding induced subgraphs: critical graphs, Random Structures and Algorithms, 2011
J. Balogh, Bollobas, and Simonovits: The fine structure of octahedron-free graphs, Journal of Combinatorial Theory, Series B., 2011
J. Balogh, B. Csaba and W. Samotij: Local resilience of almost spanning trees in random graphs, Random Structures and Algorithms, 2011
J Barát, G Tóth: Towards the Albertson Conjecture, ELECTRONIC JOURNAL OF COMBINATORICS, 2010
B. Csaba, I. Levitt, J. Nagy-György, E. Szemerédi: Tight bounds for embedding bounded degreee trees, Bolyai Society Mathematical Studies, X.(2010), Fete of Combinatorics, 2010
J. Cibulka, J. Kynˇcl, V. Mészáros, R. Stolaˇr, P. Valtr: Solution of Peter Winkler's Pizza Problem, Fete of Combinatorics, Bolyai Society Mathematical Studies, Vol. 20, 2010
J. Cibulka, J. Kynˇcl, V. Mészáros, R. Stolaˇr, P. Valtr: Graph sharing games: complexity and connectivity (extended abstract), TAMC 2010, Lecture Notes in Computer Science 6108, 340-349, Springer, Berlin, 2010
J. Cibulka, J. Kynˇcl, V. Mészáros, R. Stolaˇr, P. Valtr: On three parameters of invisibility graphs (extended abstract), Computing and Combinatorics (proceedings of COCOON 2010), 2010
A. Csernenszky, Gy. Kovács, M. Krész, A. Pluhár: Parameter Optimization of Infection Model, CS^2 Conference of PhD Students in Computer Science, 2010
L. Csizmadia, A. Bóta and A. Pluhár: Community detection and its use in Real Graphs, Proceedings of the 13th International Multiconference INFORMATION SOCIETY - IS, 2010
E. Griechisch and A. Pluhár: Community Detection by using the Extended Modularity, CS2 Conference of PhD Students in Computer Science, 2010
Gy. Kovács, M. Krész and A. Pluhár: The Spread of Infection in Real Networks, Circuits of Profit: Business Network Research Conference, 2010
Ádám Timár: Invariant 5-colorings of random planar maps, Ergodic Theory and Dynamical Systems, 2010
A. Bandyopadhyay, J. Steif and Á. Timár: On the cluster size distribution for percolation on some general graphs, Revista Matematica Iberoamericana 26, 2010
Cs. Bujtás, Gy. Dósa, Cs. Imreh, J. Nagy-György, Zs. Tuza: The Graph-Bin Packing Problem, International Journal of Foundations of Computer Science, 2011, 22 (8), pp. 1971-1993, 2011
L. Epstein, Cs. Imreh, A. Levin, J. Nagy-György: On variants of file caching, Proc. of the 38th ICALP, 2011, part 1, 195-206., 2011
J. Balogh, B. Bollobas, M. Krivelevich, T. Mueller and M. Walters: Hamilton cycles in random geometric graphs, Annals of Applied Probability, (2011)21 1053--1072., 2011
N. Alon, J. Balogh, B. Bollob\'as and R. Morris: The structure of almost all graphs in a hereditary property, Journal of Combinatorial Theory, Series B. (2011)101 85--110., 2011
J. Balogh and W. Samotij: The number of $K_{m,m}$-free graphs, Combinatorica (2011) 31 131--150., 2011
J. Balogh, J. Lenz and H. Wu: Complete Minors, Independent Sets, and Chordal Graphs, Discussiones Mathematicae Graph Theory, (2011)31 (4) 639--674 D., 2011
J. Balogh and W. Samotij: The number of $K_{s,t}$-free graphs, Journal of the London Mathematical Society, (2011) 83, 368--388., 2011
J. Balogh and D. Mubayi: Almost all triple systems with independent neighborhoods are semi-partite, Journal of Combinatorial Theory, Series A, 118, (2011) 1494--1518., 2011
J. Balogh and A. Kostochka: Large minors in graphs with a given stability number, Discrete Mathematics, (2011)311, 2203--2215., 2011
J. Balogh, and W. Samotij: On the Chvatal-Erdos triangle game, Electronic J. of Combinatorics, 18 (2011) Paper 72., 2011
J. Balogh and A. Pluhár: The positive minimum degree on game sparse graphs, Electronic J. of Combinatorics, 19 (2012) Paper 22., 2012
G Ambrus, P. Kevei, V. Vigh: The diminishing segment process, Stat. Prob. Letters 82 (2012), no.1., 191-195., 2012
A. Bota, M. Kresz and A. Pluhar: Dynamic Communities and their Detection, Acta Cybernetica, 20 (2011) 35--52., 2011
E. Griechisch and A. Pluhar: Community Detection by using the Extended Modularity, Acta Cybernetica, 20 (2011) 69--85., 2011
A. Bota, M. Kresz and A. Pluhar: Systematic learning of edge probabilities in the Domingos-Richardson model, Int. J. Complex Systems in Science, 1(2) (2011) 115--118., 2011
A. Csernenszky, R. Martin and A. Pluhar: On the Complexity of Chooser-Picker Positional Games, Integers, 11 (2011)., 2011
B. Csaba, T. Plick, A. Shokoufandeh: A note on the Caro-Tuza bound on the independence number of uniform hypergraphs, Australasian Journal of Combinatorics, 52 (2012) 235--242., 2012
B. Csaba, M. Mydlarz: Approximate multipartite version of the Hajnal--Szemerédi theorem, J. of Comb. Theory, Ser. B, 102(2012), 395–410, 2012
J. Barat, G. Joret, D.R. Wood: Disproof of the List Hadwiger Conjecture, The electronic journal of combinatorics 18 (2011), #P232, 2011
J. Barat, M. Korondi, V. Varga: How to dismantle an atomic cube in zero gravity, The 7th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications May 31 - June 3, 2011 Kyoto University, Kyoto, Japan, 2011
J Barát, P Hajnal, E K Horváth: Elementary proof techniques for the maximum number of islands, EUROPEAN JOURNAL OF COMBINATORICS 32: pp. 276-281., 2011
Timár Ádám: Invariant colorings of random planar maps, Ergodic Theory Dynam. Systems 31 (2011), no. 2, 549–562, 2011
Bandyopadhyay Antar, Steif Jeffrey, Timár Ádám: On the cluster size distribution for percolation on some general graphs, Rev. Mat. Iberoam. 26 (2010), no. 2, 529–550, 2010
Häggström Olle, Mester Péter: Some two-dimensional finite energy percolation processes, Electron. Commun. Probab. 14 (2009), 42–54., 2009
V. Meszaros: Separated matchings in convex point sets with small discrepancy, XIV Spanish Meeting on Computational Geometry, In Honor of Ferran Hurtado´s 60th Birthday, Alcala de Henares, Spain, CRM Documents, vol. 8, Centre de Recerca Matem`atica,, 2011
Meszaros V.: An upper bound on the size of separated matchings, Electronic Notes in Discrete Mathematics Volume 38, 1 December 2011, Pages 633–638, 2011
V. Meszaros, Ph.D. tezis: Extremal problems on planar point sets, 2011. majus 20. vedes.: Extremal problems on planar point sets, Ph.D. tezis, SZTE, http://www2.sci.u-szeged.hu/fokozatok/PDF/Mezsaros_Viola/mvdoktori.pdf, 2011
J. Balogh and A. Pluhár: The positive minimum degree on game sparse graph, Electronic J. of Combinatorics, 19 (2012) paper 22, 2012
J. Balogh, C. Lee and W. Samotij: Corrádi and Hajnal's theorem for sparse random graphs, Combinatorics, Probability and Computing, 21 (2012), 23--55, 2012
J. Balogh, B. Bollobás, Hugo Duminil-Copin, and R. Morris: The sharp threshold for bootstrap percolation in all dimensions, Transactions of the American Mathematical Society, 364 (2012), 2667-2701, 2012
Balogh and D. Mubayi: Almost all cancellative triple systems are tripartite, Combinatorica, 32 (2012), 143--169, 2012
J. Balogh and J. Lenz: Some Exact Ramsey-Turan Numbers, Bulletin of the London Mathematical Society, 44 (2012), 1251-1258, 2012
J. Balogh, B. Bollobás, and R. Morris: Graph bootstrap percolation, Random Structures and Algorithms, 41 (2012), 413--440, 2012
Balogh, B. Bollobás, T. Bohman and Y. Zhao: Turán densities of some hypergraphs related to $K^k_{k+1}$, SIAM J. Discrete Mathematics, 26 (2012), 1609--1617, 2012
J. Balogh and J. Lenz: On Ramsey-Turán numbers of graphs and hypergraphs, Israel Journal of mathematics, 194 (2013) 45-68, 2013
J. Balogh, A. V. Kostochka and A. Treglown: Perfect packings in graphs, Electronic Journal of Combinatorics, Volume 20, Issue 1 (2013), paper 57, 15 pages, 2013
J. Balogh, H. González-Aguilar, and G. Salazar: Large convex holes in random point sets, Computational Geometry: Theory and Applications, 46 (2013), 725--733, 2013
J. Balogh, G. Kemkes, C. Lee, and S. J. Young: Towards a weighted version of the Hajnal-Szemerédi theorem, Combin. Probab. Comput., 22 (2013), 346-350, 2013
J. Balogh, A. Kostochka and A. Raigorodskii: Coloring some finite sets in $R_n$, Discussiones Mathematicae Graph Theory, 33 (2013) 25--31, 2013
J. Balogh, J. Butterfield, P. Hu, J. Lenz and D. Mubayi: On the Chromatic Thresholds of Hypergraphs, Combin. Probab. Comput., 2013
N. Alon, J. Balogh, R. Morris and W. Samotij: Counting sum-free sets in Abelian groups, Israel Journal of mathematics, 2013
J. Balogh, R. Morris and W. Samotij: Random sum-free subsets of Abelian groups, Israel Journal of Mathematics, 2013
J. Balogh, P. Hu, B. Lidicky and H. Liu: Upper bounds on the size of $4$- and $6$-cycle-free subgraphs of the hypercube, European Journal of Combinatorics, 35 (2014), 75-85., 2014
Bartalos István, Pluhár András: Közösségek és szerepük a kisvilág gráfokban, Alkalmazott Matematikai Lapok, 29 (2012) 55--68, 2012
B. Csaba, T. Plick, A. Shokoufandeh: A note on the Caro-Tuza bound on the independence number of uniform hypergraphs, Australasian Journal of Combinatorics, 52 (2012) 235--242, 2012
B. Csaba, T. Plick, A. Shokoufandeh: Further results on optimal random matchings, tours and spanning trees in HSTs, Theoretical Computer Science, 50 (2013) 68-89, 2013
B. Bényi, P. Hajnal: The combinatorics of poly-Bernoulli numbers, Proceedings of the 8th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications June 4-7, 2013, Veszprém, Hungary, 2013



Back »