Maximum Δ‐edge‐colorable subgraphs of class II graphs

A graph G is class II, if its chromatic index is at least Δ + 1. Let H be a maximum Δ‐edge‐colorable subgraph of G. The paper proves best possible lower bounds for |E(H)|/|E(G)|, and structural properties of maximum Δ‐edge‐colorable subgraphs. It is shown that every set of vertex‐disjoint cycles of a class II graph with Δ≥3 can be extended to a maximum Δ‐edge‐colorable subgraph. Simple graphs have a maximum Δ‐edge‐colorable subgraph such that the complement is a matching. Furthermore, a maximum Δ‐edge‐colorable subgraph of a simple graph is always class I. © 2011 Wiley Periodicals, Inc. J Graph Theory     

Definable types in algebraically closed valued fields

In 15 , Marker and Steinhorn characterized models of an o‐minimal theory such that all types over M realized in N are definable. In this article we characterize pairs of algebraically closed valued fields satisfying the same property. In o‐minimal theories, a pair of models for which all 1‐types over M realized in N are definable has already the desired property. Although it is true that if M is an algebraically closed valued field such that all 1‐types over M are definable then all types over M are definable, we build a counterexample for the relative statement, i.e., we show for any that there is a pair of algebraically closed valued fields such that all n‐types over M realized in N are definable but there is an ‐type over M realized in N which is not definable.     

Mixing of the Glauber dynamics for the ferromagnetic Potts model

We present several results on the mixing time of the Glauber dynamics for sampling from the Gibbs distribution in the ferromagnetic Potts model. At a fixed temperature and interaction strength, we study the interplay between the maximum degree (Δ) of the underlying graph and the number of colours or spins (q) in determining whether the dynamics mixes rapidly or not. We find a lower bound L on the number of colours such that Glauber dynamics is rapidly mixing if at least L colours are used. We give a closely‐matching upper bound U on the number of colours such that with probability that tends to 1, the Glauber dynamics mixes slowly on random Δ‐regular graphs when at most U colours are used. We show that our bounds can be improved if we restrict attention to certain types of graphs of maximum degree Δ, e.g. toroidal grids for Δ = 4. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 48, 21–52, 2016     

On the Boolean algebras of definable sets in weakly o‐minimal theories

We consider the sets definable in the countable models of a weakly o‐minimal theory T of totally ordered structures. We investigate under which conditions their Boolean algebras are isomorphic (hence T is p‐ω‐categorical), in other words when each of these definable sets admits, if infinite, an infinite coinfinite definable subset. We show that this is true if and only if T has no infinite definable discrete (convex) subset. We examine the same problem among arbitrary theories of mere linear orders. Finally we prove that, within expansions of Boolean lattices, every weakly o‐minimal theory is p‐ω‐categorical. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

A Sufficient Condition for Edge Chromatic Critical Graphs to Be Hamiltonian—An Approach to Vizing's 2‐Factor Conjecture

In this article, we consider Vizing's 2‐Factor Conjecture which claims that any Δ‐critical graph has a 2‐factor, and show that if G is a Δ‐critical graph with n vertices satisfying , then G is Hamiltonian and thus G has a 2‐factor. Meanwhile in this article, we also consider long cycles of overfull critical graphs and obtain that if G is an overfull Δ‐critical graph with n vertices, then the circumference of G is at least min.© 2012 Wiley Periodicals, Inc. J. Graph Theory 00: 1‐14, 2012     

Oligomorphic clones

A permutation group on a countably infinite domain is called oligomorphic if it has finitely many orbits of finitary tuples. We define a clone on a countable domain to be oligomorphic if its set of permutations forms an oligomorphic permutation group. There is a close relationship to ω-categorical structures, i.e., countably infinite structures with a first-order theory that has only one countable model, up to isomorphism. Every locally closed oligomorphic permutation group is the automorphism group of an ω-categorical structure, and conversely, the canonical structure of an oligomorphic permutation group is an ω-categorical structure that contains all first-order definable relations. There is a similar Galois connection between locally closed oligomorphic clones and ω-categorical structures containing all primitive positive definable relations. In this article we generalise some fundamental theorems of universal algebra from clones over a finite domain to oligomorphic clones. First, we define minimal oligomorphic clones, and present equivalent characterisations of minimality, and then generalise Rosenberg’s five types classification to minimal oligomorphic clones. We also present a generalisation of the theorem of Baker and Pixley to oligomorphic clones. Presented by A. Szendrei. Received July 12, 2005; accepted in final form August 29, 2006.     

Ranks and definability in superstable theories

We study the notion of definable type, and use it to define theproduct of types and theheir of a type. Then, in the case of stable and superstable theories, we make a general study of the notion of rank. Finally, we use these techniques to give a new proof of a theorem of Lachlan on the number of isomorphism types of countable models of a superstable theory.     

Very rapid mixing of the Glauber dynamics for proper colorings on bounded‐degree graphs

Recent results have shown that the Glauber dynamics for graph colorings has optimal mixing time when (i) the graph is triangle‐free and Δ‐regular and the number of colors k is a small constant fraction smaller than 2Δ, or (ii) the graph has maximum degree Δ and k=2Δ. We extend both these results to prove that the Glauber dynamics has optimal mixing time when the graph has maximum degree Δ and the number of colors is a small constant fraction smaller than 2Δ. © 2002 John Wiley & Sons, Inc. Random Struct. Alg., 20, 98–114, 2002     

Bounded orbits and measures on a group

We consider a definable group G acting on the space of complete types over G, in a monster model of a theory T. We discuss the notion of a bounded orbit of this action. We prove that some boundedness assumptions imply definable amenability of G.     

On definability of types of finite Cantor‐Bendixson rank

We prove that every type of finite Cantor‐Bendixson rank over a model of a first‐order theory without the strict order property is definable and has a unique nonforking extension to a global type. © 2011 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim     

A new upper bound for the independence number of edge chromatic critical graphs

In 1968, Vizing conjectured that if G is a Δ‐critical graph with n vertices, then α(G)≤n/2, where α(G) is the independence number of G. In this paper, we apply Vizing and Vizing‐like adjacency lemmas to this problem and prove that α(G)<(((5Δ?6)n)/(8Δ?6))<5n/8 if Δ≥6. © 2010 Wiley Periodicals, Inc. J Graph Theory 68: 202‐212, 2011     

A note on stable sets,groups, and theories with NIP

Let M be an arbitrary structure. Then we say that an M ‐formula φ (x) defines a stable set in M if every formula φ (x) ∧ α (x, y) is stable. We prove: If G is an M ‐definable group and every definable stable subset of G has U ‐rank at most n (the same n for all sets), then G has a maximal connected stable normal subgroup H such that G /H is purely unstable. The assumptions hold for example if M is interpretable in an o‐minimal structure. More generally, an M ‐definable set X is weakly stable if the M ‐induced structure on X is stable. We observe that, by results of Shelah, every weakly stable set in theories with NIP is stable. (© 2007 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

On Models Constructed by Means of the Arithmetized Completeness Theorem

In this paper we study the model theory of extensions of models of first‐order Peano Arithmetic (PA) by means of the arithmetized completeness theorem (ACT) applied to a definable complete extension of PA in the original model. This leads us to many interesting model theoretic properties equivalent to reflection principles and ω‐consistency, and these properties together with the associated first‐order schemes extending PA are studied.     

Dependent first order theories, continued

A dependent theory is a (first order complete theory) T which does not have the independence property. A major result here is: if we expand a model of T by the traces on it of sets definable in a bigger model then we preserve its being dependent. Another one justifies the cofinality restriction in the theorem (from a previous work) saying that pairwise perpendicular indiscernible sequences, can have arbitrary dual-cofinalities in some models containing them. We introduce “strongly dependent” and look at definable groups; and also at dividing, forking and relatives.     

Expansions of ordered fields without definable gaps

In this paper we are concerned with definably, with or without parameters, (Dedekind) complete expansions of ordered fields, i. e. those with no definable gaps. We present several axiomatizations, like being definably connected, in each of the two cases. As a corollary, when parameters are allowed, expansions of ordered fields are o‐minimal if and only if all their definable subsets are finite disjoint unions of definably connected (definable) subsets. We pay attention to how simply (in terms of the quantifier complexity and/or usage of parameters) a definable gap in an expansion is so. Next we prove that over parametrically definably complete expansions of ordered fields, all one‐to‐one definable (with parameters) continuous functions are monotone and open. Moreover, in both parameter and parameter‐free cases again, definably complete expansions of ordered fields satisfy definable versions of the Heine‐Borel and Extreme Value theorems and also Bounded Intersection Property for definable families of closed bounded subsets.     

Topological dynamics and the complexity of strong types

We develop topological dynamics for the group of automorphisms of a monster model of any given theory. In particular, we find strong relationships between objects from topological dynamics (such as the generalized Bohr compactification introduced by Glasner) and various Galois groups of the theory in question, obtaining essentially new information about them, e.g., we present the closure of the identity in the Lascar Galois group of the theory as the quotient of a compact, Hausdorff group by a dense subgroup.We apply this to describe the complexity of bounded, invariant equivalence relations, obtaining comprehensive results, subsuming and extending the existing results and answering some open questions from earlier papers. We show that, in a countable theory, any such relation restricted to the set of realizations of a complete type over Ø is type-definable if and only if it is smooth. Then we show a counterpart of this result for theories in an arbitrary (not necessarily countable) language, obtaining also new information involving relative definability of the relation in question. As a final conclusion we get the following trichotomy. Let \(\mathfrak{C}\) be a monster model of a countable theory, p ∈ S(Ø), and E be a bounded, (invariant) Borel (or, more generally, analytic) equivalence relation on p(\(\mathfrak{C}\)). Then, exactly one of the following holds: (1) E is relatively definable (on p(\(\mathfrak{C}\))), smooth, and has finitely many classes, (2) E is not relatively definable, but it is type-definable, smooth, and has 2^?0 classes, (3) E is not type definable and not smooth, and has 2^?0 classes. All the results which we obtain for bounded, invariant equivalence relations carry over to the case of bounded index, invariant subgroups of definable groups.     

On total 9‐coloring planar graphs of maximum degree seven

Given a graph G, a total k‐coloring of G is a simultaneous coloring of the vertices and edges of G with at most k colors. If Δ(G) is the maximum degree of G, then no graph has a total Δ‐coloring, but Vizing conjectured that every graph has a total (Δ + 2)‐coloring. This Total Coloring Conjecture remains open even for planar graphs. This article proves one of the two remaining planar cases, showing that every planar (and projective) graph with Δ ≤ 7 has a total 9‐coloring by means of the discharging method. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 67–73, 1999     

Definability in the lattice of equational theories of commutative semigroups

In this paper we study first-order definability in the lattice of equational theories of commutative semigroups. In a series of papers, J. Jezek, solving problems posed by A. Tarski and R. McKenzie, has proved, in particular, that each equational theory is first-order definable in the lattice of equational theories of a given type, up to automorphism, and that such lattices have no automorphisms besides the obvious syntactically defined ones (with exceptions for special unary types). He has proved also that the most important classes of theories of a given type are so definable. In a later paper, Jezek and McKenzie have ``almost proved" the same facts for the lattice of equational theories of semigroups. There were good reasons to believe that the same can be proved for the lattice of equational theories of commutative semigroups. In this paper, however, we show that the case of commutative semigroups is different.

     

Definable types in the theory of closed ordered differential fields

We study definable types in the theory of closed ordered differential fields (CODF). We show a condition for a type to be definable, then we prove that definable types are dense in the Stone space of CODF.     

Nonstandard models that are definable in models of Peano Arithmetic

In this paper, we investigate definable models of Peano Arithmetic PA in a model of PA. For any definable model N without parameters in a model M, we show that N is isomorphic to M if M is elementary extension of the standard model and N is elementarily equivalent to M. On the other hand, we show that there is a model M and a definable model N with parameters in M such that N is elementarily equivalent to M but N is not isomorphic to M. We also show that there is a model M and a definable model N with parameters in M such that N is elementarily equivalent to M, and N is isomorphic to M, but N is not definably isomorphic to M. And also, we give a generalization of Tennenbaum's theorem. At the end, we give a new method to construct a definable model by a refinement of Kotlarski's method. (© 2007 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)