next up previous
Next: About this document ...

Discrete Math, Eights Problem Set (July 7)
REU 2003

Instructor: Laszlo Babai
Scribe: Daniel Stefankovic


Proof of Minkowski's Theorem.


Combinatorial games. Evaluation of the game tree. Existence of a winning strategy. Proof that the first player has a winning strategy in the ``Divisor'' game.


Solution to the harder Erdos puzzle: If $ A$ is a set of $ n+1$ numbers from 1 to $ 2n$ then one of them divides another.

Definition 0.1   Two elements in a partially ordered set (poset) are comparable if one is less than or equal to the other. A chain in a poset is a set of pairwise comparable elements. An antichain is a set of pairwise incomparable elements.

The solution to the Erdos puzzle was based on the following observation.


\begin{exercise}
% latex2html id marker 722
The set $\{1,2,\dots, 2n\}$, partially ordered by
divisibility, can be split into $n$\ chains.
\end{exercise}
From this it follows by the Pigeon Hole Principle that no antichain can have more than $ n$ elements, proving Erdos's claim. This is an instance of a remarkable general result at work:


\begin{exx}
% latex2html id marker 724
{\bf (Dilworth's Theorem)} Let $P$\ be a ...
...the minimum number chains whose union is $P$.
Then $\alpha(P)=\chi(P).$\end{exx}
(Note that $ \alpha(P)\le \chi(P)$ is straightforward.)


The comparability graph of a poset $ P$ has $ P$ for its set of vertices; comparable elements are adjacent.


\begin{exercise}
% latex2html id marker 726
$\alpha(P)$\ is the maximum size of ...
...e chromatic number
of the complement of the comparability graph.
\end{exercise}

The next exercise shows that the $ \alpha(G)$ vs. $ \chi({\overline{G}})$ behavior of most graphs is diametrically opposite to comparability graphs.


\begin{exercise}
% latex2html id marker 728Prove: there exist graphs $G$\ with...
...m Hint.} \ Show that
almost all graphs have the desired property.
\end{exercise}


\begin{exercise}
% latex2html id marker 730Verify that the \lq\lq SETs'' in the car...
...}(4,3)$, the 4-dimensional affine geometry over ${\mathbb{F}}_3$.
\end{exercise}


\begin{exercise}
% latex2html id marker 733Show that there are $1080$\ lines in ${\rm AG}(4,3)$.
\end{exercise}

Definition 0.2   An independent set in % latex2html id marker 1256
$ {\rm AG}(n,q)$ is a set $ S$ of points such that no line is contained in $ S$. Let $ \alpha(n,q)$ denote the maximum size of independent sets in % latex2html id marker 1264
$ {\rm AG}(n,q)$.


\begin{exercise}
% latex2html id marker 735
We are interested in the value of $\...
...3$\ ? (The answer is not known to the instructor.)
\end{enumerate}\end{exercise}


\begin{exercise}
% latex2html id marker 737Let $f(x,y)$\ be a two variable pol...
...
identically zero then it attains non-zero values
more than once.
\end{exercise}

Definition 0.3   An blocking set in % latex2html id marker 1267
$ {\rm AG}(n,q)$ is a set $ S$ of points such that every line intersects $ S$.


Note that blocking sets are the complements of the independent sets.


\begin{exx}
% latex2html id marker 741Prove: $\alpha(2,q) = (q-1)^2$. ({\em Hi...
.... Consider
the polynomial $f(x,y)=(a_2x+b_2y+1)\dots (a_mx+b_my+1)$.)
\end{exx}




next up previous
Next: About this document ...
Varsha Dani 2003-07-25