text:
Random matchings which induce Hamilton cycles, and hamiltonian decompositions of random regular graphs
- Gregory Andrews
- 2 years ago
- Views:
1 Random matchings which induce Hamilton cycles, and hamiltonian decompositions of random regular graphs Jeong Han Kim Microsoft Research One Microsoft Way Redmond, WA 9805 USA Nicholas C. Wormald Department of Mathematics and Statistics University of Melbourne VIC 3010 Australia Abstract Select four perfect matchings of n vertices, independently at random. We find the asymptotic probability that each of the first and second matchings forms a Hamilton cycle with each of the third and fourth. This is generalised to embrace any fixed number of perfect matchings, where a prescribed set of pairs of matchings must each produce Hamilton cycles with suitable restrictions on the prescribed set of pairs). We also show how the result with four matchings implies that a random d-regular graph for fixed even d 4 asymptotically almost surely decomposes into d/ Hamilton cycles. This completes a general result on the edge-decomposition of a random regular graph into regular spanning subgraphs of given degrees together with Hamilton cycles, and verifies conjectures of Janson and of Robinson and Wormald. 1 Introduction Our main concern in this paper is to address two questions. The first is whether a random d-regular graph for even d asymptotically almost surely a.a.s.) has an edgedecomposition into Hamilton cycles. Here and in all our asymptotic statements, we take n, with n restricted to even integers in statements about d-regular graphs if d is odd. Related to this, we also consider algorithms for finding these edge-decompositions in random regular graphs. The second question can be phrased in general as follows: given a set of randomly generated perfect matchings of an even number of vertices, what is the probability that each of a prescribed set of pairs of those matchings induces a connected graph that is, a Hamilton cycle) on those vertices? This question was actually motivated by the first, although the relationship between the two questions will only appear in the proof of Theorem 1 below. Research supported in part by the Australian Research Council and performed in part while visiting Microsoft Research. 1
2 1.1 Hamiltonian decompositions and contiguity By a complete hamiltonian decomposition of a d-regular graph G we mean a set of d/ edge-disjoint Hamilton cycles of G. If d is odd, the left-over edges must form a perfect matching. Let G n,d denote the uniform probability space whose elements are the d-regular graphs on the vertex set [n] = {1,..., n}. Conjecture 1 in [9] was essentially that if d 4 then G G n,d a.a.s. has a complete hamiltonian decomposition. Here we say essentially because of the unimportant restriction to even n in [9].) It is already known see [11, Section 4]) that this conjecture follows from the case d = 4, which is given explicitly as Corollary 1 below. We prove Corollary 1 using the small subgraph conditioning method, which originated in the papers of Robinson and Wormald [8, 9], from which the general method was set forth by Molloy et al. [6] and by Janson [4]; see [11] for a full development. This method is of use in certain cases when most of the variance of the random variable of interest is caused by the influence of a set of other random variables. In all cases where this method has been applied, the variable of interest has been a count of large subgraphs such as Hamilton cycles) and the other variables have been counts of small subgraphs such as cycles of given fixed lengths). The results we obtain are best described in terms of contiguity. Let F n and ˆF n be two discrete probability spaces which have the same underlying set for each n 1. We say that the two sequences of spaces F n ) and ˆF n ) are contiguous if any sequence of events A n n 1) is true a.a.s. in F n ) if and only if it is true a.a.s. in ˆF n ). In this case we write F n ˆF n and by a slight abuse of notation say that F n and ˆF n are contiguous. As in [11], if F and ˆF are probability spaces of random d-regular graphs or multigraphs on the same vertex set, we define their sum F + ˆF to be the space whose elements are defined by the random multigraph G Ĝ where G F and Ĝ ˆF are generated independently. Similarly, define the graph-restricted sum of F and ˆF, denoted by F ˆF, to be the space which is the restriction of F + ˆF to simple graphs i.e. with no multiple edges). In order to maintain identical underlying sets for spaces which are to be related, the sum space F + ˆF is extended to include all d-regular multigraphs on the same vertex set, with all multigraphs not already appearing being given probability 0. Similarly, F ˆF is extended to include the underlying set of G n,d. Defining H n to be a random Hamilton cycle on the same vertex set as G n,d, we can now state the following. Theorem 1 H n H n G n,4. Since the event of having two edge-disjoint Hamilton cycles occurs with probability 1 in H n H n, this theorem immediately implies the following. Corollary 1 G G n,4 a.a.s. has two edge-disjoint Hamilton cycles. Whenever it works, the small subgraph conditioning method gives the asymptotic distribution of the numbers of graph decompositions concerned. Thus, the number of pairs of edge-disjoint Hamilton cycles in G G n,4 is asymptotically the exponential of a linear combination of infinitely many independent Poisson variables see [4, Theorem 1] or [11, Theorem 4.3]). We approach random d-regular graphs by using the standard pairing model see Bollobás [1]). Consider dn points, with d points in each of n buckets, and take a
3 random pairing of all the points. We call this uniform probability space P n,d. Letting the buckets be vertices and each pair represent an edge which joins the buckets containing its two vertices), we obtain a random regular pseudograph possibly having loops and multiple edges). Denote this probability space by Gn,d. Graphs with no loops or multiple edges occur with equal probabilities, so the restiction of Gn,d to simple) graphs gives the probability space G n,d. As was widely expected, our proof of Corollary 1 simultaneously gives a proof the following result, which answers affirmatively a conjecture of Janson [4, Conjecture ]. For this we need to define the probability space G n,4 to be the restriction of G n,4 to loopless multigraphs. Theorem H n + H n G n,4. Contiguity is clearly an equivalence relation. So by Theorem we may deduce contiguity between H n + H n and the uniform space of d-regular multigraphs. The intermediate contiguity is given by [4, Theorem 1]. We next show how the desired decomposition of random d-regular graphs follows easily from Theorem 1 and previously known results. The corresponding multigraph version also follows in the same way, by the analogous results for multigraphs.) Corollary If d 4 is even then G G n,d a.a.s. has a complete hamiltonian decomposition. Proof. Let kf denote the graph-restricted sum of k copies of a random graph space F. First consider the case that d is even. It was proved by Frieze et al. [] that G n,d H n G n,d. Repeated use of this fact together with simple properties of contiguity see [11, Lemma 4.14]) and Theorem 1 gives G n,d G n,d H n G n,d 4 H n d H n. The corollary now follows, since a random element of the last space trivially has a complete hamiltonian decomposition with probability 1. For odd d, the conjecture was already known to be true by a similar argument using only the previously known results that dg n,1 G n,d for d 3, and that G n,3 G n,1 H n. See [11, Section 4.3] for details.) In [11, Corollary 4.17] it was shown that combining Theorem 1 with previously known contiguity results produces a general fact about graph-restricted sums of random regular graphs: provided j + d 1 i=1 ik i = d 3 for non-negative k i, G n,d jh n k 1 G n,1 k d 1 G n,d 1. This implies the existence a.a.s. of a decomposition of G G n,d into given numbers of Hamilton cycles and regular factors of prescribed degrees. This is not true for d =.) 3
4 1. Finding complete hamiltonian decompositions In Section 3 we prove the following. Theorem 3 For fixed d 4, there is a randomised algorithm which runs in polynomial time and which for G G n,d a.a.s. finds a complete hamiltonian decomposition of G. Note that the a.a.s. here refers to the randomisation over G and not the randomised algorithm. The existence of the algorithm is proved by induction on d. In [] it was also shown that there is a polynomial time near uniform generator for the set of Hamilton cycles of G G n,d a.a.s. see Section 3) and also an FPRAS fully polynomial randomised approximation scheme see [] for the definition). We conjecture that the same statements are true for complete hamiltonian decompositions rather than just Hamilton cycles. 1.3 Random perfect matchings The main difficulty in using the small subgraph conditioning method is invariably the computation of the variance of the number of decompositions. For the case of decompositions into Hamilton cycles, we will eventually be interested in sets of matchings on the same vertex set. Here and in Section 4, we consider matchings on the set of vertices [n] = {1,,,..., n}. Given two such matchings A and B, we denote by AB the multigraph on that vertex set which has edge set A B. We denote the number of components of a graph by κ, and note that AB is a union of κab) disjoint cycles. Throughout this paper, if A and B have an edge in common, we regard that as a cycle of length in the multigraph AB.) Let HAM denote the set of -regular connected graphs, i.e. those graphs whose edge set induces a Hamilton cycle on the vertex set. We say that A and B are H-compatible if AB HAM. Let hn) denote the number of Hamilton cycles on n vertices and mn) the number of perfect matchings of n vertices. Then hn) = n 1)!, mn) = n)! n! n. 1) We are interested in the probability that a set of random independent, uniformly distributed) perfect matchings on [n] are such that prescribed pairs of the matchings are H-compatible. It is easily computed from 1) that for two such random matchings, or equivalently for one fixed and one random, the probability that they are H-compatible is p H n) π/4n. ) When we consider one uniformly distributed random perfect matching S we denote probability in this space by P S. Our main result in Section 4 is the following. Theorem 4 For given perfect matchings B and R of the same set of vertices such that κbr) n/40, P S BS, SR HAM) = 1 + Ol + 1)/n) + OκBR) + log n)/n ))p H n) where l = B R. 4
5 We do not attempt to optimise the upper bound on κbr) in the hypothesis. This is already far stronger than we need. For we will show that Theorem 4 has the following easy consequence. The special case of this to be used in Section is when the graph G is just a 4-cycle. Let EG) denote the edge set of G. n/ ) Corollary 3 Let G = Gn) be a graph on r vertices where r = rn) = o log n, and assume that for all n, G has no subgraph of minimum degree greater than. Let M 1,..., M r be independent and uniformly distributed random perfect matchings of [n]. Then PM i M j HAM ij EG)) = 1 + Or log n/n))p H n) m where m = EG). Moreover, if r is fixed and G is an r-cycle, then PM i M i+1 HAM i) = 1 + Or log n/n))p H n) r. Proof of Theorems 1.1 and 1. The small subgraph conditioning method calls for computation of expectation and variance of the number of decompositions under examination, as well as computation of joint moments of the numbers of decompositions and other variables which affect its distribution. For most applications so far, including the present one, these other variables are the numbers of short cycles. It is often easiest to work directly with the random pairings in the space P n,d defined in Section 1.1. It will be seen near the end of this section that calculations in P n,d will imply what we need in Theorem about G n,4. Then Theorem 1 will be deduced at the end. So in this section we let G be a random pairing in P n,4. Define an H-cycle of G to be a set of pairs of G which induce a Hamilton cycle in the corresponding multigraph, and define an H-decomposition of G to be an ordered pair of disjoint H-cycles of G. Let H G) be the number of H-decompositions of G. Although the H-cycles in the decomposition are disjoint, the multigraph corresponding to the pairing may have two parallel edges, one from each H-cycle.) Also for k define C k G) to be the number of k-cycles of G i.e. k-cycles of the corresponding multigraph). We will compute asymptotic values for EH and EH ) as well as the joint moments EH [C ] i [C j ] ij ) for fixed j and i,..., i j. Here [x] j denotes xx 1) x j + 1). As a starting point, note that the total number of pairings is P n,4 = 4n)! n)! n ) n n 16 n. 3) e i) EH Select an H-decomposition of a pairing G as follows. First choose the adjacencies of the vertices in each of the two H-cycles this determines all the edges of the corresponding multigraph), and then for each vertex choose one of the 4! ways to 5
6 assign the four points to the four pairs involved. The whole pairing has now been determined. This shows that the number of H-decompositions of pairings is hn) 4!) n π n n e ) n 4 n 4) by 1), and thus using 3) EH π 8n 3 ) n. 5) ii) EH ) This is computed by counting pairings G for which there has been distinguished an ordered pair of H-decompositions. Each edge of G can be said to be type i, j) if it is in the i th H-cycle in the first H-decomposition and the j th H-cycle in the second. So edges are of four types: 1, 1), 1, ),, 1),, ). Vertices are now of three types: A if all four types of edge are incident, B two 1, 1) and two, ) edges are incident, and C if two 1, ) and two, 1) edges are incident. Let a, b and c denote the numbers of vertices of types A, B and C respectively. Note that the edges of any particular type induce exactly a/ paths which terminate only at the vertices of type A. In particular, a must be even. Some of these paths are just an edge between two A-type vertices, and some have other internal vertices of type B or C. However, the type of internal vertices does not change along the path, since paths of 1, 1) edges and those of, ) edges use only the B-type internal vertices, and those of 1, ) edges and those of, 1) edges each use only C-type internal vertices. Moreover, because of the existence of the four H-cycles, each B-type vertex must occur in a path of 1, 1) edges and also in a path of, ) edges, each C-type vertex is similarly in a path of 1, ) edges and in a path of, 1) edges, and the paths must induce four Hamilton cycles on the A-type vertices. In particular, the paths of i, 1) and i, ) edges combine to give a Hamilton cycle on the A-type vertices for i = 1 and ), as do the paths of 1, i) and, i) edges. So we proceed by counting the connection schemes of the paths to the A-type vertices, and then multiplying by the number of ways of choosing which are the A-type vertices and also the number of ways to run through all the B and C type vertices which is determined by b and c). Let Sa) denote the number of connection schemes of the paths to the A-type vertices, and take a = k. Then Sa) is the number of quadruples M 1, M, M 3, M 4 ) of perfect matchings of the type A vertices for paths of edges of types 1, 1), 1, ),, ) and, 1) respectively), such that M 1 M, M M 3, M 3 M 4 and M 4 M 1 are all Hamilton cycles. By Corollary 3 and ), Sk) p H k)mk)) k k 1)!) 4 6) as k. This behaviour of k can be assumed, as can be seen from the following analysis applied to the case of bounded k. Note that if k = 0 the connection scheme is empty, and it is easy to see from the following argument that the contribution from this case is negligible.) 6
7 After deciding on one such connection scheme, there are ) n k ways to choose the labels of the vertices of type A, b + k 1 k 1 ways to assign the numbers of B type vertices to the paths of edges of type 1, 1) and similarly to those of type, ), and c + k 1 k 1 ways to assign the numbers of C type vertices to the paths of edges of type 1, ) and, 1). At this point the scheme can be regarded as a set of paths between vertices of type A, with unlabelled beads on the paths marking how many vertices of type B and C is on each. But each vertex of type B appears once on each of the two types of paths 1, 1) and, ); there are b! ways to make the identifications of the two beads for each vertex, and similarly for the type C vertices. Finally, there are c! n k)! ways to label all the type B and C vertices noting that each labelling produces a different H-decomposition of a pairing) and 4!) n ways to decide the assignments of points in the vertices, as above. The total number of ordered pairs of H-decompositions of pairings with n vertices is the product of the expressions above, summed over k and b. Noting c = n k b, this is where k k b b ) ) n!4!) n 16 k k + b)! n k b)! 16k + b) n k b) k)!b!n k b)! π4!) n n n 16k + b)n k b) kbn k b) e ) n fβ, κ) n 7) fκ, β) = 16κ β + κ) β+κ) 1 κ β) 1 κ β) κ) κ β β 1 κ β) 1 κ β, κ = k/n, β = b/n. 7
8 Here we are assuming b and n k b, which gives negligible error by the following analysis of this expression. The region of summation has these constraints as well as k. To find the main contribution to the summation in 7), set the partial derivatives of log f with respect to κ and β equal to 0. The resulting equations are β + κ) 1 β κ) = β1 β κ), β + κ)1 κ β) = κ1 κ β) which can immediately be combined, after squaring the second, to give 41 κ β)β = κ. Eliminating β1 β) between this and the earlier equation gives 5κ κ1 β) = 0, with solutions κ = 0 which is on the boundary of the region of interest) or κ = 5 1 β). From an earlier equation this yields the only solution not on the boundary: κ, β) = 1 3, 1 6 ). Since f1 3, 1 6 ) = 3 and, as a routine check shows, all boundary points have strictly lower value than this, the only significant parts of the summation in 7) are for k n/3 and b n/6 respectively. Putting κ = x and β = y and expanding ln f about x = y = 0 yields fκ, β) = 3 exp 11x 4xy y + Ox y + xy )) for x and y sufficiently small. From here, a standard argument shows that n/ k=0 n k b=0 fβ, κ) n 3 n e ) 9x n x+y) n dx dy = πn ) 3 n 3. By the concentration of the summation, the terms k + b and n k b in 7) can be taken as 1 n each, and so 7) is asymptotic to 3π ) n 36 n. n On dividing by the number of pairings given by 3), we obtain n e EH ) 3π ) 9 n. 8) 8n 4 ii) EH C k )/EH To estimate this, we first count the H-decompositions of pairings G which have a given k-cycle, summed over all k-cycles, and divide by P n,4. As before, the counting 8
9 can be done first for the possibilities for the corresponding multigraph, and then for the assignment of points to the pairs by multiplying by 4!) n. Only fixed k needs to consider because cycles of length 1 cannot occur in any multigraphs with H-decompositions. To make calculations apply uniformly to all k including k =, consider a labelled directed k-cycle on n vertices, which can be selected in [n] k k nk k ways. The edges of the k-cycle actually, pairs in the cycle) must be split between the two H-cycles of the H-decomposition. Thus for some i 1, the edges of the first H-cycle induce i paths P 1,..., P i in the k-cycle, and those of the second H-cycle induce i paths Q 1,..., Q i. As we shall see, the value of i will affect the number of ways the H-cycle can be chosen, but first we count k-cycles with a given value of i. This can be done by starting at an arbitrary vertex v at the start of a path induced by the first H-cycle and proceeding around the cycle in the chosen direction. The number of ways to determine the lengths of paths P 1, Q 1, P, Q,..., P i, Q i is ) x i [x k ]. 1 x Here square brackets denote the extraction of coefficients, and the formula comes from considering the concatenation of i paths of length at least 1 each, so that x the generating function for each individual path is 1 x). This expression must be multiplied by k i since there are k ways of choosing the starting vertex v, and then every configuration has been counted i times, since there are i paths P l and two orientations of the cycle. After the k-cycle of the multigraph and its partition into paths is decided, if the number of edges of the first H-cycle which are in the k-cycle is j, the rest of the edges in this H-cycle can be chosen in 1 n j 1)!i ways. This comes from a cyclic ordering of the n j)-set whose elements are those i paths and the vertices not in the paths. Similarly, the rest of the edges in the second H-cycle can be chosen in 1 n k + j 1)!i ways. The product of these, regardless of j, is asymptotic to hn) i n k. The product of the last four displayed expressions must be multiplied by 4! n to account for the assignment of points to the pairs, summed over i 1. If we then divide by 4) the result is EH C k ) 1 EH [xk ] ) 1 4x i i 1 x) i 1 = 1 )) 4x [xk ] ln 1 1 x) = + 1)k + 3 k. k 9
10 iii) EH [C 1 ] i1 [C ] i [C j ] ij )/EH A direct generalisation of the argument above, applied to an ordered set of i 1 cycles of length 1, i -cycles, and so on, gives EH [C 1 ] i1 [C k ] ik ) EH k j=1 ρ i j j 9) where ρ j = + 1)j + 3 j. j Note that in the case j = 1 the expected number will be exactly 0, and so r 1 is correctly set to 0. iv) Synthesis One more crucial piece of information is needed: as is well known for this pairing model of random 4-regular multigraphs see [1] for example), the variables C k, k 1, are asymptotically independent Poisson random variables with expectations We write and note that from 5) and 8) EC k λ k = 3k k. ρ j = λ j 1 + δ j ) where δ j = + 1)j 3 j EH EH ) 4 = exp λ k δk. 10) Hence the hypotheses of [11, Theorem 4.1] are satisfied with H standing for Y in that theorem, and C k standing for X k. To state the conclusion of that theorem in this case, we define F Y ) to denote the probability space obtained from a space F by making the probability of each G F proportional to Y G). Noting that δ k = 1 only for k = 1, we obtain P n,4 P H ) n,4 11) where P n,4 is the space P n,4 restricted to C 1 = 0, i.e. the uniform probability space of loopless pairings. Since G n,4 is the random multigraph space corresponding to the space P n,4, and H n + H n is similarly the random multigraph space corresponding to P H ) n,4, Theorem follows from 11). One can alternatively use [6, Corollary 1] or [4, Theorem 1] in place of [11, Theorem 4.1], but then extra argument is required to make the restriction to C 1 = 0. Theorem 1 follows from Theorem by restricting both spaces to simple graphs which we write as the event C = 0 in the graph spaces as well as the pairing spaces). This observation uses only the definition of contiguity and the fact that PC = 0) tends to a non-zero constant in P n,4 as well as in P H ) n,4 the latter of which comes from noting that 9) implies that the variables C k are asymptotically 10 k=1
11 independent Poisson in P H ) n,4 with expectations ρ k ). For if A n is a.a.s. true in G n,4 then A n C = 0) is a.a.s. true in G n,4, so by Theorem it is a.a.s. true in H n + H n, whence A n is a.a.s. true in H n H n. The reverse is also true, and hence Theorem 1. 3 Proof of Theorem 1.3 Assuming a set S of subgraphs of G is nonempty, a near uniform generator for S is a randomised algorithm which on input ɛ > 0 outputs a member s of S such that for any fixed s 1 S Prs = s 1) 1 S ɛ S. 1) The probabilities here are with respect to the algorithm s random choices. The algorithm is called polynomial time if it runs in time polynomial in n and 1/ɛ. From [] we have the following result, where HAMG) denote the set of Hamilton cycles of G. Theorem 5 Let d 3 be fixed. There is a polynomial time procedure which a.a.s. for G G n,d is a near uniform generator for HAMG). As with the proof of Corollary, we focus on d even, since for odd d the result follows by the same argument using results which were already known. So begin an induction on d with d = 4 and let G G n,4. From the theorem featuring in [9], G is a.a.s. hamiltonian. So, letting A denote event that G G n,4 has a Hamilton cycle and for which the procedure referred to in Theorem 5 is a near uniform generator, we have PA) 1. Take a random G G n,4 and then use the procedure in Theorem 5 to get a random H 1 HAMG), with near uniform distribution. Let G 1 = G \ EH 1 ). Then G 1 is a -factor of G. Consider the resulting distribution of the pair G 1, H 1 ). For G A, the probability that G 1, H 1 ) arises can be computed a posteriori as 1 ± ɛ HAMH 1 G 1 ) G n,4. Hence, the probability that any given -factor G 1 arises satisfies PG 1 ) H:H G 1 A 1 ɛ o1) HAMH G 1 ) G n,4. Now take G 0 HAM. We know that the number of Hamilton cycles in G G n,4 is a.a.s. close to its expected value f n, to be precise, at most f n log n; this comes from the results of [] together with [4] or see [11, Theorem 4.3], whose conditions are verified in []). From Theorem 1, for H randomly chosen, the random graph H G 0 restricted to 4-regular graphs is contiguous to G n,4, and so it also has a.a.s. at most f n log n Hamilton cycles. Thus, summing over H, we have PG 1 = G 0 ) {H : H G 0 A} 1 ɛ o1) f n G n,4 log n. 13) 11
12 Let HAMn) denote the set of Hamilton cycles on n vertices. It is easy to find c > 0 such that if we take a random H HAMn) then with probability at least c, EH) EG 0 ) =. See [11, Proof of Lemma 4.14] for example.) Since PA) 1, it follows that the first factor on the right in 13) is at least c o1)) HAMn) n c 1 n e )n where we use c i for positive constants). Moreover, f n is given in [8] and proved in [] to be asymptotic to c n 3 )n, and G n,4 c 3 n ) 3e n is well known. Thus from 13), PG 1 = G 0 ) c 4e n n n log n and so PG 1 HAM) HAMn) c 4 e n n n log n c 5 n log n. 14) So with this probability, the pair G 1, H 1 ) chosen above gives the desired complete hamiltonian decomposition of G. By repeating the generation of this pair n times, we find such a decomposition a.a.s. and in polynomial time. Now consider an even d 4. Choose a random G G n,d and then using Theorem 5 to find a Hamilton cycle H 1 in G a.a.s. with almost uniform distribution. Again set G 1 = G \ EH 1 ) and repeat the arguement above. This time, we use the contiguity H n G n,d G n,d, and obtain for any d -regular graph G 0 that PG 1 = G 0 ) c 6 G n,d log n. So by induction, we can find a complete hamiltonian decomposition of G 1 in polynomial time with probability at least c 6 o1))/ log n. Repeating log n times gives success a.a.s. Including H 1 makes the required complete hamiltonian decomposition of G a.a.s. Finally, it is interesting to consider one potential near-uniform generator for the set of complete hamiltonian decompositions of a regular graph G: take a random Hamilton cycle in G and then by induction use a near-uniform generator to find a decomposition of G EH). This is clearly not near-uniform, but one could try to equalise probabilities by counting the decompositions of G EH). Even if these could be counted accurately, if the near-uniform generator is to work for G, it must generate all decompositions of G with nearly equal probabilities. The main difficulty is that the number of decompositions of G EH) is not bounded above by a polynomial times the expected number, so a significant number of decompositions may not be found often enough) by an algorithm running in polynomial time. Constructing an FPRAS runs into a similar difficulty. 4 Random matchings In this section, we prove Theorem 4 and Corollary 3. Consider two independent random perfect matchings B for blue) and R for red) on [n]. Then the graph BR formed from all edges in B and R is a disjoint union of even length cycles with edges in B R regarded as cycles of length ). Though it is well-known, for the sake of 1
13 completeness and as a gentle introduction to our main arguments, we first prove a bound on the probability that the number κbr) of cycles in BR is large. It is clear that we can generate a matching uniformly at random by selecting the edges one at a time, in each case choosing an unmatched vertex u by any rule whatsoever) and selecting its partner v uniformly at random from the remaining unmatched vertices. We call this exposing the edge uv. We can clearly take the matching B as fixed, and therefore work with P R. We then expose red edges one by one. Take any vertex x and expose the red edge containing x by choosing its neighbor uniformly at random among all n 1 other vertices). If the red edge is identical to a blue edge, set X 1 = 1 and delete the two vertices. Otherwise, set X 1 = 0 and contract the blue-red-blue path into one blue edge consisting of the path s end-vertices. Each case produces a blue matching, but on n vertices. We call this contracting the blue matching with respect to the red edge. Now repeat the operation, exposing one more red edge for this slightly smaller blue matching, contracting to define X, and so on. Continue this procedure until no vertex remains. The last red edge is necessarily identical to the last blue, and so X n = 1.) It is clear that this generates a random red matching and κbr) = X 1 +X + +X n. Moreover, the indicator variables {X i } are independent with p i := PX i = 1) = 1/n i + 1). Lemma 1 For a positive integer s 5, P R κbr) s log n) = O1/n s ). Proof. Using and n i=1 E expα n i=1 ) X i ) = n i=1 ) 1 + p i e α 1) exp e α 1) p i 1 + logn), the Chernoff bound with α = log 10 gives n p i ), i=1 PkBR) s log n) exp αs log n + e α 1) 1 + logn) )) = O1/n s ). To prove Theorem 4, we consider a procedure which is similar to, but more complicated than, that above. Here there are fixed blue and red perfect matchings B and R, and a random perfect matching S of, say, silver edges. Take a vertex x1) in a shortest cycle of BR0) := BR and expose the random silver edge incident with x1). To avoid ambiguity, we assume that a fixed ordering of vertices is given and x1) is the smallest vertex in a shortest cycle. Let y1) be the other end of the silver edge. By contracting each of B and R independently with respect to the silver edge, we obtain blue and red matchings on n vertices which form a graph BR1). Repeating this, we obtain x), y),..., xn 1), yn 1) and graphs BR),..., BRn 1). Clearly, the final graphs BS and RS are both Hamilton cycles if and only if this procedure creates no silver edge identical to an edge in a BRt). 13
14 The key observation is that the process {BRt)} tends to reduce the number of cycles unless there is only one cycle, and hence BRt) is frequently a Hamilton cycle on n t vertices): if BRt 1) has more than one cycle, then the silver edge added to it is more likely to connect two different) cycles, in which case the two cycles become one new cycle after contraction. If the other end yt) is in the cycle containing xt) and the cycle has length greater than, then there are two cases, depending on the distance dxt), yt)), i.e. the length of a shortest path connecting x1) and y1). If the distance is odd but not 1, then the number of cycles increases by 1. It remains the same otherwise. In the case that xt) and yt) are adjacent in the cycle, say by a red edge, it may appear at first sight that the number of cycles increases. However, the contraction operation throws away those two vertices and contracts the blue matching, so only one cycle is retained.) To be more precise, let Y t) = κbrt 1)) κbrt)). We call both yt) and the silver edge good, neutral or bad with respect to BRt 1) and xt)) if Y t) = 1, 0 or 1, respectively. The probabilities of yt) being good, neutral and bad depend upon the length σt 1) of a shortest cycle in BRt 1) recalling that the lengths of all cycles are even). Namely, if σt 1), then since all vertices not in the cycle containing xt) are good, n t + σt 1) PY t) = 1) =. n t + 1 Similarly, σt 1) + 1 PY t) = 0) = n t + 1 and σt 1) PY t) = 1) = n t + 1. If the shortest cycle length is, i.e. a blue and a red edge coincide, then σt 1) = 1 and all vertices are good, or equivalently Y t) = 1. Thus whenever κbrt 1)) > 1, Y t) is stochastically greater than Zt), where PZt) = 1) = 1 and PZt) = 0) = PZt) = 1) = 1 4. Therefore, there are i.i.d. random variables Z1),..., Zn 1) such that Y t) Zt) for all t with κbrt 1)) > 1. Though we do not directly use this fact, the idea will be used in the proof of Lemma 3. For the next lemma, we denote by Ut) the event that the silver edge created at step t is not identical to any edge in BRt 1). Then PBS, RS HAM) = P n 1 ) Ut). Lemma Let l be the number of -cycles in BR. Then for l k n 1, k ) n k + 1 P Ut) = O ). nn l + 1) In particular, if l 1 n then ) 1 PBS, RS HAM) = O. n 14
15 Proof. For any event W, define and notice that P t W ) := PW U1),..., Ut 1)), k ) P Ut) = k P t Ut)). 15) For t l, xt) is taken from a -cycle and the event Ut) occurs unless yt) is the other vertex of the -cycle. Thus, for such t, P t Ut)) = 1 1 n t + 1. Furthermore, since all vertices are good and since the number of -cycles decreases by 1 for each step as long as t l, BRl) contains no -cycles. After this, at most two -cycles are created at a time and they, if any, immediately disappear within the next step or two. So, in particular, the number of -cycles in BRt), t > l, is always at most. Thus, conditioned on the event W t) that no -cycle is created in steps t or t 1, which implies that xt) belongs to a cycle of length greater than, P t Ut) W t)) = 1 n t + 1. For Ut) occurs if and only if dxt), yt)) > 1. On the other hand, Therefore, for t > l Clearly, P t Ut)) P t W t)) 1 = P t W t)) 1 P t Ut) W t)) 1 n t + 1 n t n t + 1. ) + P tw t)) n t + 1. ) + P t W t)) 1 1 ) n t + 1 n t 1) 1 + n t ) 1 4 n t ) since dxt), yt)) must be 3 to create a -cycle, and the case dxt), yt)) = 1 was already excluded. Thus, using 15), k ) P Ut) l 1 ) 1 n t + 1 n k + 1 = O ). nn l + 1) k t=l+1 1 n t ) n t + 1) We are now ready to prove the lemma which is the heart of our arguments in this section. 15
16 Lemma 3 Let R 1 and R be two perfect matchings on [n] with κbr 1 ), κbr ) n/40. Put k = max{κbr 1 ), κbr ), 10 log n}. Then for a random silver) matching S, l1 l ) k ) P S BS, SR 1 HAM) = P S BS, SR HAM) + O n + O n 3, where l i denotes the number of -cycles of BR i i = 1 and ). Proof. Later in this proof, we will define a distribution on the set of ordered pairs S 1, S ) of silver matchings with the marginal distributions of S 1 and S exactly equal that of S. It follows that for the corresponding probability P S1,S ) we have P S BS, SR 1 HAM) = P S1,S )BS 1, S 1 R 1 HAM), P S BS, SR HAM) = P S1,S )BS, S R HAM). Let A 1, A be the events {BS 1, S 1 R 1 HAM} and {BS, S R HAM} respectively. Then ) ) P S BS, SR 1 HAM) P S BS, SR HAM) = P S1,S ) A 1 \A P S1,S ) A \A 1. In the rest of the proof, P denotes P S1,S ). Without loss of generality we may assume l l 1. From above,s it is enough to show that ) l1 l ) k ) P A 1 \ A = O n + O n 3 and ) k ) P A \ A 1 = O n 3. 17) For i = 1 and, let x i 1) be the smallest vertex in a shortest cycle of BR i, and denote that cycle by C i 0). Call a vertex of BR i good, neutral or bad if it is such with respect to BR i and x i 1). Also define BR i 0) = BR i. If the length C 1 0) of C 1 0) is at least C 0), then take a bijection on [n] with the following properties: i) the vertices or vertex) adjacent to x 1) in BR 0) are or is) mapped to vertices adjacent to x 1 1) in BR 1 0); ii) all bad vertices of BR 0) are mapped to bad vertices of BR 1 0); iii) and all neutral vertices which are not distance 1 from x 1) are mapped, if possible, to bad vertices of BR 1 0) and otherwise to neutral vertices of BR 1 0); iv) good vertices of BR 0) are mapped to the remaining vertices of BR 1 0) whether they are good or not); v) If BR 1 0) and BR 0) are isomorphic graphs then the mapping is an isomorphism. This choice of bijection is possible since C 1 0) C 0). Choose y 1 1) uniformly at random from [n] \ {x 1 1)}. We couple y 1 1) and y 1) by selecting y 1) so that it corresponds to y 1 1) under the bijection. If C 1 0) < C 0), reverse the roles of BR 1 and BR in the above discussion. The first silver) edge in S i is x i 1)y i 1), thus determining BR i 1) for i = 1 and. Repeating this procedure, we obtain a random process {x i t), y i t)},...,n 1 for 16
17 i = 1 and. Define S i to contain the set of edges {x i t), y i t)} together with the remaining pair of vertices for i = 1 and ). This induces the distribution on ordered pairs S 1, S ) mentioned at the start of this proof. For any t 1 and i = 1 and, from the above process to time t define the events U i t) and W i t) determined by BR i t 1) and x i t)y i t) as Ut) and W t) were determined by BRt 1) and xt)yt). Also let κt) = max{κbr 1 t)), κbr t))} t 0), Y t) = κt 1) κt) t 1). It is clear that the symmetric difference of U 1 t) and U t) can only contain those processes where C 1 t 1) = or C t 1) = but not both). If a process is in one but not the other and say C 1 t 1) C t 1), then it must be in U t) \ U 1 t), and we have C t 1) = and C 1 t 1) >. Hence and similarly U t) \ U 1 t) { C t 1) = } { C 1 t 1) > }, 18) U 1 t) \ U t) { C 1 t 1) = } { C t 1) > }. 19) For any t 1, condition on some trajectory of the process up to time t 1, i.e. on the sequence {x i j), y i j)} j=0,...,t 1, for which C 1 t 1) C t 1). Suppose on the one hand that κbr 1 t 1)) > 1. If y 1 t) is good, which occurs with probability p 1, then so is y t), and hence κt) = κt 1) 1 and Y t) = 1. Similarly, if y 1 t) is neutral, which occurs with probability at least 1 p)/, then y t) is neutral or good and Y t) 0. As before, Y t) is stochastically greater than Zt) where PZt) = 1) = 1, PZt) = 0) = PZt) = 1) = 1 4. On the other hand, suppose that κbr 1 t 1)) = 1, and κbr t 1)). Then all bad and neutral vertices of BR t 1), except those adjacent to x t 1), are mapped to bad vertices of BR 1 t 1). Hence if y 1 t 1) is neutral and not adjacent to x 1 t 1), which occurs with probability p = n t n t+1, then y t 1) is good and Y t) = 1. Alternatively, conditioning on y 1 t 1) being bad, y t 1) is n t 3 bad with probability at most n t, so that Y t) = 1 with probability at most 1 p) n t 3 n t < 1 4. Thus we have a conclusion similar to that in the above case: Y t) is stochastically greater than Z ɛ t) where PZ ɛ t) = 1) = 1 ɛ, PZ ɛt) = 0) = 1 4 +ɛ, and PZ ɛ t) = 1) = 1 4, provided ɛ > 1 4n 4t+. The same is also true by symmetry in the case C 1 t 1) < C t 1). Approximating Zt) from below by a coupled copy of Z ɛ t), we can obtain i.i.d. random variables {Z ɛ t)},...,n 1 with Y t) Z ɛ t) 0 whenever κt 1). Define the stopping time T to be the smallest t such that κt) = 1. Since κbr 1 n 1)) = κbr n 1)) = 1, T is well-defined. The event A 1 \ A implies that U 1 t) occurs for all t and U t) does not occur at some t, say T. If t > T, then the events U 1 t) and U t) occur at the same time. Thus provided A 1 \ A occurs and T 0k, we have T 0k 1 n and the two events 0k U 1t) \ 0k U t), and n 1 t=0k+1 U 1t), must occur. It follows that PA 1 \ A ) PT 0k) + P{T 0k} A 1 \ A )) PT 0k) + P B 17 0k U 1 t) \ 0k )) U t) 0)
18 where B = n 1 t=0k+1 U 1t). If T 0k, then Y t) Z ɛ t) for all t 0k 1, and κ0k 1) = κ0) Y 1) + + Y 0k 1)) k Z ɛ 1) + + Z ɛ 0k 1)). Therefore, PT 0k) PZ ɛ 1) + + Z ɛ 0k 1) k) = O1/n 4 ), 1) where in the equality we use the Chernoff bound for i.i.d. random variables Z ɛ t), choosing ɛ > 0 sufficiently small but the same for each t. For the second term in 0), since we have P B 0k 0k U 1 t) \ U 1 t) \ 0k 0k 0k U t) U 1 t) \ U t)), )) U t) P B 0k 0k )) U 1 t) \ U t) P U 1 t) \ U t)) B ). ) For t 0k, U 1 t )\U t ) is completely determined by {x 1 t), y 1 t), x t), y t)},...,0k, and so we have by [3, Section 3.7] for example ) ) P U 1 t ) \ U t )) B = E IU 1 t ) \ U t ))IB) ) = E I U 1 t ) \ U t ) E IB) {x 1 t), y 1 t), x t), y t)},...,0k )). 3) As l 1 k, it follows that BR 1 0k) has at most two -cycles as argued in the proof of Lemma. That lemma applied to the process which begins from t = 0k now yields ) 1 ) E IB) {x 1 t), y 1 t), x t), y t)},...,0k = O = O1/n). 4) n 0k By 19), we know that U 1 t) \ U t) = unless t > l. If l < t l 1, then ) E IU 1 t) \ U t)) 1 n t n since l 1 k n/40. If l 1 < t 0k then 19) implies that U 1 t)\u t) W 1 t)\u t) and hence ) )) ) E IU 1 t) \ U t)) E I W 1 t) \ U t) = PW 1 t))p U t) W 1 t) 4 n t + 1 n t + 1 = O1/n ) using 16). Therefore by 1), ), 3) and 4), l1 l ) k ) PA 1 \ A ) = O n + O n 3. 18
19 The same argument yields k ) PA \ A 1 ) = O n 3, as required for 17). We are now in a position to prove Theorem 4. For fixed matchings B, R 1 and R and a random matching S, l1 l ) k ) P S BS, SR 1 HAM) = P S BS, SR HAM) + O n + O n 3. Now for a random matching R, we have κbr ) < 5 log n with probability 1 O1/n 5 ) by Lemma 1. Also it is easily seen that E R l is bounded. So by taking the expectation of both sides of the equation with respect to R, we obtain l1 + 1) κsr1 ) + log n) P S BS, SR 1 HAM) = E R P S BS, SR HAM)+O n +O n 3. Theorem 4 follows since E R P S BS, SR HAM) = E R E S IBS HAM)ISR HAM)) = E S E R IBS HAM)ISR HAM)) = P S BS HAM)) = p H n), which is of order 1/n. Corollary 3 also easily follows using Lemma 1. We can clearly assume r 3. Take an ordering v 1,..., v r of the vertices of G so that the number dj) of i > j with v i v j EG) is at most. Let r denote the number of j with dj) =. For each such j, if v i1 and v i are the two neighbours of v j with i 1, i > j then by Lemma 1, with probability at least 1 O1/n r+ ), we have κm vi M vj ) r + ) log n. We can now estimate the probability that M vi M vj HAM for all i and j such that v i v j EG). The strategy is to treat the matchings in the order M vr, M vr 1,..., M v1 and check H-compatibility of each with those of the others which are required and have already appeared, conditioning progressively on each step being successful. For those r where two others are involved, we use Theorem 4. Note that κ is an upper bound for the number l of -cycles.) Otherwise, there is only one other matching involved, and the probability that the new matching is H-compatible with it is just p H n). So the required final probability is ) r r 1 + OrIdj) = ) log n/n))p H n)) dj) + O n j=1 r+ = 1 + Orr log n/n))p H n)) m. Trivially, r r. For a cycle of length r, the natural ordering yields r = 1. 19
20 References [1] B. Bollobás, Random graphs, Academic Press, London, [] A. Frieze, M. Jerrum, M. Molloy, R.W. Robinson and N.C. Wormald, Generating and counting Hamilton cycles in random regular graphs, Journal of Algorithms ), [3] G.R. Grimmett and D.R. Stirzaker, Probability and Random Processes, nd edn, Clarendon 199). [4] S. Janson, Random regular graphs: Asymptotic distributions and contiguity, Combinatorics, Probability and Computing ), [5] C. McDiarmid, On the method of bounded differences, Surveys in Combinatorics, 1989, J. Siemons ed. 1989), [6] M. Molloy, H. Robalewska, R.W. Robinson and N.C. Wormald, 1-factorisations of random regular graphs, Random Structures and Algorithms ), [7] H. Robalewska, -factors in random regular graphs, Journal of Graph Theory ), [8] R.W. Robinson and N.C. Wormald, Almost all cubic graphs are hamiltonian, Random Structures Algorithms 3 199), [9] R. W. Robinson and N. C. Wormald, Almost all regular graphs are hamiltonian, Random Structures and Algorithms ), [10] A. Steger and N.C. Wormald, Generating random regular graphs quickly, Combinatorics, Probability and Computing ), [11] N.C. Wormald, Models of random regular graphs, Surveys in Combinatorics, 1999, London Mathematical Society Lecture Note Series 67 J.D. Lamb and D.A. Preece, eds) Cambridge University Press, Cambridge, pp ,
Labeling outerplanar graphs with maximum degree three
Labeling outerplanar graphs with maximum degree three Xiangwen Li 1 and Sanming Zhou 2 1 Department of Mathematics Huazhong Normal University, Wuhan 430079, China 2 Department of Mathematics and StatisticsMore information
Partitioning edge-coloured complete graphs into monochromatic cycles and paths
arxiv:1205.5492v1 [math.co] 24 May 2012 Partitioning edge-coloured complete graphs into monochromatic cycles and paths Alexey Pokrovskiy Departement of Mathematics, London School of Economics and PoliticalMore information
High degree graphs contain large-star factors
High degree graphs contain large-star factors Dedicated to László Lovász, for his 60th birthday Noga Alon Nicholas Wormald Abstract We show that any finite simple graph with minimum degree d contains aMore information
A Turán Type Problem Concerning the Powers of the Degrees of a Graph
A Turán Type Problem Concerning the Powers of the Degrees of a Graph Yair Caro and Raphael Yuster Department of Mathematics University of Haifa-ORANIM, Tivon 36006, Israel. AMS Subject Classification:More information
8. Matchings and Factors
8. Matchings and Factors Consider the formation of an executive council by the parliament committee. Each committee needs to designate one of its members as an official representative to sit on the council,More information
136 TER 4. INDUCTION, GRHS ND TREES 4.3 Graphs In this chapter we introduce a fundamental structural idea of discrete mathematics, that of a graph. Many situations in the applications of discrete mathematicsMore information
ON INDUCED SUBGRAPHS WITH ALL DEGREES ODD. 1. Introduction
ON INDUCED SUBGRAPHS WITH ALL DEGREES ODD A.D. SCOTT Abstract. Gallai proved that the vertex set of any graph can be partitioned into two sets, each inducing a subgraph with all degrees even. We proveMore information
A 2-factor in which each cycle has long length in claw-free graphs
A -factor in which each cycle has long length in claw-free graphs Roman Čada Shuya Chiba Kiyoshi Yoshimoto 3 Department of Mathematics University of West Bohemia and Institute of Theoretical Computer ScienceMore information
Graphs without proper subgraphs of minimum degree 3 and short cycles
Graphs without proper subgraphs of minimum degree 3 and short cycles Lothar Narins, Alexey Pokrovskiy, Tibor Szabó Department of Mathematics, Freie Universität, Berlin, Germany. August 22, 2014 AbstractMore information
Large induced subgraphs with all degrees odd
Large induced subgraphs with all degrees odd A.D. Scott Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, England Abstract: We prove that every connected graph of orderMore information
Discrete Mathematics & Mathematical Reasoning Chapter 10: Graphs
Discrete Mathematics & Mathematical Reasoning Chapter 10: Graphs Kousha Etessami U. of Edinburgh, UK Kousha Etessami (U. of Edinburgh, UK) Discrete Mathematics (Chapter 6) 1 / 13 Overview Graphs and GraphMore information
Stationary random graphs on Z with prescribed iid degrees and finite mean connections
Stationary random graphs on Z with prescribed iid degrees and finite mean connections Maria Deijfen Johan Jonasson February 2006 Abstract Let F be a probability distribution with support on the non-negativeMore information
Lecture 15 An Arithmetic Circuit Lowerbound and Flows in Graphs
CSE599s: Extremal Combinatorics November 21, 2011 Lecture 15 An Arithmetic Circuit Lowerbound and Flows in Graphs Lecturer: Anup Rao 1 An Arithmetic Circuit Lower Bound An arithmetic circuit is just likeMore information
10. Graph Matrices Incidence Matrix
10 Graph Matrices Since a graph is completely determined by specifying either its adjacency structure or its incidence structure, these specifications provide far more efficient ways of representing aMore information
Every tree contains a large induced subgraph with all degrees odd
Every tree contains a large induced subgraph with all degrees odd A.J. Radcliffe Carnegie Mellon University, Pittsburgh, PA A.D. Scott Department of Pure Mathematics and Mathematical Statistics UniversityMore information
Zachary Monaco Georgia College Olympic Coloring: Go For The Gold
Zachary Monaco Georgia College Olympic Coloring: Go For The Gold Coloring the vertices or edges of a graph leads to a variety of interesting applications in graph theory These applications include variousMore information
The Goldberg Rao Algorithm for the Maximum Flow Problem
The Goldberg Rao Algorithm for the Maximum Flow Problem COS 528 class notes October 18, 2006 Scribe: Dávid Papp Main idea: use of the blocking flow paradigm to achieve essentially O(min{m 2/3, n 1/2 }More information
31 Kragujevac J. Math. 25 (2003) 31 49. SHARP BOUNDS FOR THE SUM OF THE SQUARES OF THE DEGREES OF A GRAPH Kinkar Ch. Das Department of Mathematics, Indian Institute of Technology, Kharagpur 721302, W.B.,More information
Some Polynomial Theorems. John Kennedy Mathematics Department Santa Monica College 1900 Pico Blvd. Santa Monica, CA 90405 firstname.lastname@example.com.
Some Polynomial Theorems by John Kennedy Mathematics Department Santa Monica College 1900 Pico Blvd. Santa Monica, CA 90405 firstname.lastname@example.com This paper contains a collection of 31 theorems, lemmas,More information
Mathematics for Computer Science/Software Engineering. Notes for the course MSM1F3 Dr. R. A. Wilson
Mathematics for Computer Science/Software Engineering Notes for the course MSM1F3 Dr. R. A. Wilson October 1996 Chapter 1 Logic Lecture no. 1. We introduce the concept of a proposition, which is a statementMore information
On an anti-ramsey type result
On an anti-ramsey type result Noga Alon, Hanno Lefmann and Vojtĕch Rödl Abstract We consider anti-ramsey type results. For a given coloring of the k-element subsets of an n-element set X, where two k-elementMore information
A REMARK ON ALMOST MOORE DIGRAPHS OF DEGREE THREE. 1. Introduction and Preliminaries
Acta Math. Univ. Comenianae Vol. LXVI, 2(1997), pp. 285 291 285 A REMARK ON ALMOST MOORE DIGRAPHS OF DEGREE THREE E. T. BASKORO, M. MILLER and J. ŠIRÁŇ Abstract. It is well known that Moore digraphs doMore information
The positive minimum degree game on sparse graphs
The positive minimum degree game on sparse graphs József Balogh Department of Mathematical Sciences University of Illinois, USA email@example.com András Pluhár Department of Computer Science UniversityMore information
Subsets of Euclidean domains possessing a unique division algorithm
Subsets of Euclidean domains possessing a unique division algorithm Andrew D. Lewis 2009/03/16 Abstract Subsets of a Euclidean domain are characterised with the following objectives: (1) ensuring uniquenessMore information
Non-Separable Detachments of Graphs
Egerváry Research Group on Combinatorial Optimization Technical reports TR-2001-12. Published by the Egrerváry Research Group, Pázmány P. sétány 1/C, H 1117, Budapest, Hungary. Web site: www.cs.elte.hu/egres.More information
A Sublinear Bipartiteness Tester for Bounded Degree Graphs
A Sublinear Bipartiteness Tester for Bounded Degree Graphs Oded Goldreich Dana Ron February 5, 1998 Abstract We present a sublinear-time algorithm for testing whether a bounded degree graph is bipartiteMore information
Class One: Degree Sequences
Class One: Degree Sequences For our purposes a graph is a just a bunch of points, called vertices, together with lines or curves, called edges, joining certain pairs of vertices. Three small examples ofMore information
On Integer Additive Set-Indexers of Graphs
On Integer Additive Set-Indexers of Graphs arxiv:1312.7672v4 [math.co] 2 Mar 2014 N K Sudev and K A Germina Abstract A set-indexer of a graph G is an injective set-valued function f : V (G) 2 X such thatMore information
Maximum Hitting Time for Random Walks on Graphs. Graham Brightwell, Cambridge University Peter Winkler*, Emory University
Maximum Hitting Time for Random Walks on Graphs Graham Brightwell, Cambridge University Peter Winkler*, Emory University Abstract. For x and y vertices of a connected graph G, let T G (x, y denote theMore information
I GROUPS: BASIC DEFINITIONS AND EXAMPLES Definition 1: An operation on a set G is a function : G G G Definition 2: A group is a set G which is equipped with an operation and a special element e G, calledMore information
M-Degrees of Quadrangle-Free Planar Graphs
M-Degrees of Quadrangle-Free Planar Graphs Oleg V. Borodin, 1 Alexandr V. Kostochka, 1,2 Naeem N. Sheikh, 2 and Gexin Yu 3 1 SOBOLEV INSTITUTE OF MATHEMATICS NOVOSIBIRSK 630090, RUSSIA E-mail: email@example.com information
Odd induced subgraphs in graphs of maximum degree three
Odd induced subgraphs in graphs of maximum degree three David M. Berman, Hong Wang, and Larry Wargo Department of Mathematics University of New Orleans New Orleans, Louisiana, USA 70148 Abstract A long-standingMore information
Computer Science Department. Technion - IIT, Haifa, Israel. Itai and Rodeh [IR] have proved that for any 2-connected graph G and any vertex s G there
- 1 - THREE TREE-PATHS Avram Zehavi Alon Itai Computer Science Department Technion - IIT, Haifa, Israel Abstract Itai and Rodeh [IR] have proved that for any 2-connected graph G and any vertex s G thereMore information
Mathematics Course 111: Algebra I Part IV: Vector Spaces
Mathematics Course 111: Algebra I Part IV: Vector Spaces D. R. Wilkins Academic Year 1996-7 9 Vector Spaces A vector space over some field K is an algebraic structure consisting of a set V on which areMore information
SHOT YLE OVES OF PHS WITH MINIMUM DEEE THEE TOMÁŠ KISE, DNIEL KÁL, END LIDIKÝ, PVEL NEJEDLÝ OET ŠÁML, ND bstract. The Shortest ycle over onjecture of lon and Tarsi asserts that the edges of every bridgelessMore information
2.3 Scheduling jobs on identical parallel machines
2.3 Scheduling jobs on identical parallel machines There are jobs to be processed, and there are identical machines (running in parallel) to which each job may be assigned Each job = 1,,, must be processedMore information
VERTICES OF GIVEN DEGREE IN SERIES-PARALLEL GRAPHS MICHAEL DRMOTA, OMER GIMENEZ, AND MARC NOY Abstract. We show that the number of vertices of a given degree k in several kinds of series-parallel labelledMore information
On one-factorizations of replacement products
Filomat 27:1 (2013), 57 63 DOI 10.2298/FIL1301057A Published by Faculty of Sciences and Mathematics, University of Niš, Serbia Available at: http://www.pmf.ni.ac.rs/filomat On one-factorizations of replacementMore information
The Open University s repository of research publications and other research outputs
Open Research Online The Open University s repository of research publications and other research outputs The degree-diameter problem for circulant graphs of degree 8 and 9 Journal Article How to cite:More information
Single machine parallel batch scheduling with unbounded capacity
Workshop on Combinatorics and Graph Theory 21th, April, 2006 Nankai University Single machine parallel batch scheduling with unbounded capacity Yuan Jinjiang Department of mathematics, Zhengzhou UniversityMore information
Graph theoretic techniques in the analysis of uniquely localizable sensor networks
Graph theoretic techniques in the analysis of uniquely localizable sensor networks Bill Jackson 1 and Tibor Jordán 2 ABSTRACT In the network localization problem the goal is to determine the location ofMore information
Ph.D. Thesis. Judit Nagy-György. Supervisor: Péter Hajnal Associate Professor
Online algorithms for combinatorial problems Ph.D. Thesis by Judit Nagy-György Supervisor: Péter Hajnal Associate Professor Doctoral School in Mathematics and Computer Science University of Szeged BolyaiMore information
Catalan Numbers. Thomas A. Dowling, Department of Mathematics, Ohio State Uni- versity.
7 Catalan Numbers Thomas A. Dowling, Department of Mathematics, Ohio State Uni- Author: versity. Prerequisites: The prerequisites for this chapter are recursive definitions, basic counting principles,More information
Séminaire Lotharingien de Combinatoire 53 (2006), Article B53g ON DEGREES IN THE HASSE DIAGRAM OF THE STRONG BRUHAT ORDER RON M. ADIN AND YUVAL ROICHMAN Abstract. For a permutation π in the symmetric groupMore information
Lecture 4: BK inequality 27th August and 6th September, 2007
CSL866: Percolation and Random Graphs IIT Delhi Amitabha Bagchi Scribe: Arindam Pal Lecture 4: BK inequality 27th August and 6th September, 2007 4. Preliminaries The FKG inequality allows us to lower boundMore information
Approximation Algorithms
Approximation Algorithms or: How I Learned to Stop Worrying and Deal with NP-Completeness Ong Jit Sheng, Jonathan (A0073924B) March, 2012 Overview Key Results (I) General techniques: Greedy algorithmsMore information
Mean Ramsey-Turán numbers
Mean Ramsey-Turán numbers Raphael Yuster Department of Mathematics University of Haifa at Oranim Tivon 36006, Israel Abstract A ρ-mean coloring of a graph is a coloring of the edges such that the averageMore information
MATHEMATICAL ENGINEERING TECHNICAL REPORTS. An Improved Approximation Algorithm for the Traveling Tournament Problem
MATHEMATICAL ENGINEERING TECHNICAL REPORTS An Improved Approximation Algorithm for the Traveling Tournament Problem Daisuke YAMAGUCHI, Shinji IMAHORI, Ryuhei MIYASHIRO, Tomomi MATSUI METR 2009 42 SeptemberMore information
Exponential time algorithms for graph coloring
Exponential time algorithms for graph coloring Uriel Feige Lecture notes, March 14, 2011 1 Introduction Let [n] denote the set {1,..., k}. A k-labeling of vertices of a graph G(V, E) is a function V [k].More information
Analysis of Algorithms, I
Analysis of Algorithms, I CSOR W4231.002 Eleni Drinea Computer Science Department Columbia University Thursday, February 26, 2015 Outline 1 Recap 2 Representing graphs 3 Breadth-first search (BFS) 4 ApplicationsMore information
COUNTING INDEPENDENT SETS IN SOME CLASSES OF (ALMOST) REGULAR GRAPHS Alexander Burstein Department of Mathematics Howard University Washington, DC 259, USA email@example.com Sergey Kitaev MathematicsMore information
Divisor graphs have arbitrary order and size
Divisor graphs have arbitrary order and size arxiv:math/0606483v1 [math.co] 20 Jun 2006 Le Anh Vinh School of Mathematics University of New South Wales Sydney 2052 Australia Abstract A divisor graph GMore information
On the k-path cover problem for cacti
On the k-path cover problem for cacti Zemin Jin and Xueliang Li Center for Combinatorics and LPMC Nankai University Tianjin 300071, P.R. China email@example.com, email@example.com Abstract In this paper weMore information
Introduced by Stuart Kauffman (ca. 1986) as a tunable family of fitness landscapes.
68 Part II. Combinatorial Models can require a number of spin flips that is exponential in N (A. Haken et al. ca. 1989), and that one can in fact embed arbitrary computations in the dynamics (Orponen 1995).More information
Lecture 7: Approximation via Randomized Rounding
Lecture 7: Approximation via Randomized Rounding Often LPs return a fractional solution where the solution x, which is supposed to be in {0, } n, is in [0, ] n instead. There is a generic way of obtainingMore information
Tree-representation of set families and applications to combinatorial decompositions
Tree-representation of set families and applications to combinatorial decompositions Binh-Minh Bui-Xuan a, Michel Habib b Michaël Rao c a Department of Informatics, University of Bergen, Norway. firstname.lastname@example.com information
Brendan D. McKay Computer Science Dept., Vanderbilt University, Nashville, Tennessee 37235
139. Proc. 3rd Car. Conf. Comb. & Comp. pp. 139-143 SPANNING TREES IN RANDOM REGULAR GRAPHS Brendan D. McKay Computer Science Dept., Vanderbilt University, Nashville, Tennessee 37235 Let n~ < n2More information
Best Monotone Degree Bounds for Various Graph Parameters
Best Monotone Degree Bounds for Various Graph Parameters D. Bauer Department of Mathematical Sciences Stevens Institute of Technology Hoboken, NJ 07030 S. L. Hakimi Department of Electrical and ComputerMore information
COMBINATORIAL PROPERTIES OF THE HIGMAN-SIMS GRAPH. 1. Introduction
COMBINATORIAL PROPERTIES OF THE HIGMAN-SIMS GRAPH ZACHARY ABEL 1. Introduction In this survey we discuss properties of the Higman-Sims graph, which has 100 vertices, 1100 edges, and is 22 regular. In factMore information
PUTNAM TRAINING POLYNOMIALS. Exercises 1. Find a polynomial with integral coefficients whose zeros include 2 + 5.
PUTNAM TRAINING POLYNOMIALS (Last updated: November 17, 2015) Remark. This is a list of exercises on polynomials. Miguel A. Lerma Exercises 1. Find a polynomial with integral coefficients whose zeros includeMore information
The degree, size and chromatic index of a uniform hypergraph
The degree, size and chromatic index of a uniform hypergraph Noga Alon Jeong Han Kim Abstract Let H be a k-uniform hypergraph in which no two edges share more than t common vertices, and let D denote theMore information
INDISTINGUISHABILITY OF ABSOLUTELY CONTINUOUS AND SINGULAR DISTRIBUTIONS STEVEN P. LALLEY AND ANDREW NOBEL Abstract. It is shown that there are no consistent decision rules for the hypothesis testing problemMore information
Uniform Multicommodity Flow through the Complete Graph with Random Edge-capacities
Combinatorics, Probability and Computing (2005) 00, 000 000. c 2005 Cambridge University Press DOI: 10.1017/S0000000000000000 Printed in the United Kingdom Uniform Multicommodity Flow through the CompleteMore information
Homework Exam 1, Geometric Algorithms, 2016
Homework Exam 1, Geometric Algorithms, 2016 1. (3 points) Let P be a convex polyhedron in 3-dimensional space. The boundary of P is represented as a DCEL, storing the incidence relationships between theMore information
On end degrees and infinite cycles in locally finite graphs
On end degrees and infinite cycles in locally finite graphs Henning Bruhn Maya Stein Abstract We introduce a natural extension of the vertex degree to ends. For the cycle space C(G) as proposed by DiestelMore information
arxiv:math/0202219v1 [math.co] 21 Feb 2002
RESTRICTED PERMUTATIONS BY PATTERNS OF TYPE (2, 1) arxiv:math/0202219v1 [math.co] 21 Feb 2002 TOUFIK MANSOUR LaBRI (UMR 5800), Université Bordeaux 1, 351 cours de la Libération, 33405 Talence Cedex, FranceMore information
FACTORING POLYNOMIALS IN THE RING OF FORMAL POWER SERIES OVER Z DANIEL BIRMAJER, JUAN B GIL, AND MICHAEL WEINER Abstract We consider polynomials with integer coefficients and discuss their factorizationMore information
Integer roots of quadratic and cubic polynomials with integer coefficients
Integer roots of quadratic and cubic polynomials with integer coefficients Konstantine Zelator Mathematics, Computer Science and Statistics 212 Ben Franklin Hall Bloomsburg University 400 East Second StreetMore information
Cycles and clique-minors in expanders
Cycles and clique-minors in expanders Benny Sudakov UCLA and Princeton University Expanders Definition: The vertex boundary of a subset X of a graph G: X = { all vertices in G\X with at least one neighborMore information
A simple criterion on degree sequences of graphs
Discrete Applied Mathematics 156 (2008) 3513 3517 Contents lists available at ScienceDirect Discrete Applied Mathematics journal homepage: www.elsevier.com/locate/dam Note A simple criterion on degreeMore information
SEQUENCES OF MAXIMAL DEGREE VERTICES IN GRAPHS. Nickolay Khadzhiivanov, Nedyalko Nenov
Serdica Math. J. 30 (2004), 95 102 SEQUENCES OF MAXIMAL DEGREE VERTICES IN GRAPHS Nickolay Khadzhiivanov, Nedyalko Nenov Communicated by V. Drensky Abstract. Let Γ(M) where M V (G) be the set of all verticesMore information
1. Prove that the empty set is a subset of every set.
1. Prove that the empty set is a subset of every set. Basic Topology Written by Men-Gen Tsai email: firstname.lastname@example.com Proof: For any element x of the empty set, x is also an element of every set sinceMore information
Random graphs with a given degree sequence
Sourav Chatterjee (NYU) Persi Diaconis (Stanford) Allan Sly (Microsoft) Let G be an undirected simple graph on n vertices. Let d 1,..., d n be the degrees of the vertices of G arranged in descending order.More information
Markov random fields and Gibbs measures
Chapter Markov random fields and Gibbs measures 1. Conditional independence Suppose X i is a random element of (X i, B i ), for i = 1, 2, 3, with all X i defined on the same probability space (.F, P).More information
Math 312 Homework 1 Solutions
Math 31 Homework 1 Solutions Last modified: July 15, 01 This homework is due on Thursday, July 1th, 01 at 1:10pm Please turn it in during class, or in my mailbox in the main math office (next to 4W1) PleaseMore information
3. Eulerian and Hamiltonian Graphs
3. Eulerian and Hamiltonian Graphs There are many games and puzzles which can be analysed by graph theoretic concepts. In fact, the two early discoveries which led to the existence of graphs arose fromMore information
Social Media Mining. Graph Essentials
Graph Essentials Graph Basics Measures Graph and Essentials Metrics 2 2 Nodes and Edges A network is a graph nodes, actors, or vertices (plural of vertex) Connections, edges or ties Edge Node MeasuresMore information
Discrete Mathematics and Probability Theory Fall 2009 Satish Rao,David Tse Note 11
CS 70 Discrete Mathematics and Probability Theory Fall 2009 Satish Rao,David Tse Note Conditional Probability A pharmaceutical company is marketing a new test for a certain medical condition. AccordingMore information
Basic Concepts of Point Set Topology Notes for OU course Math 4853 Spring 2011
Basic Concepts of Point Set Topology Notes for OU course Math 4853 Spring 2011 A. Miller 1. Introduction. The definitions of metric space and topological space were developed in the early 1900 s, largelyMore information
8.1 Min Degree Spanning Tree
CS880: Approximations Algorithms Scribe: Siddharth Barman Lecturer: Shuchi Chawla Topic: Min Degree Spanning Tree Date: 02/15/07 In this lecture we give a local search based algorithm for the Min DegreeMore information
DETERMINANTS IN THE KRONECKER PRODUCT OF MATRICES: THE INCIDENCE MATRIX OF A COMPLETE GRAPH CHRISTOPHER RH HANUSA AND THOMAS ZASLAVSKY Abstract We investigate the least common multiple of all subdeterminants,More information
Finite Sets. Theorem 5.1. Two non-empty finite sets have the same cardinality if and only if they are equivalent.
MATH 337 Cardinality Dr. Neal, WKU We now shall prove that the rational numbers are a countable set while R is uncountable. This result shows that there are two different magnitudes of infinity. But weMore information
U.C. Berkeley CS276: Cryptography Handout 0.1 Luca Trevisan January, 2009. Notes on Algebra
U.C. Berkeley CS276: Cryptography Handout 0.1 Luca Trevisan January, 2009 Notes on Algebra These notes contain as little theory as possible, and most results are stated without proof. Any introductoryMore information
ONLINE VERTEX COLORINGS OF RANDOM GRAPHS WITHOUT MONOCHROMATIC SUBGRAPHS MARTIN MARCINISZYN AND RETO SPÖHEL Abstract. Consider the following generalized notion of graph colorings: a vertex coloring ofMore information
The chromatic spectrum of mixed hypergraphs
The chromatic spectrum of mixed hypergraphs Tao Jiang, Dhruv Mubayi, Zsolt Tuza, Vitaly Voloshin, Douglas B. West March 30, 2003 Abstract A mixed hypergraph is a triple H = (X, C, D), where X is the vertexMore information
Cycles in a Graph Whose Lengths Differ by One or Two
Cycles in a Graph Whose Lengths Differ by One or Two J. A. Bondy 1 and A. Vince 2 1 LABORATOIRE DE MATHÉMATIQUES DISCRÉTES UNIVERSITÉ CLAUDE-BERNARD LYON 1 69622 VILLEURBANNE, FRANCE 2 DEPARTMENT OF MATHEMATICSMore information
Cycle transversals in bounded degree graphs
Electronic Notes in Discrete Mathematics 35 (2009) 189 195 www.elsevier.com/locate/endm Cycle transversals in bounded degree graphs M. Groshaus a,2,3 P. Hell b,3 S. Klein c,1,3 L. T. Nogueira d,1,3 F.More information
DETERMINANTS. b 2. x 2
DETERMINANTS 1 Systems of two equations in two unknowns A system of two equations in two unknowns has the form a 11 x 1 + a 12 x 2 = b 1 a 21 x 1 + a 22 x 2 = b 2 This can be written more concisely inMore information
Chapter 4, Arithmetic in F [x] Polynomial arithmetic and the division algorithm.
Chapter 4, Arithmetic in F [x] Polynomial arithmetic and the division algorithm. We begin by defining the ring of polynomials with coefficients in a ring R. After some preliminary results, we specializeMore information
SUBGROUPS OF CYCLIC GROUPS. 1. Introduction In a group G, we denote the (cyclic) group of powers of some g G by
SUBGROUPS OF CYCLIC GROUPS KEITH CONRAD 1. Introduction In a group G, we denote the (cyclic) group of powers of some g G by g = {g k : k Z}. If G = g, then G itself is cyclic, with g as a generator. ExamplesMore information
1 if 1 x 0 1 if 0 x 1
Chapter 3 Continuity In this chapter we begin by defining the fundamental notion of continuity for real valued functions of a single real variable. When trying to decide whether a given function is orMore information
ORIENTATIONS. Contents
ORIENTATIONS Contents 1. Generators for H n R n, R n p 1 1. Generators for H n R n, R n p We ended last time by constructing explicit generators for H n D n, S n 1 by using an explicit n-simplex whichMore information
3. Equivalence Relations. Discussion
3. EQUIVALENCE RELATIONS 33 3. Equivalence Relations 3.1. Definition of an Equivalence Relations. Definition 3.1.1. A relation R on a set A is an equivalence relation if and only if R is reflexive, symmetric,More information
Math 55: Discrete Mathematics
Math 55: Discrete Mathematics UC Berkeley, Fall 2011 Homework # 5, due Wednesday, February 22 5.1.4 Let P (n) be the statement that 1 3 + 2 3 + + n 3 = (n(n + 1)/2) 2 for the positive integer n. a) WhatMore information
RESULTANT AND DISCRIMINANT OF POLYNOMIALS SVANTE JANSON Abstract. This is a collection of classical results about resultants and discriminants for polynomials, compiled mainly for my own use. All resultsMore information
most 4 Mirka Miller 1,2, Guillermo Pineda-Villavicencio 3, The University of Newcastle Callaghan, NSW 2308, Australia University of West Bohemia
Complete catalogue of graphs of maimum degree 3 and defect at most 4 Mirka Miller 1,2, Guillermo Pineda-Villavicencio 3, 1 School of Electrical Engineering and Computer Science The University of NewcastleMore information
Chapter 7. Permutation Groups
Chapter 7 Permutation Groups () We started the study of groups by considering planar isometries In the previous chapter, we learnt that finite groups of planar isometries can only be cyclic or dihedralMore information
CHAPTER 2 American mathematician Paul Halmos (1916 2006), who in 1942 published the first modern linear algebra book. The title of Halmos s book was the same as the title of this chapter. Finite-DimensionalMore information
Minimum degree condition forcing complete graph immersion
Minimum degree condition forcing complete graph immersion Matt DeVos Department of Mathematics Simon Fraser University Burnaby, B.C. V5A 1S6 Jacob Fox Department of Mathematics MIT Cambridge, MA 02139More information
Lecture 6 Online and streaming algorithms for clustering
CSE 291: Unsupervised learning Spring 2008 Lecture 6 Online and streaming algorithms for clustering 6.1 On-line k-clustering To the extent that clustering takes place in the brain, it happens in an on-lineMore information


text:
Most antivirus programs identify Vkmusicdownloader.exe as malware—for instance Symantec identifies it as Trojan.Gen or Trojan.Gen.2, and Microsoft identifies it as Trojan:Win32/Radonskra.D.
The free file information forum can help you find out how to remove it. If you have additional information about this file, please leave a comment or a suggestion for other users.
Click to Run a Free Virus Scan for the Vkmusicdownloader.exe malware
The Application process contains no information about its author.
Description: Vkmusicdownloader.exe is not essential for Windows and will often cause problems. The Vkmusicdownloader.exe file is located in a subfolder of the user's profile folder.
Known file sizes on Windows 10/8/7/XP are 318,956 bytes (66% of all occurrences) or 319,468 bytes.
The software has no file description. The process starts when Windows starts (see Registry key: Run, MACHINE\Run). Vkmusicdownloader.exe is not a Windows core file. The program is not visible. Vkmusicdownloader.exe is able to monitor applications and record keyboard and mouse inputs. Therefore the technical security rating is 80% dangerous.
Recommended: Identify Vkmusicdownloader.exe related errors
If Vkmusicdownloader.exe is located in a subfolder of "C:\Program Files", the security rating is 74% dangerous. The file size is 269,312 bytes. There is no file information. The program is not visible. The program is loaded during the Windows boot process (see Registry key: Run, MACHINE\Run). The Vkmusicdownloader.exe file is not a Windows system file. Vkmusicdownloader.exe is able to monitor applications.
Important: You should check the Vkmusicdownloader.exe process on your PC to see if it is a threat. We recommend Security Task Manager for verifying your computer's security. This was one of the Top Download Picks of The Washington Post and PC World.
The following programs have also been shown useful for a deeper analysis: ASecurity Task Manager examines the active Vkmusicdownloader process on your computer and clearly tells you what it is doing. Malwarebytes' well-known Banti-malware tool tells you if the Vkmusicdownloader.exe on your computer displays annoying ads, slowing it down. This type of unwanted adware program is not considered by some antivirus software to be a virus and is therefore not marked for cleanup.
A clean and tidy computer is the key requirement for avoiding PC trouble. This means running a scan for malware, cleaning your hard drive using 1cleanmgr and 2sfc /scannow, 3uninstalling programs that you no longer need, checking for Autostart programs (using 4msconfig) and enabling Windows' 5Automatic Update. Always remember to perform periodic backups, or at least to set restore points.
Should you experience an actual problem, try to recall the last thing you did, or the last thing you installed before the problem appeared for the first time. Use the 6resmon command to identify the processes that are causing your problem. Even for serious problems, rather than reinstalling Windows, you are better off repairing of your installation or, for Windows 8 and later versions, executing the 7DISM.exe /Online /Cleanup-image /Restorehealth command. This allows you to repair the operating system without losing data.
scrybeupdater.exe mightymagoo32.exe pcpitstop-nitro.exe Vkmusicdownloader.exe blaero start orb.exe msys1.dll smbios.sys clvirtualdrive.sys lplatsvc.exe studentmain.exe onenoteim.exe [all]

subset: commoncrawl


text:
The Company
Southern Enterprises Ltd. is a registered Limited Company with its
headquarters at Amadinda House, Plot 13B Kampala Road. It started
operations in 1986 with a staff of 14 but has now expanded to a
total workforce of 100. It is a member of UGANDA FREIGHT FORWARDERS
ASSOCIATION with a valid Customs Agents License.
A Webnet Design 2010


text:
- Doctors
- Pennsylvania
- York
- Dentists
- Dr. George S. Agapis
You may also like
Dr. Timothy L. Wright
Ratings for Dr. George S. Agapis
Everyone is so friendly. I use to be a afraid to go to the dentist. Not anymore!
Have been going here for years. Before the sons joined. I am very pleased and would recommend them to anyone.
Dr. George is patient and treats me gently. I look forward going to the dentist every 6 months. The staff is great.
Clean, modern office. They open instruments in front of me which I like. The two doctors are friendly and honest. I have been going here for 3 years now and would never go anywhere else.
Dr. George is a great dentist. He takes his time to explain things to me and I never feel rushed. His staff is very friendly and treat me the same way. I am very scared if dental work but I have been a lot better ever since I switched to this location. His dental assistant Kristy takes your mind off of getting your cleaning and makes it enjoyable.
I am relatively new to the York area and needed to find a local dentist. With the recommendation from a co-worker, I scheduled an appointment for a check-up. I am a nervous patient, even for a cleaning, and the staff and Dr. Agapis made me feel comfortable from the start. The hygenist was so gentle and pleasant and Dr. Agapis answered all of my questions in a way that I could actually understand. I had to go back for a filling and then a crown and they were the easiest dental appointments I've ever had. I would definitely recommend this office to anyone even if you aren't scared of the dentist :-)
Very grumpy staff and dated appearance of facility. Does not have cheer or charm due to uninspired team. Too tense for a casual person like me. I would not recommend this office due to appearance and tension. Overheard staff discuss "low wages and cheap boss" Oh well... moving on!!!
I have been going to these dentists for several years. They are very friendly and knowledgable and best of all pain free. My husband had sedation dentistry with Dr. Agapis last month and didn't feel or remember a thing. He had several wisdom teeth removed and a root canal and felt great the next day. Everyone is great at the office. Thank You!!!
They are a money racket, they actually filled a cavity for me, and two days later I was in so much pain, come to find out I needed a root canal. Called them and they squeezed me in, and Dr Agapis one of the sons... started my root canal, well he did the WRONG ONE. He admited to it. I had to sit thru 2 root canals due to his mistake.
Hello, the office staff was so rude I had to call my congressman! No joke they lied put false charges on my account. I told them it was illegal and they laughed and hung up on me. I had to get my state representative Eugene DePasquelle involved before they stopped acting crazy. The office manager was the one who started the games, because I cancelled an appointment and she did not like it so said I would have to pay. I refused she got loud and started yelling. I was in shock. I can't remember her name but she has red hair. She would not let me speak to the dentist. I had to threaten to call him during off hours and tell what she was doing. She then began to act more professional. The Dr.s are great, the practice is beautiful. But the staff is a joke.
Dr. George S. Agapis's Credentials
Facility Affiliations
Accepting New Patients
Other Specialties
Areas of Expertise
Awards & Recognitions
Publications & Research
Insurance accepted by this Doctor
Top Hospitals in York, PA
Find a Doctor by Specialty
Featured News
You may also like
Dr. Timothy L. Wright
Top Dentists
#1 of 125
#2 of 125
#3 of 125
#4 of 125
#5 of 125


text:
Wondering what will freeze well. Grandkids and I are making caramel tartlettes. They have melted chocolate and caramel in the center and are topped with pecans. Also doing thumbprint cookies with the Hershey's kiss in the middle,some dipped pretzels,almond roca, and not sure what else. I'm sure the thumbprints will freeze OK but what about the Caramel.?. Will it be gooey again after it thaws?
Thanks for any help. Oh, one more, the Mexican Wedding Cookies.


text:
WILMINGTON, NC (WECT) – The third requirement of NC DOT's plan to reroute large trucks around the city of Wilmington attracted only a handful of people Monday night.
The first two phases of allowing trucks with twin trailers to take Interstate 140 around Wilmington and onto U.S. 74/76 included a traffic study showing the road can safely accommodate the trucks and a determination of public convenience of the trucks.
The state's Department of Transportation already found both requirements to have been met, leaving a public hearing as the final step of the process.
But that's where some folks questioned the department's work up until this point. Johnnie Henagan, President of the Sunset Park Neighborhood Association, asked DOT representatives when he'll have the details about the first two phases.
"We have this one opportunity," said Henagan. "We didn't get an opportunity to be in on the determination of whether this is feasible, necessary, or wanted."
Henegan's wife spoke out against the proposal as well, sharing her frustration with what she considered inadequate advertising for the public hearing.
Wilmington City Council member Laura Padgett said the city's Metropolitan Planning Organization initially supported the proposal. Padgett is the chair of the Wilmington MPO.
After a closer look at the information provided, Padgett asked for more information about the roads that already allow twin trailers in Wilmington. Most of the concerns expressed at the meeting involved acceptable twin trailer roads near the Port of Wilmington.
Those roads were approved in the early 1980s, according to DOT reps.
Anyone interested in adding a comment about the proposal has until July 23 to submit it.
Copyright 2013 WECT. All rights reserved.


text:
Just received my probes. They are exactly as illustrated on the pictures (15cm cable, 24cm from the coax plug to the tip of probe).
This is commercially OK but from a technical point of view, the cables are much too short. Please offer longer cab
Ordered two of these, in the hope of having two similar, usable digital probes for the DSO quad. Unfortunately the cable length is disappointingly small, around 10-15 cm maybe - this makes the probes almost useless, as I have to hold the DSO quad in my
Free shipping on your first order over $50 or more. Discounted items included!


text:
12 Oaks is an established master-planned community in Holly Springs, NC, featuring a variety of home styles from townhome to executive living. From your initial approach to the community with its impressive brick entrance to the award winning championship Nicklaus Designed golf course, resort-style pool, lighted tennis courts, playground and fitness center, you will feel like you're living on a vacation resort! There's truly something for everyone; from yoga and children's story time to ladies night and craft beer, the calendar is packed with fun choices for the entire family, all located inside 12 Oaks.
This stunning Wake County, golf course community has country charm with all of today's modern conveniences. Nestled in Southern Wake County, off of Highway 55, 12 Oaks is located in Holly Springs close to Cary, Apex, Fuquay–Varina and Raleigh. This community has easy access to all the North Carolina can offer! With its close proximity to highways, the Triangle Expressway(I-540) and US1, getting around town is a breeze! Jordan Lake, Harris Lake and Womble Park are nearby with plenty of outdoor activities. Enjoy all local conveniences of shopping and dining with Holly Springs Town Center, Crossroads Plaza, Cary Town Center, Beaver Creek Shopping Center and Downtown Raleigh, all within 20 minutes. Residents in 12 Oaks have a choice between Wake County School District, Magnet & Charter Schools as well as a variety of private schools.
Come home to a carefree life in either of the two collections offered by M/I Homes in 12 Oaks. These innovative designs truly match the way you live today. The Townhome Collection offers 3 bedroom and 2-1/2 baths. Some basement homesites and downstairs Owner's suites are available. Our ranch-style Villa Collection are designed with one-level living in mind. The Owner's suite and guest room are located on the main floor. These homes showcase extensive hardwood floors, granite counter tops, stainless appliances, tile backsplash, crown moldings on high ceiling and covered porches. And, the lawn maintenance is included, giving you more time to spend in this spectacular community.
M/I Homes in Raleigh offers the country's only 15 Year Transferrable Structural Warranty as well as building homes to our Whole Home standards. Each and every home M/I builds carries the Energy Star Certified. 12 Oaks also qualifies for a USDA loan with 100% financing! Be sure to ask our New Home Consultant for details. Whether you are a first time buyer, are looking to downsize or just need more space in your home, 12 Oaks has what you're looking for! Contact us today for more details.


text:
Young Victorian Couple 2 by Aquateen510Watch
©2013-2017 Aquateen510
Love in sight.
She looks like she's way taller than him. Or is it just the dress?
Maybe Their Names Are Victor And Victoria.
(Chuckle) They are so smitten with each other, it's adorable! I can imagine the girl being so in love with her boyfriend that she swoons under a tree and the boy drops down next to her and is partially encapsulated in her full skirts. As they play "footsie", they gently embrace and get lost in each other's arms. Beautifully done once again!
Egads! How does she move in that thing? Does she just avoid doorways?
Sometimes she avoids doorways despite that she has lots of petticoats to make her dress poofy instead of using a hoop.
Her dress is gonna eat him... @.@;;


text:
Space X's delayed cargo mission to ISS will launch March 30
Space X was the first private company to make commercial deliveries to the ISS carrying food, water, science gear and more. Space X has now made several successful deliveries to the ISS since its contract began. We mentioned a few days ago that the ISS had to fire its boosters and push itself into a slightly higher orbit to avoid space junk.


text:
Welcome to Mr. Jones' Grade 4 Class page. In this section of the site you'll be able to read about event in our class, access archived parent letters and homework and learn more about upcoming events.
Colin Jones is an experienced educator who spent his time working abroad in public and international schools in South Korea, Australia and England. He's taught a variety of grade levels from K-8 and has worked in school administration. Now he's very excited about having returned home to Canada and the opportunities that working at Kinuso School present.


text:
Princess MononokeDirector: Hayao Miyazaki
Cast: Yoji Matsuda, Yuriko Ishida, Yuko Tanaka
- Disney Movies
- Featured Anime
- Overview
- Editorial Reviews
- Product Details
- Special Features
- Related Subjects
- Cast & Crew
- Scene Index
- Menu
Princess Mononoke arrives on DVD in a widescreen anamorphic format (1.85:1 theatrical aspect ratio enhanced for 16 x 9 television) and these audio tracks: Japanese (Dolby Digital 5.1), English (Dolby Digital 5.1), and French (Dolby Digital 2.0), with English subtitles. The DVD is dual-layered with an astonishingly clear and crisp picture that really brings out the animated magic of the film. Sound quality is consistently good with particularly clear and bass-resonant music, particularly during the action scenes. Special features are limited to theatrical trailers and a "making of" featurette. A glossy insert in the cover of the plastic DVD case lists the chapter index.
Editorial Reviews
Product Details
- Release Date:
- 12/19/2000
- 0717951007414
- Original Release:
- 1997
- Rating:
- Source:
- Walt Disney Video
- Region Code:
- 1
- Presentation:
- [Wide Screen]
- Sound:
- [Dolby Digital 5.1 Surround]
- Time:
- 2:14:00
- Sales rank:
- 465
Special Features
Cast & Crew
|Yoji Matsuda
|Yuriko Ishida
|Yuko Tanaka
|Lady Eboshi
|Kaoru Kobayashi
|Masahiko Nishimura
|Billy Crudup
|Ashitaka [English Version]
|Claire Danes
|San [English Version]
|Billy Bob Thornton
|Jiko [English Version]
|Minnie Driver
|Lady Eboshi [English Version]
|Gillian Anderson
|Moro [English Version]
Technical Credits
|Hayao Miyazaki
Scene Index
0. chapter selection
1. Opening Credits [:13]
2. Prince Ashitaka's Fate [:54]
3. The Arm Of A Demon [:54]
4. A New Friend [:14]
5. The Wolf Gods Attack [:08]
6. First Sight Of Princess Mononoke [:08]
7. The Tree Spirits [6:12]
8. A Magical Place [:46]
9. Returning Home To Iron Town [4:09]
10. The Story Of The Demon Boar [1:44]
11. The Inner Workings Of Iron Town [1:34]
12. San Invades Iron Town [3:01]
13. The Ape Tribe [2:24]
14. The Great Spirit [2:01]
15. The Boars Want A Battle [:31]
16. Fighting For Iron [1:51]
17. A Warning From The Wolf God [3:12]
18. A Trap Is Set [3:00]
19. Iron Town Is Under Attack [1:05]
20. Many Lives Lost [3:29]
21. Becoming A Demon [3:25]
22. A God, A Demon, And A Spirit [4:27]
23. The Great Spirit's Head [7:41]
24. Rejuvenating The Forest [2:11]
25. End Credits [3:48]
set up
Spoken Language
bonus materials
Theatrical Trailer
Customer Reviews
Average Review:
Most Helpful Customer Reviews
See all customer reviews
In the running for the title of Miyazaki's greatest film are Spirited Away and the slightly lesser known Princess Mononoke. Though, odds are that if you've heard of one, you've heard of the other. Although Princess Mononoke is less subtle and maybe less nuanced, there's a definite larger emphasis on character development and interplay that make it just as interesting of a film, but for different reasons. There's no reason to choose one over the other; both are necessary watching for anime fans or newcomers. Oh, and the soundtrack is incredible.
This is the first Miyazaki movie I ever saw. I remember thinking it was the coolest thing ever. I especially remember the decapitation scene at the beginning of the movie changing my expectations for the film. This is a great story about the balance between man and nature. The animation is amazing and intense. A must have for Miyazaki fans.
This movie had great meaning behind, which makes this movie so enjoyable.
I can watch it over an over again. Different from american animation in the aspect of a slightly darker plot and ending. I have only ever watched this movie in Japanese to practice so I don't know what the English version is like, but I love the Japanese one.
Family entertaining. Excellent Movie!
This is one of my favorite animes next to Inuyasha and Full Metal Alchemist. This is the story about a man who is cursed by a demon and sets out to rid the curse before it consumes him. Along way the way he meets the legendary title character and other faces along the way thus in the middle of a long hard conflict between the princess of the forest and the villagers below.
I have watched this movie again and again, and it never ceases to amaze me. Many a many times it has awed me into silence. By the end, it seems you were not watching a movie but living it instead from the eyes of a bystander, no different from the characters. It is, without a doubt, animated heaven. With realistic imagery, that is so detailed it is near the impossible that this is fake. That all this came together by a brilliant crew and a unique idea. It was a vision, a vision that was made real. A vision that has inspired many and enchanted the rest. With a sensational plot and out-of-this-world graphics, Princess Mononoke is total bliss, from start to finish.
One word: stunning. This movie is so many different kinds of amazing. The storyline is amazing, the characters are amazing, the drawing is amazing, the animation is amazing, the...need I go on? Basically, this is hands-down one of the best movies I have ever seen. I was blown away. BUY THIS. Trust me, you won't regret it.
Princess Mononoke is an enjoyable anime film that involves how a young boy's life is changed once a negative spirit inhabits a large boor and creates chaos in his home village. The young boy named Ashitaka is left with a situation that endangers his life and he ends up crossing paths with a perplexing young woman named San who enchants him with her beauty and who was raised by wolves. Both San and Ashitake end up seeing a lot, such as a forest spirit who has the gift of bringing great healing and saving a living being from dying if the spirit sees that they are meant to live. I'm fortunate to have first watched Princess Mononoke with my husband when we were living in the Jacksonville Florida area (through the U.S. navy).
Great Great Great Movie. I've watched it about 20 times and it never gets old. A must have! =]
If you want to see a movie that keeps you into it the WHOLE WAY THROUGH, then I highly recomend Princess Mononoke. This 5 star rated anime movie is the best ive ever seen!! Princess Mononoke is about a young warrior that fights a demon, so therefore, he is cursed with a twisted scar on his right arm where the demon touched him. He gets banished from his village because of the scar that is adventually supposed to spread throughout his whole body and destroy him. He heads towards the west and soon meets San-the wolf girl who hates all humans that destroy the forest. But after she meets the warrior, she helps him try to save the Forest Spirit-the most important god in all the forest that gives life and death. To find out the rest... watch this amazing, mythical movie.


text:
Advance 6076; ca. 1952; View 1, Dress with Contrast Cummerbund: Bolero with Contrast Collar - Optional Lining. View 2, Dress with Unlined Short-sleeve Bolero - Contrast Cummerbund.
Links to reviews/blog postsEdit
Add a photo to the gallery by clicking the "modify" button below.
[insert your username, and make sure your preferences allow for people to contact you via e-mail. Do not list your email address here!]


text:
You're about to spend a lot of money, and the thought of it probably makes you feel nauseous. You want to own a spankin' new gaming computer, but the idea surrounds you in clouds of options and alternatives. Making a purchase of a gaming computer is a daunting task. This is one task that you need to take careful thought to in order to get the most bang for your buck. This decision is also one that you will need to consider a whole host of options for as different options create different performance results. If done right, if will provide you with an excellent PC that will play all of your games just the way you want to see them look.
This guide is going to help you look for a gaming computer that will give you great gameplay and performance. It will also give you an idea of what exactly to look for when it comes to the parts and components. Finally, you will get to know some of the great gaming computer manufacturers so to head you in the right direction when it comes to your purchase without getting ripped off.
The following are the most important computer parts you will need to take into consideration
Video Card
CPU (processor)
Power Supply
RAM (memory)
The Video Card
A video card is the part of the computer that processes your game's 3D graphics and is the most important part of your game's performance. Getting a good video card is absolutely essential for a good gaming computer. Without this, your gaming computer is only a regular computer. The best advice for your gaming computer is to not skimp on the video card.
In choosing a video card there are two computers which hold on to the entire market – Nvidia and ATI (owned by AMD). Nvidia's consumer end brand is the Nvidia GeForce. ATI commands the Radeon HD line of video cards. Although, these two companies offer great options for gaming, there are few differences in performance when you buy a gaming level model (we'll get to good models soon). In my personal opinion Nvidia cards have an edge because they come with a technology called PhsyX that adds more realistic effects to many games which are optimized for it. Some PhsyX effects include life-like clothing and flags, exploding particles and more. PhsyX will only work with games that use PhsyX and only work on a video card build for it from Nvidia.
Now to the models. When searching for a model you need to look at the model numbers. The first number is the model line and the numbers after give you the exact model. For instance, Nvidia's 400 series includes the model 450, 460, 470 and 480. Generally, the higher the exact model number, the better the performance you will see from it.
What model to get? We recommend Nvidia so we'll give you the best of their cards
GTX 460 or better (GTX 460, GTX 460 2Win, GTX 470, GTX 480)
GTX 550Ti or better (GTX 550Ti, GTX 560Ti, GTX 570, GTX 580, GTX 590)
The CPU
The CPU isn't quite as important to gaming as the video card but it is still one of the most important as the speed of your computer is based on the CPU. Currently there are two companies which dominate the market – Intel and AMD. We recommend AMD as they offer the best bang for your buck. Also, Intel isn't favored by most gamers because you pay extra to get a technology called hyper-threading which isn't used in PC games.
The latest trend in the CPU is multi cores. These are important and you should try and get the most cores possible since more cores generally mean better speed and performance. We highly suggest that you get AT LEAST 4 cores (quad core) since many games are optimized for quad core cpu's.
AMD offers two main model lines for CPU's – Athlon II and Phenom II. The Phenom II is preferred for gaming and tend to have better performance than the Athlon II. Furthermore, the Phenom II Black Edition models are even better.
Random Access Memory has nothing to do with how much space you can have on your computer, but that isn't important. What is important is that there are different types of memory. The latest type of RAM is DDR3. Every new computer (gaming or not) should include DDR3.
The most important thing about memory is amount and NOT speed. There is nearly no performance change between 1333MHz and 2000MHz, but there is a HUGE difference between 2GB and 4GB. We recommend to have 4GB and 8GB if you want to 'future-proof'.
Another aspect to RAM is Cas Latency. This is not as important as the amount of RAM, but it does matter more than speed. We recommend a Latency of 9 or LOWER.
The Power Supply
This is a HUGE, HUGE, HUGE, HUGE mistake people make. Power Supplies are the things that take the power from the plug in the wall to all the components in your computer. Power Supplies don't really matter much in your gaming performance; however, they are extremely important.
Power Supplies are measured in wattage where higher amounts provide more power. It is absolutely vital to get a high powered power supply. We recommend a 550 to 700 watt power supply for a gaming computer with a the video cards we listed above. For the GTX 480, GTX 580, and GTX 590 a 650 watt or greater power supply is needed.
Now to the mistakes people make.
Weak Power supplies – A power supply that is too weak and doesn't provide enough power can destroy or permanently damage vital components by having them operate without enough power.
Cheap Brands – The price range for a 550 watt power supply can range from $20 to $100. Sure the $20 supply sounds like a convincing deal as it offers 550 watts, but these power supplies break down easily and VERY often only last 8 or 9 months. It they die while the computer is on or slowly lose efficiency, they can damage components. The best brands out there are Corsair and Ultra. We recommend paying the extra 20 or 30 bucks them. You computer will thank you.
Best Prices
Shop around…longer than you should. You can find an excellent PC but you really must be patient. Don't make a bad purchase because you didn't want to wait.
Where To Avoid
Ebay- Although there are plenty of great sellers on ebay, there are also plenty of bad sellers. If you really want to purchase from eBay, make sure the seller is reputable and read all the negative feedback.
Dell- The computer company may sell plenty of great consumer computers, but they simply don't have a strong performance computer or product line for gamers.
Alienware- Now owned by Dell, Alienware is a WAY overpriced extension of Dell computers.