The class of infinite dimensional neat reducts of quasi‐polyadic algebras is not axiomatizable

SC, CA, QA and QEA denote the classes of Pinter's substitution algebras, Tarski's cylindric algebras, Halmos' quasi‐polyadic algebras and quasi‐polyadic equality algebras, respectively. Let ω ≤ α < β and let K ∈ {SC,CA,QA,QEA}. We show that the class of α ‐dimensional neat reducts of algebras in K_β is not elementary. This solves a problem in [3]. Also our result generalizes results proved in [2] and [3]. (© 2006 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

On the definition and the representability of quasi‐polyadic equality algebras

We show that the usual axiom system of quasi polyadic equality algebras is strongly redundant. Then, so called non‐commutative quasi‐polyadic equality algebras are introduced (), in which, among others, the commutativity of cylindrifications is dropped. As is known, quasi‐polyadic equality algebras are not representable in the classical sense, but we prove that algebras in are representable by quasi‐polyadic relativized set algebras, or more exactly by algebras in .     

Representations of polyadic-like equality algebras

Assuming the usual finite axiom schema of polyadic equality algebras, axiom (P10) is changed to a stronger version. It is proved that infinite dimensional, polyadic equality algebras satisfying the resulting system of axioms are representable. The foregoing stronger axiom is not given with a first order schema. The latter is to be expected knowing the negative results for the Halmos schema axiomatizability of the representable, infinite dimensional, polyadic equality algebras. Furthermore, Halmos’ well-known classical theorem that “locally finite polyadic equality algebras of infinite dimension α are representable” is generalized for locally-\({\mathfrak{m}}\) polyadic equality algebras, where \({\mathfrak{m}}\) is an arbitrary infinite cardinal and \({\mathfrak{m}}\) < α. Also, a neat embedding theorem is proved for the foregoing classes of polyadic-like equality algebras (a neat embedding theorem does not exists for polyadic equality algebras).     

On amalgamation of reducts of polyadic algebras

Following research initiated by Tarski, Craig and Németi, and further pursued by Sain and others, we show that for certain subsets G of w, G polyadic algebras have the strong amalgamation property. G polyadic algebras are obtained by restricting the (similarity type and) axiomatization of -dimensional polyadic algebras to finite quantifiers and substitutions in G. Using algebraic logic, we infer that some theorems of Beth, Craig and Robinson hold for certain proper extensions of first order logic (without equality).     

A construction of cylindric and polyadic algebras from atomic relation algebras

Given a simple atomic relation algebra ${\mathcal{A}}$ and a finite n ?? 3, we construct effectively an atomic n-dimensional polyadic equality-type algebra ${\mathcal{P}}$ such that for any subsignature L of the signature of ${\mathcal{P}}$ that contains the boolean operations and cylindrifications, the L-reduct of ${\mathcal{P}}$ is completely representable if and only if ${\mathcal{A}}$ is completely representable. If ${\mathcal{A}}$ is finite then so is ${\mathcal{P}}$ . It follows that there is no algorithm to determine whether a finite n-dimensional cylindric algebra, diagonal-free cylindric algebra, polyadic algebra, or polyadic equality algebra is representable (for diagonal-free algebras this was known). We also obtain a new proof that the classes of completely representable n-dimensional algebras of these types are non-elementary, a result that remains true for infinite dimensions if the diagonals are present, and also for infinite-dimensional diagonal-free cylindric algebras.     

Varieties of Algebras without the Amalgamation Property

Let α be an ordinal and κ be a cardinal, both infinite, such that κ ≤ |α|. For τ ∈^αα, let sup(τ) = {i ∈ α: τ(i) ≠ i}. Let G _κ = {τ ∈^αα: |sup(τ)| < κ}. We consider variants of polyadic equality algebras by taking cylindrifications on Γ ? α, |Γ| < κ and substitutions restricted to G _κ. Such algebras are also enriched with generalized diagonal elements. We show that for any variety V containing the class of representable algebas and satisfying a finite schema of equations, V fails to have the amalgamation property. In particular, many varieties of Halmos’ quasi-polyadic equality algebras and Lucas’ extended cylindric algebras (including that of the representable algebras) fail to have the amalgamation property.     

On notions of representability for cylindric‐polyadic algebras,and a solution to the finitizability problem for quantifier logics with equality

We consider countable so‐called rich subsemigroups of ; each such semigroup T gives a variety CPEA_T that is axiomatizable by a finite schema of equations taken in a countable subsignature of that of ω‐dimensional cylindric‐polyadic algebras with equality where substitutions are restricted to maps in T. It is shown that for any such T, if and only if is representable as a concrete set algebra of ω‐ary relations. The operations in the signature are set‐theoretically interpreted like in polyadic equality set algebras, but such operations are relativized to a union of cartesian spaces that are not necessarily disjoint. This is a form of guarding semantics. We show that CPEA_T is canonical and atom‐canonical. Imposing an extra condition on T, we prove that atomic algebras in CPEA_T are completely representable and that CPEA_T has the super amalgamation property. If T is rich and finitely represented, it is shown that CPEA_T is term definitionally equivalent to a finitely axiomatizable Sahlqvist variety. Such semigroups exist. This can be regarded as a solution to the central finitizability problem in algebraic logic for first order logic with equality if we do not insist on full fledged commutativity of quantifiers. The finite dimensional case is approached from the view point of guarded and clique guarded (relativized) semantics of fragments of first order logic using finitely many variables. Both positive and negative results are presented.     

Archimedean classes in integral commutative residuated chains

This paper investigates a quasi‐variety of representable integral commutative residuated lattices axiomatized by the quasi‐identity resulting from the well‐known Wajsberg identity (p → q) → q ≤ (q → p) → p if it is written as a quasi‐identity, i. e., (p → q) → q ≈ 1 ? (q → p) → p ≈ 1 . We prove that this quasi‐identity is strictly weaker than the corresponding identity. On the other hand, we show that the resulting quasi‐variety is in fact a variety and provide an axiomatization. The obtained results shed some light on the structure of Archimedean integral commutative residuated chains. Further, they can be applied to various subvarieties of MTL‐algebras, for instance we answer negatively Hájek's question asking whether the variety of ΠMTL‐algebras is generated by its Archimedean members (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

On some sets of dictionaries whose ω ‐powers have a given

A dictionary is a set of finite words over some finite alphabet X. The ω ‐power of a dictionary V is the set of infinite words obtained by infinite concatenation of words in V. Lecomte studied in [10] the complexity of the set of dictionaries whose associated ω ‐powers have a given complexity. In particular, he considered the sets ??( Σ ⁰k) (respectively, ??( Π ⁰_k), ??( Δ ¹₁)) of dictionaries V ? 2* whose ω ‐powers are Σ ⁰_k‐sets (respectively, Π ⁰_k‐sets, Borel sets). In this paper we first establish a new relation between the sets ??( Σ ⁰₂) and ??( Δ ¹₁), showing that the set ??( Δ ¹₁) is “more complex” than the set ??( Σ ⁰₂). As an application we improve the lower bound on the complexity of ??( Δ ¹₁) given by Lecomte, showing that ??( Δ ¹₁) is in Σ ¹ ₂(2^2*)\ Π ⁰₂. Then we prove that, for every integer k ≥ 2 (respectively, k ≥ 3), the set of dictionaries ??( Π ⁰_k+1) (respectively, ??( Σ ⁰_{k +1})) is “more complex” than the set of dictionaries ??( Π ⁰_k) (respectively, ??( Σ ⁰_k)) (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

A local limit theorem for the number of nodes,the height,and the number of final leaves in a critical branching process tree

Let Z_i be the number of particles in the ith generation of a non-degenerate critical Bienaymé-Galton-Watson process with offspring distribution $ p_r = P \{\hbox{a given individual has {\it r} children}\},\kern2em r\geq 0. $ Let ν = Σ^infinity₀ Z_j be the total progeny and let ζ = inf{r: Z_r = 0} be the extinction time. Equivalently, ν and ζ are the total number of nodes and (1 + the height), respectively, of the family tree of the branching process. Assume that E{Z₁} = Σ p_rr = 1 and E{Z₁^{3 + δ}} = Σ p_rr^{3 + δ} < infinity for some δ ϵ (0, 1). We find an asymptotic formula with remainder term for k⁴P{ζ = k + 1, Z_k = ℓ ν = n} when k→ infinity, which is uniform over n and ℓ. This is used to confirm a conjecture by Wilf that the number of leaves in the last generation of a randomly chosen rooted tree converges in distribution. More precisely, in the terminology introduced above, there exists a probability distribution {q₁} such that for n → infinity $ P\{Z_{\zeta-1} = l | \nu=n\} = q_l + O \left({{\log^3 n } \over {n^{1/2}}}\right), $ uniformly over ℓ ≥1. The limiting distribution is identified by means of a functional equation for the generating function Σ^infinity₁ q s^ℓ. Numerically, q₁ ≅ 0.0602, q₂ ≅ 0.248, q₃ ≅ 0.094, and q₄ ≅ 0.035. Our method can also be used to find lim _{k→ infinity} k⁴P{ζ = k + 1, Z_k = ℓ ν = n} when only E{Z₁^{2 + δ}} < infinity for some 0 ≤δ≤1, but we do not treat this case here; it goes without saying that the fewer moment assumptions one makes, the poorer the estimates become. © 1996 John Wiley & Sons, Inc.     

Quasi‐randomness of graph balanced cut properties

Quasi‐random graphs can be informally described as graphs whose edge distribution closely resembles that of a truly random graph of the same edge density. Recently, Shapira and Yuster proved the following result on quasi‐randomness of graphs. Let k ≥ 2 be a fixed integer, α₁,…,α_k be positive reals satisfying \begin{align*}\sum_{i} \alpha_i = 1\end{align*} and (α₁,…,α_k)≠(1/k,…,1/k), and G be a graph on n vertices. If for every partition of the vertices of G into sets V ₁,…,V _k of size α₁n,…,α_kn, the number of complete graphs on k vertices which have exactly one vertex in each of these sets is similar to what we would expect in a random graph, then the graph is quasi‐random. However, the method of quasi‐random hypergraphs they used did not provide enough information to resolve the case (1/k,…,1/k) for graphs. In their work, Shapira and Yuster asked whether this case also forces the graph to be quasi‐random. Janson also posed the same question in his study of quasi‐randomness under the framework of graph limits. In this paper, we positively answer their question. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011     

A Modeltheoretic Solution to a Problem of Tarski

Let 1 < n < ω and β > n. We show that the class Nr_nCA_β of n‐dimensional neat reducts of β‐dimensional cylindric algebras is not closed under forming elementary subalgebras. This solves a long‐standing open problem of Tarski and his co‐authors Andréka, Henkin, Monk and Németi. The proof uses genuine model‐theoretic arguments.     

Weak quasi‐randomness for uniform hypergraphs

We study quasi‐random properties of k‐uniform hypergraphs. Our central notion is uniform edge distribution with respect to large vertex sets. We will find several equivalent characterisations of this property and our work can be viewed as an extension of the well known Chung‐Graham‐Wilson theorem for quasi‐random graphs. Moreover, let K_k be the complete graph on k vertices and M(k) the line graph of the graph of the k‐dimensional hypercube. We will show that the pair of graphs (K_k,M(k)) has the property that if the number of copies of both K_k and M(k) in another graph G are as expected in the random graph of density d, then G is quasi‐random (in the sense of the Chung‐Graham‐Wilson theorem) with density close to d. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011     

On the structure of the sumsets

Let A be a set of nonnegative integers. For h≥2, denote by hA the set of all the integers representable by a sum of h elements from A. In this paper, we prove that, if k≥3, and A={a₀,a₁,…,a_k−1} is a finite set of integers such that 0=a₀<a₁<?<a_k−1 and (a₁,…,a_k−1)=1, then there exist integers c and d and sets C⊆[0,c−2] and D⊆[0,d−2] such that hA=C∪[c,ha_k−1−d]∪(ha_k−1−D) for all . The result is optimal. This improves Nathanson’s result: h≥max{1,(k−2)(a_k−1−1)a_k−1}.     

Quasi‐random hypergraphs revisited

The quasi‐random theory for graphs mainly focuses on a large equivalent class of graph properties each of which can be used as a certificate for randomness. For k ‐graphs (i.e., k ‐uniform hypergraphs), an analogous quasi‐random class contains various equivalent graph properties including the k ‐discrepancy property (bounding the number of edges in the generalized induced subgraph determined by any given (k ‐ 1) ‐graph on the same vertex set) as well as the k ‐deviation property (bounding the occurrences of “octahedron”, a generalization of 4 ‐cycle). In a 1990 paper (Chung, Random Struct Algorithms 1 (1990) 363‐382), a weaker notion of l ‐discrepancy properties for k ‐graphs was introduced for forming a nested chain of quasi‐random classes, but the proof for showing the equivalence of l ‐discrepancy and l ‐deviation, for 2 ≤ l < k, contains an error. An additional parameter is needed in the definition of discrepancy, because of the rich and complex structure in hypergraphs. In this note, we introduce the notion of (l,s) ‐discrepancy for k ‐graphs and prove that the equivalence of the (k,s) ‐discrepancy and the s ‐deviation for 1 ≤ s ≤ k. We remark that this refined notion of discrepancy seems to point to a lattice structure in relating various quasi‐random classes for hypergraphs. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011     

Euler‐lagrange equation and regularity for flat minimizers of the Willmore functional

Let \input amssym $S\subset{\Bbb R}^2$ be a bounded domain with boundary of class C^∞, and let g_ij = δ_ij denote the flat metric on \input amssym ${\Bbb R}^2$ . Let u be a minimizer of the Willmore functional within a subclass (defined by prescribing boundary conditions on parts of ∂S) of all W^2,2 isometric immersions of the Riemannian manifold (S, g) into \input amssym ${\Bbb R}^3$ . In this article we derive the Euler‐Lagrange equation and study the regularity properties for such u. Our main regularity result is that minimizers u are C³ away from a certain singular set Σ and C^∞ away from a larger singular set Σ ∪ Σ₀. We obtain a geometric characterization of these singular sets, and we derive the scaling of u and its derivatives near Σ₀. Our main motivation to study this problem comes from nonlinear elasticity: On isometric immersions, the Willmore functional agrees with Kirchhoff's energy functional for thin elastic plates. © 2010 Wiley Periodicals, Inc.     

On disjointly representable sets

A system of setsE ₁,E ₂, ...,E _k ⊂X is said to be disjointly representable if there existx ₁,x ₂, ...,x _k teX such thatx _i teE _j ⇔i=j. Letf(r, k) denote the maximal size of anr-uniform set-system containing nok disjointly representable members. In the first section the exact value off(r, 3) is determined and (asymptotically sharp) bounds onf(r, k),k>3 are established. The last two sections contain some generalizations, in particular we prove an analogue of Sauer’ theorem [16] for uniform set-systems. Dedicated to Paul Erdős on his seventieth birthday     

3‐Coloring graphs embedded in surfaces

In this article, we show that there exists an integer k(Σ) ≥ 5 such that, if G is a graph embedded in a surface Σ without i‐circuits, 4 ≤ i ≤ k(Σ), then G is 3‐colorable. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 140–143, 2000     

Quasi‐graphic matroids*

Frame matroids and lifted‐graphic matroids are two interesting generalizations of graphic matroids. Here, we introduce a new generalization, quasi‐graphic matroids, that unifies these two existing classes. Unlike frame matroids and lifted‐graphic matroids, it is easy to certify that a 3‐connected matroid is quasi‐graphic. The main result is that every 3‐connected representable quasi‐graphic matroid is either a lifted‐graphic matroid or a frame matroid.     

On the divisor function of sets with even partition functions

Summary For P∈ F₂[z] with P(0)=1 and deg(P)≧ 1, let A =A(P) be the unique subset of N (cf. [9]) such that Σ_n≧0 p(A,n)zⁿ ≡ P(z) mod 2, where p(A,n) is the number of partitions of n with parts in A. To determine the elements of the set A, it is important to consider the sequence σ(A,n) = Σ _{d|n, d∈A} d, namely, the periodicity of the sequences (σ(A,2^kn) mod 2^k+1)_n≧1 for all k ≧ 0 which was proved in [3]. In this paper, the values of such sequences will be given in terms of orbits. Moreover, a formula to σ(A,2^kn) mod 2^k+1 will be established, from which it will be shown that the weight σ(A₁,2^kz_i) mod 2^k+1 on the orbit <InlineEquation ID=IE"1"><EquationSource Format="TEX"><![CDATA[<InlineEquation ID=IE"2"><EquationSource Format="TEX"><![CDATA[$]]></EquationSource></InlineEquation>]]></EquationSource></InlineEquation>z_i$ is moved on some other orbit z_j when A₁ is replaced by A₂ with A₁= A(P₁) and A₂= A(P₂) P₁ and P₂ being irreducible in F₂[z] of the same odd order.