Math Problems Vault

Problem 2.7.1

(1)(2)(3)(4)

The parts of this problem, except (2), are various versions and special cases of Turán's theorem.

A triangle in a graph is a cycle of length 3.

?

(1)

If a graph contains no triangles, then $e \leq n^{2}/4$ .

(2)

If $e = [n^{2}/4] + 1$ , then the graph has at least $[n/2]$ triangles.

(3)

If $n = km$ and the graph contains no $(k+1)$ -clique, then $2e \leq k(k-1) \times m^{2}$ . (Passing to the complementary graph, we obtain that if $n = km$ and the graph contains no $(k+1)$ -anticlique, then $2e \geq km(m-1)$ .)

(4)

If the graph contains no $(k+1)$ -anticlique, then $2e \geq km(m-1) + 2mr$ , where $m := [n/k]$ and $r := k\{ n/k\}$ .

Problem 2.7.2

(1)(2)(3)(4)

?

(1)

If a graph contains no non-self-intersecting cycle of length 4, then $e < n^{3/2}$ .

(2)

If a graph contains no subgraph $K_{3,2}$ , then $e < 2n^{3/2}$ .

(3)

If a graph contains no subgraph $K_{3,3}$ , then $e < 2n^{5/3}$ .

(4)

For any integers $s, t$ , $2 \leq s \leq t$ , if a graph contains no subgraph $K_{s,t}$ , then $e < t n^{2-1/s}$ .

Problem 2.7.3

For any $n$ points in the plane there are at most $n$ diameters, i.e., (unordered) pairs of points whose distance equals the maximum of all possible distances between pairs of these $n$ points.

?

Problem 2.7.4

(1)(2)(3)(4)

For any $n$ points $A_{1}, \ldots , A_{n}$ in $\mathbb {R}^{d}$ , denote by $D(A_{1}, \ldots , A_{n})$ the number of (unordered) pairs of points whose distance equals 1. Let

E_{n}(d) = \max \{ D(A_{1},\ldots ,A_{n}) : A_{1},\ldots ,A_{n} \in \mathbb {R}^{d}\} .

Then:

?

(1)

$E_{n}(2) > n[\log_{2} n]/4$ ;

(2)

$E_{n}(2) \leq 2n^{3/2}$ ;

(3)

$E_{n}(3) \leq 2n^{5/3}$ ;

(4)

$\dfrac {(n-1)^{2}}{4} \leq E_{n}(4) \leq \dfrac {2(n+4)^{2}}{5}$ .

Problem 2.7.5

(1)(2)

?

(1)

Let $V$ be an $11^{q}$ -element subset of the space $\mathbb {R}^{q}$ (for the definition of the space $\mathbb {R}^{q}$ , see Ch. 7) every $10^{q}$ -element subset of which contains two points $x,y$ at distance 1: $\left|x-y\right|=1$ . Prove that for sufficiently large $q$ the number of unit distances between points of the set $V$ is greater than $12^{q}/2$ :

\frac{1}{2} \left|\{ (x,y) \in V \times V : \left|x-y\right|=1\} \right| > \frac{12^{q}}{2}.

(2)

Prove that under the conditions of the previous part the number $12^{q}/2$ can be replaced by $12{,}1^{q}$ .

Problem 2.7.6

One can consider a generalization of Turán's problem (see Problem 2.7.1) in which, instead of cliques of a given size, other subgraphs are forbidden. Denote by $\operatorname {ex}_{H}(n)$ the maximum number of edges in a graph with $n$ vertices containing no subgraphs isomorphic to $H$ . For example, $\operatorname {ex}_{K_{k+1}}(n)$ is the maximum number of edges in a graph with $n$ vertices containing no $(k+1)$ -clique.

Prove that if $H_{1}$ is a subgraph of the graph $H_{2}$ , then $\operatorname {ex}_{H_{1}}(n) \leq \operatorname {ex}_{H_{2}}(n)$ .