On MODkP Counting Degrees

For a prime k, the embeddability of finite lattices are discussed for various kind of the MOD_kP degrees of recursive sets. In particular, all finite lattices are embeddable into the MOD_kP Turing degrees, whereas the non distributive lattice M₃ is embeddable into the MOD₂P many-one degrees but N₅ is not.     

More Sublattices of the Lattice of Local Clones

We investigate the complexity of the lattice of local clones over a countably infinite base set. In particular, we prove that this lattice contains all algebraic lattices with at most countably many compact elements as complete sublattices, but that the class of lattices embeddable into the local clone lattice is strictly larger than that: For example, the lattice M_2^wM_{2^\omega} is a sublattice of the local clone lattice.     

Substructure lattices and almost minimal end extensions of models of Peano arithmetic

This paper concerns intermediate structure lattices Lt(??/??), where ?? is an almost minimal elementary end extension of the model ?? of Peano Arithmetic. For the purposes of this abstract only, let us say that ?? attains L if L ? Lt(??/??) for some almost minimal elementary end extension of ??. If T is a completion of PA and L is a finite lattice, then: (A) If some model of T attains L, then every countable model of T does. (B) If some rather classless, ?₁‐saturated model of T attains L, then every model of T does. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Enumerating Motzkin–Rabin geometries

The main result of this paper is an enumeration of all Motzkin‐Rabin geometries on up to 18 points. A Motzkin‐Rabin geometry is a two‐colored linear space with no monochromatic line. We also study the embeddings of Motzkin‐Robin geometries into projective spaces over fields and division rings. We find no Motzkin‐Rabin geometries on up to 18 points embeddable in ?² or ??₂(t)². We find many examples of Motzkin‐Rabin geometries with no proper linear subspaces. We give an example of a proper linear space embeddable in ?(?( )²). © 2006 Wiley Periodicals, Inc. J Combin Designs 15: 179–194, 2007     

A splitting theorem for the Medvedev and Muchnik lattices

This is a contribution to the study of the Muchnik and Medvedev lattices of non‐empty Π⁰₁ subsets of 2^ω. In both these lattices, any non‐minimum element can be split, i. e. it is the non‐trivial join of two other elements. In fact, in the Medvedev case, ifP > _M Q, then P can be split above Q. Both of these facts are then generalised to the embedding of arbitrary finite distributive lattices. A consequence of this is that both lattices have decidible ?‐theories.     

Reducible classes of finite lattices

In this paper we study a notion of reducibility in finite lattices. An element x of a (finite) lattice L satisfying certain properties is deletable if L-x is a lattice satisfying the same properties. A class of lattices is reducible if each lattice of this class admits (at least) one deletable element (equivalently if one can go from any lattice in this class to the trivial lattice by a sequence of lattices of the class obtained by deleting one element in each step). First we characterize the deletable elements in a pseudocomplemented lattice what allows to prove that the class of pseudocomplemented lattices is reducible. Then we characterize the deletable elements in semimodular, modular and distributive lattices what allows to prove that the classes of semimodular and locally distributive lattices are reducible. In conclusion the notion of reducibility for a class of lattices is compared with some other notions like the notion of order variety.     

1‐Rotational Steiner triple systems over arbitrary groups

Phelps and Rosa introduced the concept of 1‐rotational Steiner triple system, that is an STS(ν) admitting an automorphism consisting of a fixed point and a single cycle of length ν ? 1 [Discrete Math. 33 ( 12 ), 57–66]. They proved that such an STS(ν) exists if and only if ν ≡ 3 or 9 (mod 24). Here, we speak of a 1‐rotational STS(ν) in a more general sense. An STS(ν) is 1‐rotational over a group G when it admits G as an automorphism group, fixing one point and acting regularly on the other points. Thus the STS(ν)'s by Phelps and Rosa are 1‐rotational over the cyclic group. We denote by ??_1r, ??_1r, ??_1r, ??_1r, the spectrum of values of ν for which there exists a 1‐rotational STS(ν) over an abelian, a cyclic, a dicyclic, and an arbitrary group, respectively. In this paper, we determine ??_1r and find partial answers about ??_1r and ??_1r. The smallest 1‐rotational STSs have orders 9, 19, 25 and are unique up to isomorphism. In particular, the only 1‐rotational STS(25) is over SL₂(3), the special linear group of dimension 2 over Z₃. © 2001 John Wiley & Sons, Inc. J Combin Designs 9: 215–226, 2001     

A technique for constructing non‐embeddable quasi‐residual designs

We propose a technique for constructing two infinite families of non‐embeddable quasi‐residual designs as soon as one such design satisfying certain conditions exists. The main tools are generalized Hadamard matrices and balanced generalized weighing matrices. Starting with a specific non‐embeddable quasi‐residual 2‐(27,9,4) design, we construct for every positive integer m a non‐embeddable 2‐(3^m,3^m?1,(3^m?1?1)/2)‐design, and, if r_m=(3^m?1)/2 is a prime power, we construct for every positive integer n a non‐embeddable design. For each design in these families, a symmetric design with the corresponding parameters is known to exist. © 2002 Wiley Periodicals, Inc. J Combin Designs 10: 160–172, 2002; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.900     

Symmetries that latin squares inherit from 1‐factorizations

A 1‐factorization of a graph is a decomposition of the graph into edge disjoint perfect matchings. There is a well‐known method, which we call the ??‐construction, for building a 1‐factorization of K_n,n from a 1‐factorization of K_{n + 1}. The 1‐factorization of K_n,n can be written as a latin square of order n. The ??‐construction has been used, among other things, to make perfect 1‐factorizations, subsquare‐free latin squares, and atomic latin squares. This paper studies the relationship between the factorizations involved in the ??‐construction. In particular, we show how symmetries (automorphisms) of the starting factorization are inherited as symmetries by the end product, either as automorphisms of the factorization or as autotopies of the latin square. Suppose that the ??‐construction produces a latin square L from a 1‐factorization F of K_{n + 1}. We show that the main class of L determines the isomorphism class of F, although the converse is false. We also prove a number of restrictions on the symmetries (autotopies and paratopies) which L may possess, many of which are simple consequences of the fact that L must be symmetric (in the usual matrix sense) and idempotent. In some circumstances, these restrictions are tight enough to ensure that L has trivial autotopy group. Finally, we give a cubic time algorithm for deciding whether a main class of latin squares contains any square derived from the ??‐construction. The algorithm also detects symmetric squares and totally symmetric squares (latin squares that equal their six conjugates). © 2005 Wiley Periodicals, Inc. J Combin Designs 13: 157–172, 2005.     

Vanishing thetanull and hyperelliptic curves

Let ??_g,2 be the moduli space of curves of genus g with a level‐2 structure. We prove here that there is always a non hyperelliptic element in the intersection of four thetanull divisors in ??_6,2. We prove also that for all g ≥ 3, each component of the hyperelliptic locus in ??_g,2 is a connected component of the intersection of g – 2 thetanull divisors. (© 2007 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Regions of variability for convex functions

Let ?? be the class of convex univalent functions f in the unit disc ?? normalized by f (0) = f ′(0) – 1 = 0. For z ₀ ∈ ?? and |λ | ≤ 1 we shall determine explicitly the regions of variability {log f ′(z ₀): f ∈ ??, f ″(0) = 2λ }. (© 2006 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Linear lower bounds for δc(p) for a class of 2D self‐destructive percolation models

The self‐destructive percolation model is defined as follows: Consider percolation with parameter p > p_c. Remove the infinite occupied cluster. Finally, give each vertex (or, for bond percolation, each edge) that at this stage is vacant, an extra chance δ to become occupied. Let δ_c(p) be the minimal value of δ, needed to obtain an infinite occupied cluster in the final configuration. This model was introduced by van den Berg and Brouwer. They showed, for the site model on the square lattice (and a few other 2D lattices satisfying a special technical condition) that δ_c(p) ≥ . In particular, δ_c(p) is at least linear in p ? p_c. Although the arguments used by van den Berg and Brouwer look very lattice‐specific, we show that they can be suitably modified to obtain similar linear lower bounds for δ_c(p) (with p near p_c) for a much larger class of 2D lattices, including bond percolation on the square and triangular lattices, and site percolation on the star lattice (or matching lattice) of the square lattice. © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009     

Tychonoff products of compact spaces in ZF and closed ultrafilters

Let {(X_i, T_i): i ∈I } be a family of compact spaces and let X be their Tychonoff product. ??(X) denotes the family of all basic non‐trivial closed subsets of X and ??_R(X) denotes the family of all closed subsets H = V × ΠX_i of X, where V is a non‐trivial closed subset of ΠX_i and Q_H is a finite non‐empty subset of I. We show: (i) Every filterbase ?? ? ??_R(X) extends to a ??_R(X)‐ultrafilter ? if and only if every family H ? ??(X) with the finite intersection property (fip for abbreviation) extends to a maximal ??(X) family F with the fip. (ii) The proposition “if every filterbase ?? ? ??_R(X) extends to a ??_R(X)‐ultrafilter ?, then X is compact” is not provable in ZF. (iii) The statement “for every family {(X_i, T_i): i ∈ I } of compact spaces, every filterbase ?? ? ??_R(Y), Y = Π_{i ∈I}Y_i, extends to a ??_R(Y)‐ultrafilter ?” is equivalent to Tychonoff's compactness theorem. (iv) The statement “for every family {(X_i, T_i): i ∈ ω } of compact spaces, every countable filterbase ?? ? ??_R(X), X = Π_{i ∈ω}X_i, extends to a ??_R(X)‐ultrafilter ?” is equivalent to Tychonoff's compactness theorem restricted to countable families. (v) The countable Axiom of Choice is equivalent to the proposition “for every family {(X_i, T_i): i ∈ ω } of compact topological spaces, every countable family ?? ? ??(X) with the fip extends to a maximal ??(X) family ? with the fip” (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Strengthening Erdös–Pósa property for minor‐closed graph classes

Let ?? and ?? be graph classes. We say that ?? has the Erd?s–Pósa property for ?? if for any graph G ∈??, the minimum vertex covering of all ??‐subgraphs of G is bounded by a function f of the maximum packing of ??‐subgraphs in G (by ??‐subgraph of G we mean any subgraph of G that belongs to ??). Robertson and Seymour [J Combin Theory Ser B 41 (1986), 92–114] proved that if ?? is the class of all graphs that can be contracted to a fixed planar graph H, then ?? has the Erd?s–Pósa property for the class of all graphs with an exponential bounding function. In this note, we prove that this function becomes linear when ?? is any non‐trivial minor‐closed graph class. © 2010 Wiley Periodicals, Inc. J Graph Theory 66:235‐240, 2011     

A generalization of Turán's theorem

In this paper, we obtain an asymptotic generalization of Turán's theorem. We prove that if all the non‐trivial eigenvalues of a d‐regular graph G on n vertices are sufficiently small, then the largest K_t‐free subgraph of G contains approximately (t ? 2)/(t ? 1)‐fraction of its edges. Turán's theorem corresponds to the case d = n ? 1. © 2005 Wiley Periodicals, Inc. J Graph Theory     

Comparing First Order Theories of Modules over Group Rings

We consider R‐torsionfree modules over group rings RG, where R is a Dedekind domain and G is a finite group. We compare the (first order) theory T of al these modules and the theory T₀ of the finitely generated ones (so of RG‐lattices). It is easy to realize that they are equal iff R is a field. The obstruction is the existence of R‐divisible R‐torsionfree RG‐modules. Accordingly we consider R‐reduced R‐torsionfree RG‐modules for a local R. We show that the key conditions ensuring that their theory equals T₀ are: (1) RG‐lattices have a finite representation type; (2) each attice over the completion R̂G is isomorphic to the completion of some RG‐lattice.Some related questions are discussed.     

ω‐categorical weakly o‐minimal expansions of Boolean lattices

We study ω‐categorical weakly o‐minimal expansions of Boolean lattices. We show that a structure ?? = (A,≤, ?) expanding a Boolean lattice (A,≤) by a finite sequence I of ideals of A closed under the usual Heyting algebra operations is weakly o‐minimal if and only if it is ω‐categorical, and hence if and only if A/I has only finitely many atoms for every I ∈ ?. We propose other related examples of weakly o‐minimal ω‐categorical models in this framework, and we examine the internal structure of these models.     

LatticeW algebras and quantum groups

We present Feigin's construction [Lectures given in Landau Institute] of latticeW algebras and give some simple results: lattice Virasoro andW ₃ algebras. For the simplest caseg=sl(2), we introduce the wholeU _q(2)) quantum group on this lattice. We find the simplest two-dimensional module as well as the exchange relations and define the lattice Virasoro algebra as the algebra of invariants ofU _q(sl(2)). Another generalization is connected with the lattice integrals of motion as the invariants of the quantum affine groupU _q(ñ₊). We show that Volkov's scheme leads to a system of difference equations for a function of non-commutative variables.Landau Institute for Theoretical Physics, 142432, Chernogolovka, Russia. Published in Teoreticheskaya i Matematicheskaya Fizika, Vol. 100, No. 1, pp. 132–147, July, 1994.     

Inequalities for convex bodies and polar reciprocal lattices inR n

LetL be a lattice and letU be ano-symmetric convex body inR ⁿ . The Minkowski functional ∥ ∥ _U ofU, the polar bodyU ⁰, the dual latticeL ^*, the covering radius μ(L, U), and the successive minima λ _i (L,U)i=1,...,n, are defined in the usual way. Let ℒ _n be the family of all lattices inR ⁿ . Given a pairU,V of convex bodies, we define and kh(U, V) is defined as the smallest positive numbers for which, given arbitraryL∈ℒ _n andu∈R ⁿ /(L+U), somev∈L ^* with ∥v∥ _V ≤sd(uv, ℤ) can be found. Upper bounds for jh(U, U ⁰), j=k, l, m, belong to the so-called transference theorems in the geometry of numbers. The technique of Gaussian-like measures on lattices, developed in an earlier paper [4] for euclidean balls, is applied to obtain upper bounds for jh(U, V) in the case whenU, V aren-dimensional ellipsoids, rectangular parallelepipeds, or unit balls inl _p ⁿ , 1≤p≤∞. The gaps between the upper bounds obtained and the known lower bounds are, roughly speaking, of order at most logn asn→∞. It is also proved that ifU is symmetric through each of the coordinate hyperplanes, then jh(U, U ⁰) are less thanCn logn for some numerical constantC.