Maximal small extensions of o‐minimal structures

A proper elementary extension of a model is called small if it realizes no new types over any finite set in the base model. We answer a question of Marker, and show that it is possible to have an o‐minimal structure with a maximal small extension. Our construction yields such a structure for any cardinality. We show that in some cases, notably when the base structure is countable, the maximal small extension has maximal possible cardinality (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

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)     

Uniform bounds on growth in o‐minimal structures

We prove that a function definable with parameters in an o‐minimal structure is bounded away from ∞ as its argument goes to ∞ by a function definable without parameters, and that this new function can be chosen independently of the parameters in the original function. This generalizes a result in [1]. Moreover, this remains true if the argument is taken to approach any element of the structure (or ±∞), and the function has limit any element of the structure (or ±∞) (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Minimality conditions on circularly ordered structures

We explore analogues of o‐minimality and weak o‐minimality for circularly ordered sets. Much of the theory goes through almost unchanged, since over a parameter the circular order yields a definable linear order. Working over ?? there are differences. Our main result is a structure theory (with infinitely many doubly transitive examples related to Jordan permutation groups) for ?₀‐categorical weakly circularly minimal structures. There is a 5‐homogeneous (or ‘5‐indiscernible’) example which is not 6‐homogeneous, but any example which is k‐homogeneous for some k ≥ 6 is k‐homogeneous for all k. (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

On the strong cell decomposition property for weakly o‐minimal structures

We consider a class of weakly o‐minimal structures admitting an o‐minimal style cell decomposition, for which one can construct certain canonical o‐minimal extension. The paper contains several fundamental facts concerning the structures in question. Among other things, it is proved that the strong cell decomposition property is preserved under elementary equivalences. We also investigate fiberwise properties (of definable sets and definable functions), definable equivalence relations, and conditions implying elimination of imaginaries.     

Binary types in ℵ0‐categorical weakly o‐minimal theories

Orthogonality of all families of pairwise weakly orthogonal 1‐types for ?₀‐categorical weakly o‐minimal theories of finite convexity rank has been proved in 6 . Here we prove orthogonality of all such families for binary 1‐types in an arbitrary ?₀‐categorical weakly o‐minimal theory and give an extended criterion for binarity of ?₀‐categorical weakly o‐minimal theories (additionally in terms of binarity of 1‐types). © 2011 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim     

Cell decomposition for P‐minimal fields

In [12], P. Scowcroft and L. van den Dries proved a cell decomposition theorem for p‐adically closed fields. We work here with the notion of P‐minimal fields defined by D. Haskell and D. Macpherson in [6]. We prove that a P‐minimal field K admits cell decomposition if and only if K has definable selection. A preprint version in French of this result appeared as a prepublication [8] (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

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)     

ω‐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.     

A fixed point theorem for o‐minimal structures

We prove a definable analogue to Brouwer's Fixed Point Theorem for o‐minimal structures of real closed field expansions: A continuous definable function mapping from the unit simplex into itself admits a fixed point, even though the underlying space is not necessarily topologically complete. Our proof is direct and elementary; it uses a triangulation technique for o‐minimal functions, with an application of Sperner's Lemma. (© 2003 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Dirichlet regularity in arbitrary o‐minimal structures on the field ℝ up to dimension 4

In this article we show that the set of Dirichlet regular boundary points of a bounded domain of dimension up to 4, definable in an arbitrary o‐minimal structure on the field ?, is definable in the same structure. Moreover we give estimates for the dimension of the set of non‐regular boundary points, depending on whether the structure is polynomially bounded or not. This paper extends the results from the author's Ph.D. thesis [6, 7] where the problem was solved for polynomially bounded o‐minimal structures expanding the real field. (© 2006 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Hamilton cycle and Hamilton path extendability of Cayley graphs on abelian groups

In this paper the concepts of Hamilton cycle (HC) and Hamilton path (HP) extendability are introduced. A connected graph Γ is n‐HC‐extendable if it contains a path of length n and if every such path is contained in some Hamilton cycle of Γ. Similarly, Γ is weakly n‐HP‐extendable if it contains a path of length n and if every such path is contained in some Hamilton path of Γ. Moreover, Γ is strongly n‐HP‐extendable if it contains a path of length n and if for every such path P there is a Hamilton path of Γ starting with P. These concepts are then studied for the class of connected Cayley graphs on abelian groups. It is proved that every connected Cayley graph on an abelian group of order at least three is 2‐HC‐extendable and a complete classification of 3‐HC‐extendable connected Cayley graphs of abelian groups is obtained. Moreover, it is proved that every connected Cayley graph on an abelian group of order at least five is weakly 4‐HP‐extendable. Copyright © 2011 Wiley Periodicals, Inc. J Graph Theory     

Definability and nondefinability results for certain o‐minimal structures

The main goal of this note is to study for certain o‐minimal structures the following propriety: for each definable C^∞ function g₀: [0, 1] → ? there is a definable C^∞ function g: [–ε, 1] → ?, for some ε > 0, such that g (x) = g₀(x) for all x ∈ [0, 1] (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

3‐Flows and Combs

Tutte's 3‐Flow Conjecture states that every 2‐edge‐connected graph with no 3‐cuts admits a 3‐flow. The 3‐Flow Conjecture is equivalent to the following: let G be a 2‐edge‐connected graph, let S be a set of at most three vertices of G; if every 3‐cut of G separates S then G has a 3‐flow. We show that minimum counterexamples to the latter statement are 3‐connected, cyclically 4‐connected, and cyclically 7‐edge‐connected.     

Every DFS Tree of a 3‐Connected Graph Contains a Contractible Edge

Tutte proved that every 3‐connected graph G on more than 4 vertices contains a contractible edge. We strengthen this result by showing that every depth‐first‐search tree of G contains a contractible edge. Moreover, we show that every spanning tree of G contains a contractible edge if G is 3‐regular or if G does not contain two disjoint pairs of adjacent degree‐3 vertices.     

A Characterization of b‐Perfect Graphs

A b‐coloring is a coloring of the vertices of a graph such that each color class contains a vertex that has a neighbor in all other color classes, and the b‐chromatic number of a graph G is the largest integer k such that G admits a b‐coloring with k colors. A graph is b‐perfect if the b‐chromatic number is equal to the chromatic number for every induced subgraph of G. We prove that a graph is b‐perfect if and only if it does not contain as an induced subgraph a member of a certain list of 22 graphs. This entails the existence of a polynomial‐time recognition algorithm and of a polynomial‐time algorithm for coloring exactly the vertices of every b‐perfect graph. © 2011 Wiley Periodicals, Inc. J Graph Theory 71:95–122, 2012     

High‐girth cubic graphs are homomorphic to the Clebsch graph

We give a (computer assisted) proof that the edges of every graph with maximum degree 3 and girth at least 17 may be 5‐colored (possibly improperly) so that the complement of each color class is bipartite. Equivalently, every such graph admits a homomorphism to the Clebsch graph (Fig. 1 ). Hopkins and Staton [J Graph Theory 6(2) (1982), 115–121] and Bondy and Locke [J Graph Theory 10(4) (1986), 477–504] proved that every (sub)cubic graph of girth at least 4 has an edge‐cut containing at least of the edges. The existence of such an edge‐cut follows immediately from the existence of a 5‐edge‐coloring as described above; so our theorem may be viewed as a coloring extension of their result (under a stronger girth assumption). Every graph which has a homomorphism to a cycle of length five has an above‐described 5‐edge‐coloring; hence our theorem may also be viewed as a weak version of Ne?et?il's Pentagon Problem (which asks whether every cubic graph of sufficiently high girth is homomorphic to C₅). Copyright © 2011 Wiley Periodicals, Inc. J Graph Theory 66: 241—259, 2011     

DAG‐Width and Circumference of Digraphs

We prove that every digraph of circumference l has DAG‐width at most l. This is best possible and solves a recent conjecture from S. Kintali (ArXiv:1401.2662v1 [math.CO], January 2014).¹ As a consequence of this result we deduce that the k‐linkage problem is polynomially solvable for every fixed k in the class of digraphs with bounded circumference. This answers a question posed in J. Bang‐Jensen, F. Havet, and A. K. Maia (Theor Comput Sci 562 (2014), 283–303). We also prove that the weak k‐linkage problem (where we ask for arc‐disjoint paths) is polynomially solvable for every fixed k in the class of digraphs with circumference 2 as well as for digraphs with a bounded number of disjoint cycles each of length at least 3. The case of bounded circumference digraphs is still open. Finally, we prove that the minimum spanning strong subdigraph problem is NP‐hard on digraphs of DAG‐width at most 5.     

On removable cycles through every edge

Mader and Jackson independently proved that every 2‐connected simple graph G with minimum degree at least four has a removable cycle, that is, a cycle C such that G/E(C) is 2‐connected. This paper considers the problem of determining when every edge of a 2‐connected graph G, simple or not, can be guaranteed to lie in some removable cycle. The main result establishes that if every deletion of two edges from G remains 2‐connected, then, not only is every edge in a removable cycle but, for every two edges, there are edge‐disjoint removable cycles such that each contains one of the distinguished edges. © 2002 Wiley Periodicals, Inc. J Graph Theory 42: 155–164, 2003