Conference on Extremal Combinatorics
honoring 200 years of

Peter Frankl, Zoltán Füredi, Ervin Győri and János Pach


Workshop on Algebraic and Geometric Methods in Combinatorics

April 3-8, 2004
Budapest, Hungary

Rényi Institute




List of talks


How to come to the conference

    This conference is the second meeting of Group I of  DIMACS/DIMATIA/Renyi Tripartite Partnership

Organizing committee

  • Gyula O. H. Katona
  • Dezső Miklós
  • Attila Sali


Sunday 04.04. Monday 04.05. Tuesday 04.06. Wednesday 04.07.
9:30 - 10:00 M. Sharir I. Bárány F. Roberts L. Lovász
10:05 - 10:35 M. Simonovits
10:35 - 10:55 Coffee break
10:55 - 11:25 K. Böröczky B. Llano P. Valtr L. Rónyai
11:30 - 12:00 M. Ruszinkó J. Kahn M. Loebl A. Khelladi
12:00 - 14:00 Lunch Break
14:00 - 14:30 G. Simonyi Gy. Elekes J. Nesetřil A. Marcus
14:35 - 15:05 A. Rucinski A. Frank D. Kral
15:10 - 15:40 E. Szemerédi R. Martin P. Hell A. Sali
15:40 - 16:00 Coffee break
16:00 - 16:30 G. Tóth Zs. Katona Gy. Károlyi V. Vatter
16:35 - 17:05 M. Karonski O. Einstein N. Singhi Problem Session
17:10 - 17:40 G. Tardos E. Rivera-Campo N. Weininger
17:45 - 18:15 B. Latka M. Klazar W. Cuckler

The joint conference banquet will be held on April 5th.

List of Talks

I. Bárány:The six circle conjecture of László Fejes Tóth
K. Böröczky:A notion of density for hyperbolic packings and coverings
W. Cuckler:Hamiltonian cycles in regular tournaments
O. Einstein:Combinatorics of Problems/Solutions systems
Gy. Elekes:On an incidence bound of Pach--Sharir
A. Frank:An algorithmic approach to a theorem of Győri on intervals
P. Hell:Matrix partitions of graphs
J. Kahn:TBA
Gy. Karolyi:Combinatorial number theory and the polynomial method
M. Karonski:Irregular assignments
Zs. Katona:Multiply intersecting families of sets
A. Khelladi:Some results on the fibered product of graphs
M. Klazar:Extremal and enumerative results on ordered hypergraphs
D. Kral:Equipartite graphs, polytopes and sets of points
B. Latka:Well-quasi-orderings, tournaments, and a finiteness result
B. Llano:Infinite families of tight 3-uniform hypergraphs
M. Loebl:Discrete Shortcuts in Quantum Knot Theory
L. Lovász:Graph homomorphisms, statistical physics and quasirandom graphs
A. Marcus:On Topological Graphs without Self-Intersecting 4-cycles
R. Martin:On the editing distance in graphs
J. Nesetril:TBA
E. Rivera-Campo:A note on an heterochromatic number for hypercubes
F. Roberts:Role Assignments in Social Networks
L. Rónyai:Gröbner bases of finite point sets
A. Rucinski:Dirac Theorem for 3-uniform hypergraphs I
M. Ruszinkó:Sidon type problems in extremal set theory
A. Sali:Saturated chain partitions of ranked posets and symmetric 11-Venn-diagrams
M. Sharir:János Pach and me: From union of pseudodisks to geometric incidences
M. Simonovits:The Erdős - T. Sós conjecture on the extremal problem of (large) trees
G. Simonyi:Local chromatic number of stable Kneser graphs and a generalization of the Borsuk-Ulam theorem
E. Szemerédi:Dirac Theorem for 3-uniform hypergraphs II
G. Tardos:On 0-1 matrices and small excluded submatrices
G. Tóth:Crossing stars in topological graphs
P. Valtr:Remarks on the unit distance problem for strictly convex norms
V. Vatter:Well-quasi-ordering and Permutations
N. Weininger:On correlation properties of some random colorings

Information for participants

map of relevant locations


There is a limited number of rooms avaliable at City Hotel Mátyás , located at the Pest side of Elizabeth Bridge, approximately 5 minutes walk from the Institute. The price is 60 Euros/night, if reserved through the conference organizers. If you would like us to reserve a room for you, please let us know your arrival and departure dates. (A link to a map )


4th of April, Sunday 8:30-9:30 at the Renyi Institute, Please be advised that we can only accept cash for registration fee and banquet cost. Registration fee is USD 50 or HUF 10,000. The cost of the conference banquet is HUF 5,500, which is to be paid in Hungarian Forints at the registration. Please let us know in advance if you would like to attend. (See next item)


It will be held in restaurant "Satchmo", Louisana cajun style food. (A link to a map ) There will be a choice of seafood or beef, with appetizers and a glass of wine or alcohol free drink. We would like to ask you to inform us as soon as possible of your choice of main course, also if you request vegetarian entree. We have to report the restaurant the number of each kind of dishes in advance. (That night only our group will be in the restaurant.) The address is Nador street 29, you can get there from the institute by bus No. 15.


There are machines in the guest rooms, at the entrance of the library and on the 3rd floor. Each participant is assigned a personal account on our system, since we do not have guest accounts. You'll get your account name and password at the registration. If you bring your laptop, you can connect it to our network via DHCP, either by plugging in to network plug, or by a wireless card.

Opening hours

The Institute is open Sunday from 8:30 till about 7:00 P.M., weekdays from 7:30 A.M. till 8:00 P.M.


You will be able to use the library, but only for reading there, unfortunately, you will not be able to borrow books.

If you are interested in participating, please contact us at

Registration fee: $50, which does not include the conference banquet.


The event is supported by NSF, OTKA, and the Hungarian Academy of Sciences

Mailing Address:

Alfréd Rényi Institute of Mathematics,
Hungarian Academy of Sciences
POB 127
H-1364 Budapest, Hungary

Phone:(36 1) 483 8300
Fax: (36 1) 483 8333