Ramsey Properties of Finite Posets II

We classify Fra?ssé classes of finite posets with convex linear orderings with respect to the Ramsey property and extend the list of extremely amenable groups and universal minimal flows thanks to a theory developed by Kechris et al. (Geom Funct Anal 15:106–189, 2005). For the structures from the Schmerl list for which this technique is not applicable, we provide a direct calculation of universal minimal flows.     

Categorical equivalence and the Ramsey property for finite powers of a primal algebra

In this paper, we investigate the best known and most important example of a categorical equivalence in algebra, that between the variety of boolean algebras and any variety generated by a single primal algebra. We consider this equivalence in the context of Kechris-Pestov-Todor?evi? correspondence, a surprising correspondence between model theory, combinatorics and topological dynamics. We show that relevant combinatorial properties (such as the amalgamation property, Ramsey property and ordering property) carry over from a category to an equivalent category. We then use these results to show that the category whose objects are isomorphic copies of finite powers of a primal algebra \({\mathcal{A}}\) together with a particular linear ordering <, and whose morphisms are embeddings, is a Ramsey age (and hence a Fraïssé age). By the Kechris-Pestov-Todor?evi? correspondence, we then infer that the automorphism group of its Fraïssé limit is extremely amenable. This correspondence also enables us to compute the universal minimal flow of the Fraïssé limit of the class \({{\bf V}_{fin} \mathcal{(A)}}\) whose objects are isomorphic copies of finite powers of a primal algebra \({\mathcal{A}}\) and whose morphisms are embeddings.     

Ramsey degrees of boron tree structures

We investigate the combinatorial properties of the Fraïssé class of structures induced by the leaf sets of boron trees — graph-theoretic binary trees without an assigned root — and compute their Ramsey degrees. The Ramsey degree of a boron tree structure is shown to equal the number of its possible orientations, which are herein defined to depend on the embedding of the said structure. One direction of this computation involves an asymmetric version of the Graham-Rothschild theorem. By expanding these structures to oriented ones, we arrive at a Fraïssé class which possesses the Ramsey property. Consequently, the automorphism group of its Fraïssé limit is extremely amenable, i.e., it possesses a very strong fixed point property. Furthermore, we construct the universal minimal flow of the automorphism group of this limit.     

Ramsey property, ultrametric spaces, finite posets, and universal minimal flows

We introduce the class COU _S of finite ultrametric spaces with distances in the set S and with two additional linear orderings. We also introduce the class EOP of finite posets with two additional linear orderings. In this paper, we prove that COU _S and EOP are Ramsey classes. In addition, we give an application of our results to calculus of universal minimal flows.     

Axiomatisability and hardness for universal Horn classes of hypergraphs

We consider hypergraphs as symmetric relational structures. In this setting, we characterise finite axiomatisability for finitely generated universal Horn classes of loop-free hypergraphs. An Ehrenfeucht–Fraïssé game argument is employed to show that the results continue to hold when restricted to first order definability amongst finite structures. We are also able to show that every interval in the homomorphism order on hypergraphs contains a continuum of universal Horn classes and conclude the article by characterising the intractability of deciding membership in universal Horn classes generated by finite loop-free hypergraphs.     

Automorphism Groups of Countably Categorical Linear Orders are Extremely Amenable

We show that the automorphism groups of countably categorical linear orders are extremely amenable. Using methods of Kechris, Pestov, and Todorcevic, we use this fact to derive a structural Ramsey theorem for certain families of finite ordered structures with finitely many partial equivalence relations with convex classes.     

Symmetrized Induced Ramsey Theory

We prove induced Ramsey theorems in which the monochromatic induced subgraph satisfies that all members of a prescribed set of its partial isomorphisms extend to automorphisms of the colored graph (without requirement of preservation of colors). We consider vertex and edge colorings, and extensions of partial isomorphisms in the set of all partial isomorphisms between singletons as considered by Babai and Sós (European J Combin 6(2):101–114, 1985), the set of all finite partial isomorphisms as considered by Hrushovski (Combinatorica 12(4):411–416, 1992), Herwig (Combinatorica 15:365–371, 1995) and Herwig-Lascar (Trans Amer Math Soc 5:1985–2021, 2000), and the set of all total isomorphisms. We observe that every finite graph embeds into a finite vertex transitive graph by a so called bi-embedding, an embedding that is compatible with a monomorphism between the corresponding automorphism groups. We also show that every countable graph bi-embeds into Rado’s universal countable graph Γ.     

Universal and homogeneous structures on the Urysohn and Gurarij spaces

Using Fraïssé theoretic methods we enrich the Urysohn universal space by universal and homogeneous closed relations, retractions, closed subsets of the product of the Urysohn space itself and some fixed compact metric space, L-Lipschitz map to a fixed Polish metric space. The latter lifts to a universal linear operator of norm L on the Lispchitz-free space of the Urysohn space.Moreover, we enrich the Gurarij space by a universal and homogeneous closed subspace and norm one projection onto a 1-complemented subspace. We construct the Gurarij space by the classical Fraïssé theoretic approach.     

A Ramsey theorem for multiposets

In the parlance of relational structures, the Finite Ramsey Theorem states that the class of all finite chains has the Ramsey property. A classical result from the 1980s claims that the class of all finite posets with a linear extension has the Ramsey property. In 2010 Sokić proved that the class of all finite structures consisting of several linear orders has the Ramsey property. This was followed by a 2017 result of Solecki and Zhao that the class of all finite posets with several linear extensions has the Ramsey property.Using the categorical reinterpretation of the Ramsey property in this paper we prove a common generalization of all these results. We consider multiposets to be structures consisting of several partial orders and several linear orders. We allow partial orders to extend each other in an arbitrary but fixed way, and require that every partial order is extended by at least one of the linear orders. We then show that the class of all finite multiposets conforming to a fixed template has the Ramsey property.     

Domination Number of Certain Infinite Tournaments

We consider tournaments defined by several linear orderings of the vertex set according to some rule specifying the direction of each arc depending only on the order of the end vertices in each of the orderings. In the finite case, it was proved in Alon et al. (J Comb Theory Ser B 96:374–387, 2006) that the domination number of such tournaments is bounded in terms of the rule only. We show that for infinite tournaments, under some natural restrictions, the domination number is always finite, though in general cannot be bounded. We give some sufficient conditions under which there exists an upper bound in terms of the rule and/or the order types, and provide examples demonstrating that the bounds obtained are not very far from truth.     

Irreducible Width 2 Posets of Linear Discrepancy 3

The linear discrepancy of a poset P is the least k such that there is a linear extension L of P such that if x and y are incomparable in P, then |h _L (x) − h _L (y)| ≤ k, where h _L (x) is the height of x in L. Tannenbaum, Trenk, and Fishburn characterized the posets of linear discrepancy 1 as the semiorders of width 2 and posed the problem for characterizing the posets of linear discrepancy 2. Howard et al. (Order 24:139–153, 2007) showed that this problem is equivalent to finding all posets of linear discrepancy 3 such that the removal of any point reduces the linear discrepancy. In this paper we determine all of these minimal posets of linear discrepancy 3 that have width 2. We do so by showing that, when removing a specific maximal point in a minimal linear discrepancy 3 poset, there is a unique linear extension that witnesses linear discrepancy 2. The first author was supported during this research by National Science foundation VIGRE grant DMS-0135290.     

The Partial Ordering on the Automorphism Group of the Countable Generic Partial Order

The countable generic poset (P,?≤?) is the Fraïssé limit of the amalgamation class of finite partially ordered sets (see Glass et al., Math Z 214:55–66, 1993; Schmerl, Algebra Univers 9:317–321, 1979). It is homogeneous and \(\aleph_0\)-categorical with quantifier elimination. This paper concerns the structure (G,?°?,?≤?), where \((G,\circ)=\textrm{Aut}(P,\leq)\) and ≤ is the pointwise ordering on G. This is a natural structure to look at, because the ordering on G is ?-definable up to reversal in the language {?°?} (but this fact is not proved here). In this paper I show that (G,?≤?) is elementarily equivalent to (P,?≤?) itself. More generally, (G,?°?,?≤?) satisfies a weakening of the existential closure property for partially ordered groups. (Existential closure in groups has been studied for example in Higman and Scott.) This requires one to study the group G ^???, obtained by freely adjoining a finite set of generators to G.     

The Weil-��tale fundamental group of a number field II

We define the fundamental group underlying the Weil-étale cohomology of number rings. To this aim, we define the Weil-étale topos as a refinement of the Weil-étale sites introduced by Lichtenbaum (Ann Math 170(2):657–683, 2009). We show that the (small) Weil-étale topos of a smooth projective curve defined in this paper is equivalent to the natural definition. Then we compute the Weil-étale fundamental group of an open subscheme of the spectrum of a number ring. Our fundamental group is a projective system of locally compact topological groups, which represents first degree cohomology with coefficients in locally compact abelian groups. We apply this result to compute the Weil-étale cohomology in low degrees and to prove that the Weil-étale topos of a number ring satisfies the expected properties of the conjectural Lichtenbaum topos.     

Definability in Substructure Orderings,II: Finite Ordered Sets

Let \({{\uppercase {\mathcal{p}}}} \) be the ordered set of isomorphism types of finite ordered sets (posets), where the ordering is by embeddability. We study first-order definability in this ordered set. We prove among other things that for every finite poset P, the set \(\{p,p^{\partial}\}\) is definable, where p and \(p^{\partial}\) are the isomorphism types of P and its dual poset. We prove that the only non-identity automorphism of \({{\uppercase {\mathcal{p}}}}\) is the duality map. Then we apply these results to investigate definability in the closely related lattice of universal classes of posets. We prove that this lattice has only one non-identity automorphism, the duality map; that the set of finitely generated and also the set of finitely axiomatizable universal classes are definable subsets of the lattice; and that for each member K of either of these two definable subsets, \(\{K,K^{\partial}\}\) is a definable subset of the lattice. Next, making fuller use of the techniques developed to establish these results, we go on to show that every isomorphism-invariant relation between finite posets that is definable in a certain strongly enriched second-order language \(\textup{\emph L}_2\) is, after factoring by isomorphism, first-order definable up to duality in the ordered set \({{\uppercase {\mathcal{p}}}}\). The language \(\textup{\emph L}_2\) has different types of quantifiable variables that range, respectively, over finite posets, their elements and order-relation, and over arbitrary subsets of posets, functions between two posets, subsets of products of finitely many posets (heteregenous relations), and can make reference to order relations between elements, the application of a function to an element, and the membership of a tuple of elements in a relation.     

RESTRICTION RESPECTUEUSE ET RECONSTRUCTION DES CHAINES ET DES RELATIONS INFINITES

We show a faithful restriction theorem among infinite chains which implies a reconstructibility conjecture of Halin. This incite us to study the reconstructibility in the sense of Fraïssé and to prove it for orders of cardinality infinite or ≥ 3 and for multirelations of cardinality infinite or ≥ 7, what improves the theory obtained by G. Lopez in the finite case. For this work we had to study the infinite classes of difference which have to be a linear order of type ω, ω* or ω* + ω; this complete the theory made by G. Lopez for the finite case ([13]). We show also Ulam-reconstructibility for linear orders which have a fixed point.     

Uniqueness of orientation-preserving free actions of finite abelian groups on surfaces

Let G be a finite abelian group. We list all the cases where the topological equivalence class of orientation-preserving free G-actions on a closed surface is unique. Moreover, we obtain the classification of topological equivalence classes of orientation-preserving free actions of finite abelian groups of rank 2.     

Canonizing structural Ramsey theorems

At the beginning of 1950s Erd?s and Rado suggested the investigation of the Ramsey-type results where the number of colors is not finite. This marked the birth of the so-called canonizing Ramsey theory. In 1985 Prömel and Voigt made the first step towards the structural canonizing Ramsey theory when they proved the canonical Ramsey property for the class of finite linearly ordered hypergraphs, and the subclasses thereof defined by forbidden substructures. Building on their results in this paper we provide several new structural canonical Ramsey results. We prove the canonical Ramsey theorem for the class of all finite linearly ordered tournaments, the class of all finite posets with linear extensions and the class of all finite linearly ordered metric spaces. We conclude the paper with the canonical version of the celebrated Ne?et?il–Rödl Theorem. In contrast to the “classical” Ramsey-theoretic approach, in this paper we advocate the use of category theory to manage the complexity of otherwise technically overwhelming proofs typical in canonical Ramsey theory.     

An Example of a Fraïssé Class Without a Katětov Functor

We disprove a conjecture from Kubi? and Ma?ulovi? [2] by showing the existence of a Fraïssé class \(\mathcal {C}\) which does not admit a Katětov functor. On the other hand, we show that the automorphism group of the Fraïssé limit of \(\mathcal {C}\) is universal, as it happens in the presence of a Katětov functor.