(Your Regular) Workshop on
Extremal Graphs and Hypergraphs

CMU in Spring

Pittsburgh, May 5-6, 2007

The Workshop on Extremal Graph and Hypergraphs will be held in Pittsburgh, at the CMU campus, May 5-6, 2007. The topic of this informal workshop is extremal problems for graphs and hypergraphs, with a special interest in the Regularity Lemmas (various versions and flavors) and their applications.

Invited Speakers

We are happy to announce the following invited speakers:
  • Penny Haxell (Waterloo)
  • Benny Sudakov (Princeton)
  • Balázs Szegedy (Toronto)
  • Endre Szemerédi (Rutgers)
Also, we have invited Paul Erdős as an honorary guest. Professor Erdős has been very active mathematically, coauthoring many papers submitted well after his death in 1996.  Clearly, it is much easier for a deceased person to listen to a mathematical talk than to write a research paper, so we do count on the presence of his spirit at the workshop.
Photo credit: www.ams.org

Schedule (including some other events)

Thursday, May 3

14:30-16:30 [PPB 300] Tutorial on the Regularity Lemma by Prasad Chebolu, Pall Melsted, David Offner, Mike Picollelli

16:30-17:20 [PPB 300, ACO seminar] Gopal Pandurangan "Efficient Distributed Approximation Algorithms for Minimum Spanning Trees"

Friday, May 4

13:30-15:00 [Posner Hall 153] Anureet Saxena "Integer Programming, A Technology" (Dissertation proposal)

15:30-16:30 [Wean Hall 7220, CS Theory Seminar] Balázs Szegedy "Graph limits, property testing and extremal combinatorics"

16:45 [Stadium] Random Distance Run (If you want to run, come at least 5-10 minutes earlier to register.)

Saturday, May 5 (all talks in Baker Hall, A51)

9:00-10:00 Endre Szemerédi "Some results about embedding bounded degree graphs (hypergraphs) in dense graphs (hypergraphs)"

10:00 Workshop Photo

Coffee break

Penny Haxell "Regularity and Ramsey problems for hypergraphs"
11:30-12:00 Po-Shen Loh "Constrained Ramsey numbers"

12:00-14:00 Lunch

14:00-15:00 Ryan Martin "On the edit distance in graphs"

15:00-15:30 Coffee break

15:30-16:15 Andrei Raigorodskii "An alteration principle for bounding the chromatic number of some geometric graphs"
16:15-17:00 Zoltan Füredi "A proof of the stability of extremal graphs"

18:00- Dinner at Walnut Grill

18:00-21:00 GSA's Annual End-of-the-Year Happy Hour at Doc's Place with free food & beer if you can find a CMU graduate student who can take you as a guest :-)

Sunday, May 6 (all talks in Baker Hall, A51)

9:00-10:00 Balázs Szegedy "Limits of hypergraphs and the hypergraph regularity lemma. A non-standard approach"

Coffee break

Benny Sudakov "Density theorems for bipartite graphs"
11:30-12:00 Tao Jiang " Cyclic Arrangements of k-sets with local intersection constraints"

12:00-14:00 Lunch

14:00-15:00 Jan Vondrak "Nearly optimal embedding of trees"

15:00-15:30 Coffee break

15:30-16:30 Jacob Fox "Induced Ramsey-type theorems"
16:30-17:00 Boris Bukh "Induced subgraphs of Ramsey graphs with many distinct degrees"

Monday, May 7

8:00-17:00 [Roberts Hall] Computational Biology Symposium

Here are all abstracts (in PDF format).


There is no registration fee for the workshop. If you wish to participate, please send your name, affiliation, and email address to extr@math.cmu.edu ASAP.

Main Pittsburgh Attractions

View from Mt Washington
walking distance = within 10-minute walking distance from the campus.

Getting to the CMU Campus

From the Pittsburgh International Airport (PIT) take either a taxi (about $40 one way) or the shuttle 28X whose last stop is CMU (currently $2.25 one way, departs every 20 minutes).

All talks will take place in Baker Hall (Building No 3 on campus map), Room A51 (the Giant Eagle Auditorium). This room is in basement and is most conveniently accessed from Frew Street via the entrance between Hunt Library (No 8 on the map) and Baker Hall.

Internet/email access will be available via public Mac's (no password required) situated near the Giant Eagle Auditorium.

Between Fri 5pm and Mon 8am parking on campus is free, including the Campus Garage (P5 on campus map). You can park anywhere except places marked "Reserved 24 hours a day, 7 days a week".

See http://www.cmu.edu/home/visitors/map/ for the full legend to the campus map.

The Organizers

David Offner and Oleg Pikhurko

Supported by the Aladdin Center, CMU, the Department of Mathematical Sciences, CMU, and the National Science Foundation.