PUMaC 2019 · 加试 · 第 2 题

2. E ⊆ {{ u, v }| ( u, v ) ∈ V × V, u 6 = v } is a set of edges , i.e. a subset of the set of unordered pairs of vertices. If ( u, v ) ∈ E , we say that uv is an edge. Definition 1.1.B. If { u, v } is an edge in a graph we say that u and v are connected (by an edge) or adjacent . Figure 2: Three examples of non-graphs. Definition 1.1.C. A cycle of length n , C is the sequence of distinct vertices v , v , ..., v , n 1 2 n n ≥ 3, in a graph G such that v v are edges for every i = 1 , ..., n and indices are taken i i +1 modulo n . Figure 3: A cycle C on n vertices. n Definition 1.1.D. A complete graph on n vertices, denoted K is a graph on n vertices with n all possible edges, i.e. K = ( V, E ) where V = [ n ] and E = {{ u, v }| ( u, v ) ∈ V × V, u 6 = v } n Definition 1.1.E. For a vertex v ∈ V of a graph G = ( V, E ), the degree of vertex v is the number of vertices u ∈ V such that { u, v } is an edge. Definition 1.1.F. A graph G = ( V, E ) is said to be d -regular if every vertex in G has degree d . Definition 1.1.G. A graph G = ( V, E ) is bipartite if the set of vertices V can be split into two sets X, Y such that every edge in E connects two vertices, one in X and the other in Y . Definition 1.1.H. A complete bipartite graph on n and t vertices K is a bipartite graph n,t G = ( X ∪ Y, E ) for X ∩ Y = ∅ , | X | = n, | Y | = t and the set of edges E are all the edges between a point in X and a point in Y . Figure 4: A bipartite graph, K 3 , 3 Example: The graph in Figure 4 is a complete bipartite graph K ; This graph is 3 , 3 3-regular. The leftmost graph in Figure 1 is also 2-regular. Figure 5: An example of a graph homomorphism from the left graph to K . What does the 5 homomorphism look like, symbolically? ′ ′ ′ Definition 1.1.I. A graph H = ( V , E ) is said to be a subgraph of a graph G if V ⊆ V , ′ E ⊆ E . ′ ′ Definition 1.1.J. A subgraph H = ( V , E ) of a graph G = ( V, E ) is said to be spanning ′ if V = V . ′ ′ Definition 1.1.K. A subgraph H = ( V , E ) of a graph G = ( V, E ) is said to be induced ′ ′ if E are all the edges in E between the vertices in V . For example, both K and C are subgraphs of K but only K is an induced subgraph. 3 4 4 3 Definition 1.1.L. An independent set in a graph G = ( V, E ) is a subset of vertices such that no two are connected by an edge. In C , for example, the maximal independent set contains two vertices. 5 Definition 1.1.M. The r -blowup of a graph G is a graph obtained from G by replacing every vertex by an independent set of size r and every edge by a complete bipartite subgraph between corresponding independent sets. For example, K is an r -blowup of a graph with two vertices and an edge between r,r them. Definition 1.1.N. Let H and G be graphs. A homomorphism from H to G is a function f : V ( H ) → V ( G ) (not necessarily one-to-one) such that for all vertices u, v which form an edge in H , there is also an edge joining f ( u ) to f ( v ) in G ( two vertices that are connected in H map to sifferent vertices in G , but if they are not connected they can map to the same vertex). For example, there is a homomorphism between between C and C . 5 3 Definition 1.1.O. An isomorphism between H and G that is a homomorphism between H and G which is bijective and whose inverse is also a homomorphism. Figure 6: Two isomorphic, hence homomorphic, copies of K . 4 See Figures 3–5 for examples of homomorphisms and isomorphisms. ′ Definition 1.1.P. The core of a graph H is a subgraph H with the minimum possible ′ number of edges such that there exists a homomorphism from H to H . For example, the core of every bipartite graph is a single edge. 1.2 Asymptotic notation Little o and big O notations are used to compare the order of growth of two real functions.

Definition 1.2.A. For two real functions f, g : R → R we say that f ( x ) is o ( g ( x )) (or in f ( x ) words f is in small o of g ), written as f ( x ) = o ( g ( x )) as x → ∞ if lim = 0. x →∞ g ( x ) 2 x Example: 1 /x is o (1), x is o ( x ), and any polynomial of finite degree in x is o ( e ). + Definition 1.2.B. For two real function f, g : R → R we say that f ( x ) is O ( g ( x )) (or in words f is in big O of g ), written as f ( x ) = O ( g ( x )), if there exists a constant c ∈ R and + M ∈ R , such that for all x > M , f ( x ) < cg ( x ). 1.3 Probability Probability theory is the mathematical study of randomness. It has broad applications across natural sciences, engineering, social sciences and pure mathematics. As we will see later, probability has also applications in combinatorics. First we will introduce the main definitions of probability that are needed to use it in combinatorics, and then we will see a few examples of applications of probability in general. 1.4 Definitions A random experiment is an experiment whose outcome cannot be predicted before the experiment is performed, but the possible outcomes are known. Definition 1.4.A. The sample space , usually denoted Ω, is the set of all possible outcomes of a random experiment. Example: Let the random experiment be throwing one red and one blue die. Denote the outcome as ( i, j ) if the red one comes up i and the blue one comes up j . Define the sample space Ω = { ( i, j ) : 1 ≤ i, j ≤ 6 } 2 Thus, here there are 6 = 36 possible outcomes. Now we can discuss what types of question we can ask about outcomes of a random experiment. Informally an event is a statement for which we can determine whether it is true or false after the experiment has been performed. Formally, we define an event in the following way: Definition 1.4.B. An event is a subset A of the sample space Ω. Example: From the previous example of two dice, an example of an event might be “The sum of numbers on the dice is 8.” Consider now two events A and B . The intersection A ∩ B is the event that A and B both occur. The union A ∪ B is the event that A or B occurs (meaning either A , B or c both occur). The complement A = Ω − A is the event that A does not occur . Definition 1.4.C. A probability measure is an assignment of a nonnegative real number P ( A ) ∈ [0 , 1] to every event A such that the following rules are satisfied.