SCHWEITZER 2002

For an arbitrary ordinal number $\alpha$ let $H(\alpha)$ denote the set of functions $f\colon \alpha \rightarrow \{ -1,0,1\}$ that map all but finitely many elements of $\alpha$ to $0$ . Order $H(\alpha)$ according to the last difference, that is, for $f, g\in H(\alpha)$ let $f\prec g$ if $f(\beta) < g(\beta)$ holds for the maximum ordinal number $\beta < \alpha$ with $f(\beta) \neq g(\beta)$ . Prove that the ordered set $(H(\alpha), \prec)$ is scattered (i.e. it doesn't contain a subset isomorphic to the set of rational numbers with the usual order), and that any scattered order type can be embedded into some $(H(\alpha), \prec)$ .

Let $G$ be a simple $k$ edge-connected graph on $n$ vertices and let $u$ and $v$ be different vertices of $G$ . Prove that there are $k$ edge-disjoint paths from $u$ to $v$ each having at most $\frac{20n}{k}$ edges.

Put $\mathbb{A}=\{ \mathrm{yes}, \mathrm{no} \}$ . A function $f\colon \mathbb{A}^n\rightarrow \mathbb{A}$ is called a decision function if (a) the value of the function changes if we change all of its arguments; and (b) the values does not change if we replace any of the arguments by the function value. A function $d\colon \mathbb{A}^n \rightarrow \mathbb{A}$ is called a dictatoric function, if there is an index $i$ such that the value of the function equals its $i$ th argument. The democratic function is the function $m\colon \mathbb{A}^3 \rightarrow \mathbb{A}$ that outputs the majority of its arguments. Prove that any decision function is a composition of dictatoric and democratic functions.

For a given natural number $n$ , consider those sets $A\subseteq \mathbb{Z}_n$ for which the equation $xy=uv$ has no other solution in the residual classes $x,y,u,v\in A$ than the trivial solutions $x=u$ , $y=v$ and $x=v$ , $y=u$ . Let $g(n)$ be the maximum of the size of such sets $A$ . Prove that $$\limsup_{n\to\infty}\frac{g(n)}{\sqrt{n}}=1$$

Denote by $\lambda (H)$ the Lebesgue outer measure of $H\subseteq \left[ 0,1\right]$ . The horizontal and vertical sections of the set $A\subseteq [0, 1]\times [ 0, 1]$ are denoted by $A^y$ and $A_x$ respectively; that is, $A^y=\{ x\in [ 0, 1] \colon (x, y) \in A\}$ and $A_x=\{ y\in [ 0, 1]\colon (x,y)\in A\}$ for all $x,y\in [0,1]$ . (a) Is there a decomposition $A\cup B$ of the unit square $[0,1]\times [0,1]$ such that $A^y$ is the union of finitely many segments of total length less than $\frac12$ and $\lambda (B_x)\le \frac12$ for all $x, y\in [0,1]$ ? (b) Is there a decomposition $A\cup B$ of the unit square $[0,1] \times [0,1]$ such that $A^y$ is the union of finitely many segments of total length not greater than $\frac12$ and $\lambda (B_x)<\frac12$ for all $x,y\in [0,1]$ ?

Let $K\subseteq \mathbb{R}$ be compact. Prove that the following two statements are equivalent to each other. (a) For each point $x$ of $K$ we can assign an uncountable set $F_x\subseteq \mathbb{R}$ such that $$\mathrm{dist}(F_x, F_y)\ge |x-y|$$ holds for all $x,y\in K$ ; (b) $K$ is of measure zero.

Let the complex function $F(z)$ be regular on the punctuated disk $\{ 0<|z| < R\}$ . By a level curve we mean a component of the level set of $\mathrm{Re}F(z)$ , that is, a maximal connected set on which $\mathrm{Re}F(z)$ is constant. Denote by $A(r)$ the union of those level curves that are entirely contained in the punctuated disk $\{ 0<|z|<r\}$ . Prove that if the number of components of $A(r)$ has an upper bound independent of $r$ then $F(z)$ can only have a pole type singularity at $0$ .

Prove that there exists an absolute constant $c$ such that any set $H$ of $n$ points of the plane in general position can be coloured with $c\log n$ colours in such a way that any disk of the plane containing at least one point of $H$ intersects some colour class of $H$ in exactly one point.

Let $M$ be a connected, compact $C^{\infty}$ -differentiable manifold, and denote the vector space of smooth real functions on $M$ by $C^{\infty}(M)$ . Let the subspace $V\le C^{\infty}(M)$ be invariant under $C^{\infty}$ -diffeomorphisms of $M$ , that is, let $f\circ h\in V$ for every $f\in V$ and for every $C^{\infty}$ -diffeomorphism $h\colon M\rightarrow M$ . Prove that if $V$ is different from the subspaces $\{ 0\}$ and $C^{\infty}(M)$ then $V$ only contains the constant functions.

Let $X_1, X_2, \ldots$ be independent random variables of the same distribution such that their joint distribution is discrete and is concentrated on infinitely many different values. Let $a_n$ denote the probability that $X_1,\ldots, X_{n+1}$ are all different on the condition that $X_1,\ldots, X_n$ are all different ( $n\ge 1$ ). Show that (a) $a_n$ is strictly decreasing and tends to $0$ as $n\to \infty$ ; and (b) for any sequence $1\le f(1)\le f(2) < \ldots$ of positive integers the joint distribution of $X_1, X_2, \ldots$ can be chosen such that $$\limsup_{n\to\infty}\frac{a_{f(n)}}{a_n}=1$$ holds.