Competing first passage percolation on random graphs with finite variance degrees

We study the growth of two competing infection types on graphs generated by the configuration model with a given degree sequence. Starting from two vertices chosen uniformly at random, the infection types spread via the edges in the graph in that an uninfected vertex becomes type 1 (2) infected at rate λ₁ (λ₂) times the number of nearest neighbors of type 1 (2). Assuming (essentially) that the degree of a randomly chosen vertex has finite second moment, we show that if λ₁ = λ₂, then the fraction of vertices that are ultimately infected by type 1 converges to a continuous random variable V ∈ (0,1), as the number of vertices tends to infinity. Both infection types hence occupy a positive (random) fraction of the vertices. If λ₁ ≠ λ₂, on the other hand, then the type with the larger intensity occupies all but a vanishing fraction of the vertices. Our results apply also to a uniformly chosen simple graph with the given degree sequence.     

Inequalities for Stationary Poisson Cuboid Processes

A cuboid is a rectangular parallelepipedon. By the notion “stationary Poisson cuboid process” we understand a stationary Poisson hyperplane process which divides the Euclidean space ?^d into cuboids. It is equivalent to speak of a stationary Poisson cuboid tessellation. The distributions of volume and total edge length of the typical cuboid and the origin-cuboid of a stationary Poisson cuboid process are considered. It is shown that these distributions become minimal, in the sense of a specific order relation, in the case of quasi-isotropy. A possible connection to a more general problem, treated in [6], is also discussed.     

Phase transition of the minimum degree random multigraph process

We study the phase transition of the minimum degree multigraph process. We prove that for a constant h_g ≈︁ 0.8607, with probability tending to 1 as n → ∞, the graph consists of small components on O(log n) vertices when the number of edges of a graph generated so far is smaller than h_gn, the largest component has order roughly n^2/3 when the number of edges added is exactly h_gn, and the graph consists of one giant component on Θ(n) vertices and small components on O(log n) vertices when the number of edges added is larger than h_gn. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2007     

Slow mixing of Glauber dynamics for the hard‐core model on regular bipartite graphs

Let ∑ = (V,E) be a finite, d‐regular bipartite graph. For any λ > 0 let π_λ be the probability measure on the independent sets of ∑ in which the set I is chosen with probability proportional to λ^|I| (π_λ is the hard‐core measure with activity λ on ∑). We study the Glauber dynamics, or single‐site update Markov chain, whose stationary distribution is π_λ. We show that when λ is large enough (as a function of d and the expansion of subsets of single‐parity of V) then the convergence to stationarity is exponentially slow in |V(∑)|. In particular, if ∑ is the d‐dimensional hypercube {0,1}^d we show that for values of λ tending to 0 as d grows, the convergence to stationarity is exponentially slow in the volume of the cube. The proof combines a conductance argument with combinatorial enumeration methods. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

Berry–Esseen bounds and Cramér-type large deviations for the volume distribution of Poisson cylinder processes

A stationary Poisson cylinder process Π _cyl ^(d,k) is composed of a stationary Poisson process of k-flats in ℝ ^d that are dilated by i.i.d. random compact cylinder bases taken from the corresponding orthogonal complement. We study the accuracy of normal approximation of the d-volume V _ϱ ^(d,k) of the union set of Π _cyl ^(d,k) that covers ϱW as the scaling factor ϱ becomes large. Here W is some fixed compact star-shaped set containing the origin as an inner point. We give lower and upper bounds of the variance of V _ϱ ^(d,k) that exhibit long-range dependence within the union set of cylinders. Our main results are sharp estimates of the higher-order cumulants of V _ϱ ^(d,k) under the assumption that the (d − k)-volume of the typical cylinder base possesses a finite exponential moment. These estimates enable us to apply the celebrated “Lemma on large deviations” of Statulevičius.     

How good can polynomial interpolation on the sphere be?

This paper explores the quality of polynomial interpolation approximations over the sphere S ^r−1⊂R ^r in the uniform norm, principally for r=3. Reimer [17] has shown there exist fundamental systems for which the norm ‖Λ _n ‖ of the interpolation operator Λ _n , considered as a map from C(S ^r−1) to C(S ^r−1), is bounded by d _n , where d _n is the dimension of the space of all spherical polynomials of degree at most n. Another bound is d _n ^1/2(λ_avg/λ_min)^1/2, where λ_avg and λ_min are the average and minimum eigenvalues of a matrix G determined by the fundamental system of interpolation points. For r=3 these bounds are (n+1)² and (n+1)(λ_avg/λ_min)^1/2, respectively. In a different direction, recent work by Sloan and Womersley [24] has shown that for r=3 and under a mild regularity assumption, the norm of the hyperinterpolation operator (which needs more point values than interpolation) is bounded by O(n ^1/2), which is optimal among all linear projections. How much can the gap between interpolation and hyperinterpolation be closed?

For interpolation the quality of the polynomial interpolant is critically dependent on the choice of interpolation points. Empirical evidence in this paper suggests that for points obtained by maximizing λ_min, the growth in ‖Λ _n ‖ is approximately n+1 for n<30. This choice of points also has the effect of reducing the condition number of the linear system to be solved for the interpolation weights. Choosing the points to minimize the norm directly produces fundamental systems for which the norm grows approximately as 0.7n+1.8 for n<30. On the other hand, ‘minimum energy points’, obtained by minimizing the potential energy of a set of (n+1)² points on S ², turn out empirically to be very bad as interpolation points.

This paper also presents numerical results on uniform errors for approximating a set of test functions, by both interpolation and hyperinterpolation, as well as by non-polynomial interpolation with certain global basis functions.

     

The Increment Ratio statistic under deterministic trends

The Increment Ratio (IR) statistic (see (1.1) below) was introduced in Surgailis et al. [16]. The IR statistic can be used for testing nonparametric hypotheses for d-integrated (−1/2 < d < 5/4) behavior of time series, including short memory (d = 0), (stationary) long-memory (0 < d < 1/2), and unit roots (d = 1). For stationary/stationary increment Gaussian observations, in [16], a rate of decay of the bias of the IR statistic and a central limit theorem are obtained. In this paper, we study the asymptotic distribution of the IR statistic under the model X _t = X _t⁰ + g _N(t) (t = 1, …, N), where X _t⁰ is a stationary/stationary increment Gaussian process as in [16], and g _N(t) is a slowly varying deterministic trend. In particular, we obtain sufficient conditions on X _t⁰ and g _N(t) under which the IR test has the same asymptotic confidence intervals as in the absence of the trend. We also discuss the asymptotic distribution of the IR statistic under change-points in mean and scale parameters. Partially supported by the bilateral France-Lithuania scientific project Gilibert and Lithuanian State Science and Studies Foundation, grant No. T-25/08.     

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     

Cycles with a given number of vertices from each partite set in regular multipartite tournaments

If x is a vertex of a digraph D, then we denote by d ⁺(x) and d ⁻(x) the outdegree and the indegree of x, respectively. A digraph D is called regular, if there is a number p ∈ ℕ such that d ⁺(x) = d ⁻(x) = p for all vertices x of D. A c-partite tournament is an orientation of a complete c-partite graph. There are many results about directed cycles of a given length or of directed cycles with vertices from a given number of partite sets. The idea is now to combine the two properties. In this article, we examine in particular, whether c-partite tournaments with r vertices in each partite set contain a cycle with exactly r − 1 vertices of every partite set. In 1982, Beineke and Little [2] solved this problem for the regular case if c = 2. If c ⩾ 3, then we will show that a regular c-partite tournament with r ⩾ 2 vertices in each partite set contains a cycle with exactly r − 1 vertices from each partite set, with the exception of the case that c = 4 and r = 2.     

Hyperuniform and rigid stable matchings

We study a stable partial matching τ of the d‐dimensional lattice with a stationary determinantal point process Ψ on R^d with intensity α>1. For instance, Ψ might be a Poisson process. The matched points from Ψ form a stationary and ergodic (under lattice shifts) point process Ψ^τ with intensity 1 that very much resembles Ψ for α close to 1. On the other hand Ψ^τ is hyperuniform and number rigid, quite in contrast to a Poisson process. We deduce these properties by proving more general results for a stationary point process Ψ, whose so‐called matching flower (a stopping set determining the matching partner of a lattice point) has a certain subexponential tail behavior. For hyperuniformity, we also additionally need to assume some mixing condition on Ψ. Furthermore, if Ψ is a Poisson process then Ψ^τ has an exponentially decreasing truncated pair correlation function.     

Perfect fractional matchings in random hypergraphs

Given an r-uniform hypergraph H = (V, E) on |V| = n vertices, a real-valued function f:E→R⁺ is called a perfect fractional matching if Σ_vϵe f(e) ≤ 1 for all vϵV and Σ_eϵE f(e) = n/r. Considering a random r-uniform hypergraph process of n vertices, we show that with probability tending to 1 as n→ infinity, at the very moment t₀ when the last isolated vertex disappears, the hypergraph H_t0 has a perfect fractional matching. This result is clearly best possible. As a consequence, we derive that if p(n) = (ln n + w(n))/ , where w(n) is any function tending to infinity with n, then with probability tending to 1 a random r-uniform hypergraph on n vertices with edge probability p has a perfect fractional matching. Similar results hold also for random r-partite hypergraphs. © 1996 John Wiley & Sons, Inc.     

Coloring random graphs online without creating monochromatic subgraphs

Consider the following random process: The vertices of a binomial random graph G_n,p are revealed one by one, and at each step only the edges induced by the already revealed vertices are visible. Our goal is to assign to each vertex one from a fixed number r of available colors immediately and irrevocably without creating a monochromatic copy of some fixed graph F in the process. Our first main result is that for any F and r, the threshold function for this problem is given by p₀(F,r,n) = n^‐1/m*₁(F,r), where m*₁(F,r) denotes the so‐called online vertex‐Ramsey density of F and r. This parameter is defined via a purely deterministic two‐player game, in which the random process is replaced by an adversary that is subject to certain restrictions inherited from the random setting. Our second main result states that for any F and r, the online vertex‐Ramsey density m*₁(F,r) is a computable rational number. Our lower bound proof is algorithmic, i.e., we obtain polynomial‐time online algorithms that succeed in coloring G_n,p as desired with probability 1 ‐ o(1) for any p(n) = o(n^‐1/m*₁(F,r)). © 2012 Wiley Periodicals, Inc. Random Struct. Alg. 44, 419–464, 2014     

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.     

Extremal properties of some geometric processes

In this paper some isoperimetric inequalities for stationary random tessellations are discussed. At first, classical results on deterministic tessellations in the Euclidean plane are extended to the case of random tessellations. An isoperimetric inequality for the random Poisson polygon is derived as a consequence of a theorem of Davidson concerning an extremal property of tessellations generated by random lines inR ². We mention extremal properties of stationary hyperplane tessellations inR ^d related to Davidson's result in cased=2. Finally, similar problems for random arrangements ofr-flats inR ^d are considered (r).This work was done while the author was visiting the University of Strathclyde in Glasgow.     

Stochastic homogenization of heat transfer in polycrystals with nonlinear contact conductivities

The heat transfer problem in a polycrystal with nonlinear jump conditions on the grain boundaries will be homogenized using the method of stochastic two-scale convergence developed by Zhikov and Pyatnitskii [V.V. Zhikov and A.L. Pyatnitskii, Homogenization of random singular structures and random measures, Izv. Math. 70(1) (2006), pp. 19–67] and recently extended by the author [M. Heida, An extension of stochastic two-scale convergence and application, Asympt. Anal. (2010) (in press)]. It will be shown that for monotone Lipschitz jump conditions differentiable in 0, the nonlinearity vanishes in the limit. Additionally, existing Poincaré inequalities will be extended to more general geometric settings with the only restriction of local C ¹-interfaces with finite intensity. In particular, the result can now be applied to the Poisson–Voronoi tessellation.     

Nonvanishing of Kronecker coefficients for rectangular shapes

We prove that for any partition (λ₁,…,λd²) of size ?d there exists k?1 such that the tensor square of the irreducible representation of the symmetric group Sk?d with respect to the rectangular partition (k?,…,k?) contains the irreducible representation corresponding to the stretched partition (kλ₁,…,kλd²). We also prove a related approximate version of this statement in which the stretching factor k is effectively bounded in terms of d. We further discuss the consequences for geometric complexity theory which provided the motivation for this work.     

How many cyclic subpolytopes can a non-cyclic polytope have?

Acyclic d-polytope is ad-polytope that is combinatorially equivalent to a polytope whose vertices lie on the moment curve {(t, t ², …,t ^d):t∈R}. Every subpolytope of an even-dimensional cyclic polytope is again cyclic. We show that a polytope [or neighborly polytope] withv vertices that is not cyclic has at mostd+1 [respectivelyd]d-dimensional cyclic subpolytopes withv−1 vertices, providedd is even andv≧d+5.     

Root Sublattices and Torus-Restriction of Prehomogeneous Vector Spaces Associated with Dynkin Quivers

For a Dynkin quiver Γ with r vertices, a subset S of the vertices of Γ, and an r-tuple d = (d⁽¹⁾, d⁽²⁾,…, d^(r)) of positive integers, we define a “torus-restricted” representation (G_S, R _d (Γ)) in natural way. Here we put G_S = G₁ × G₂ × … ×G_r, where each G_i is either SL(d⁽ⁱ⁾) or GL(d⁽ⁱ⁾) according to S containing i or not. In this paper, for a prescribed torus-restriction S, we give a necessary and sufficient condition on d that R _d (Γ) has only finitely many G_S-orbits. This can be paraphrased as a condition whether or not d is contained in a certain lattice spanned by positive roots of Γ. We also discuss the prehomogeneity of (G_S, R _d (Γ)).     

Spin depolarization decay rates in α-symmetric stable fields on cubic lattices

We study the asymptotic, long-time behavior of the energy function where {X_s : 0 ≤ s < ∞} is the standard random walk on the d-dimensional lattice Z^d, 1 < α ≤ 2, and f:R⁺ → R⁺ is any nondecreasing concave function. In the special case f(x) = x, our setting represents a lattice model for the study of transverse magnetization of spins diffusing in a homogeneous, α-stable, i.i.d., random, longitudinal field {λV(x) : x ∈ Z^d} with common marginal distribution, the standard α-symmetric stable distribution; the parameter λ describes the intensity of the field. Using large-deviation techniques, we show that S_c(λ α f) = lim_t→∞ E(t; λ f) exists. Moreover, we obtain a variational formula for this decay rate S_c. Finally, we analyze the behavior S_c(λ α f) as λ → 0 when f(x) = x^β for all 1 ≥ β > 0. Consequently, several physical conjectures with respect to lattice models of transverse magnetization are resolved by setting β = 1 in our results. We show that S_c(λ, α, 1) ≈ λ^α for d ≥ 3, λ^agr;(ln 1/λ)^α−1 in d = 2, and in d = 1. © 1996 John Wiley & Sons, Inc.