<HTML>
<HEAD>
<TITLE>2011 Erd&#337;s  
Lectures in Discrete Mathematics and Theoretical&nbsp;Computer&nbsp;Science 
</TITLE>

<script type="text/javascript">
function toggle(obj) {
var obj=document.getElementById(obj);
if (obj.style.display == "block") obj.style.display = "none";
else obj.style.display = "block";
}
</script>
</HEAD>

<BODY BGCOLOR="#FFFFF0" TEXT="#000000" LINK="#003366"
   VLINK="#440088" ALINK="#FF0000">
<TABLE WIDTH=70% ALIGN="CENTER" BORDER=0"
<TR>
<TD WIDTH=40%>
<A HREF="http://www.huji.ac.il/" TARGET="_blank"  
style="text-decoration: none">
The Hebrew University of Jerusalem</A><BR>
<A HREF="http://www.ma.huji.ac.il" TARGET="_blank"  
style="text-decoration: none">
Einstein Institute of Mathematics</A>
<TD WIDTH=20%>
<A HREF="http://www.huji.ac.il/" style="text-decoration: none">
<IMG SRC="../gifs/HUJI_logos1_08.jpg" ALT="Hebrew University of Jerusalem" 
width=97 height=99 BORDER=0 hspace=10 vspace=10></A>
<TD WIDTH=40%>
<A HREF="http://www.huji.ac.il/" TARGET="_blank"  
style="text-decoration: none">
The Hebrew University of Jerusalem</A><BR>
<A HREF="http://www.cse.huji.ac.il/" TARGET="_blank"  
style="text-decoration: none">
The Rachel and Selim Benin School of Computer Science & Engineering</A>
<TR>
<TH COLSPAN=3>Center for Theoretical Computer Science and Discrete Mathematics
</TABLE><P>

<CENTER>
<font face="Times New Roman,Times" SIZE=+1>
<A HREF="erdos.html" style="text-decoration: none">
Erd&#337;s  
Lectures in Discrete Mathematics and Theoretical&nbsp;Computer&nbsp;Science</A>
</font></B>
</CENTER>

<HR><P>
<CENTER>
  The Hebrew University Center for Theoretical Computer Science and Discrete 
Mathematics invites you to this year's
Erd&#337;s&nbsp;Lecture&nbsp;in&nbsp;Discrete&nbsp;Mathematics&nbsp;and&nbsp;
Theoretical&nbsp;Computer&nbsp;Science<P>

<FONT SIZE=+2><B>
<I>Prof.  <!-- http://www.math.tu-berlin.de/~ziegler/" -->
<A HREF="http://www.math.fu-berlin.de/groups/discgeom/members/gmziegler.html"
style="text-decoration: none">G&uuml;nter M. Ziegler</A></I>
&nbsp;&nbsp;
(Freie Universit&auml;t Berlin)</B>
</FONT>
</CENTER>
<HR>
<BLOCKQUOTE>
<B>Lectures</B>: 
<!--
&nbsp;&nbsp;&nbsp;&nbsp; (<B><A HREF="erdos_10.pdf">Poster</A></B>)
-->

<OL>
<LI><B>Centrally-symmetric polytopes with few faces</B><BR>
<I>Tuesday, March 22, 2011 &nbsp;&nbsp; 11:00am</I> &nbsp;&nbsp; 
Combinatorics Seminar, Lecture hall 110<BR>
<a href="javascript: void(0);" onClick="toggle('a1')">Abstract</a>
<div id="a1" style="display:none;">
In 1989, Gil Kalai published three remarkable conjectures
about the f-vectors of centrally-symmetric convex polytopes, which he
termed Conjectures A, B, and C.<P> 

Conjecture A became famous (the <I>3<SUP>d</SUP>-conjecture</I>): 
It claims that
every centrally-symmetric d-polytope has at least 3<SUP>d</SUP> faces.
While this conjecture still stands, and could be proved for dimensions 
at most 4, Conjectures B and C turned out to be false 
in dimensions 5 resp. 4  (Sanyal, Werner & Z., 2009).<P>

In the course of subsequent studies, the family of <I>Hansen polytopes</I>
derived from certain perfect graphs has come into the focus of investigations.
We highlight specific examples that are combinatorially close to 
<I>Hanner polytopes</I>, with intriguing properties.<BR>
(Joint work with 
<A 
HREF="http://www.chalmers.se/math/SV/kontakt/personal/doktorander/freij-ragnar"
style="text-decoration: none">
Ragnar Freij</A> and Matthias Henze)<P>

Reference:
<UL>
<LI>Sanyal, Raman ; Werner, Axel ; Ziegler, G&uumlnter M. :
<A HREF="http://www.springerlink.com/content/d7134284n6tuv135/"
TARGET="_blank"  
style="text-decoration: none">
On Kalai's conjectures concerning centrally symmetric polytopes</A>. 
<I>Discrete Comput. Geom.</I> 41 (2009), no. 2, p.183-198. 
</UL>
</div><P>

<!--
<LI><B>Small faces in large polytopes, via <I>metric geometry</I></B><BR> 
<I>Tuesday, March 22, 2011 &nbsp;&nbsp; 11:00am</I> &nbsp;&nbsp; 
Combinatorics Seminar, Lecture hall 110<BR>
<a href="javascript: void(0);" onClick="toggle('a1')">Abstract</a>
<div id="a1" style="display:none;">
In 1990, Kalai proved theorems on low-dimensional faces that
high-dimensional
polytopes must have, via a remarkable application of Linear Programming to
flag-vector combinatorics.<P>

I will explain a new, quite different approach, which also yields new
results,
for example: Every convex polytope of dimension at least 3 contains a
triangle
or its dual contains a triangle; every 4-dimensional polytope has a facet
with
a vertex of degree at most 4.
In particular, we complete the solution of a problem by Perles & Shephard
(1967)
on regular polytopes that occur as the facets of polytopes one dimension
higher.
We also classify the regular polytopes that tile Euclidean space, and
reprove
results about tilings of Euclidean space by acute simplices.<P>

Our approach is based on the theory of polyhedral CAT(0) polyhedral spaces,
as pioneered by Alexandrov (1951) and Gromov (1987): Polytope boundaries
cannot
carry a metric of non-positive curvature, since this is not compatible with
the
topology of a sphere. For polyhedral spaces we have a codimension two
criterion
for the non-positive curvature property.<BR>
(Joint work with 
<A HREF="http://www.math.fu-berlin.de/groups/discgeom/members/forti.html"
style="text-decoration: none">
Karim Adiprasito</A>)
</div><P>
-->

<LI><B>Many realizations for the associahedron</B><BR>
<I>Wednesday, March 23, 2011 &nbsp;&nbsp; 10:30am</I> &nbsp;&nbsp; 
Theory Seminar, Ross, 201<BR>
<a href="javascript: void(0);" onClick="toggle('a2')">Abstract</a>
<div id="a2" style="display:none;">
<I>The associahedron</I> is a "mythical" polytope encoding Catalan
combinatorics
(for example, the vertices, counted by Catalan numbers, encode
triangulations
of a convex polygon). The associahedron was first "sighted" in the sixties
by
Stasheff and Milnor, but the first published construction is from 1989.<P>

We report about a several very natural constructions - as fiber polytopes,
via root systems, and as Minkowski sums. Surprisingly, these constructions
produce distinct results, which are not affinely equivalent.
But we get even more: we describe a construction that turns different
triangulations into different triangulations.
Thus we obtain Catalan-many realizations of the associahedron.<BR>
(Joint work with 
<A HREF="http://www.math.fu-berlin.de/groups/discgeom/members/ceballos.html"
style="text-decoration: none">
Cesar Ceballos</A> and 
<A HREF="http://personales.unican.es/santosf/" style="text-decoration: none">
Francisco Santos</A>)
</div><P>

<LI><B>3N colored points in a plane</B> &nbsp;&nbsp;&nbsp;&nbsp; 
The talk is meant for a large audience and students
<BR>
<I>Thursday, March 24, 2011 &nbsp;&nbsp; 4:00pm</I> 
&nbsp;&nbsp; Department Colloquium<BR>
<a href="javascript: void(0);" onClick="toggle('a3')">Abstract</a>
<div id="a3" style="display:none;">
<DL>
<DT>More than 50 years ago, the Cambridge undergraduate Bryan Birch
showed that any <I>3N points in a plane</I> can be split into
N triples that span triangles with a non-empty intersection.
He also conjectured a sharp, higher-dimensional version of this,
which was proved by Helge Tverberg in 1964 (freezing, in a hotel
room in Manchester).<P>

In a 1988 Computational Geometry paper, Bárány, F&uuml;redi & Lovász
noted that they needed <I>a colored version of Tverberg's theorem</I>.
Bárány & Larman proved such a theorem for 3N colored points in a plane,
and conjectured a version for d dimensions.
A remarkable 1992 paper by Zivaljevic & Vrecica obtained such a result,
though not with a tight bound on the number of points.<P>

We now propose a new <I>colored Tverberg theorem</I>, which is
tight, which generalizes Tverberg's original theorem -
and which has three quite different proofs. Pick your favourite!<BR>
(Joint work with 
<A HREF="http://www.math.fu-berlin.de/groups/discgeom/members/blagojevic.html"
style="text-decoration: none">
Pavle V. Blagojevic</A> and 
<!-- http://www.math.tu-berlin.de/~matschke/" -->
<A HREF="http://www.math.fu-berlin.de/groups/discgeom/members/matschke.html"
style="text-decoration: none">
Benjamin Matschke</A>)<P>

References:
<UL>
<LI>Birch, B. J. :
On <I>3N</I> points in a plane. 
<I>Proc. Cambridge Philos. Soc.</I> 55 (1959), p.289-293.
<LI>Tverberg, H. :
<A HREF="http://jlms.oxfordjournals.org/content/s1-41/1/123" TARGET="_blank"  
style="text-decoration: none">
A generalization of Radon's theorem</A>. 
<I>J. London Math. Soc.</I> 41 (1966), p.123-128.<P>

<LI>Bárány, I.; Füredi, Z.; Lovász, L. :
<A HREF="http://www.springerlink.com/content/kj17x33133g69116/fulltext.pdf"
TARGET="_blank"  
style="text-decoration: none">
On the number of halving planes</A>. 
<I>Combinatorica</I> 10 (1990), no. 2, p. 175-183.
<LI>Bárány, I.; Larman, D. G. :
<A HREF="http://jlms.oxfordjournals.org/content/s2-45/2/314.full.pdf+html"
TARGET="_blank"  
style="text-decoration: none">
A colored version of Tverberg's theorem</A>. 
<I>J. London Math. Soc.</I> (2) 45 (1992), no. 2, p.314-320. 
<LI>Živaljević, Rade T.; Vrećica, Siniša T. :
<A HREF="http://dx.doi.org/10.1016/0097-3165(92)90028-S"
TARGET="_blank"  
style="text-decoration: none">
The colored Tverberg's problem and complexes of injective functions</A>. 
<I>J. Combin. Theory Ser. A</I> 61 (1992), no. 2, p.309-318<P>

<LI>Pavle V. M. Blagojević, Benjamin Matschke, Günter M. Ziegler :
<A HREF="http://front.math.ucdavis.edu/0910.4987" TARGET="_blank"  
style="text-decoration: none">
Optimal bounds for the colored Tverberg problem</A>. <I>arXiv</I>
</UL>
</div><P>
</OL>
</BLOCKQUOTE>
<HR noshade>
<font size=-1><B>Comments to</B>:
Naavah Levin, email: <I>naavah at math.huji.ac.il</I><BR>
<B>Design, construction &amp; editing</B>: Naavah Levin<BR>
<B>Last updated</B>: March. 17th, 2011</font>

</BODY>
</HTML>
�