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     

Doubly eulerian trails on rectangular grids

Let K be the 1-skeleton of the regular tessellation of Euclidean n-space by n-cubes, n ≥ 2. We show that K admits a doubly Eulerian trail (simply Eulerian trail), that is, a doubly infinite path π = … e_?1e₀e₁ … where, out of each pair {e, e^?1} of oppositely directed edges, both (exactly one) appear(s) exactly once in π, and where no e_i+1 = e_i^?1 (there are no U-turns).     

Multiple positive solutions of boundary value problems for second-order discrete equations on the half-line

In this paper, we study the existence of multiple positive solutions of boundary value problems for second-order discrete equations Δ² x(n ? 1) ? pΔx(n ? 1) ? qx(n ? 1)+f(n, x(n)) = 0, n ∈ {1,2,…}, αx(0) ? βΔx(0) = 0, x(∞) = 0. The proofs are based on the fixed point theorem in Fréchet space (see Agarwal and O'Regan, 2001, Cone compression and expansion and fixed point theorems in Fréchet spaces with application, Journal of Differential Equations, 171, 412–42).     

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     

A phase transition phenomenon in a random directed acyclic graph

Let a random directed acyclic graph be defined as being obtained from the random graph G_{n, p} by orienting the edges according to the ordering of vertices. Let γ_n* be the size of the largest (reflexive, transitive) closure of a vertex. For p=c(log n)/n, we prove that, with high probability, γ_n* is asymptotic to n^c log n, 2n(log log n)/log n, and n(1−1/c) depending on whether c<1, c=1, or c>1. We also determine the limiting distribution of the first vertex closure in all three ranges of c. As an application, we show that the expected number of comparable pairs is asymptotic to n^1+c/c log n, ½(n(log log n)/log n)², and ½(n(1−1/c))², respectively. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 18: 164–184, 2001     

Differences of Convex Compact Sets in the Space of Directed Sets. Part II: Visualization of Directed Sets

This paper is a continuation of the author's first paper (Set-Valued Anal. 9 (2001), pp. 217–245), where the normed and partially ordered vector space of directed sets is constructed and the cone of all nonempty convex compact sets in R ⁿ is embedded. A visualization of directed sets and of differences of convex compact sets is presented and its geometrical components and properties are studied. The three components of the visualization are compared with other known differences of convex compact sets.     

On the Simplicity of Lie Algebras Associated to Leavitt Algebras

For any field 𝕂 and integer n ≥ 2, we consider the Leavitt algebra L _𝕂(n); for any integer d ≥ 1, we form the matrix ring S = M _d (L _𝕂(n)). S is an associative algebra, but we view S as a Lie algebra using the bracket [a, b] = ab ? ba for a, b ∈ S. We denote this Lie algebra as S ^?, and consider its Lie subalgebra [S ^?, S ^?]. In our main result, we show that [S ^?, S ^?] is a simple Lie algebra if and only if char(𝕂) divides n ? 1 and char(𝕂) does not divide d. In particular, when d = 1, we get that [L _𝕂(n)^?, L _𝕂(n)^?] is a simple Lie algebra if and only if char(𝕂) divides n ? 1.     

On tree census and the giant component in sparse random graphs

For each of the two models of a sparse random graph on n vertices, G(n, # of edges = cn/2) and G(n, Prob (edge) = c/n) define t_n(k) as the total number of tree components of size k (1 ≤ k ≤ n). the random sequence {[t_n(k) - nh(k)]n^?1/2} is shown to be Gaussian in the limit n →∞, with h(k) = k^k?2c^k?1e^?kc/k! and covariance function being dependent upon the model. This general result implies, in particular, that, for c> 1, the size of the giant component is asymptotically Gaussian, with mean nθ(c) and variance n(1 ? T)^?2(1 ? 2Tθ)θ(1 ? θ) for the first model and n(1 ? T)^?2θ(1 ? θ) for the second model. Here Te^?T = ce^?c, T<1, and θ = 1 ? T/c. A close technique allows us to prove that, for c < 1, the independence number of G(n, p = c/n) is asymptotically Gaussian with mean nc^?1(β + β²/2) and variance n[c^?1(β + β²/2) ?c^?2(c + 1)β²], where βe^β = c. It is also proven that almost surely the giant component consists of a giant two-connected core of size about n(1 ? T)β and a “mantle” of trees, and possibly few small unicyclic graphs, each sprouting from its own vertex of the core.     

A lower bound on the number of Semi‐Boolean quadruple systems

A Steiner quadruple system of order 2ⁿ is Semi‐Boolean (SBQS(2ⁿ) in short) if all its derived triple systems are isomorphic to the point‐line design associated with the projective geometry PG(n?1, 2). We prove by means of explicit constructions that for any n, up to isomorphism, there exist at least 2^{? 3(n?4)/2?} regular and resolvable SBQS(2ⁿ). © 2003 Wiley Periodicals, Inc. J Combin Designs 11: 229–239, 2003; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10050     

Rotationally Invariant Rank 1 Convex Functions

Let f be a function on the set M ⁿ xn of all n by n real matrices. If f is rotationally invariant with respect to the proper orthogonal group, it has a representation \tilde f through the signed singular values of the matrix argument ?∈ M^nxn. Necessary and sufficient conditions are given for the rank 1 convexity of f in terms of \tilde f . Accepted 20 December 2000. Online Publication 18 May, 2001.     

Real Zeros of Algebraic Polynomials with Dependent Random Coefficients

The expected number of real zeros of polynomials a ₀ + a ₁ x + a ₂ x ² +…+a _n?1 x ^n?1 with random coefficients is well studied. For n large and for the normal zero mean independent coefficients, irrespective of the distribution of coefficients, this expected number is known to be asymptotic to (2/π)log n. For the dependent cases studied so far it is shown that this asymptotic value remains O(log n). In this article, we show that when cov(a _i , a _j ) = 1 ? |i ? j|/n, for i = 0,…, n ? 1 and j = 0,…, n ? 1, the above expected number of real zeros reduces significantly to O(log n)^1/2.     

A small embedding for partial even-cycle systems

Let m = 2k. We show that for some 0 ≤ ξ <1, a partial directed m-cycle system of order n can be embedded in a directed m-cycle system of order (mn)/2 + (2m² 1) √(8n + 1)/4 + 4m^{3 2} + 4 + 1/2. For fixed m, this is asymptotic in n to (mn)/2 and so for large n is roughly one-fourth the best known bound of 2mn + 1. © 1999 John Wiley & Sons, Inc. J Combin Designs 7: 205–215, 1999     

A Tight Bound on the Number of Geometric Permutations of Convex Fat Objects in R d

We show that the maximum number of geometric permutations of a set of n pairwise-disjoint convex and fat objects in R ^d is O(n ^d-1 ) . This generalizes the bound of Θ (n ^d-1 ) obtained by Smorodinsky et al. [5] on the number of geometric permutations of n pairwise-disjoint balls. Received August 22, 2000, and in revised form February 6, 2001. Online publication October 12, 2001.     

Oriented hamilton cycles in digraphs

We show that a directed graph of order n will contain n-cycles of every orientation, provided each vertex has indegree and outdegree at least (1/2 + n^-1/6)n and n is sufficiently large. © 1995 John Wiley & Sons, Inc.     

Complete space-like hypersurfaces with constant scalar curvature

Let M ⁿ be a complete space-like hypersurface with constant normalized scalar curvature R in the de Sitter space S ^{n + 1} ₁ and denote . We prove that if the norm square of the second fundamental form of M ⁿ satisfies , then either and M ⁿ is a totally umbilical hypersurface; or , and, up to rigid motion, M ⁿ is a hyperbolic cylinder . Received: 8 February 2001 / Revised version: 27 April 2001     

The Birman–Murakami–Wenzl Algebras of Type D n

The Birman–Murakami–Wenzl algebra (BMW algebra) of type D _n is shown to be semisimple and free of rank (2 ⁿ  + 1)n!! ? (2 ^n?1 + 1)n! over a specified commutative ring R, where n!! =1·3…(2n ? 1). We also show it is a cellular algebra over suitable ring extensions of R. The Brauer algebra of type D _n is the image of an R-equivariant homomorphism and is also semisimple and free of the same rank, but over the ring ?[δ^±1]. A rewrite system for the Brauer algebra is used in bounding the rank of the BMW algebra above. As a consequence of our results, the generalized Temperley–Lieb algebra of type D _n is a subalgebra of the BMW algebra of the same type.     

The asymptotic number of labeled connected graphs with a given number of vertices and edges

Let c(n, q) be the number of connected labeled graphs with n vertices and q ≤ N = (2n ) edges. Let x = q/n and k = q ? n. We determine functions w_k ? 1. a(x) and φ(x) such that c(n, q) ? w_k(q^N)eⁿφ(x)+a(x) uniformly for all n and q ≥ n. If ? > 0 is fixed, n→ ∞ and 4q > (1 + ?)n log n, this formula simplifies to c(n, q) ? (N^q) exp(–ne^?2q/n). on the other hand, if k = o(n^1/2), this formula simplifies to c(n, n + k) ? 1/2 w_k (3/π)^1/2 (e/12k)^k/2nⁿ?^(3k?1)/2.     

Some results on (k, μ)′-almost Kenmotsu manifolds

In this paper, we study the Weyl conformal curvature tensor 𝒲 and the concircular curvature tensor 𝒞 on a (k, μ)′-almost Kenmotsu manifold M²ⁿ⁺¹ of dimension greater than 3. We obtain that if M²ⁿ⁺¹ satisfies either R · 𝒲 = 0 or 𝒞 · 𝒞 = 0, then it is locally isometric to either the hyperbolic space ?²ⁿ⁺¹ (?1) or the Riemannian product ?ⁿ⁺¹(?4) × ?ⁿ.     

Large sets of disjoint group‐divisible designs with block size three and type 2n41

Large sets of disjoint group‐divisible designs with block size three and type 2ⁿ4¹ have been studied by Schellenberg, Chen, Lindner and Stinson. These large sets have applications in cryptography in the construction of perfect threshold schemes. It is known that such large sets can exist only for n ≡ 0 (mod 3) and do exist for n = 6 and for all n = 3^k, k ≥ 1. In this paper, we present new recursive constructions and use them to show that such large sets exist for all odd n ≡ 0 (mod 3) and for even n = 24m, where m odd ≥ 1. © 2001 John Wiley & Sons, Inc. J Combin Designs 9: 285–296, 2001     

Bounds on the number of Hadamard designs of even order

A new lower bound on the number of non‐isomorphic Hadamard symmetric designs of even order is proved. The new bound improves the bound on the number of Hadamard designs of order 2n given in [12] by a factor of 8n ? 1 for every odd n > 1, and for every even n such that 4n ? 1 > 7 is a prime. For orders 8, 10, and 12, the number of non‐isomorphic Hadamard designs is shown to be at least 22,478,260, 1.31 × 10¹⁵, and 10²⁷, respectively. For orders 2n = 14, 16, 18 and 20, a lower bound of (4n ? 1)! is proved. It is conjectured that (4n ? 1)! is a lower bound for all orders 2n ≥ 14. © 2001 John Wiley & Sons, Inc. J Combin Designs 9: 363‐378, 2001