Discrete Math, 3rd day, 6/23/04 REU 2004

$\begin{exercise} % latex2html id marker 834Let $R$ be an equivalence relation... ...on induces the original equivalence relation in the natural way). \end{exercise}$

$\begin{exercise} Recall: Every connected graph contains a spanning tree. Prove t... ...the (finite) number of cycles (cycles have no repeated vertices). \end{exercise}$

$\begin{exercise} % latex2html id marker 838(A) \begin{description} \item[(a)]I... ...em[(c)$^\ast$]Disprove (a) for connected graphs. \end{description}\end{exercise}$

$\begin{exercise} % latex2html id marker 840(B)\\ (Helly-type Theorem) Let $R_... ...\neq \emptyset$. Then $V(R_1)\cap \ldots\cap V(R_k)\neq\emptyset.$\end{exercise}$

$\begin{exercise} % latex2html id marker 842(C)\\ Let $G$ be a connected grap... ...st paths in $G$. Prove that $ V(P_1) \cap V(P_2) \neq \emptyset. $\end{exercise}$

Definition 3.1 A legal coloring of a graph

is an assignment of a ``color'' to each vertex such that adjacent vertices have different ``colors''.
The chromatic number $\chi (G)$ of

is defined to be the minimum number of colors necessary to color

legally.

$\begin{exercise} % latex2html id marker 844The graph $G$ is bipartite if and only if $\chi (G) \leq 2$. \end{exercise}$

$\begin{exercise} % latex2html id marker 846Construct a graph $G$ such that $K... ... \chi (G)=4.$ \\ {\sc Hint:} $11$ vertices, $5$-fold symmetry. \end{exercise}$

For a set of

positive real numbers, $x_1, \ldots, x_n$ we can define several means:

$\begin{exercise} % latex2html id marker 848Prove, for any $x_1, \ldots, x_n$, ... ...$ is difficult; $G \geq H$ follows immediately from $A \geq G$. \end{exercise}$

$\begin{exercise} % latex2html id marker 850 [JENSEN'S INEQUALITY] There is a gen... ...(x_1, \ldots, x_n)) \leq A(f(x_1), \ldots, f(x_n)). \end{equation}\end{exercise}$

Note: A continuous function satisfying inequality (

) is concave and a continuous function satisfying inequality (

) is convex. However, not every function satisfying either (or even both) inequalities is continuous. (Prove! $^\ast$ )

$\begin{exercise} % latex2html id marker 852Prove Jensen's inequality. Hint: Fi... ... any $n < 2^k$ as well, thus proving the inequality for all $n$. \end{exercise}$

$\begin{exercise} % latex2html id marker 854Deduce Exercise \ref{mean} from Exercise \ref{jensen}. \end{exercise}$

Theorem 3.2 (cf. Exercise 6.1.22 in the text) There exists

such that, if $\cal G$ is a graph with

edges and

vertices, and $\cal G$ has no

-cycles, i.e. ${\cal G} \not \supseteq C_4$ , then $m \leq c n^{3/2}$ . In other words, $m = O(n^{3/2})$ .

In fact we showed that, as

tends to infinity, $m \lesssim \frac{1}{2} n^{3/2}$ .

The following exercise strengthens this result:
$\begin{exercise} % latex2html id marker 856Show that, in the above situation o... ...uation} \frac{n-1}{2} \geq {\frac{2m}{n} \choose 2} \end{equation}\end{exercise}$

The following exercise shows the tightness of the bound:
$\begin{exercise} % latex2html id marker 858Show that there exists $c' > 0$ su... ..._4$ with $m$edges and $n$ vertices, such that $m > c' n^{3/2}$. \end{exercise}$

$\begin{exercise} % latex2html id marker 860Show that $(\forall k) (\exists {\c... ...t contain triangles which have arbitrarily high chromatic number. \end{exercise}$

$\begin{exercise} % latex2html id marker 862Show that $(\forall k,\ell) (\exist... ...ich do not contain any odd cycles of length $3, 5, \ldots, \ell$. \end{exercise}$

Remark 3.3 Exercise

remains valid if we drop the word "odd":

Erdos proved this in 1960 using the probabilistic method but did not exhibit any specific examples of such graphs. No explicit construction was known of such graphs until 30 years later, around 1990.