Graphs, geometry, randomness, algoritms  Page description

Help  Print 
Back »

 

Details of project

 
Identifier
49398
Type K
Principal investigator Hajnal, Péter
Title in Hungarian Gráfok, geometria, véletlen, algoritmusok
Title in English Graphs, geometry, randomness, algoritms
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
Pete, Gábor
Pluhár, András Sándor
Timár, Ádám
Varjú, Péter Pál
Starting date 2005-01-01
Closing date 2009-12-31
Funding (in million HUF) 11.964
FTE (full time equivalent) 11.41
state closed project





 

Final report

 
Results in Hungarian
Jelentős eredményeket értünk el a gráfelmélet, geometria, sztochasztika és algoritmusok kérdésköreiben, sokszor a területek közös elméletét gyarapítottuk. Kiemelünk néhány karakterisztikus eredményt: Hozzájárultunk annak megértéséhez ''hogyan viselkednek'' végtelen tranzitív gráfok minimális elvágó élhalmazai kvaziizometriák mellett (Babson és Benjamini két kérdésének megválaszolásával). Gráfokhoz rendeltünk egy geometria jellegű slope paramétert, amely különböző változatai több kutatást indítottak el. Gráfok pakolásainak központi megoldatlan kérdésével, az Bollobás-Eldridge-sejtéssel, kapcsolatban több részeredményt értünk el. Az OTKA résztvevői sok társszerzővel dolgoztak együtt. Az OTKA pályázat segítségévél született munkában társszerzőink között vannak: Pavel Valtr, Oded Schramm, Bezdek András, Yuval Peres, Bollobás Béla, Turán György, Jiri Matousek, Alexandr Kostochka, T. Sós Vera a témaköreink nemzetközileg elismert nagyságai. A szegedi kombinatorika szeminárium munkája a kutatás mellett a fiatal diákok érdeklődését is felkelti. Szakdolgozatok mellett két phd értekezés is születendőben van és további phd hallgatók kutatnak kombinatorika témában. A szeminárium honlapja: http://www.math.u-szeged.hu/~hajnal/seminars/kombszem/kombszem.htm
Results in English
We have achieved several important results in graph theory, geometry, probability theory and algorithm theory, often connecting these central fields. We underline a few characteristic results. We contributed to understanding how minimal cut sets in infinite transitive graphs are behaving under quasiisometries (we have answered two questions of Babson and Benjami). We have introduced and investigated the geometrical notion, the slope parameter of a graph. This notion motivated further research. We made major steps in the topics of graph packing, strongly related to the Bollobas-Eldridge conjecture. For example if H is a bipartite graph on n vertices, with maximal degree D, then for large enough n H is a spanning subgraph of G a graph on n vertices with minimal degree at least D/(D+1). Our participants worked with several co-authors, among others, with Pavel Valtr, Oded Schramm, Andras Bezdek, Yuval Peres, Bela Bollobas, Gyorgy Turan, Jiri Matousek, Alexandr Kostocka, Vera T. Sos. The Combinatorics Seminar in Szeged is not only a research center, but it plays important role in education. Several students have written their diploma thesis in combinatorics, two phd dissertations is about to be submitted and other phd students are working strongly connected to our seminar. The homepage of the seminar is http://www.math.u-szeged.hu/~hajnal/seminars/kombszem/kombszem.htm
Full text http://real.mtak.hu/1967/
Decision
Yes





 

List of publications

 
B. Csaba: On embedding well-separable graphs, Disc. Math., 2006
Adam Timar: Cutsets in transitive graphs, CPC, 2006
Adam Timar: Ends in free minimal spanning forests, Ann of Prob, 2006
J. Balogh and B. Bollobás: Bootstrap percolation on the hypercube, Probability and Related Fields, 2006
Adam Timar: Neighboring clusters in Bernoulli percolation, Ann of Prob, 2006
J. Balogh and R. Pemantle: The Klee-Minty random edge chain moves with linear speed, Random Structures and Algorithms, 2006
J. Balogh and G. Salazar: On k-sets, convex quadrilaterals, and the rectilinear crossing number of K_n, Discrete Comput. Geom., 2006
J. Balogh and B. Bollobás: Unavoidable traces of set systems, Combinatorica, 2006
J. Balogh, B. Bollobás, and D. Weinreich: A jump to the Bell number for hereditary graph properties, J. Combin. Theory Ser. B, 2005
J. Balogh, P. Keevash, and B. Sudakov: Disjoint representability of sets and their complements, Journal of Combinatorial Theory B, 2005
J. Balogh and B. Bollobás: Hereditary properties of words, RAIRO, 2005
J. Barat, P.P. Varju: On square-free edge colorings of graphs, Ars Combinatoria, 2006
Y. Peres - G. Pete - A. Scolnicov: Critical percolation on certain non-unimodular graphs, New York Journal of Math., 2006
J. Balogh, D. Mubayi and A. Pluhár: On the edge-bandwidth of graph products, Theoretical Computer Science, 2006
G. Ambrus, A. Bezdek, F. Fodor: A Helly-type transversal theorem for n-dimensional unit balls, Archiv der Mathemati, 2006
J. Balogh, M. Kochol, A. Pluhár and X. Yu: Covering planar graphs with trees, Journal Combinatorial Theory B, 2005
J. Barát, J. Matousek, D.R. Wood: Bounded-Degree Graphs have Arbitrarily Large Geometric Thickness, The Electronic Journal of Combinatorics, 2006
P. Hajnal, Z. Liu and Gy. Turán: Nearest neighbor representations of Boolean functions, Ninth International Symposium on Artificial Intelligence and Mathematics, 2006
J.Balogh-Y.Peres-G.Pete: Bootstrap percolation on infinite trees and non-amenable groups, Combin.Probab.&Computing., 2006
G. Ambrus, J. Barat: A contribution to queens graphs: a substitution method, Disc. Math., 2006
J. Barat: Directed path-width and monotonicity in digraph searching, Graphs Combin., 2006
J. Barat, C. Thomassen: Claw-decompositions and Tutte-orientations, J. Graph Theory, 2006
B. Csaba: On the Bollobás-Eldridge conjecture for bipartite graphs, Combinatorics, Probability and Computing, 2007
G. Ambrus, J. Barat, P. Hajnal: The slope parameters of Graphs, Acta Sci. Math., 2006
J. Balogh: A remark on the number of edge colorings of graphs, European J. Combin., 2006
J. Balogh, B. Pittel,G. Salazar,: Near-perfect non-crossing harmonic matchings in randomly labeled points on a circle, Discrete Math. Theor. Comput. Sci. Proc., 2006
Bela Csaba: Regular spanning subgraphs of bipartite graphs of high minimum degree, The Electronic Journal of Combinatorics, 2007
J. Barat, P. Varju: On square-free vertex colorings of graphs, Studia Scientiarum Mathematicarum Hungarica, 2007
J. Balogh, B. Bollobas, R. Morris: Hereditary properties of tournaments, Electron. J. Combin., 2007
J. Balogh, R. Pemantle: The Klee-Minty random edge chain moves with linear speed, Random Structures Algorithms, 2007
J. Balogh, J. Leanos, S. Pan, R. Richter, G. Salazar: The convex hull of every optimal pseudolinear drawing of $K_n$ is a triangle, Australas. J. Combin., 2007
M. Axenovich, J. Balogh: Graphs having small number of sizes on induced $k$-subgraphs, SIAM J. Discrete Math., 2007
J. Balogh, B.G. Pittel: Bootstrap percolation on the random regular graphs, Random Structures Algorithms, 2007
J. Balogh, B.G. Pittel, G. Salazar: Large harmonic sets of noncrossing edges for n randomly labeled vertices in convex position, Random Structures Algorithms, 2007
Adam Timar: Percolation on Nonunimodular Graphs, Annals of Probability, 2006
Adam Timar: Cutsets in Infinite Graphs, Combinatorics, Probability and Computing, 2007
J. Balogh, Bollobas and Morris: Hereditary properties of ordered graphs, Algorithms Combin., 2006
J. Balogh, P. Keevash, B. Sudakov,: On the minimal degree implying equality of the largest triangle-free and bipartite subgraphs, JCT B, 2006
J. Balogh, B. Bollobas, Morris: Hereditary properties of partitions, ordered graphs and ordered hypergraphs, European J. of Combinatorics, 2006
G. Ambrus, A. Bezdek: On iterative processes generating dense point sets, Periodica Mathematica Hungarica, 2006
G. Ambrus, F. Fodor: A new lower bound on the surface area of a Voronoi polyhedron, Periodica Mathematica Hungarica, 2006
G. Ambrus, A. Bezdek: Incenter iterations in 3 space, Periodica Mathematica Hungarica, 2007
G. Ambrus, A. Bezdek: On the number of mutually touching cylinders, is it 8?, European Journal of Combinatorics, 2008
B. Csaba: On embedding well-separable graphs, Discrete Mathematics, 2008
B. Csaba, A. Pluhar: A randomized algorithm for the on-line weighted bipartite matching problem, Journal of Scheduling, 2008
J. Abrahamson, B. Csaba, A. Shokoufandeh: Optimal random matchings on trees and applications, APPROX and RANDOM 2008, LNCS 5171, 2008
A. Timar: Split hypergraphs, SIAM J. on Discrete Mathematics, 2008
A. Lapidoth and G. Pete: On the entropy of the sum and difference of independent random variables, IEEE 25th Convention of Electrical and Electronics Engineers in Israel, 2008
G. Pete: Corner percolation on Z^2 and the square root of 17, Ann. Probab., 2008
G. Pete: A note on percolation on Z^d: isoperimetric profile via cluster repulsion, Elect. Commun. Probab., 2008
C. Garban, G. Pete and O. Schramm: The Fourier spectrum of critical percolation, Acta. Math., 2009
Josef Cibulka, Jan Kyncl, Viola Meszaros, Rudolf Stolar and Pavel Valtr: Hamiltonian Alternating Paths on Bicolored Double-chains, Graph Drawing, Heraklion, Kreta, 2008
J. Barat and D. Wood: Notes on nonrepetitive graph colouring, Electron. J. Combinatorics, 2008
J. Barat and P. Varju: On square-free edge colorings of graphs, Ars Combin, 2008
J. Balogh and R. Martin: Edit distance and its computation, Electronic Journal of Combinatorics, 2008
S. Kumar, T. H. Lai and J. Balogh: On k-coverage in a mostly sleeping sensor network, Wireless Network, 2008
Abrego, Balogh, Fernadez-Merchant and Leanos: An extended lower bound on the number of k-edges to generalized configurations of points and the pseudolinear crossing number of K_n, J. Combin. Theory Ser. A, 2008
J. Balogh, Bezrukov, Harper and Seress: On the bandwidth of 3-dimensional Hamming graphs, Theoretical Computer Science, 2008
J. Balogh and Kostochka: On 2-detour subgraphs of the hypercube, Graphs and Combinatorics, 2008
J. Balogh, G. Araujo, R. Fabila, G. Salazar and J. Urrutia: A note on harmonic subgraphs in labelled geometric graphs, Inform. Process. Lett., 2008
J. Balogh, D. Mubayi: A new short proof of a theorem of Ahlswede and Khachatrian, J. Combin. Theory Ser. A, 2008
J. Balogh, S.G. Hartke, Qi Liu, and Gexin Yu,: On the First-Fit Chromatic Number of Graphs, SIAM J. Discrete Math., 2008
J. Balogh and C. Smyth: On the variance of Shannon products of graphs, Discrete Applied Mathematics, 2008
J. Balogh, B. Bollobas, M. Saks, and V. T. Sos: On the diversity function of a hereditary graph property, JCT B, 2009




Back »