Linear Equations for the Number of Intervals Which are Isomorphic with Boolean Lattices and the Dehn–Sommerville Equations

Let P be a finite poset. Let L: = J(P) denote the lattice of order ideals of P. Let b _i (L) denote the number of Boolean intervals of L of rank i.

We construct a simple graph G(P) from our poset P. Denote by f _i (P) the number of the cliques K _i+1, contained in the graph G(P).

Our main results are some linear equations connecting the numbers f _i (P) and b _i (L).

We reprove the Dehn–Sommerville equations for simplicial polytopes.

In our proof, we use free resolutions and the theory of Stanley–Reisner rings.     

Iterated clique graphs with increasing diameters

A simple argument by Hedman shows that the diameter of a clique graph G differs by at most one from that of K(G), its clique graph. Hedman described examples of a graph G such that diam(K(G)) = diam(G) + 1 and asked in general about the existence of graphs such that diam(Kⁱ(G)) = diam(G) + i. Examples satisfying this equality for i = 2 have been described by Peyrat, Rall, and Slater and independently by Balakrishnan and Paulraja. The authors of the former work also solved the case i = 3 and i = 4 and conjectured that such graphs exist for every positive integer i. The cases i ≥ 5 remained open. In the present article, we prove their conjecture. For each positive integer i, we describe a family of graphs G such that diam(Kⁱ(G)) = diam(G) + i. © 1998 John Wiley & Sons, Inc. J. Graph Theory 28: 147–154, 1998     

Greedy linear extensions for minimizing bumps

Let P be a finite poset and let L={x ₁<...n} be a linear extension of P. A bump in L is an ordered pair (x _i , x _i+1) where x _ii+1 in P. The bump number of P is the least integer b(P), such that there exists a linear extension of P with b(P) bumps. We call L optimal if the number of bumps of L is b(P). We call L greedy if x _{i j} for every j>i, whenever (x _i, x _i+1) is a bump. A poset P is called greedy if every greedy linear extension of P is optimal. Our main result is that in a greedy poset every optimal linear extension is greedy. As a consequence, we prove that every greedy poset of bump number k is the linear sum of k+1 greedy posets, each of bump number zero.This research (Math/1406/31) was supported by the Research Center, College of Science, King Saud University, Riyadh, Saudi Arabia.     

Normal families of meromorphic functions and shared values

Let k be a positive integer, b ≠ 0 be a finite complex number, let P be a polynomial with either deg P ≥ 3 or deg P = 2 and P having only one distinct zero, and let F{\mathcal{F}} be a family of functions meromorphic in a domain D, all of whose zeros have multiplicities at least k. If, each pair of functions f and g in F, P(f)f^(k){\mathcal{F}, P(f)f^{(k)}} and P(g)g ^(k) share b in D, then F{\mathcal{F}} is normal in D.     

Networks and chain coverings in partial orders and their products

For an arbitrary poset P, subposets {P _i : 1ik} form a transitive basis of P if P is the transitive closure of their union. Let u be the minimum size of a covering of P by chains within posets of the basis, s the maximum size of a family of elements with no pair comparable in any basis poset, and a the maximum size of an antichain in P. Define a dense covering to be a collection D of chains within basis posets such that each element belongs to a chain in D within each basis poset and is the top of at least k-1 chains and the bottom of at least k-1 chains in D. Dense coverings generalize ordinary chain coverings of poset. Let d=min {|D|–(k–1)|P|}. For an arbitrary poset and transitive basis, a convenient network model for dense coverings yields the following: Theorem 1: da, with equality iff P has a minimum chain decomposition in which every pair of consecutive elements on each chain are comparable in some basis poset. Theorem 2: usda. Theorem 3: s=d iff s=a. The most interesting special case is where the transitive basis expresses P as the product of two posets, in which case u and s measure the minimum and maximum sizes of unichain coverings and semiantichains.     

A characterization of domination perfect graphs

Let γ(G) and i(G) be the domination number and independent domination number of a graph G, respectively. Sumner and Moore [8] define a graph G to be domination perfect if γ(H) = i(H), for every induced subgraph H of G. In this article, we give a finite forbidden induced subgraph characterization of domination perfect graphs. Bollobás and Cockayne [4] proved an inequality relating γ(G) and i(G) for the class of K^1,k -free graphs. It is shown that the same inequality holds for a wider class of graphs.     

Lacunary Quadrature Formulae and Interpolation Singularity

Birkholl quadrature formulae (q.f.), which have algebraic degree of precision (ADP) greater than the number of values used, are studied. In particular, we construct a class of quadrature rules of ADP = 2n + 2r + 1 which are based on the information {ƒ^(j)(−1), ƒ^(j)(−1), j = 0, ..., r − 1 ; ƒ(x_i), ƒ^(2m)(x_i), i = 1, ..., n}, where m is a positive integer and r = m, or r = m − 1. It is shown that the corresponding Birkhoff interpolation problems of the same type are not regular at the quadrature nodes. This means that the constructed quadrature formulae are not of interpolatory type. Finally, for each In, we prove the existence of a quadrature formula based on the information {ƒ(x_i), ƒ^(2m)(x_i), i = 1, ..., 2m}, which has algebraic degree of precision 4m + 1.     

Embedding ω-continuous posets in function spaces of domains

We prove a number of results, including the following: IfD is an ω-algebraic poset which is not an antichain, andE is an ω-continuous poset, then there exists a Scott-continuous order-embedding fromE to [D?D]; in particular, there exists a Scott-continuous order-embedding from (P(ω), ⊂-) to [D?D]. The proof of this main result does not use the Axiom of Choice.     

Zero dimensional and connected domains

We study continuous domains with bottomD such that every principal ideal inD is compact in the Lawson topology ofD. This class contains all objects of cartesian closed categories of continuous domains with bottom; it is also closed under arbitrary products and projection-embedding pairs. We employ the notion of apospace and useKoch's Arc Theorem to show that such a domainD is zero dimensional in its Lawson topology iffD is algebraic. This also classifies those continuous domainsD with bottom for which the Lawson topology λ(D) is a Stone Space. Finally, we give a criterion for the connectedness of the space λ(D) in terms of the poset of finite elements ofD and in terms of arc chains connecting bottom with every other element.     

On Poset Boolean Algebras

Let (P,≤) be a partially ordered set. The poset Boolean algebra of P, denoted F(P), is defined as follows: The set of generators of F(P) is {x _p  : p∈P}, and the set of relations is {x _p ⋅x _q =x _p  : p≤q}. We say that a Boolean algebra B is well-generated, if B has a sublattice G such that G generates B and (G,≤ ^B |G) is well-founded. A well-generated algebra is superatomic. THEOREM 1. Let (P,≤) be a partially ordered set. The following are equivalent. (i) P does not contain an infinite set of pairwise incomparable elements, and P does not contain a subset isomorphic to the chain of rational numbers, (ii) F(P) is superatomic, (iii) F(P) is well-generated. The equivalence (i) ⇔ (ii) is due to M. Pouzet. A partially ordered set W is well-ordered, if W does not contain a strictly decreasing infinite sequence, and W does not contain an infinite set of pairwise incomparable elements. THEOREM 2. Let F(P) be a superatomic poset algebra. Then there are a well-ordered set W and a subalgebra B of F(W), such that F(P) is a homomorphic image of B. This is similar but weaker than the fact that every interval algebra of a scattered chain is embeddable in an ordinal algebra. Remember that an interval algebra is a special case of a poset algebra. This revised version was published online in June 2006 with corrections to the Cover Date.     

How Close to Regular Must a Semicomplete Multipartite Digraph Be to Secure Hamiltonicity?

 Let D be a semicomplete multipartite digraph, with partite sets V ₁, V ₂,…, V _c, such that |V ₁|≤|V ₂|≤…≤|V _c|. Define f(D)=|V(D)|−3|V _c|+1 and . We define the irregularity i(D) of D to be max|d ⁺(x)−d ⁻(y)| over all vertices x and y of D (possibly x=y). We define the local irregularity i _l(D) of D to be max|d ⁺(x)−d ⁻(x)| over all vertices x of D and we define the global irregularity of D to be i _g(D)=max{d ⁺(x),d ⁻(x) : x∈V(D)}−min{d ⁺(y),d ⁻(y) : y∈V(D)}. In this paper we show that if i _g(D)≤g(D) or if i _l(D)≤min{f(D), g(D)} then D is Hamiltonian. We furthermore show how this implies a theorem which generalizes two results by Volkmann and solves a stated problem and a conjecture from [6]. Our result also gives support to the conjecture from [6] that all diregular c-partite tournaments (c≥4) are pancyclic, and it is used in [9], which proves this conjecture for all c≥5. Finally we show that our result in some sense is best possible, by giving an infinite class of non-Hamiltonian semicomplete multipartite digraphs, D, with i _g(D)=i(D)=i _l(D)=g(D)+?≤f(D)+1. Revised: September 17, 1998     

Partitioning Posets

Given a poset P = (X, ≺ ), a partition X ₁, ..., X _k of X is called an ordered partition of P if, whenever x ∈ X _i and y ∈ X _j with x ≺ y, then i ≤ j. In this paper, we show that for every poset P = (X, ≺ ) and every integer k ≥ 2, there exists an ordered partition of P into k parts such that the total number of comparable pairs within the parts is at most (m − 1)/k, where m ≥ 1 is the total number of edges in the comparability graph of P. We show that this bound is best possible for k = 2, but we give an improved bound, , for k ≥ 3, where c(k) is a constant depending only on k. We also show that, given a poset P = (X, ≺ ) and an integer 2 ≤ k ≤ |X|, we can find an ordered partition of P into k parts that minimises the total number of comparable pairs within parts in time polynomial in the size of P. We prove more general, weighted versions of these results. Supported by an EPSRC doctoral training grant.     

Random matrix products and applications to cellular automata

Let λ be the upper Lyapunov exponent corresponding to a product of i.i.d. randomm×m matrices (X _i) _i ^0/∞ over ℂ. Assume that theX _i's are chosen from a finite set {D ₀,D ₁...,D _t-1(ℂ), withP(X _i=D_j)>0, and that the monoid generated byD ₀, D₁,…, D_q−1 contains a matrix of rank 1. We obtain an explicit formula for λ as a sum of a convergent series. We also consider the case where theX _i's are chosen according to a Markov process and thus generalize a result of Lima and Rahibe [22]. Our results on λ enable us to provide an approximation for the numberN _≠0(F(x)ⁿ,r) of nonzero coefficients inF(x) ⁿ.(modr), whereF(x) ∈ ℤ[x] andr≥2. We prove the existence of and supply a formula for a constant α (<1) such thatN _≠0(F(x)ⁿ,r) ≈n ^α for “almost” everyn. Supported in part by FWF Project P16004-N05     

Pressure in Classical Statistical Mechanics and Interacting Brownian Particles in Multi-dimensions

. Let P(u) denote the pressure at the density u defined in the Gibbs statistical mechanics determined by a 2 body potential U (_qi - _qj). The function U(x) is supposed rotationally invariant and of finite range but may be unbounded about the origin. We establish a representation of P(u) by means of the law of large numbers for the virial ?_i,j q_i ·? U(q_i-q_j)\sum_{i,j} q_i \cdot {\nabla} U(q_i-q_j), whether or not there occur phase transitions. This result on P(u) is motivated by a study of the hydrodynamic behavior of a system of a large number of interacting Brownian particles moving on a d-dimensional torus (d = 1, 2, ...) in which the interaction is given by binary potential forces of potential U. Employing our representation of P(u), we also show that in the hydrodynamic limit of such a system there arises a non linear evolution equation of the form u_t = ¹/₂ DP(u)u_t = {1\over2} \Delta P(u) under a certain hypothetical postulate concerning concentration of particles.     

Path decompositions of multigraphs

Let G be a loopless finite multigraph. For each vertex x of G, denote its degree and multiplicity by d(x) and μ(x) respectively. Define Ø(x) = the least even integer ≥ μ(x), if d(x) is even, the least odd integer ≥ μ(x), if d(x) is odd. In this paper it is shown that every multigraph G admits a faithful path decomposition—a partition P of the edges of G into simple paths such that every vertex x of G is an end of exactly Ø(x) paths in P. This result generalizes Lovász's path decomposition theorem, Li's perfect path double cover theorem (conjectured by Bondy), and a result of Fan concerning path covers of weighted graphs. It also implies an upper bound on the number of paths in a minimum path decomposition of a multigraph, which motivates a generalization of Gallai's path decomposition conjecture. © 1995 John Wiley & Sons, Inc.     

Cleavages of graphs: the spectral radius

A cleavage of a finite graph G is a morphism f : H → G of graphs such that if P is the m × n characteristic matrix defined as P _ik = 1 if i ∈ f ^?1(k), otherwise = 0, then A(H)P ≤ PA(G), where A(G) and A(H) are the adjacency matrices of G and H, respectively. This concept generalizes induced subgraphs, quotients of graphs, Galois covers, path-tree graphs and others. We show that for spectral radii we have the inequality ρ(H) ≤ ρ(G). Equality holds only in case f : H → G is an equivariant quotient and H has isoperimetric constant i(H) = 0.     

Normal families and shared functions of meromorphic functions

Let k be a positive integer, let M be a positive number, let F be a family of meromorphic functions in a domain D, all of whose zeros are of multiplicity at least k, and let h be a holomorphic function in D, h ≢ 0. If, for every f ∈ F, f and f ^(k) share 0, and |f(z)| ≥ M whenever f ^(k)(z) = h(z), then F is normal in D. The condition that f and f ^(k) share 0 cannot be weakened, and the condition that |f(z)| ≥ M whenever f ^(k)(z) = h(z) cannot be replaced by the condition that |f(z)| ≥ 0 whenever f ^(k)(z) = h(z). This improves some results due to Fang and Zalcman [2] etc.     

Bose-Mesner Algebras Associated with Four-Weight Spin Models

It is known that for each matrix W _i and it's transpose ^t W _i in any four-weight spin model (X, W ₁, W ₂, W ₃, W ₄; D), there is attached the Bose-Mesner algebra of an association scheme, which we call Nomura algebra. They are denoted by N(W _i ) and N( ^t W _i ) = N′(W _i ) respectively. H. Guo and T. Huang showed that some of them coincide with a self-dual Bose-Mesner algebra, that is, N(W ₁) = N′(W ₁) = N(W ₃) = N′(W ₃) holds. In this paper we show that all of them coincide, that is, N(W _i ), N′(W _i ), i=1, 2, 3, 4, are the same self-dual Bose-Mesner algebra. Received: June 17, 1999 Final version received: Januray 17, 2000     

Quasi-periodic solutions for the general semilinear Duffing equations with asymmetric nonlinearity and oscillating potential

In this paper,we prove the existence of quasi-periodic solutions and the boundedness of all the solutions of the general semilinear quasi-periodic differential equation x′′+ax~+-bx~-=G_x(x,t)+f (t),where x~+=max{x,0},x~-=max{-x,0},a and b are two different positive constants,f(t) is C~(39) smooth in t,G(x,t)is C~(35) smooth in x and t,f (t) and G(x,t) are quasi-periodic in t with the Diophantine frequency ω=(ω_1,ω_2),and D_x~iD_t~jG(x,t) is bounded for 0≤i+j≤35.     

Davenport constant for semigroups

Let G be a finite commutative semigroup. The Davenport constant of G is the smallest integer d such that, every sequence S of d elements in G contains a subsequence T (≠S) with the same product of S. Let . Among other results, we determine D(R ^×)−D(U(R)), where R ^× is the multiplicative semigroup of R and U(R) is the group of units of R.