PUMaC 2019 · 加试 · 第 1 题

Problem 1.5.7. Prove that for every integer n there exists a bipartite graph on two classes of vertices A, B such that | A | = | B | = n with less than 32 n edges so n that for any X ⊆ A, Y ⊆ B , | X | = | Y | = b c , there is an edge from X to Y . 4 2 Collegiate partition theorem “The following lemma is just combinatorics.” — Jose D. Edelstein 2.1 Introduction Consider the following (hypothetical) scenario, which motivates the mathematics that fol- low. All students at Princeton University are separated into k colleges so called residental col- leges . All residental buildings are separated into residental colleges, in a way such that any two residental colleges are disjoint. Currently, there are six: Rockefeller, Mathey, Butler, Whitman, Wilson, and Forbes (but there are plans to build more). Before freshman year, each person is assigned to one college. For the first two years of your time at Princeton University, your room is in your college and there are many different college specific events intended to make people hang out with each other. Therefore, in some sense, people from one college will spend more time with other people from their college, and are more likely to get to know each other. Thus in order to have the most homogeneous distribution of friendships on campus, we want to distribute people into colleges in a pseudo-random way such that there is no preference whether people that were friends before coming to Prince- ton are put in the same or different college. Because of this we want friendships between people of different colleges to be close to random. We will prove that this is always possible under certain restrictions on number of stu- dents and friendships between them prior to coming to Princeton. We will call this theorem the collegiate splitting theorem . Informally, it says that the vertices of every large graph can be partitioned into a bounded number of nearly equal parts so that nearly all bipartite graphs between pieces are “random-like.” We model this problem with graphs. Each per- son will represent a vertex in the friendship graph and two vertices will be connected if and only if the two people were friends before coming to Princeton. To formally formulate the theorem, we will need a few definitions first. Figure 7: An example of what a random like split of people into colleges might look like Definition 2.1.A. Let G = ( V, E ) be a graph with | V | = n . For two disjoint sets U, W ⊂ V , let e ( U, W ) = number of edges between U and W , meaning that we take only edges with one vertex in U and the other in W . Definition 2.1.B. The density of the pair ( U, W ) is defined as e ( U, W ) d ( U, W ) = . | U || W | Definition 2.1.C. For ε > 0 the pair ( U, W ) is called ε -regular if for every X ⊆ U and Y ⊆ W satisfying | X | ≥ ε | U | and | Y | ≥ ε | W | we have | d ( X, Y ) − d ( U, W ) | ≤ ε. U W Figure 8: An ε -regular pair ( U, W ) For example, if U and W are two classes of vertices of K then they are ε -regular since n,n d ( X, Y ) is a constant function on X ∈ U, Y ∈ W .