摘要:

AbstractIn this paper we shall investigate the connection between the Szemerédi Regularity Lemma and quasirandom graph sequences, defined by Chung, Graham, and Wilson, and also, slightly differently, by Thomason. We prove that a graph sequence (Gn) is quasirandom if and only if in the Szemerédi partitions ofGnalmost all densities are ½+o(

ISSN:1042-9832    

DOI:10.1002/rsa.3240020102

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1991

数据来源: WILEY

摘要:

AbstractWe establish a uniform asymptotic approximation of certain probabilities arising in the coupon collector's problem. Then we use this approximation to prove that almost all graphs withnvertices and 1.44nedges contain no subgraph with minimum degree at least three, and hence are 3‐colorabl

ISSN:1042-9832    

DOI:10.1002/rsa.3240020103

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1991

数据来源: WILEY

摘要:

AbstractWe consider a randomized version of the greedy algorithm for finding a large matching in a graph. We assume that the next edge is always randomly chosen from those remaining. We analyze the performance of this algorithm when the input graph is fixed. We show that there are graphs for which this Randomized Greedy Algorithm(RGA)usually only obtains a matching close in size to that guaranteed by worst‐case analysis (i.e., half the size of the maximum). For some classes of sparse graphs (e.g., planar graphs and forests) we show that theRGAperforms significantly better than the worst‐case. Our main theorem concerns forests. We prove that the ratio to maximum here is at least 0.7690…, and that this bound is

ISSN:1042-9832    

DOI:10.1002/rsa.3240020104

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1991

数据来源: WILEY

摘要:

Abstract.

ISSN:1042-9832    

DOI:10.1002/rsa.3240020105

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1991

数据来源: WILEY

摘要:

AbstractIn this note we determine the structure of “almost all” graphs not containing a quadrilateral (i.e., a cycle of length four) as an induced subgraph. In particular, it turns out that there are asymptotically twice as many graphs not containing an induced quadrilateral than there are bipartite gra

ISSN:1042-9832    

DOI:10.1002/rsa.3240020106

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1991

数据来源: WILEY

摘要:

AbstractThe “best” inequalities of type P{(ζ, η)⊂E}≧f(P{η⊂D1}P{η⊂Dm}) for independent and identically distributed random elements ζ and η can be reduced to Turán‐type problems for graphs with colored vertices. In the present work we describe a finite algorithm for obtaining the asymptotical solution for an arbitrary problem of such type. In the case of two colors we obtain the final form of asymptotic solution without

ISSN:1042-9832    

DOI:10.1002/rsa.3240020107

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1991

数据来源: WILEY

摘要:

AbstractWe consider P(G is connected) when G is a graph with vertex set Z+= {1,2, …}, and the edge betweeniandjis present with probability p(i,j) = min(λh(i, j), 1) for certain functionsh(i, j) homogeneous of degree ‐1. It is known that there is a critical value λcof λ such that.We show that the probability, at the critical point λc, thatn1, andn2are connected satisfies a power law, in the sense that forn2≧nt≧ 1for any δ>0 and certain consta

ISSN:1042-9832    

DOI:10.1002/rsa.3240020108

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1991

数据来源: WILEY

ISSN:1042-9832    

DOI:10.1002/rsa.3240020101

出版商:Wiley Subscription Services, Inc., A Wiley Company    

年代:1991

数据来源: WILEY