The 2D‐directed spanning forest is almost surely a tree

We consider the Directed Spanning Forest (DSF) constructed as follows: given a Poisson point process N on the plane, the ancestor of each point is the nearest vertex of N having a strictly larger abscissa. We prove that the DSF is actually a tree. Contrary to other directed forests of the literature, no Markovian process can be introduced to study the paths in our DSF. Our proof is based on a comparison argument between surface and perimeter from percolation theory. We then show that this result still holds when the points of N belonging to an auxiliary Boolean model are removed. Using these results, we prove that there is no bi‐infinite paths in the DSF. © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012     

Fluctuations in a general preferential attachment model via Stein's method

We consider a class of dynamic random graphs known as preferential attachment models, where the probability that a new vertex connects to an older vertex is proportional to a sublinear function of the indegree of the older vertex at that time. It is well known that the distribution of a uniformly chosen vertex converges to a limiting distribution. Depending on the parameters, the tail of the limiting distribution may behave like a power law or a stretched exponential. Using Stein's method we provide rates of convergence to zero of the total variation distance between the finite distribution and its limit. Our proof uses the fact that the limiting distribution is the stationary distribution of a Markov chain together with the generator method of Barbour.     

Foolproof eternal domination in the all-guards move model

The eternal domination problem requires a graph be protected against an infinitely long sequence of attacks at vertices, by guards located at vertices, with the requirement that the configuration of guards induces a dominating set at all times. An attack is defended by sending a guard from a neighboring vertex to the attacked vertex. We allow all guards to move to neighboring vertices in response to an attack, but allow the attacked vertex to choose which neighboring guard moves to the attacked vertex. This is the all-guards move version of the ??foolproof?? eternal domination problem that has been previously studied. We present some results and conjectures on this problem.     

Some Structural Properties of Acyclic Heaps of Pieces

We introduce the notions of boundary vertex, linear equivalence, and effective boundary vertex in the context of Viennot??s heaps of pieces. We prove that in the heap of a fully commutative element in a star reducible Coxeter group, every boundary vertex is linearly equivalent to an effective boundary vertex.     

Approximating average parameters of graphs

Inspired by Feige (36th STOC, 2004), we initiate a study of sublinear randomized algorithms for approximating average parameters of a graph. Specifically, we consider the average degree of a graph and the average distance between pairs of vertices in a graph. Since our focus is on sublinear algorithms, these algorithms access the input graph via queries to an adequate oracle. We consider two types of queries. The first type is standard neighborhood queries (i.e., what is the ith neighbor of vertex v?), whereas the second type are queries regarding the quantities that we need to find the average of (i.e., what is the degree of vertex v? and what is the distance between u and v?, respectively). Loosely speaking, our results indicate a difference between the two problems: For approximating the average degree, the standard neighbor queries suffice and in fact are preferable to degree queries. In contrast, for approximating average distances, the standard neighbor queries are of little help whereas distance queries are crucial. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

Digraph searching, directed vertex separation and directed pathwidth

The four digraph search models, directed search, undirected search, strong search, and weak search, are studied in this paper. There are three types of actions for searchers in these models: placing, removing, and sliding. The four models differ in the abilities of searchers and intruders depending on whether or not they must obey the edge directions when they move along the directed edges. In this paper, we investigate the relationships between these search models. We introduce the concept of directed vertex separation for digraphs. We also discuss the properties of directed vertex separation, and investigate the relations between directed vertex separation, directed pathwidth and search numbers in different search models.     

Concentration results for a Brownian directed percolation problem

We consider the hydrodynamic limit for a certain Brownian directed percolation model, and establish uniform concentration results. In view of recent work on the connection between this directed percolation model and eigenvalues of random matrices, our results can also be interpreted as uniform concentration results at the process level for the largest eigenvalue of Hermitian Brownian motion.     

Asymptotic of the Critical Value of the Large-Dimensional SIR Epidemic on Clusters

In this paper we are concerned with the susceptible-infective-removed (SIR) epidemic on open clusters of bond percolation on the square lattice. For the SIR model, a susceptible vertex is infected at rate proportional to the number of infective neighbors, while an infective vertex becomes removed at a constant rate. A removed vertex will never be infected again. We assume that at \(t=0\) the only infective vertex is the origin and define the critical value of the model as the supremum of the infection rates with which infective vertices die out with probability one; then, we show that the critical value under the annealed measure is \(\big (1+o(1)\big )/(2dp)\) as the dimension d of the lattice grows to infinity, where p is the probability that a given edge is open. Furthermore, we show that the critical value under the quenched measure equals the annealed one when the origin belongs to an infinite open cluster of the percolation.     

The complexity of node blocking for dags

We consider the following modification of annihilation games called node blocking. Given a directed graph, each vertex can be occupied by at most one token. There are two types of tokens, each player can move only tokens of his type. The players alternate their moves and the current player i selects one token of type i and moves the token along a directed edge to an unoccupied vertex. If a player cannot make a move then he loses. We consider the problem of determining the complexity of the game: given an arbitrary configuration of tokens in a planar directed acyclic graph (dag), does the current player have a winning strategy? We prove that the problem is PSPACE-complete.     

Indestructibility of Vop��nka��s Principle

Vop??nka??s Principle is a natural large cardinal axiom that has recently found applications in category theory and algebraic topology. We show that Vop??nka??s Principle and Vop??nka cardinals are relatively consistent with a broad range of other principles known to be independent of standard (ZFC) set theory, such as the Generalised Continuum Hypothesis, and the existence of a definable well-order on the universe of all sets. We achieve this by showing that they are indestructible under a broad class of forcing constructions, specifically, reverse Easton iterations of increasingly directed closed partial orders.     

Baxter-Guttmann-Jensen conjecture for power series in directed percolation problem

A probabilistic model of a flow of fluid through a random medium,percolation model, provides a typical example of statistical mechanical problems which are easy to describe but difficult to solve. While the percolation problem on undirected planar lattices is exactly solved as a limit of the Potts models, there still has been no exact solution for the directed lattices. The most reliable method to provide good approximations is a numerical estimation using finite power-series expansion data of the infinite formal power series for percolation probability. In order to calculate higher-order terms in power series, Baxter and Guttmann [6] and Jensen and Guttmann [33] proposed an extrapolation procedure based on an assumption that thecorrection terms, which show the difference between the exact infinite power series and approximate finite series, are expressed as linear combinations of the Catalan numbers.In this paper, starting from a brief review on the directed percolation problem and the observation by Baxter, Guttmann, and Jensen, we state some theorems in which we explain the reason why the combinatorial numbers appear in the correction terms of power series. In the proof of our theorems, we show several useful combinatorial identities for the ballot numbers, which become the Catalan numbers in a special case. These identities ensure that a summation of products of the ballot numbers with polynomial coefficients can be expanded using the ballot numbers. There is still a gap between our theorems and the Baxter-Guttmann-Jensen observation, and we also give some conjectures.As a generalization of the percolation problem on a directed planar lattice, we present two topics at the end of this paper: The friendly walker problem and the stochastic cellular automata in higher dimensions. We hope that these two topics as well as the directed percolation problem will be of much interest to researchers of combinatorics.     

全矩阵环上理想包含图的自同构群

设R是一个环,其上的理想包含图,记为Γ_I(R),是一个有向图,它以R的非平凡左理想为顶点,从R的左理想I_1到I_2有一条有向边当且仅当I_1真包含于I_2.环R上的理想关系图,记为Γ_i(R),也是一个有向图,它以R为顶点集,从R中元素A到B有一条有向边当且仅当A生成的左理想真包含于B生成的左理想.设F_q为有限域,其上n阶全矩阵环记为M_n(F_q),本文刻画了环M_n(F_q)上的理想包含图以及理想关系图的任意自同构.     

Bounding the feedback vertex number of digraphs in terms of vertex degrees

The Turán bound (Turán (1941) [17]) is a famous result in graph theory, which relates the independence number of an undirected graph to its edge density. Also the Caro-Wei inequality (Caro (1979) [4] and Wei (1981) [18]), which gives a more refined bound in terms of the vertex degree sequence of a graph, might be regarded today as a classical result. We show how these statements can be generalized to directed graphs, thus yielding a bound on directed feedback vertex number in terms of vertex out-degrees and in terms of average out-degree, respectively.     

On directed graphs with an independent covering set

We prove that if a directed graph,D, contains no odd directed cycle and, for all but finitely many vertices, EITHER the in-degrees are finite OR the out-degrees are at most one, thenD contains an independent covering set (i.e. there is a kernel). We also give an example of a countable directed graph which has no directed cycle, each vertex has out-degree at most two, and which has no independent covering set.Research supported by N.S.E.R.C. grants #69-0982 and #69-0259.     

Passive Advection in a Percolation Process: Two-Loop Approximation

Theoretical and Mathematical Physics - We study an instructive model of the directed percolation process near its second-order phase transition between absorbing and active states. We first express...     

The small-time Chung-Wichura law for L��vy processes with non-vanishing Brownian component

We give a ??small time?? functional version of Chung??s ??other?? law of the iterated logarithm for Lévy processes with non-vanishing Brownian component. This is an analogue of the ??other?? law of the iterated logarithm at ??large times?? for Lévy processes and random walks with finite variance, as extended to a functional version by Wichura. As one of many possible applications, we mention a functional law for a two-sided passage time process.     

Site percolation and isoperimetric inequalities for plane graphs

We use isoperimetric inequalities combined with a new technique to prove upper bounds for the site percolation threshold of plane graphs with given minimum degree conditions. In the process we prove tight new isoperimetric bounds for certain classes of hyperbolic graphs. This establishes the vertex isoperimetric constant for all triangular and square hyperbolic lattices, answering a question of Lyons and Peres. We prove that plane graphs of minimum degree at least 7 have site percolation threshold bounded away from 1/2, which was conjectured by Benjamini and Schramm, and make progress on a conjecture of Angel, Benjamini, and Horesh that the critical probability is at most 1/2 for plane triangulations of minimum degree 6. We prove additional bounds for stronger minimum degree conditions, and for graphs without triangular faces.     

Bipartite and directed scale-free complex networks arising from zeta functions

We construct a new class of directed and bipartite random graphs whose topology is governed by the analytic properties of multiple zeta functions. The bipartite L-graphs and the multiplicative zeta graphs are relevant examples of the proposed construction. Phase transitions and percolation thresholds for our models are determined.