ω, Δ, and χ

We discuss bounding the chromatic number of a graph by a convex combination of its clique number and its maximum degree plus 1. We will often have recourse to the probabilistic method. © 1998 John Wiley & Sons, Inc. J Graph Theory 27: 177–212, 1998     

Canonical forms of Borel-measurable mappings Δ: [ω]ω → R

We show that for every Borel-measurable mapping Δ: [ω]^ω → $\text{R}$ there exists A ∈ [ω]^ω and there exists a continuous mapping Γ: [A]^ω → [A]^?ω with Γ(X) ? X such that for all X, Y ∈ [A]^ω it follows that Δ(X) = Δ(Y) if Γ(X) = Γ(Y). In a sense, this is generalization of the Erdös-Rado canonization theorem     

A Short Proof That χ Can be Bounded ε Away from Δ + 1 toward ω

In 1998 the second author proved that there is an such that every graph satisfies . The first author recently proved that any graph satisfying contains a stable set intersecting every maximum clique. In this note, we exploit the latter result to give a much shorter, simpler proof of the former. Working from first principles, we omit only some five pages of proofs of known intermediate results (which appear in an extended version of this paper), and the proofs of Hall's Theorem, Brooks' Theorem, the Lovász Local Lemma, and Talagrand's Inequality.     

Claw‐Free Graphs,Skeletal Graphs,and a Stronger Conjecture on ω, Δ, and χ

The second author's (B.A.R.) ω, Δ, χ conjecture proposes that every graph satisfies . In this article, we prove that the conjecture holds for all claw‐free graphs. Our approach uses the structure theorem of Chudnovsky and Seymour. Along the way, we discuss a stronger local conjecture, and prove that it holds for claw‐free graphs with a three‐colorable complement. To prove our results, we introduce a very useful χ‐preserving reduction on homogeneous pairs of cliques, and thus restrict our view to so‐called skeletal graphs.     

ω‐saturated quasi‐minimal models of Th(ℚω, +, σ, 0)

We show that (ℚ^ω, +, σ, 0) is a quasi-minimal torsion-free divisible abelian group. After discussing the axiomatization of the theory of this structure, we present its ω-saturated quasi-minimal model. (© 2005 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

A short proof of the preservation of the ωω‐bounding property

There are two versions of the Proper Iteration Lemma. The stronger (but less well‐known) version can be used to give simpler proofs of iteration theorems (e.g., [7, Lemma 24] versus [9, Theorem IX.4.7]). In this paper we give another demonstration of the fecundity of the stronger version by giving a short proof of Shelah's theorem on the preservation of the ω^ω‐bounding property. (© 2003 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Recursiveness of ω-Operations

It is well known that any finitary operation is recursive in a suitable total numeration. A. Orlicki showed that there is an ω-operation not recursive in any total numeration. We will show that any ω-operation is recursive in a partial numeration. Mathematics Subject Classification: 03D45.     

Finding Δ(Σ) for a surface σ of characteristic χ(Σ) = −5

For each surface Σ, we define Δ(Σ) = max{Δ(G)|Gis a class two graph of maximum degree Δ(G) that can be embedded in Σ}. Hence, Vizing's Planar Graph Conjecture can be restated as Δ(Σ) = 5 if Σ is a plane. In this paper, we show that Δ(Σ) = 9 if Σ is a surface of characteristic χ(Σ) = ?5. © 2010 Wiley Periodicals, Inc. J Graph Theory 68:148‐168, 2011     

Index sets for ω‐languages

An ω‐language is a set of infinite sequences (words) on a countable language, and corresponds to a set of real numbers in a natural way. Languages may be described by logical formulas in the arithmetical hierarchy and also may be described as the set of words accepted by some type of automata or Turing machine. Certain families of languages, such as the languages, may enumerated as P₀, P₁, … and then an index set associated to a given property R (such as finiteness) of languages is just the set of e such that P_e has the property. The complexity of index sets for 7 types of languages is determined for various properties related to the size of the language.     

ON THE ITERATED ω-RULE

Let Γ_n(φ) be a formula of L_PA (PA = Peano Arithmetic) meaning “there is a proof of φ from PA-axioms, in which ω-rule is iterated no more than n times”. We examine relations over pairs of natural numbers of the kind. (n, k) ≦_H (n', k') iff PA + RFN_n' (H_k') ? RFN_n (H_k). Where H denotes one of the hierarchies ∑ or Π and RFN_n(C) is the scheme of the reflection principle for Γ_n restricted to formulas from the class C(Γ_n(φ) implies “φ is true”, for every φ ∈ C). Our main result is that. (n, k) ≦H (n', k') if n ≦ n' and k ≦ max (k', 2n' + 1).     

Difference between irregular chaotic patterns of second-order double-loop ΣΔ modulators and second-order interpolative bandpass ΣΔ modulators

In this paper, we find that, by computing the difference between two consecutive state vectors of second-order double-loop sigma-delta modulators (SDMs) and plotting one component of the subtracted vectors against the other component, irregular chaotic patterns will become two vertical lines. By multiplying a matrix on the subtracted vectors, it can be further transformed to two fixed points. However, second-order interpolative bandpass SDMs still exhibit chaotic behaviors after applying the same transformations. Moreover, it is found that the Lyapunov exponent of state vectors of second-order double-loop SDMs is higher than that of second-order interpolative bandpass SDMs, whereas the Lyapunov exponent of transformed vectors becomes negative infinity for second-order double-loop SDMs and increases for second-order interpolative bandpass SDMs. Hence, by examining the occurrence of chaotic behaviors of the transformed vectors of these two SDMs, these two SDMs can be distinguished from their state vectors and their transformed vectors without solving the state equations and knowing the information of input signals.     

The Computational Power of ℳ︁ω

We prove that the Kleene schemes for primitive recursion relative to the μ‐operator, relativized to some nondeterministic objects, have the same power to express total functionals when interpreted over the partial continuous functionals and over the Kleene‐Kreisel continuous functionals. Relating the former interpretation to Niggl's ℳ︁^ω we prove Nigg's conjecture that ℳ︁^ω is strictly weaker than Plotkin's PCF + PA.     

ω-operations over partial enumerated sets

In the present paper we concentrate on fundamental problems concerning ω-operations over partial enumerated sets. The notion of “HOM-lifts” seems to be an adequate tool for this kind of investigations. MSC: 03D45, 18A30.     

Quotient Fields of a Model of IΔ0 + Ω1

In [4] the authors studied the residue field of a model M of IΔ₀ + Ω₁ for the principal ideal generated by a prime p. One of the main results is that M/<p> has a unique extension of each finite degree. In this paper we are interested in understanding the structure of any quotient field of M, i.e. we will study the quotient M/I for I a maximal ideal of M. We prove that any quotient field of M satisfies the property of having a unique extension of each finite degree. We will use some of Cherlin's ideas from [3], where he studies the ideal theory of non standard algebraic integers.