Homework 1

Deadline: Sept. 30, 22:00:00
  1. Suppose five points are chosen inside an equilateral triangle with side length . Show that there is at least one pair of points whose distance apart is at most .

  2. Let be the chromatic number of graph . Show that any graph must have at least edges.

  3. Suppose is a graph on vertices. For an edge , let be the number of triangles containing , and be the number of triangles in .

    • Show that for each pair of adjacent vertices , .
    • Summing over all edges we have Show that .

    Remark: This implies that a graph on n vertices with edges not only contains one triangle (as it must be by Mantel’s theorem), but more than .

  4. Given a family of subsets of , its intersection graph is defined by: if and only if . Suppose that the average size of is at least , and the average size of for is at most . Show that .

    (Hint: Compute .)

  5. [Noga Alon, 1986] Let be a set of strings of length over some alphabet . Suppose that every two strings of differ in at least coordinates. Let be a number satisfying . Show that any distinct strings of attain distinct values in at least one coordinate.

    (Hint: Assume the opposite and count the sum of distances between the pairs of 's.)

  6. Prove that for any positive integer , there is a number such that for any -coloring of all subsets of , , there exists non-empty disjoint sets such that , and are the same.