Percolation in Voronoi tilings

We consider a percolation process on a random tiling of ℝ^d into Voronoi cells based on points of a realization of a Poisson process. We prove the existence of a phase transition as the proportion p of open cells is varied and provide estimates for the critical probability p_c. Specifically, we prove that for large d, 2^−d(9d log d)⁻¹ ≤ p_c(d) ≤ C2^−d log d. © 2004 Wiley Periodicals, Inc. Random Struct. Alg., 2005     

Critical percolation on random regular graphs

The behavior of the random graph G(n,p) around the critical probability p_c = is well understood. When p = (1 + O(n^1/3))p_c the components are roughly of size n^2/3 and converge, when scaled by n^?2/3, to excursion lengths of a Brownian motion with parabolic drift. In particular, in this regime, they are not concentrated. When p = (1 ‐ ?(n))p_c with ?(n)n^1/3 →∞ (the subcritical regime) the largest component is concentrated around 2?^?2 log(?³n). When p = (1 + ?(n))p_c with ?(n)n^1/3 →∞ (the supercritical regime), the largest component is concentrated around 2?n and a duality principle holds: other component sizes are distributed as in the subcritical regime. Itai Benjamini asked whether the same phenomenon occurs in a random d‐regular graph. Some results in this direction were obtained by (Pittel, Ann probab 36 (2008) 1359–1389). In this work, we give a complete affirmative answer, showing that the same limiting behavior (with suitable d dependent factors in the non‐critical regimes) extends to random d‐regular graphs. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2010     

Critical points for spread-out self-avoiding walk,percolation and the contact process above the upper critical dimensions

We consider self-avoiding walk and percolation in ^d, oriented percolation in ^d×₊, and the contact process in ^d, with p D(·) being the coupling function whose range is proportional to L. For percolation, for example, each bond is independently occupied with probability p D(y–x). The above models are known to exhibit a phase transition when the parameter p varies around a model-dependent critical point p_c. We investigate the value of p_c when d>6 for percolation and d>4 for the other models, and L1. We prove in a unified way that p_c=1+C(D)+O(L^–2d), where the universal term 1 is the mean-field critical value, and the model-dependent term C(D)=O(L^–d) is written explicitly in terms of the random walk transition probability D. We also use this result to prove that p_c=1+cL^–d+O(L^–d–1), where c is a model-dependent constant. Our proof is based on the lace expansion for each of these models.     

Energy of Flows on Percolation Clusters

It is well known for which gauge functions H there exists a flow in Z ^d with finite H energy. In this paper we discuss the robustness under random thinning of edges of the existence of such flows. Instead of Z ^d we let our (random) graph cal C cal (Z ^d,p) be the graph obtained from Z ^d by removing edges with probability 1–p independently on all edges. Grimmett, Kesten, and Zhang (1993) showed that for d3,p>p _c(Z ^d), simple random walk on cal C cal (Z ^d,p) is a.s. transient. Their result is equivalent to the existence of a nonzero flow f on the infinite cluster such that the x ² energy _e f(e)² is finite. Levin and Peres (1998) sharpened this result, and showed that if d3 and p>p _c(Z ^d), then cal C cal (Z ^d,p) supports a nonzero flow f such that the x ^q energy is finite for all q>d/(d–1). However, for general gauge functions, there is a gap between the existence of flows with finite energy which results from the work of Levin and Peres and the known results on flows for Z ^d. In this paper we close the gap by showing that if d3 and Z ^d supports a flow of finite H energy then the infinite percolation cluster on Z ^d also support flows of finite H energy. This disproves a conjecture of Levin and Peres.     

On the geometry of random Cantor sets and fractal percolation

Random Cantor sets are constructions which generalize the classical Cantor set, middle third deletion being replaced by a random substitution in an arbitrary number of dimensions. Two results are presented here. (a) We establish a necessary and sufficient condition for the projection of ad-dimensional random Cantor set in [0,1]^d onto ane-dimensional coordinate subspace to contain ane-dimensional ball with positive probability. The same condition applies to the event that the projection is the entiree-dimensional unit cube [0,1] ^e . This answers a question of Dekking and Meester,⁽⁹⁾ (b) The special case of fractal percolation arises when the substitution is as follows: The cube [0,1] ^d is divided intoM ^d subcubes of side-lengthM ^–, and each such cube is retained with probabilityp independently of all other subcubes. We show that the critical valuep _c(M, d) ofp, marking the existence of crossings of [0,1] ^d contained in the limit set, satisfiesp _c(M, d)p _c(d) asM, wherep _c(d) is the critical probability of site percolation on a latticeL ^d obtained by adding certain edges to the hypercubic lattice ^d . This result generalizes in an unexpected way a finding of Chayes and Chayes,⁽⁴⁾ who studied the special case whend=2.     

Point sets with distinct distances

For positive integersd andn letf _d (n) denote the maximum cardinality of a subset of then ^d -gird {1,2,...,n} ^d with distinct mutual euclidean distances. Improving earlier results of Erds and Guy, it will be shown thatf ₂ (n)c·n ^2/3 and, ford3, thatf _d (n)c _d ·n ^2/3 ·(lnn)^1/3, wherec, c _d >0 are constants. Also improvements of lower bounds of Erds and Alon on the size of Sidon-sets in {1²,22²,...,n ²} are given.Furthermore, it will be proven that any set ofn points in the plane contains a subset with distinct mutual distances of sizec ₁·n ^1/4, and for point sets in genral position, i.e. no three points on a line, of sizec ₂·n ^1/3 with constantsc ₁,c ₂>0. To do so, it will be shown that forn points in ² with distinct distancesd ₁,d ₂,...,d _t , whered _i has multiplicitym _i , one has _i=1 ^t m _i ² c·n _3.25 for a positive constantc. If then points are in general position, then we prove _i=1 ^t m _i ² c·n ₃ for a positive constantc and this bound is tight.Moreover, we give an efficient sequential algorithm for finding a subset of a given set with the desired properties, for example with distinct distances, of size as guaranteed by the probabilistic method under a more general setting.     

On (p a , p b , p a , p a-b )-Relative Difference Sets

This paper provides new exponent and rank conditions for the existence of abelian relative (p ^a,p ^b,p ^a,p ^a–b)-difference sets. It is also shown that no splitting relative (2^2c,2^d,2^2c,2^2c–d)-difference set exists if d > c and the forbidden subgroup is abelian. Furthermore, abelian relative (16, 4, 16, 4)-difference sets are studied in detail; in particular, it is shown that a relative (16, 4, 16, 4)-difference set in an abelian group G Z₈ × Z₄ × Z₂ exists if and only if exp(G) 4 or G = Z₈ × (Z₂)³ with N Z₂ × Z₂.     

Proof of Oppenheim's area inequalities for triangles and quadrilaterals

Leta ₁,b ₁,c ₁,A ₁ anda ₂,b ₂,c ₂,A ₂ be the sides and areas of two triangles. Ifa=(a ₁ ^p +a ₂ ^p )^1/p ,b=(b ₁ ^p +b ₂ ^p )^1/p ,c=(c ₁ ^p +c ₂ ^p )^1/p , and 1p4, thena, b, c are the sides of a triangle and its area satisfiesA ^p/2A ₁ ^p/2 +A ₂ ^p/2 . If obtuse triangles are excluded,p>4 is allowed. For convex cyclic quadrilaterals, a similar inequality holds. Also, leta, b, c, A be the sides and area of an acute or right triangle. Iff(x) satisfies certain conditions,f(a),f(b),f(c) are the sides of a triangle having areaA _f, which satisfies (4A _f/3)^1/2f((4A/3)^1/2).     

On a conjecture on maximal planar sequences

Let d1 d2 dp denote the nonincreasing sequence d₁, …, d₁, d₂, …, d₂, …, d_p, …, d_p, where the term d_i appears k_i times (i = 1, 2, …, p). In this work the author proves that the maximal 2-sequences: 7³6¹5¹⁵, 7⁵6¹5¹⁷, 7⁷6¹5¹⁹ are planar graphical, in contrast to a conjecture by Schmeichel and Hakimi.     

Comparison of fractal measures

In this paper, the relationship between the s-dimensional Hausdorff measures and the g-measures in Rd is discussed, where g is a gauge function which is equivalent to ts and 0 < s≤d. It shows that if s=d, then Hg = c1Hd, Cg = c2Cd and Pg = c3Pd on Rd, where constants c1, c2 and c3 are determined by where Wg, Cg and Pg are the g-Hausdorff, g-central Hausdorff and g-packing measures on Rd respectively. In the case 0相似文献   

Об отделимости множе ств гиперплоскостью вL p

LetA and be two arbitrary sets in the real spaceL _p, 1p<. Sufficient conditions are obtained for their strict separability by a hyperplane, in terms of the distance between the setsd(A,B) _p=inf{x-y_p,xA,yB} and their diametersd(A) _p, d(B)_p, whered(A) _p=sup{x-y_p; x,yA}. In particular, it is proved that if in an infinite-demensional spaceL _p we haved ^r(A,B)_p>2^–r+1(d^r(A)_p+d^r(B)_p), r=min{p, p(p–1)^–1}, then there is a hyperplane which separatesA andB. On the other hand, the conditiond ^r(A,B)_p=2^–r+1(d^r(A)_p+d^r(B)_p) does not guarantee strict separability. Earlier these results where obtained by V. L. Dol'nikov for the case of Euclidean spaces.     

Linear series computing the Clifford index of a projective curve

For a (smooth irreducible) curveC of genus g and Clifford indexc>2 with a linear seriesg _d ^r computing c (so ) it is well known thatc + 2 ≤d ≤2 (c + 2), and if then 2c + 1 ≤g ≤ 2c + 4 unlessd = 2c + 4 in which caseg = 2c + 5. Let c ≥ 0 andg be integers. If 2c + 1 ≤g ≤2c + 4 we prove that for any integerd <g such thatd ≡c mod 2 andc + 2 ≤d < 2(c + 2) there exists a curve of genus g and Clifford index c with a g_d ^r computing c. Ford ≥c + 6 (i.e.r ≥ 3) we construct this curve on a surface of degree 2r-2 in ℙ^r, and ford ≥c + 8 (i.e.r ≥ 4) we show that such a curve cannot be found on a surface in ℙ^r of smaller degree. In fact, if g_d ^r computes the Clifford index c of C such thatc + 8 ≤d ≤ 2c + 3 then the birational morphism defined by this series cannot map C onto a (maybe, singular) curve contained in a surface of degree at most 2r-3 in ℙ^r.     

On the degree of commutativity of p ‐groups of maximal class

Let G be a p ‐group of maximal class of order p^m , p ≠ 2, and c (G) the degree of commutativity of G. Let c₀ be the nonnegative residue of c modulo p – 1. In this paper, by using only Lie algebra techniques, we prove that 2c ≥ m – 2p + c 0 + 1. Also, we give examples of Lie algebras satisfying the following equalities: In addition, there exist examples of p ‐groups of maximal class satisfying 2c = m – 2p + c₀ + 3 for each c₀ ∈ [2, p – 2] (see [6, Theorem 4.5]). (© 2008 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Geometric methods in the study of irregularities of distribution

Let be a signed measure on E ^d with E ^d =0 and ¦¦E^d<. DefineD _s() as sup ¦H¦ whereH is an open halfspace. Using integral and metric geometric techniques results are proved which imply theorems such as the following.Theorem A. Let be supported by a finite pointsetp _i. ThenD _s()>c _d(₁/ ₂)^1/2{ _{i(p i})²}^1/2 where ₁ is the minimum distance between two distinctp _i, and ₂ is the maximum distance. The numberc _d is an absolute dimensional constant. (The number .05 can be chosen forc ₂ in Theorem A.)Theorem B. LetD be a disk of unit area in the planeE ², andp ₁,p ₂,...,p _n be a set of points lying inD. If m if the usual area measure restricted toD, while nP _i=1/n defines an atomic measure _n, then independently of _n,nD _s(m – _n) .0335n ^1/4. Theorem B gives an improved solution to the Roth disk segment problem as described by Beck and Chen. Recent work by Beck shows thatnD _s(m – _n)cn ^1/4(logn)^–7/2.     

Mean-field critical behaviour for correlation length for percolation in high dimensions

Summary Extending the method of [27], we prove that the corrlation length of independent bond percolation models exhibits mean-field type critical behaviour (i.e. (p(p _c –p)^–1/2 aspp _c ) in two situations: i) for nearest-neighbour independent bond percolation models on ad-dimensional hypercubic lattice ^d , withd sufficiently large, and ii) for a class of spread-out independent bond percolation models, which are believed to belong to the same universality class as the nearest-neighbour model, in more than six dimensions. The proof is based on, and extends, a method developed in [27], where it was used to prove the triangle condition and hence mean-field behaviour of the critical exponents , , , and ₂ for the above two cases.     

Many triangulated spheres

Lets(d, n) be the number of triangulations withn labeled vertices ofS ^d–1, the (d–1)-dimensional sphere. We extend a construction of Billera and Lee to obtain a large family of triangulated spheres. Our construction shows that logs(d, n)C ₁(d)n ^[(d–1)/2], while the known upper bound is logs(d, n)C ₂(d)n ^[d/2] logn.Letc(d, n) be the number of combinatorial types of simpliciald-polytopes withn labeled vertices. (Clearly,c(d, n)s(d, n).) Goodman and Pollack have recently proved the upper bound: logc(d, n)d(d+1)n logn. Combining this upper bound forc(d, n) with our lower bounds fors(d, n), we obtain, for everyd5, that lim _n(c(d, n)/s(d, n))=0. The cased=4 is left open. (Steinitz's fundamental theorem asserts thats(3,n)=c(3,n), for everyn.) We also prove that, for everyb4, lim _d(c(d, d+b)/s(d, d+b))=0. (Mani proved thats(d, d+3)=c(d, d+3), for everyd.)Lets(n) be the number of triangulated spheres withn labeled vertices. We prove that logs(n)=2^{0.69424n(1+o(1))}. The same asymptotic formula describes the number of triangulated manifolds withn labeled vertices.Research done, in part, while the author visited the mathematics research center at AT&T Bell Laboratories.     

Behavior of the constant in Korenblum's maximum principle

Let A^p (??) (p ≥ 1) be the Bergman space over the open unit disk ?? in the complex plane. Korenblum's maximum principle states that there is an absolute constant c ∈ (0, 1) (may depend on p), such that whenever |f (z)| ≤ |g (z)| (f, g ∈ A^p (??)) in the annulus c < |z | < 1, then ∥f ≤ ∥g ∥. For p ≥ 1, let c_p be the largest value of c for which Korenblum's maximum principle holds. In this note we prove that c_p → 1 as p → ∞. Thus we give a positive answer of a question of Hinkkanen. (© 2008 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

On critical Fujita exponents for heat equations with nonlinear flux conditions on the boundary

We consider nonnegative solutions of initial-boundary value problems for parabolic equationsu _t=u_xx, u_t=(u^m)_xxand (m>1) forx>0,t>0 with nonlinear boundary conditions−u _x=u^p,−(u ^m)_x=u^pand forx=0,t>0, wherep>0. The initial function is assumed to be bounded, smooth and to have, in the latter two cases, compact support. We prove that for each problem there exist positive critical valuesp ₀,p_c(withp ₀<p_c)such that forp∃(0,p ₀],all solutions are global while forp∃(p₀,p_c] any solutionu≢0 blows up in a finite time and forp>p _csmall data solutions exist globally in time while large data solutions are nonglobal. We havep _c=2,p _c=m+1 andp _c=2m for each problem, whilep ₀=1,p ₀=1/2(m+1) andp ₀=2m/(m+1) respectively. This work was done during visits of the first author to Iowa State University and the Institute for Mathematics and its Applications at the University of Minnesota. The second author was supported in part by NSF Grant DMS-9102210.     

Properly colored subgraphs and rainbow subgraphs in edge‐colorings with local constraints

We consider a canonical Ramsey type problem. An edge‐coloring of a graph is called m‐good if each color appears at most m times at each vertex. Fixing a graph G and a positive integer m, let f(m, G) denote the smallest n such that every m‐good edge‐coloring of K_n yields a properly edge‐colored copy of G, and let g(m, G) denote the smallest n such that every m‐good edge‐coloring of K_n yields a rainbow copy of G. We give bounds on f(m, G) and g(m, G). For complete graphs G = K_t, we have c₁mt²/ln t ≤ f(m, K_t) ≤ c₂mt², and cmt³/ln t ≤ g(m, K_t) ≤ cmt³/ln t, where c₁, c₂, c, c are absolute constants. We also give bounds on f(m, G) and g(m, G) for general graphs G in terms of degrees in G. In particular, we show that for fixed m and d, and all sufficiently large n compared to m and d, f(m, G) = n for all graphs G with n vertices and maximum degree at most d. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 2003     

Elementarteiler von Inzidenzmatrizen symmetrischer Blockpläne

By a study of the integral code generated by the rows of the incidence matrix and its extention the following results are obtained: Let d ₁,...,d _V(d ₁|d ₂,d ₂|d ₃...) be the elementary divisors of the incidence matrix of a symmetric (v,n+, ) design. Then d _v=(n+)n/g.c.d. (n, ). Moreover, if p is a prime such that p|n, p and if x _p denotes the p-part of x, then (d _id_v+2–i) _p =n _p for 2iv. For projective planes it can be shown that d ₁=···=d _3n–2=1, hence and . The paper also contains some results about elementary divisors of incidence matrices G satisfying the condition G ^tG=nI+ J.

---

Elementarteiler von Inzidenzmatrizen symmetrischer Blockpläne