The scaling window of the 2‐SAT transition

We consider the random 2‐satisfiability (2‐SAT) problem, in which each instance is a formula that is the conjunction of m clauses of the form x∨y, chosen uniformly at random from among all 2‐clauses on n Boolean variables and their negations. As m and n tend to infinity in the ratio m/n→α, the problem is known to have a phase transition at α_c=1, below which the probability that the formula is satisfiable tends to one and above which it tends to zero. We determine the finite‐size scaling about this transition, namely the scaling of the maximal window W(n, δ)=(α_?(n,δ), α₊(n,δ)) such that the probability of satisfiability is greater than 1?δ for α<α_? and is less than δ for α>α₊. We show that W(n,δ)=(1?Θ(n^?1/3), 1+Θ(n^?1/3)), where the constants implicit in Θ depend on δ. We also determine the rates at which the probability of satisfiability approaches one and zero at the boundaries of the window. Namely, for m=(1+ε)n, where ε may depend on n as long as |ε| is sufficiently small and |ε|n^1/3 is sufficiently large, we show that the probability of satisfiability decays like exp(?Θ(nε³)) above the window, and goes to one like 1?Θ(n^?1|ε|^?3 below the window. We prove these results by defining an order parameter for the transition and establishing its scaling behavior in n both inside and outside the window. Using this order parameter, we prove that the 2‐SAT phase transition is continuous with an order parameter critical exponent of 1. We also determine the values of two other critical exponents, showing that the exponents of 2‐SAT are identical to those of the random graph. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 18: 201–256 2001     

Modularity of Erdős‐Rényi random graphs

For a given graph G, each partition of the vertices has a modularity score, with higher values indicating that the partition better captures community structure in G. The modularity q^?(G) of the graph G is defined to be the maximum over all vertex partitions of the modularity score, and satisfies 0 ≤ q^?(G)<1. Modularity is at the heart of the most popular algorithms for community detection. We investigate the behaviour of the modularity of the Erd?s‐Rényi random graph G_n,p with n vertices and edge‐probability p. Two key findings are that the modularity is 1+o(1) with high probability (whp) for np up to 1+o(1) and no further; and when np ≥ 1 and p is bounded below 1, it has order (np)^?1/2 whp, in accord with a conjecture by Reichardt and Bornholdt in 2006. We also show that the modularity of a graph is robust to changes in a few edges, in contrast to the sensitivity of optimal vertex partitions.     

An infinite series of regular edge‐ but not vertex‐transitive graphs

Let n be an integer and q be a prime power. Then for any 3 ≤ n ≤ q?1, or n=2 and q odd, we construct a connected q‐regular edge‐but not vertex‐transitive graph of order 2qⁿ⁺¹. This graph is defined via a system of equations over the finite field of q elements. For n=2 and q=3, our graph is isomorphic to the Gray graph. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 249–258, 2002     

The random planar graph process

We consider the following variant of the classical random graph process introduced by Erd?s and Rényi. Starting with an empty graph on n vertices, choose the next edge uniformly at random among all edges not yet considered, but only insert it if the graph remains planar. We show that for all ε > 0, with high probability, θ(n²) edges have to be tested before the number of edges in the graph reaches (1 + ε)n. At this point, the graph is connected with high probability and contains a linear number of induced copies of any fixed connected planar graph, the first property being in contrast and the second one in accordance with the uniform random planar graph model. © 2007 Wiley Periodicals, Inc. Random Struct. Alg., 2008     

Lower bounds for the cardinality of minimal blocking sets in projective spaces

In this paper new lower bounds for the cardinality of minimal m-blocking sets are determined. Let r₂(q) be the number such that q+r₂(q)+1 is the cardinality of the smallest non-trivial line-blocking set in a plane of order q. If B is a minimal m-blocking set in PG(n,q) that contains at most q^m+q^m−1+…+q+1+r₂(q)·(∑_i=2m−n′^m−1qⁱ) points for an integer n′ satisfying mn′2m, then the dimension of B is at most n′. If the dimension of B is n′, then the following holds. The cardinality of B equals q^m+q^m−1+…+q+1+r₂(q)(∑_i=2m−n′^m−1qⁱ). For n′=m the set B is an m-dimensional subspace and for n′=m+1 the set B is a cone with an (m−2)-dimensional vertex over a non-trivial line-blocking set of cardinality q+r₂(q)+1 in a plane skew to the vertex. This result is due to Heim (Mitt. Math. Semin. Giessen 226 (1996), 4–82). For n′>m+1 and q not a prime the number q is a square and for q16 the set B is a Baer cone. If q is odd and |B|<q^m+q^m−1+…+q+1+r₂(q)(q^m−1+q^m−2), it follows from this result that the subspace generated by B has dimension at most m+1. Furthermore we prove that in this case, if , then B is an m-dimensional subspace or a cone with an (m−2)-dimensional vertex over a non-trivial line-blocking set of cardinality q+r₂(q)+1 in a plane skew to the vertex. For q=p^3h, p7 and q not a square we show this assertion for |B|q^m+q^m−1+…+q+1+q^2/3·(q^m−1+…+1).     

Randomly coloring constant degree graphs

We study a simple Markov chain, known as the Glauber dynamics, for generating a random k ‐coloring of an n ‐vertex graph with maximum degree Δ. We prove that, for every ε > 0, the dynamics converges to a random coloring within O(nlog n) steps assuming k ≥ k₀(ε) and either: (i) k/Δ > α* + ε where α*≈? 1.763 and the girth g ≥ 5, or (ii) k/Δ >β * + ε where β*≈? 1.489 and the girth g ≥ 7. Our work improves upon, and builds on, previous results which have similar restrictions on k/Δ and the minimum girth but also required Δ = Ω (log n). The best known result for general graphs is O(nlog n) mixing time when k/Δ > 2 and O(n²) mixing time when k/Δ > 11/6. Related results of Goldberg et al apply when k/Δ > α* for all Δ ≥ 3 on triangle‐free “neighborhood‐amenable” graphs.© 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2013     

Random majority percolation

We shall consider the discrete time synchronous random majority‐vote cellular automata on the n by n torus, in which every vertex is in one of two states and, at each time step t, every vertex goes into the state the majority of its neighbors had at time t ‐ 1 with a small chance p of error independently of all other events. We shall show that, if n is fixed and p is sufficiently small, then the process spends almost half of its time in each of two configurations. Further more, we show that the expected time for it to reach one of these configurations from the other is Θ(1/pⁿ⁺¹) despite the actual time spent in transit being O(1/p³). Unusually, it appears difficult to obtain any results for this regime by simulation. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2010     

Approximating Fixed Points of Weakly Contracting Mappings

We consider the problem of approximating fixed points of contractive functions whose contraction factor is close to 1. In a previous paper (1993, K. Sikorski et al., J. Complexity9, 181–200), we proved that for the absolute error criterion, the upper bound on the number of function evaluations to compute ε-approximations is O(n³(ln(1/ε)+ln(1/(1−q))+ln n)) in the worst case, where 0<q<1 is the contraction factor in the Euclidean norm and n is the dimension of the problem. This upper bound is achieved by the circumscribed ellipsoid (CE) algorithm combined with a dimensional deflation process. In this paper we present an inscribed ellipsoid (IE) algorithm that enjoys O(n(ln(1/ε)+ln(1/(1−q)))) bound. For q close to 1, the IE algorithm thus runs in many fewer iterations than the simple iteration method, that requires ⌈ln(1/ε)/ln(1/q)⌉ function evaluations. Our analysis also implies that: (1) The dimensional deflation procedure in the CE algorithm is not necessary and that the resulting “plain” CE algorithm enjoys O(n²(log(1/ε)+log(1/(1−q)))) upper bound on the number of function evaluations. (2) The IE algorithm solves the problem in the residual sense, i.e., computes x such that 6f(x)−x6⩽δ, with O(n ln(1/δ)) function evaluations for every q⩽1.     

The random binary growth model

We describe a family of models of random partial orders, called classical sequential growth models, and study a specific case, which is the simplest interesting model, called a random binary growth model. This model produces a random poset, called a random binary order, B₂, on the vertex set ? by considering each vertex n ≥ 2 in turn and placing it above 2 vertices chosen uniformly at random from the set {0,…,n ? 1} (with additional relations added to ensure transitivity). We show that B₂ has infinite dimension, almost surely. Using the differential equation method of Wormald, we can closely approximate the size of the up‐set of an arbitrary vertex. We give an upper bound on the largest vertex incomparable with vertex n, which is polynomial in n, and, using this bound, we provide an example of a poset P, such that there is a positive probability that B₂ does not contain P. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2005     

The mixing time of Glauber dynamics for coloring regular trees

We consider Metropolis Glauber dynamics for sampling proper q‐colorings of the n‐vertex complete b‐ary tree when 3 ≤ q ≤ b/(2lnb). We give both upper and lower bounds on the mixing time. Our upper bound is n^{O(b/ log b)} and our lower bound is n^{Ω(b/(q log b))}, where the constants implicit in the O() and Ω() notation do not depend upon n, q or b. © 2010 Wiley Periodicals, Inc. Random Struct. Alg., 2010     

The critical behavior of random digraphs

We study the critical behavior of the random digraph D(n,p) for np = 1 + ε, where ε = ε(n) = o(1). We show that if ε³n →—∞, then a.a.s. D(n,p) consists of components which are either isolated vertices or directed cycles, each of size O_p(|ε|^?1). On the other hand, if ε³n →∞, then a.a.s. the structure of D(n,p) is dominated by the unique complex component of size (4 + o(1))ε²n, whereas all other components are of size O_p(ε^?1). © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

On generalized Hadamard matrices of minimum rank

Generalized Hadamard matrices of order qⁿ⁻¹ (q—a prime power, n2) over GF(q) are related to symmetric nets in affine 2-(qⁿ,qⁿ⁻¹,(qⁿ⁻¹−1)/(q−1)) designs invariant under an elementary abelian group of order q acting semi-regularly on points and blocks. The rank of any such matrix over GF(q) is greater than or equal to n−1. It is proved that a matrix of minimum q-rank is unique up to a monomial equivalence, and the related symmetric net is a classical net in the n-dimensional affine geometry AG(n,q).     

Positional Games and the Second Moment Method

Dedicated to the memory of Paul Erdős We study the fair Maker–Breaker graph Ramsey game MB(n;q). The board is , the players alternately occupy one edge a move, and Maker wants a clique of his own. We show that Maker has a winning strategy in MB(n;q) if , which is exactly the clique number of the random graph on n vertices with edge-probability 1/2. Due to an old theorem of Erdős and Selfridge this is best possible apart from an additive constant. Received March 28, 2000     

Component structure of the vacant set induced by a random walk on a random graph

We consider random walks on several classes of graphs and explore the likely structure of the vacant set, i.e. the set of unvisited vertices. Let Γ(t) be the subgraph induced by the vacant set of the walk at step t. We show that for random graphs G_n,p (above the connectivity threshold) and for random regular graphs G_r,r ≥ 3, the graph Γ(t) undergoes a phase transition in the sense of the well‐known ErdJW‐RSAT1100590x.png ‐Renyi phase transition. Thus for t ≤ (1 ‐ ε)t^*, there is a unique giant component, plus components of size O(log n), and for t ≥ (1 + ε)t^* all components are of size O(log n). For G_n,p and G_r we give the value of t^*, and the size of Γ(t). For G_r, we also give the degree sequence of Γ(t), the size of the giant component (if any) of Γ(t) and the number of tree components of Γ(t) of a given size k = O(log n). We also show that for random digraphs D_n,p above the strong connectivity threshold, there is a similar directed phase transition. Thus for t ≤ (1 ‐ ε)t^*, there is a unique strongly connected giant component, plus strongly connected components of size O(log n), and for t ≥ (1 + ε)t^* all strongly connected components are of size O(log n). © 2012 Wiley Periodicals, Inc. Random Struct. Alg., 2012     

Small maximal matchings of random cubic graphs

We consider the expected size of a smallest maximal matching of cubic graphs. Firstly, we present a randomized greedy algorithm for finding a small maximal matching of cubic graphs. We analyze the average‐case performance of this heuristic on random n‐vertex cubic graphs using differential equations. In this way, we prove that the expected size of the maximal matching returned by the algorithm is asymptotically almost surely (a.a.s.) less than 0.34623n. We also give an existence proof which shows that the size of a smallest maximal matching of a random n‐vertex cubic graph is a.a.s. less than 0.3214n. It is known that the size of a smallest maximal matching of a random n‐vertex cubic graph is a.a.s. larger than 0.3158n. © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 293–323, 2009     

The transitive closure of a random digraph

In a random n-vertex digraph, each arc is present with probability p, independently of the presence or absence of other arcs. We investigate the structure of the strong components of a random digraph and present an algorithm for the construction of the transitive closure of a random digraph. We show that, when n is large and np is equal to a constant c greater than 1, it is very likely that all but one of the strong components are very small, and that the unique large strong component contains about Θ₂n vertices, where Θ is the unique root in [0, 1] of the equation 1 ? x ? e^?ex = 0. Nearly all the vertices outside the large strong component line in strong components of size 1. Provided that the expected degree of a vertex is bounded away from 1, our transitive closure algorithm runs in expected time O(n). for all choices of n and p, the expected execution time of the algorithm is O(w(n) (n log n)^4/3), where w(n) is an arbitrary nondecreasing unbounded function. To circumvent the fact that the size of the transitive closure may be Ω(n²) the algorithm presents the transitive closure in the compact form (A × B)U C, where A and B are sets of vertices, and C is a set of arcs.     

Stochastic Differential Games with Multiple Modes and a Small Parameter

Abstract

Two persons stochastic differential games with multiple modes where the system is driven by a wideband noise is considered. The state of the system at time t is given by a pair (x ^ε(t), θ^ε(t)), where θ^ε(t) takes values in S = {1, 2,…, N} and ε is a small parameter. The discrete component θ^ε(t) describes various modes of the system. The continuous component x ^ε(t) is governed by a “controlled process” with drift vector which depends on the discrete component θ^ε (t). Thus, the state of the system, x ^ε(t), switches from one random path to another at random times as the mode θ^ε(t) changes. The discrete component θ^ε (t) is a “controlled Markov chain” with transition rate matrix depending on the continuous component. Both zero-sum and nonzero-sum games will be considered. In a zero-sum game, player I is trying to maximize certain expected payoff over his/her admissible strategies, where as player II is trying to minimize the same over his/her admissible strategies. This kind of game typically occurs in a pursuit-evation problem where an interceptor tries to destroy a specific target. Due to swift manuaring of the evador and the corresponding reaction by the interceptor, the trajectory keep switching rapidly at random times. We will show that the process (x ^ε(t), θ^ε(t)) converges to a process whose evolution is given by a “controlled diffusion process” with switching random paths. We will also establish the existence of randomized δ -optimal strategies for both players.     

Sublines of Prime Order Contained in the Set of Internal Points of a Conic

In [2] it was shown that if q ≥ 4n²−8n+2 then there are no subplanes of order q contained in the set of internal points of a conic in PG(2,qⁿ), q odd, n≥ 3. In this article we improve this bound in the case where q is prime to , and prove a stronger theorem by considering sublines instead of subplanes. We also explain how one can apply this result to flocks of a quadratic cone in PG(3,qⁿ), ovoids of Q(4,qⁿ), rank two commutative semifields, and eggs in PG(4n−1,q). AMS Classification:11T06, 05B25, 05E12, 51E15     

Rate of escape on the lamplighter tree

Suppose we are given a homogeneous tree {ie173-01} of degree q ≥ 3, where at each vertex sits a lamp, which can be switched on or off. This structure can be described by the wreath product (ℤ/2)≀Γ, where Γ = * _i=1^qℤ/2 is the free product group of q factors ℤ/2. We consider a transient random walk on a Cayley graph of (ℤ/2) ≀Γ, for which we want to compute lower and upper bounds for the rate of escape, that is, the speed at which the random walk flees to infinity. Translated from Sovremennaya Matematika i Ee Prilozheniya (Contemporary Mathematics and Its Applications), Vol. 50, Functional Analysis, 2007.