SCHWEITZER 1997

Define a class of graphs $G_k$ for each positive integer k as follows. A graph G = ( V , E ) is an element of $G_k$ if and only if there exists an edge coloring $\psi: E\to [ k ] = \{1,2, ..., k\}$ such that for all vertex coloring $\phi: V\to [ k ]$ there exist an edge e = { x , y } such that $\phi ( x ) = \phi( y ) = \psi( e )$ . Prove that there exist $c_1< c_2$ positive constants with the following two properties: (i) each graph in $G_k$ has at least $c_1 k^2$ vertices; (ii) there is a graph in $G_k$ which has at most $c_2 k^2$ vertices.

Let A = {1,4,6, ...} be a set of natural numbers n for which n is the product of an even number of primes and n+1 is the product of an odd number of primes (taking into account the multiplicity of prime powers). Prove that the series of the reciprocals of the elements of A is divergent. In other words, $A=\{n|\lambda(n)=1$ and $\lambda(n+1)=-1\}$ , where $\lambda$ is the liouville lambda function.

Denote $f_n(X) \in \Bbb Z [X]$ the polynomial $\Pi_{j=1}^n ( X + j -1)$ . Show that if the numbers $\alpha$ and $\beta$ satisfy $f'_{1997} (\alpha) = f'_{1999} (\beta) = 0$ , then $f_{1997} (\alpha ) \neq f_{1999} (\beta)$ .

An elementary change in a 0-1 matrix is a change in an element and with it all its horizontal, vertical, and diagonal neighbors (0 to 1 or 1 to 0). Can any 1791 x 1791 0-1 matrix be transformed into a zero matrix with elementary changes?

Let $a_1>a_2>a_3>\cdots$ be a sequence of real numbers which converges to 0. We put circles of radius $a_1$ into a unit square until no more can fit. (A previously laid circle must not be moved.) Then we put circles of radius $a_2$ in the remaining space until no more can fit, continuing the process for $a_3$ ,... What can the area covered by the circles be?

a similar problem involving circles in a square: https://artofproblemsolving.com/community/c7h1979044

Let $\kappa$ be an infinite cardinality and let A , B be sets of cardinality $\kappa$ . Construct a family $\cal F$ of functions $f : A \to B$ with cardinality $2^\kappa$ such that for all functions $f_1,\cdots, f_n \in\cal F$ and for all $b_1 , ..., b_n \in B$ , there exist $a\in A$ such that $f_1(a) = b_1,\cdots, f_n(a) = b_n$ .

Let G be an abelian group, $0\leq\varepsilon<1$ and $f : G\to\Bbb R^n$ a function that satisfies the inequality. $$||f(x+y)-f(x)-f(y)|| \leq \varepsilon ||f (y)|| (x, y)\in G^2$$ Prove that there is an additive function $A : G\to \Bbb R^n$ and a continuous function $\varphi : A (G) \to\Bbb R^n$ such that $f = \varphi\circ A$ .

Let H be an infinite dimensional, separable, complex Hilbert space and denote $\cal B (\cal H)$ the $\cal H$ -algebra of its bounded linear operators. Consider the algebras $l_{\infty} ({\Bbb N}, \cal B (\cal H) ) =$ $\{ (a_n) | A_n \in\cal B (\cal H)$ $(n \in {\Bbb N}), \sup_n ||A_n|| <\infty \}$ $C(\beta {\Bbb N}, \cal B (\cal H) )$ = $\{ f: \beta {\Bbb N} \to \cal B (\cal H)|$ f is continuous $\}$ with pointwise operations and supremum norm. Show that these C*-algebras are not isometrically isomorphic. (Here, $\beta {\Bbb N}$ denotes the Stone-Cech compactification of the set of natural numbers.)

Let ( M , g ) be a Riemannian manifold. Extend the metric tensor g to the set of tangents TM with the following specification: if $a,b\in T_v TM (v\in T_p M)$ , then $$\tilde g_v (a, b): = g_p (\dot {\alpha} (0), \dot {\beta} (0) ) + g_p (D _ {\alpha} X(0) , D_{\beta} Y(0) )$$ where $\alpha, \beta$ are curves in M such that $\alpha(0) = \beta(0) = p$ . X and Y are vector fields along $\alpha,\beta$ respectively, with the condition $\dot X (0) = a,\dot Y(0) = b$ . $D _{\alpha}$ and $D _{\beta}$ are the operators of the covariant derivative along the corresponding curves according to the Levi-Civita connection. Is the eigenfunction from the Riemannian manifold (M,g) to the Riemannian manifold $(TM, \tilde g)$ harmonic?

Assign independent standard normally distributed random variables to the vertices of an n-dimensional cube. Say one vertex is greater than another if the assigned number is greater. Define a random walk on the vertices according to the following rules: a) the starting point is chosen from all the vertices with equal probability, b) during our journey, if we reach a vertex such that there are adjacent vertices which have higher values, we choose the next vertex with equal probability, c) if there is none, we stop. Prove that $\forall\varepsilon>0 \,\exists K \forall n>1$ $$P(\lambda> K \log n) <\varepsilon$$ where $\lambda$ is the number of steps of the random walk.