Hebrew University
SPECIAL: ERDOS TALKS
Speakers Prof. Janos Pach (Courant Institute)
and Prof. Joel Spencer (of Courant)
Date: Friday May 21st
Place: Ulam 2 (Math. Bldg.)
Times:
10:00 --11:00 (Pach) Intersection patterns of geometric objects
11:10 - 12:10 (Spencer) "Liar! Playing 20 questions with false answers"
12:20 - 13:20 (Pach) Geometric graphs
ABSTRACTS OF THE THREE TALKS:
FIRST TALK: Intersection patterns (Pach).
Not every graph can be obtained as the intersection graph of, say,
straight-line segments (or other geometric objects) in the plane. These
graphs have many nice structural properties. In particular, they contain
much larger homogeneous subgraphs than guaranteed by Ramsey's theorem. It
seems that this phenomenon is related to some basic topological facts,
including the Borsuk-Ulam theorem. But does it have anything to do with
algebra? We discuss this question and some of its computational
consequences. As a byproduct, we prove a conjecture of Erdos
about distance distributions in 3-space.
SECOND TALK "Liar! Playing 20 questions ." (Spencer)
Paul is trying to ascertain an unknown $x$, out of $n$ possibilities, from
an adversary Carole by asking a series of $q$ queries. In the standard
``Twenty Questions" Paul wins if and only if $n\leq 2^q$.
In Liar Games, Carole is allowed, under certain restrictions, to give an
incorrect response, a lie. She may do this at most $k$ times. In this
talk we examine asymptotics for $k$ fixed
and $q\rightarrow\infty$.
There is a natural connection between Liar Games and Coding Theory. The
protocol must allow Paul to determine $x$ despite (at most)
$k$ ``errors" in the ``transmission." The major distinction is that
Paul's queries are sequential and can depend on previous responses.
We first discuss the ``classic" case where Carole has no further
restrictions.
This game, often called the R\'enyi-Ulam game, has been very well studied.
Recent work has concentrated on the Half-Lie game. Here,
if the correct answer is yes then Carole {\em must} say yes.
In Coding Theory, this corresponds to the {\tt Z-}channel. (We shall
further explore the game over other channels.) We show, basically, that
this increases the maximal $n$ for which Paul wins by a factor of $2^k$.
The techniques involve both linear algebra (creating a suitable weight
function) and some interesting combinatorial notions on the Hamming cube.
Joint work with Ioana Dumitriu and Catherine Yan.
THIRD TALK: Geometric graphs. (Pach).
According to Euler's formula, every planar graph with $n$ vertices has at
most $O(n)$ edges. How much can we relax the condition of planarity
without violating the conclusion? After surveying some classical and
recent results of this kind, we
prove that every graph of $n$ vertices, which can be drawn in the plane
without three pairwise crossing edges, has at most $O(n)$ edges. What
happens if the forbidden pattern consists of four pairwise crossing edges?
These questions can be regarded as dual counterparts of some old problems
of Erdos, Kupitz, Perles, and others. Why are they interesting?
---------------------------------------------------------
Technion Math Net-2 (TECHMATH2)
Editor: Michael Cwikel
Announcement from: Raima Sternheim