Eurocomb'03 - Conference Program

Sunday, September 7

18:00-22:00 Welcome party

Monday, September 8

9:30-10:30 Martin Grötschel:
Combinatorics and Telecommunication
10:30-11:00cofee break
11:00-12:00 William J. Cook:
Planar Graphs, Parallel Computing, and the Traveling Salesman Problem
lecture room Alecture room Blecture room C
14:30-16:10 Janka Chlebikova, Klaus Jansen:
The d-precoloring problem on k-degenerate graphs
Matej Stehlik:
On Matching and Colouring of Graphs
Adrian Dumitrescu, Rados Radoicic:
On a coloring problem for the integer grid
Guillaume Fertin, Andre Raspaud:
L(p,q) Labeling of d-Dimensional Grids
Daniel Berend, Amir Sapir:
The Cyclic and Path Multi-peg Tower of Hanoi
Katarina Cechlarova, Tamas Fleiner:
On a generalization of the stable roommates problem
Ilse Fischer:
A method for proving polynomial enumeration formulas
Nachum Dershowitz, Mitch Harris:
Enumerating Satisfiable Propositional Formulae
Omer Gimenez, Marc Noy:
On the complexity of computing the Tutte polynomial of bicircular matroids
Marek Janata:
About a new class of matroidal packing families
Winfried Hochstaettler, Jaroslav Nesetril:
Antisymmetric Flows in Matroids
Rieuwert J. Blok, Bruce E. Sagan:
Topological Properties of Active orders on Matroid Bases
16:10-16:40cofee break
16:40-17:55 Mickael Montassier:
Observability of odd graphs, bi-odd graphs and recursive clique-trees
Zdenek Dvorak, Tomas Kaiser, Daniel Kral:
Eulerian colorings and the Bipartizing matchings conjecture of Fleischner
Jiri Fiala, Jana Maxova:
Cantor-type theorem for locally constrained graph homomorphisms
Mirka Miller, Minh Hoang Nguyen, Rinovia Simanjuntak:
Repeat structure in regular graphs and digraphs
Stephan Brandt:
Properties of expanding graphs and digraphs
Eyal Beigman:
Extension of Arrow's theorem to symmetric sets of tournaments
Jiri Matousek, Milos Stojakovic:
On Restricted Min-Wise Independence of Permutations
Simone Severini:
Towards a characterization of uni-stochastic matrices
Margaret Archibald, Arnold Knopfmacher, Helmut Prodinger:
The number of distinct values in a geometrically distributed sample

Tuesday, September 9

9:30-10:30 Bert Gerards:
On the Structure of Matrices and Matroids
10:30-11:00cofee break
11:00-12:00 Béla Bollobás:
The number of k-SAT functions
lecture room Alecture room Blecture room C
14:30-16:10 Isidoro Gitler, Feliu Sagols:
On Hamiltonian decompositions of 4-regular planar graphs
Rostislav Caha, Vaclav Koubek:
Paths and Cycles Spanning Hypercubes
Tomas Dvorak:
Hamiltonian cycles and paths with prescribed edges in hypercubes
Ladislav Nebesky:
The Interval Function of a Connected Graph and Road Systems
Arnaud Pecher, Annegret K. Wagler:
A construction for non-rank facets of stable set polytopes of webs
David Orden, Francisco Santos:
The polytope of non-crossing graphs on a planar point set
Pavel Valtr:
Open caps and cups in planar point sets
Csaba D. Toth:
Binary Space Partition for Fat Orthogonal Hyperrectangles
Y. Kohayakawa, Vojtech Roedl, Mathias Schacht:
Discrepancy and Eigenvalues of Cayley Graphs
Daniele A. Gewurz, Francesca Merola:
Orbits on cycles and circulant objects
Vince Grolmusz:
Fast Matrix Multiplication via Matrix-Covers
Simeon Ball:
The functions over a finite field that determine few directions
16:10-16:40cofee break
16:40-17:55 Charles Pinter:
A Combinatorial Measure of Information
Petrica C. Pop:
A New Relaxation Method for the Generalized Minimum Spanning Tree Problem
Benjamin Doerr:
Non-independent Randomized Rounding, Linear Discrepancy and an Application to Digital Halftoning
Yoshio Okamoto:
The free complex of a two-dimensional generalized convex shelling
Alexander Tiskin:
Packing tripods:
a computational approach
Olivier Bodini:
Tilings on the Butterfly Lattice
Y.O.Hamidoune, Oriol Serra, G. Zemor:
Sets with small sumset in Z/pZ.
Shalom Eliahou:
On the construction of small sumsets
Francesc Aguilo-Gost:
An efficient algorithm to find tight families of additive bases

Wednesday, September 10

9:30-10:30 Robin Thomas:
The Strong Perfect Graph Theorem
10:30-11:00cofee break
11:00-12:00 Vera T. Sós:
Paradoxical decompositions
14:00-16:00 Excursion to national library at Klementinum
17:00-18:00 European prize in combinatorics award ceremony
18:00-19:00 Concert in the Mirror chapel
20:00-23:30 Conference dinner at Michna's pallace

Thursday, September 11

9:30-10:30 Gil Kalai:
Topological Helly Type Theorems
10:30-11:00cofee break
11:00-12:00 Miroslav Fiedler:
Algebraic connectivity --- 30 years after
lecture room Alecture room Blecture room C
14:30-16:10 Hein van der Holst:
An algorithm to find a linkless embedding of a graph
R. Bruce Richter, Antoine Vella:
Graphs as topological objects
Reza Naserasr:
K5-free bound for the class of planar graphs
Daniel Goncalves:
Caterpillar arboricity of planar graphs
Juergen Koehl, Ronald Luijten:
A Reduced Non-blocking Routing Network
Mohammad Taghi Hajiaghayi, Mahdi Hajiaghayi:
Bounded Fragmentation Property and Its Applications In Network Reliability
Cyril Gavoille, Martin Nehez:
On Interval Routing in Random Meshes
Andreas Baltz, Gerold Jaeger, Anand Srivastav:
Constructions of Sparse Asymmetric Connectors
Gyula Karolyi:
The Erdos-Heilbronn problem in the additive theory and the polynomial method
A. A. Saphozenko:
The Cameron-Erdos Conjecture
Veselin Jungic, Jacob Licht, Mohammad Mahdian, Jaroslav Nesetril, Rados Radoicic:
Rainbow Arithmetic Progressions and Anti-Ramsey Results
Alain Plagne:
A proof of two Erdos' conjectures on restricted addition and further results
16:10-16:40cofee break
16:40-17:55 David Hartvigsen, Pavol Hell, Jacint Szabo:
The k-Piece Packing Problem
Nikolai Kuzjurin:
Generalized covers and their approximations
Gregory Gutin:
Introduction to Domination Analysis
Andrea Vietri:
Arc-coloring of directed hypergraphs and chromatic number of walls
Jiri Fiala, Daniel Kral, Riste Skrekovski:
Brooks-type Theorem for Generalized List T-Coloring
Josep Diaz, Maria Serna, Dimitrios M. Thilikos:
Counting List H-Colorings and Variants
Nils Hebbinghaus, Tomasz Schoen, Anand Srivastav:
Discrepancy of Linear Hyperplanes in F_q^r
Christian Bey:
On 2-perfect codes in the odd graphs
Gyula O. H. Katona:
A coding problem for pairs of subsets

Friday, September 12

9:30-10:30 Joel Spencer:
10:30-11:00cofee break
11:00-12:00 Tomasz Luczak:
Phase transition phenomena in random discrete structures
lecture room Alecture room Blecture room C
14:30-16:10 Janos Barat, Carsten Thomassen:
Dividing the edges of a graph into connected subgraphs of prescribed size
Sul-young Choi, Puhua Guan :
Construction of a family of graphs with a small induced proper subgraph with minimum degree 3
Manuel Bodirsky, Clemens Groepl, Mihyun Kang:
Generating Unlabeled Cubic Planar Graphs Uniformly at Random
Laszlo Szego:
On constructive characterizations of (k,l)-sparse graphs
Ton Kloks, C. M. Lee, Jiping Liu, C. L. Lu, S. L. Peng:
Descrying induced interval graphs
Michel Habib, Christophe Paul, Jan Arne Telle:
Generalization of interval graphs defined as intersection graphs
Stephen Finbow, Andrew King, Gary MacGillivray, Romeo Rizzi:
The Firefighter Problem for Graphs of Maximum Degree Three
Susumu Suzuki, Toshihide Ibaraki:
The complexity of assigning genotypes to people in a pedigree consistently
Eugenia O'Reilly Regueiro:
Flag-Transitive Symmetric Designs
Reinhard Laue:
Many Isomorphism Types of 6- and 7-Designs
Hugh Thomas:
Tamari Lattices for Types B and D
Yared Nigussie:
Algorithm for Computing Structural Descriptions and Obstructions of Tree Ideals
16:10-16:40cofee break
16:40-17:55 Noga Alon, Eitan Bachmat:
Constructing d-regular graphs whose subgraphs tend to be acyclic
Gyula Pap:
The H-factor problem in directed graphs
Marton Makai:
A polyhedral approach to even factors
A. Llado, Susana Clara Lopez Masip:
Minimum tree decompositions in simple graphs
Yon Dourisboure, Cyril Gavoille:
Tree-decompostion of Graphs with small Diameter Bags
Petr Hlineny, Geoff Whittle:
Tree-Width and Matroids
Michel Habib, David Kelly, Emmanuelle Lebhar, Christophe Paul:
Sandwich Problems for Posets
W. L. Fouche, L. M. Pretorius, C. J. Swanepoel:
On the Ramsey degrees of posets
Freydoon Rahbarnia:
An Algorithm for Finding A Hamiltonian Cycle in Middle Two Ranks of Poset Bn

August 2003