组合数学 (Spring 2025)/Problem Set 3

probability and computing 6.17 (page 166)

extremal comb 4.17

Problem 1

Use the Lovász Local Lemma to show that, if [math]\displaystyle{ 4\binom{k}{2}\binom{n}{k-2}2^{1-\binom{k}{2}} \leq 1 }[/math], then it is possible to color the edges of [math]\displaystyle{ K_n }[/math] with two colors so that it has no monochromatic [math]\displaystyle{ K_k }[/math] subgraph.

Problem 2

Let [math]\displaystyle{ G = (V, E) }[/math] be an undirected graph and suppose each [math]\displaystyle{ v \in V }[/math] is associated with a set [math]\displaystyle{ S(v) }[/math] of at least [math]\displaystyle{ 2\mathrm{e}r }[/math] colors, where [math]\displaystyle{ r \geq 1 }[/math]. Suppose, in addition, that for each [math]\displaystyle{ v \in V }[/math] and [math]\displaystyle{ c \in S(v) }[/math] there are at most [math]\displaystyle{ r }[/math] neighbors [math]\displaystyle{ u }[/math] of [math]\displaystyle{ v }[/math] such that [math]\displaystyle{ c }[/math] lies in [math]\displaystyle{ S(u) }[/math]. Prove that there is a proper coloring of [math]\displaystyle{ G }[/math] assigning to each vertex [math]\displaystyle{ v }[/math] a color from its class [math]\displaystyle{ S(v) }[/math] such that, for any edge [math]\displaystyle{ (u, v) \in E }[/math], the colors assigned to [math]\displaystyle{ u }[/math] and [math]\displaystyle{ v }[/math] are different.

Problem 3

• (Goodman 1959). Let [math]\displaystyle{ G=(V,E) }[/math] be a graph on [math]\displaystyle{ n }[/math] vertices and [math]\displaystyle{ t(G) }[/math] denote the number of triangles contained in the graph [math]\displaystyle{ G }[/math] or in its complement. Prove that [math]\displaystyle{ t(G)\geq \binom{n}{3}+\frac{2m^2}{n}-m(n-1) }[/math].

Hint: Let [math]\displaystyle{ t_i }[/math] be the number of triples of vertices [math]\displaystyle{ (i,j,k) }[/math] such that the vertex [math]\displaystyle{ i }[/math] is adjacent to precisely one of [math]\displaystyle{ j }[/math] or [math]\displaystyle{ k }[/math]. Note that [math]\displaystyle{ t_i = d_i(n-1-d_i) }[/math] where [math]\displaystyle{ d_i }[/math] is the degree of the vertex [math]\displaystyle{ i }[/math]. Show that [math]\displaystyle{ t(G) \geq \binom{n}{3}-\frac{1}{2}\sum_i t_i }[/math] and use the Cauchy–Schwarz to bound [math]\displaystyle{ \sum_i t_i }[/math].

Problem 4

Prove the following theorem on extremal graph theory:

• (Graham–Kleitman 1973). If the edges of a complete graph on [math]\displaystyle{ n }[/math] vertices are labeled arbitrarily with the integers [math]\displaystyle{ 1, 2,\dots, \frac{n(n-1)}{2} }[/math], each edge receiving its own integer, then there is a trail (i.e., a walk without repeated edges) of length at least [math]\displaystyle{ n − 1 }[/math] with an increasing sequence of edge-labels. (Hint: To each vertex [math]\displaystyle{ v }[/math], assign its weight [math]\displaystyle{ w_v }[/math] equal to the length of the longest increasing trail ending at [math]\displaystyle{ v }[/math]. Can you show that [math]\displaystyle{ \sum\limits_{i=1}^{n} w_i\geq n(n-1) }[/math]?)

Problem 5

(Frankl 1986)

Let [math]\displaystyle{ \mathcal{F}\subseteq {[n]\choose k} }[/math] be a [math]\displaystyle{ k }[/math]-uniform family, and suppose that it satisfies that [math]\displaystyle{ A\cap B \not\subset C }[/math] for any [math]\displaystyle{ A,B,C\in\mathcal{F} }[/math].

• Fix any [math]\displaystyle{ B\in\mathcal{F} }[/math]. Show that the family [math]\displaystyle{ \{A\cap B\mid A\in\mathcal{F}, A\neq B\} }[/math] is an anti chain.
• Show that [math]\displaystyle{ |\mathcal{F}|\le 1+{k\choose \lfloor k/2\rfloor} }[/math].