EuroComb'11
Budapest, August 29-September 2, 2011
Rényi Institute

Program (pdf)

August 29, Monday

8:00-14:00Registration
9:00-9:10Opening
9:10-10:00 Nets Hawk Katz: Erdős' distinct distances problem in the plane
10:00-10:30Coffee break
 Lecture Room ALecture Room BLecture Room CLecture Room D
10:30-10:50 Nikolaos Fountoulakis, Ross J. Kang and Colin McDiarmid:
Largest sparse subgraphs of random graphs 		Agnieszka Polak and Daniel Simson:
Symbolic and numerical computation in determining P-critical unit forms and Tits P-critical posets 		Michal Kotrbčík:
Maximum genus of regular graphs 		Vadim Levit and David Tankus:
Lower Bounds on the Odds Against Tree Spectral Sets
10:55-11:15 Kunal Dutta and C. R. Subramanian:
On induced acyclic subgraphs in sparse random digraphs 		Noah Streib and William Trotter:
Dimension and Height for Posets with Planar Cover Graphs 		Anna de Mier, Andrew Goodall, Steven Noble and Marc Noy:
The Tutte polynomial characterizes simple outerplanar graphs 		Csilla Bujtás and Zsolt Tuza:
Combinatorial batch codes: Extremal problems under Hall-type conditions
11:30-11:50 Hiệp Hàn, Yury Person and Mathias Schacht:
Note on forcing pairs 		Jiří Fink and Petr Gregor:
Linear extension diameter of subposets of Boolean lattice induced by two levels 		Clément Charpentier, Mickaël Montassier and André Raspaud:
Minmax degree of planar graphs 		Hervé Hocquard, Pascal Ochem and Petru Valicov:
Bounds and complexity results for strong edge colouring of subcubic graphs
11:55-12:15 Marianna Bolla:
Spectra and structure of weighted graphs 		Harout Aydinian and Péter L. Erdős:
On two-part Sperner systems for regular posets 		Lali Barrière, Clemens Huemer, Dieter Mitsche and David Orden:
On the Fiedler value of large planar graphs 		Nils Hebbinghaus and Anand Srivastav:
Discrepancy of Centered Arithmetic Progressions in ℤp
12:15-14:00 Lunch Break
14:00-14:50 Eyal Lubetzky: Cycle factors, Renewals and the Comb Conjecture
14:50-15:25Coffee break
 Lecture Room ALecture Room BLecture Room CLecture Room D
15:25-15:45 Luca Gugelmann, Yury Person, Angelika Steger and Henning Thomas:
A Randomized Version of Ramsey's Theorem 		Richard Mycroft:
Packing k-partite k-uniform hypergraphs 		Robin Christian, Bruce Richter and Gelasio Salazar:
Asymptotically settling Zarankiewicz's Conjecture in finite time, for each m 		Vladimir Blinovsky:
Complete Intersection Theorem for Permutations
15:50-16:10 Benjamin Doerr and Mahmoud Fouz:
Asymptotically Optimal Randomized Rumor Spreading 		Radoslav Fulek and Andrew Suk:
On disjoint crossing families in geometric graphs 		Graham Brightwell, Gérard Cohen, Emanuela Fachini, Marianne Fairthorne, János Körner, Gábor Simonyi and Ágnes Tóth:
Permutation Capacities and Oriented Infinite Paths
16:25-16:45 Benjamin Doerr, Mahmoud Fouz and Tobias Friedrich:
Social Networks Spread Rumors in Sublogarithmic Time 		Tomás Feder, Pavol Hell and Shekoofeh Nekooei Rizi:
Partitioning Chordal Graphs 		Jesús Leaños, Oswin Aichholzer, Bernardo Ábrego, Silvia Fernández-Merchant and Gelasio Salazar:
There is a unique crossing-minimal rectilinear drawing of K18 		Antônio Bastos, Carlos Hoppen, Yoshiharu Kohayakawa and Rudini Sampaio:
Every hereditary permutation property is testable
16:50-17:10 Konstantinos Panagiotou, Reto Spöhel, Angelika Steger and Henning Thomas:
Explosive Percolation in Erdős-Rényi-Like Random Graph Processes 		Alexey Pokrovskiy:
Partitioning 3-coloured complete graphs into three monochromatic paths 		Bojan Mohar and Tamon Stephen:
Expected Crossing Numbers 		Filippo Disanto, Enrica Duchi, Simone Rinaldi and Gilles Schaeffer:
Permutations with few internal points

August 30, Tuesday

9:10-10:00 Balázs Szegedy: Higher order Fourier analysis
10:00-10:30Coffee break
 Lecture Room ALecture Room BLecture Room CLecture Room D
10:30-10:50 Zoltán Füredi:
Linear paths and trees in uniform hypergraphs 		Roman Čada, Shuya Chiba and Kiyoshi Yoshimoto:
2-factors in claw-free graphs 		Julio Araujo, Victor Campos, Frédéric Giroire, Leonardo Sampaio and Ronan Soares:
On the hull number of some graph classes 		Archontia Giannopoulou and Dimitrios Thilikos:
A min-max theorem for LIFO-search
10:55-11:15 Pavle Blagojević, Boris Bukh and Roman Karasev:
Turán numbers for Ks,t-free graphs: topological obstructions and algebraic constructions 		Vadim Levit and Eugen Mandrescu:
A Characterization of König-Egerváry Graphs Using a Common Property of All Maximum Matchings 		Petr Gregor, Riste Škrekovski and Vida Vukašinović:
On the queue-number of the hypercube 		Torsten Mütze and Reto Spöhel:
On the path-avoidance vertex-coloring game
11:30-11:50 Andrew Treglown, Daniela Kühn and Deryk Osthus:
Matchings in 3-uniform hypergraphs of large minimum vertex degree 		Viola Mészáros:
An upper bound on the size of separated matchings 		Arnaud Pêcher and Annegret Wagler:
Computing the clique number of a-perfect graphs in polynomial time 		Asaf Ferber, Dan Hefetz and Michael Krivelevich:
Fast embedding of spanning trees in biased Maker-Breaker games
11:55-12:15 Younjin Kim and Zoltán Füredi:
Minimum Ck-saturated graphs 		Ken-ichi Kawarabayashi and Kenta Ozeki:
Hamilton cycles in 4-connected triangulations of the torus 		Cédric Bentz, Marie-Christine Costa, Dominique de Werra, Christophe Picouleau and Bernard Ries:
Minimum d-Transversals of Maximum-Weight Stable Sets in Trees 		Luca Gugelmann and Reto Spöhel:
On Balanced Coloring Games in Random Graphs
12:15-14:00Lunch Break
14:00-14:50 Daniela Kühn: Hamilton cycles in graphs and directed graphs
14:50-16:00Coffee break and Poster session
 Lecture Room ALecture Room BLecture Room CLecture Room D
16:00-16:20 Demetres Christofides, Jan Hladký and András Máthé:
A proof of the dense version of Lovász conjecture 		Ameera Chowdhury:
On a Conjecture of Frankl and Füredi 		Balázs Keszegh and Dömötör Pálvölgyi:
Octants are Cover Decomposable 		Hidehiro Shinohara and Tadashi Sakuma:
On circular thin Lehman matrices
16:25-16:45 Peter Allen, Julia Böttcher, Jan Hladký and Diana Piguet:
A density Corrádi-Hajnal theorem 		David Pritchard and Filip Morić:
Counting large distances in convex polygons: A computational approach 		Oriol Serra and Lluís Vena:
On the number of monochromatic solutions of integer linear systems on Abelian groups
17:00-17:20 Julia Böttcher, Anusch Taraz and Andreas Würfl:
Induced C5-free graphs of fixed density: counting and homogeneous sets 		Peter Borg:
The maximum sum and product of sizes of cross-intersecting families 		Marie Albenque, Éric Fusy and Dominique Poulalhon:
On symmetric quadrangulations
17:25-17:45 Shinya Fujita, Henry Liu and Colton Magnant:
Rainbow k-connection in Dense Graphs 		János Barát, Zoltán Füredi, Ida Kantor, Younjin Kim and Balázs Patkós:
Large Bd-free and union-free subfamilies 		Naoki Matsumoto and Atsuhiro Nakamoto:
Transformations in hexangulations on the sphere 		Maria Bras-Amorós:
Ordinarization of Numerical Semigroups

August 31, Wednesday

9:10-10:00 Jacob Fox: Graph regularity and removal lemmas
10:00-10:30Coffee break
 Lecture Room ALecture Room BLecture Room CLecture Room D
10:30-10:50 Atsuhiro Nakamoto and Ryuichi Mori:
Linear number of diagonal flips in triangulations on surfaces 		Rommel Barbosa, Erika Coelho, Mitre Dourado, Dieter Rautenbach and Jayme Szwarcfiter:
On the Carathéodory Number for the Convexity of Paths of Order Three 		Marthe Bonamy, Benjamin Lévêque and Alexandre Pinlou:
2-distance coloring of sparse graphs 		Ángeles Carmona, Enrique Bendito, Andrés M. Encinas and Margarida Mitjana:
On the Moore-Penrose inverse of distance-regular graphs
10:55-11:15 Tobias Christ, Andrea Francke, Heidi Gebauer, Jiří Matoušek and Takeaki Uno:
A Doubly Exponentially Crumbled Cake 		Cristina Araúz, Ángeles Carmona, Andrés M. Encinas and Enrique Bendito:
The Kirchhoff Index of Cluster Networks 		Gary MacGillivray, André Raspaud and Jacobus Swarts:
Obstructions to Locally Injective Oriented Colourings 		Marc Cámara, Cristina Dalfó, Josep Fàbrega, Miquel Ángel Fiol and Ernest Garriga:
Edge-distance-regular graphs
11:30-11:50 Dieter Rautenbach and Jayme Szwarcfiter:
Unit Interval Graphs - A Story with Open Ends 		Bartłomiej Bosek, Tomasz Krawczyk and Grzegorz Matecki:
Forbidden structures for efficient First-Fit chain partitioning 		Sagnik Sen:
2-dipath and oriented L(2,1)-labelings of some families of oriented planar graphs 		David Hartman and Dragan Mašulović:
Towards finite homomorphism-homogeneous relational structures
11:55-12:15 Tobias Christ, Dömötör Pálvölgyi and Miloš Stojaković:
Digitalizing line segments 		Marcin Gąsiorek and Daniel Simson:
Programming in PYTHON and an algorithmic description of positive wandering on one-peak posets 		Mirka Miller, Oudone Phanalasy and Joe Ryan:
All graphs have total antimagic labelings 		Vasco Mano, Enide Martins and Luís Vieira:
Feasibility Conditions on the Parameters of a Strongly Regular Graph
12:15-14:00Lunch Break
14:30-17:00     Celebration at the Main Building of the Hungarian Academy of Sciences (map)
14:30-   Celebration of the 70th birthday of Gyula O.H. Katona. This program includes greetings by
                József Pálinkás - President of the Hungarian Academy of Sciences,
                Péter Pál Pálfy - Director of the Alfréd Rényi Institute of Mathematics and
                Domokos Szász - Vice President of the Hungarian Academy of Sciences.
15:00-   A talk by Jerry Griggs honoring Gyuszi. The talk title is Searching for Diamonds.
15:45-   Classical music concert by the Popper Quartett (cello quartett).
16:15-   European Prize award celebration.
16:50-   The Popper Quartett (cello quartett).
19:00-banquet on the sightseeing ship Zsófia Főhercegnő (map)

September 1, Thursday

9:00-9:50 European Prize winner's talk: David Conlon: Combinatorial theorems in random sets
9:55-10:45 European Prize winner's talk: Daniel Kráľ: Algorithmic metatheorems
10:45-11:15Coffee break
 Lecture Room ALecture Room BLecture Room CLecture Room D
11:15-11:35 Roman Glebov, Yury Person and Wilma Weps:
On Extremal Hypergraphs for Hamiltonian Cycles 		Richard Anstee, Miguel Raggi and Attila Sali:
Forbidden Configurations: Boundary Cases 		Edita Máčajová and Edita Rollová:
On the flow numbers of signed complete and complete bipartite graphs 		Tomoki Nakamigawa and Norihide Tokushige:
Counting lattice paths via a cycle lemma
11:40-12:00 Kim Marshall, Mirka Miller and Joe Ryan:
Extremal Graphs without Cycles of Length 8 or Less 		Zoltán Füredi, Ida Kantor, Angelo Monti and Blerina Sinaimeri:
Reverse-free codes and permutations 		Delia Garijo, Andrew Goodall and Jaroslav Nešetřil:
Contractors for flows 		Michael Drmota and Marc Noy:
Universal exponents and tail estimates in the enumeration of planar maps
12:05-12:25 Enno Buß, Hiệp Hàn and Mathias Schacht:
Minimum vertex degree conditions for loose Hamilton cycles in 3-uniform hypergraphs 		János Körner, Silvia Messuti and Gábor Simonyi:
Families of Very Different Paths 		Edita Máčajová and Martin Škoviera:
Determining the flow numbers of signed eulerian graphs 		Hsun-Wen Chang and Siang-Ning Zeng:
Enumeration of RNA Hairpins and Cloverleaves
12:25-14:00Lunch Break
14:00-14:50 Ken-ichi Kawarabayashi: What makes 4-edge-connected graphs so special??
14:50-15:20Coffee break
 Lecture Room ALecture Room BLecture Room CLecture Room D
15:20-15:40 Antoni Lozano:
Symmetry Breaking in Tournaments 		Giuseppe O. Longo and Andrea Sgarro:
Unruly codes with unruly distances raise (combinatorial) problems 		Zoltán Király:
Monochromatic components in edge-colored complete uniform hypergraphs 		Athanassios Koutsonas, Koichi Yamazaki and Dimitrios Thilikos:
Outerplanar Obstructions for Matroid Pathwidth
15:45-16:05 Deryk Osthus, Daniela Kühn and Richard Mycroft:
A proof of Sumner's universal tournament conjecture for large tournaments 		Alexander Sapozhenko:
Upper bound for the number of perfect (n,3)-codes 		Robert Šamal:
New approach to Petersen coloring 		Kolja Knauer, Juan José Montellano-Ballesteros and Ricardo Strausz:
A graph-theoretical axiomatization of oriented matroids
16:20-16:40 Camino Balbuena and Julián Salas:
New results on connectivity of cages 		Florent Foucaud, Sylvain Gravier, Reza Naserasr, Aline Parreau and Petru Valicov:
Edge identifying codes 		Peter Whalen:
Three coloring planar graphs without cycles of length from 4 to 6 or seven cycles with close triangles 		Elad Aigner-Horev, Reinhard Diestel and Luke Postle:
Decomposing infinite matroids into their 3-connected minors
16:45-17:05 Shinya Fujita and Ken-ichi Kawarabayashi:
High connectivity keeping connected subgraph 		Ingo Schiermeyer, Maria Koch and Stephan Matos Camacho:
Algorithmic approaches for the minimum rainbow subgraph problem 		Anastasia Rozovskaya and Dmitry Shabanov:
On colorings of non-uniform hypergraphs without short cycles 		Petr Golovach, Marcin Kamiński, Daniël Paulusma and Dimitrios Thilikos:
Lift contractions
17:15-17:45 DIMATIA business meeting

September 2, Friday

9:10-10:00 Aart Blokhuis: The structure of Generalized Kneser graphs
10:00-10:30Coffee break
 Lecture Room ALecture Room BLecture Room CLecture Room D
10:30-10:50 Carlos Hoppen, Yoshiharu Kohayakawa and Hanno Lefmann:
Edge colorings of graphs avoiding some fixed monochromatic subgraph with linear Turán number 		Arash Asadi and Spencer Backman:
Chip-Firing and Riemann-Roch Theory for Directed Graphs 		Pablo Soberón and Ricardo Strausz:
On Tverberg's Theorem 		Márcia R. Cerioli, Hugo Nobrega and Petrucio Viana:
On characterizations by nice forbidding sets
10:55-11:15 Raquel Águeda, Valentin Borozan, Marina Groshaus, Gervais Mendy, Yannis Manoussakis and Leandro Montero:
Proper Hamiltonian Paths in Edge-Colored Multigraphs 		Gyula Y. Katona and Nándor Sieben:
Bounds on the Rubbling and Optimal Rubbling Numbers of Graphs 		Gadi Aleksandrowicz and Gill Barequet:
The Growth Rate of High-Dimensional Tree Polycubes 		Nestor Nestoridis and Dimitrios Thilikos:
Square Roots of Minor Closed Graph Classes
11:30-11:50 Guillem Perarnau and Oriol Serra:
Rainbow Matchings: existence and counting 		Antal Iványi and János Madarász:
Perfect hypercubes 		Vladimir Shlyk:
Vertex Structure of Master Corner Polyhedra 		Arash Asadi, Luke Postle and Robin Thomas:
Minor-Minimal Non-Projective Planar Graphs with an Internal 3-Separation
11:55-12:15 Subramanya Bharadwaj, Sathish Govindarajan and Karmveer Sharma:
On the Erdős-Szekeres n-interior point problem 		Ilia Averbouch, Tomer Kotek, Johann A. Makowsky and Elena V. Ravve:
The Universal Edge Elimination Polynomial and the Dichromatic Polynomial 		Edward Kim:
Polyhedral graph abstractions and an approach to the Linear Hirsch Conjecture 		Hervé Hocquard and Mickaël Montassier:
Adjacent vertex-distinguishing edge coloring of graphs with maximum degree at least five
12:15-14:00Lunch Break
14:00-14:50 József Balogh: On the Ramsey-Turán numbers of graphs and hypergraphs
14:50-15:25Coffee break
 Lecture Room ALecture Room BLecture Room CLecture Room D
15:25-15:45 Marthe Bonamy, Matthew Johnson, Ioannis Lignos, Viresh Patel and Daniël Paulusma:
On the diameter of reconfiguration graphs for vertex colourings 		Kazuyuki Amano:
On Extremal k-CNF Formulas 		Susanna F. de Rezende, Cristina G. Fernandes, Daniel M. Martin and Yoshiko Wakabayashi:
Intersection of Longest Paths in a Graph
15:50-16:10 Richard Wilson and Tony Wong:
Diagonal forms for incidence matrices and zero-sum Ramsey theory 		Uwe Leck and Ian Roberts:
Minimizing the weight of the union-closure of uniform families of i-sets 		Colin McDiarmid and Tobias Müller:
Counting disk graphs 		L. Sunil Chandran, Anita Das, Deepak Rajendraprasad and Nithin M. Varma:
Rainbow Connection Number and Connected Dominating Sets
16:15-16:35 Sang-il Oum:
Rank-width and Well-quasi-ordering of Skew-Symmetric or Symmetric Matrices 		Maria Axenovich and Lale Özkahya:
On homometric sets in graphs