Combinatorial Methods And Probabilistic Methods In Graph Theory

A random graph is a graph in which properties such as the number of vertices,edges,and connections between vertices are randomly determined.The theory of random graphs founded by Erd(o|¨)s and Rényi during the period of 1959-1961([91,92,93,94]) has been an active area of research that combines probability theory and graph theory,and that is widely applied in various disciplines,such as computer science,chemistry,social science and biology,among others.Now the theory of random graphs has been developed into one of the main research streams of modern discrete mathematics which has produced a prodigious number of results,many of which highly ingenious,describe statistical properties of graphs,such as the evaluation of the random graph,asymptotic distribution,subgraph properties, extremal properties and Ramsey properties.Nowadays,probabilistic methods and ideas play a more and more important role in graphs theory.In this thesis we will focus on the study of asymptotic behaviors of random graphs on n vertices where n tends to infinity.As customary,we say that almost every(a.e.) graph has a certain property if the probability of the set of graphs with that property tends to 1 as n→+∞.This thesis is divided into three parts.The first part is the introduction chapter (Chapter 1);the second part consists of 3 chapters(Chapter 2,3 and 4),and investigate the degree sequence of random multigraphs and random hypergraphs and the third part is on the rainbow Hamilton cycles and H-factors in edge-colored hypergraphs(Chapter 5,6).Let n be a natural number,r a fixed natural number and n_i=n_i(n)(1≤i≤r) nonnegative integer-valued functions on n with n₁+n₂+…+n_r=n.The random r-uniform r-partite hypergraph model H(n₁,n₂,…,n_r;n,p),as a generalization of the classic random bipartite graph model,consists of all the r-uniform r-partite hypergraphs with vertex partition {V₁,V₂,…,V_r},where |V_i|=n_i=n_i(n)(1≤i≤r) and where each r-subset of vertex set V=V₁∪V₂∪…∪V_r containing exactly one element in V_i(1≤i≤r) is chosen to be a hyperedge of H_n,p^(r)∈H(n₁,n₂,…,n_r;n,p) with probability p=p(n),all choices being independent.In Chapter 2 we consider the limit distribution of the degree sequence in V₁ of H_n,p^(r)∈H(n₁,n₂,…,n_r;n,p),as n→∞.LetΔ_V1=Δ_V1(H) andδ_V1=δ_V1(H) be the maximum degree and the minimum degree of vertices in V₁ in H,respectively;X_d,V1=X_d,V1(H),Y_d,V1=Y_d,V1(H),Z_d,V1=Z_d,V1(H) and Z_c,d,V1=Z_c,d,V1(H) be the number of vertices in V₁ with degree d,at least d,at most d,and between c and d in H,respectively.In Chapter 2 we obtain that in the space H(n₁,n₂,…,n_r;n,p),random variables X_d,V1,Y_d,V1,Z_d,V1,and Z_c,d,V1 all have asymptotically Poisson distributions as n→∞.We also consider the following two questions.In what range of p can there be a function D(n) such that in the space H(n₁,n₂,…,n_r;n,p),lim_n→∞P{Δ_V1=D(n)}=1? In what range ofp has almost every H_n,p^(r)∈H(n₁,n₂,…,n_r;n,p) a unique vertex in V₁ with degreeΔ_V1(H_n,p^(r))? We prove that if p≤1/2 then the answer for the first question is Np/log n₁→0,and for the second is Np/log n₁→∞.We also give a good estimate for d_i,V1-d_i+1,V1,whered_1,V1≥d_2,V2＞…＞d_n1,V1 are the degree sequence of H_n,p^(r) in V₁ in decreasing order.In Chapter 3,we generalize the binomial random model G(n,p),and define the model of multigraphs as follows:let G(n;{P_k}) be the probability space of all the labeled loopless multigraphs with vertex set V={v₁,v₂,…,v_n},in which the numbers t_vi,vj of the edges between any two vertices v_i and v_j are identically independent random variables with distributionP{t_vi,vj=k}=p_k,k=0,1,2,…where p_k≥0 and sum from k=0 to∞p_k=1.Then we give a sufficient condition for which the degree distribution of a random multigraph has asymptotically a Poisson distribution as n tends to∞.In order to improve the condition,we also consider the corresponding problem in the special cases of G(n;{p_k}) with {p_k} having geometric distribution,binomial distribution and Poisson distribution,respectively.In Chapter 4,we generalize the classic random bipartite graph model and define the model of random multigraphs as follows:let G(n,m;{p_k}) be the probability space of all the labeled loopless bipartite multigraphs with vertex set A={a₁,a₂,…,a_n} and B={b₁,b₂,…,b_m} in which the numbers t_ai,bj(1≤i≤n,1≤j≤m) of the edges between any two vertices a_i∈A and b_j∈B are identically independent random variables with distributionP{t_ai,bj=k}=p_k,k=0,1,2,…where p_k≥0 and sum from k=0 to∞p_k=1.Results analogous to those in Chapter 2 are obtained for this random bipartite multigraph model G(n,m;{p_k}).On the other hand,the study on the edge-colored graphs and hypergraphs is another hot topic in graph theory.As of today,the study on these problems has produced many classic results and many new methods including the probabilistic method.If H is a hypergraph with h vertices and G is hypergraph with hn vertices,we say that G has an H-factor if it contains n vertex disjoint copies of H.We say a subhypergraph of an edge-colored hypergraph is rainbow if all of its edges have distinct colors,and a rainbow H-factor is an H-factor whose components are rainbow H-subhypergraphs.In Chapter 5,by the probabilistic method,we prove that if the hyperedges of a complete 3-uniform complete hypergraph K_n⁽³⁾ are so colored that no color appears more than [cn]times,where c＜1/1152 is a constant,and if n is even and is sufficiently large, then the edge-colored complete 3-uniform complete hypergraph K_n⁽³⁾ contains a rainbow Hamilton cycle.In Chapter 6,by the probabilistic method,we prove that if h,r and s are positive integers with s≤r≤h and if H is a fixed s-uniform hypergraph with h vertices and with x(H)=r,then there exists a constant k=k(h,r,s) such that any proper edgecolored T_s,r(k) has a rainbow H-factor,where T_s,r(k) is the complete s-uniform r-partite hypergraph with k vertices in each vertex class.