Envelopes,indicators and conservativeness

A well known theorem proved (independently) by J. Paris and H. Friedman states that B Σ_{n +1} (the fragment of Arithmetic given by the collection scheme restricted to Σ_{n +1}‐formulas) is a Π_{n +2}‐conservative extension of I Σ_n (the fragment given by the induction scheme restricted to Σ_n ‐formulas). In this paper, as a continuation of our previous work on collection schemes for Δ_{n +1}(T )‐formulas (see [4]), we study a general version of this theorem and characterize theories T such that T + B Σ_{n +1} is a Π_{n +2}‐conservative extension of T . We prove that this conservativeness property is equivalent to a model‐theoretic property relating Π_n ‐envelopes and Π_n ‐indicators for T . The analysis of Σ_{n +1}‐collection we develop here is also applied to Σ_{n +1}‐induction using Parsons' conservativeness theorem instead of Friedman‐Paris' theorem. As a corollary, our work provides new model‐theoretic proofs of two theorems of R. Kaye, J. Paris and C. Dimitracopoulos (see [8]): B Σ_{n +1} and I Σ_{n +1} are Σ_{n +3}‐conservative extensions of their parameter free versions, B Σ^–_{n +1} and I Σ^–_{n +1}. (© 2006 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Boolean products of R0‐algebras

In this paper, the (weak) Boolean representation of R₀‐algebras are investigated. In particular, we show that directly indecomposable R₀‐algebras are equivalent to local R₀‐algebras and any nontrivial R₀‐algebra is representable as a weak Boolean product of local R₀‐algebras (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Groups and C*‐Algebras from a 4‐Dimensional Anzai Flow

The rotation flow on the circle T gives a concrete representation of the irrational rotation algebra, which is an in finite dimensional simple quotient of the group C*‐algebra of the discrete Heisenberg group H₃ analogously certain 2‐ and 3‐dimensional Anzai flows on T ² and T ³are known to give concrete representations of the corresponding quotients of the group C*‐algebras of the groups H₄ and H_5,5. Considered here is the (minimal, effective) 4‐dimensional Anzai flow F = (ℤ, T ⁴) generated by the homeomorphism (y, x, w, v) ↦ (λy, yx, xw, wv); a group H_6,10 is determined by F the faithful in finite dimensional simple quotients of whose group C*‐algebra C*‐(H_6,10 have concrete representations given by F. Furthermore, the rest of the infinite dimensional simple quotients of C*‐(H_6,10 are identified and displayed as C*‐crossed products generated by minimal effective actions and also as matrix algebras over simple C*‐algebras from groups of lower dimension; these lower dimensional groups are H₃ and subgroups of H₄ and H_5,5.     

The existence of a 2‐factor in K1, n‐free graphs with large connectivity and large edge‐connectivity

In this article, we study the existence of a 2‐factor in a K_{1, n}‐free graph. Sumner [J London Math Soc 13 (1976), 351–359] proved that for n?4, an (n?1)‐connected K_{1, n}‐free graph of even order has a 1‐factor. On the other hand, for every pair of integers m and n with m?n?4, there exist infinitely many (n?2)‐connected K_{1, n}‐free graphs of even order and minimum degree at least m which have no 1‐factor. This implies that the connectivity condition of Sumner's result is sharp, and we cannot guarantee the existence of a 1‐factor by imposing a large minimum degree. On the other hand, Ota and Tokuda [J Graph Theory 22 (1996), 59–64] proved that for n?3, every K_{1, n}‐free graph of minimum degree at least 2n?2 has a 2‐factor, regardless of its connectivity. They also gave examples showing that their minimum degree condition is sharp. But all of them have bridges. These suggest that the effects of connectivity, edge‐connectivity and minimum degree to the existence of a 2‐factor in a K_{1, n}‐free graph are more complicated than those to the existence of a 1‐factor. In this article, we clarify these effects by giving sharp minimum degree conditions for a K_{1, n}‐free graph with a given connectivity or edge‐connectivity to have a 2‐factor. Copyright © 2010 Wiley Periodicals, Inc. J Graph Theory 68:77‐89, 2011     

Robust designs for Haar wavelet approximation models

In this paper, we discuss the construction of robust designs for heteroscedastic wavelet regression models when the assumed models are possibly contaminated over two different neighbourhoods: G ₁ and G ₂ . Our main findings are: (1) A recursive formula for constructing D‐optimal designs under G ₁ ; (2) Equivalency of Q‐optimal and A‐optimal designs under both G ₁ and G ₂ ; (3) D‐optimal robust designs under G ₂ ; and (4) Analytic forms for A‐ and Q‐optimal robust design densities under G ₂ . Several examples are given for the comparison, and the results demonstrate that our designs are efficient. Copyright © 2010 John Wiley & Sons, Ltd.     

On realization of the Kreĭn–Langer class Nκ of matrix‐valued functions in Pontryagin spaces

In this paper the realization problems for the Kre?n–Langer class N_κ of matrix‐valued functions are being considered. We found the criterion when a given matrix‐valued function from the class N_κ can be realized as linear‐fractional transformation of the transfer function of canonical conservative system of the M. Livsic type (Brodskii–Livsic rigged operator colligation) with the main operator acting on a rigged Pontryagin space Π_κ with indefinite metric. We specify three subclasses of the class N_κ (R) of all realizable matrix‐valued functions that correspond to different properties of a realizing system, in particular, when the domains of the main operator of a system and its conjugate coincide, when the domain of the hermitian part of a main operator is dense in Π_κ . Alternatively we show that the class N_κ (R) can be realized as transfer matrix‐functions of some canonical impedance systems with self‐adjoint main operators in rigged spaces Π_κ . The case of scalar functions of the class N_κ (R) is considered in details and some examples are presented. (© 2008 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Spanning 2‐trails from degree sum conditions

Suppose G is a simple connected n‐vertex graph. Let σ₃(G) denote the minimum degree sum of three independent vertices in G (which is ∞ if G has no set of three independent vertices). A 2‐trail is a trail that uses every vertex at most twice. Spanning 2‐trails generalize hamilton paths and cycles. We prove three main results. First, if σ₃G)≥ n ‐ 1, then G has a spanning 2‐trail, unless G ? K_1,3. Second, if σ₃(G) ≥ n, then G has either a hamilton path or a closed spanning 2‐trail. Third, if G is 2‐edge‐connected and σ₃(G) ≥ n, then G has a closed spanning 2‐trail, unless G ? K_2,3 or K (the 6‐vertex graph obtained from K_2,3 by subdividing one edge). All three results are sharp. These results are related to the study of connected and 2‐edge‐connected factors, spanning k‐walks, even factors, and supereulerian graphs. In particular, a closed spanning 2‐trail may be regarded as a connected (and 2‐edge‐connected) even [2,4]‐factor. © 2004 Wiley Periodicals, Inc. J Graph Theory 45: 298–319, 2004     

Fragments of Martin's Maximum in generic extensions

We show that large fragments of MM, e. g. the tree property and stationary reflection, are preserved by strongly (ω₁ + 1)‐game‐closed forcings. PFA can be destroyed by a strongly (ω₁ + 1)‐game‐closed forcing but not by an ω₂‐closed. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

The A4‐structure of a graph

We define the A₄‐structure of a graph G to be the 4‐uniform hypergraph on the vertex set of G whose edges are the vertex subsets inducing 2K₂, C₄, or P₄. We show that perfection of a graph is determined by its A₄‐structure. We relate the A₄‐structure to the canonical decomposition of a graph as defined by Tyshkevich [Discrete Math 220 (2000) 201–238]; for example, a graph is indecomposable if and only if its A₄‐structure is connected. We also characterize the graphs having the same A₄‐structure as a split graph.     

Uncountable Homogeneous Partial Orders

A partially ordered set (P, ≤) is called k‐homogeneous if any isomorphism between k‐element subsets extends to an automorphism of (P, ≤). Assuming the set‐theoretic assumption ⋄(ϰ₁), it is shown that for each k, there exist partially ordered sets of size ϰ₁ which embed each countable partial order and are k‐homogeneous, but not (k + 1)‐homogeneous. This is impossible in the countable case for k ≥ 4.     

A class of symmetric graphs with 2‐arc transitive quotients

Let Γ be an X‐symmetric graph admitting an X‐invariant partition ?? on V(Γ) such that Γ_?? is connected and (X, 2)‐arc transitive. A characterization of (Γ, X, ??) was given in [S. Zhou Eur J Comb 23 (2002), 741–760] for the case where |B|>|Γ(C)∩B|=2 for an arc (B, C) of Γ_??.We con‐sider in this article the case where |B|>|Γ(C)∩B|=3, and prove that Γ can be constructed from a 2‐arc transitive graph of valency 4 or 7 unless its connected components are isomorphic to 3 K ₂, C ₆ or K _{3, 3}. As a byproduct, we prove that each connected tetravalent (X, 2)‐transitive graph is either the complete graph K ₅ or a near n‐gonal graph for some n?4. © 2010 Wiley Periodicals, Inc. J Graph Theory 65: 232–245, 2010     

On Countable Products of Finite Hausdorff Spaces

We investigate in ZF (i.e., Zermelo‐Fraenke set theory without the axiom of choice) conditions that are necessary and sufficient for countable products ∏_m∈ℕX_m of (a) finite Hausdorff spaces X_m resp. (b) Hausdorff spaces X_m with at most n points to be compact resp. Baire. Typica results: (i) Countable products of finite Hausdorff spaces are compact (resp. Baire) if and only if countable products of non‐empty finite sets are non‐empty. (ii) Countable products of discrete spaces with at most n + 1 points are compact (resp. Baire) if and only if countable products of non‐empty sets with at most n points are non‐empty.     

Continuous k‐to‐1 functions between complete graphs whose orders are of a different parity

A function between graphs is k‐to‐1 if each point in the codomain has precisely k pre‐images in the domain. Given two graphs, G and H, and an integer k≥1, and considering G and H as subsets of ?³, there may or may not be a k‐to‐1 continuous function (i.e. a k‐to‐1 map in the usual topological sense) from G onto H. In this paper we consider graphs G and H whose order is of a different parity and determine the even and odd values of k for which there exists a k‐to‐1 map from G onto H. We first consider k‐to‐1 maps from K_2r onto K_2s+1 and prove that for 1≤r≤s, (r, s)≠(1, 1), there is a continuous k‐to‐1 map for k even if and only if k≥2s and for k odd if and only if k≥?s?_o (where ?s?_o indicates the next odd integer greater than or equal to s). We then consider k‐to‐1 maps from K_2s+1 onto K_2s. We show that for 1≤r<s, such a map exists for even values of k if and only if k≥2s. We also prove that whatever the values of r and s are, no such k‐to‐1 map exists for odd values of k. To conclude, we give all triples (n, k, m) for which there is a k‐to‐1 map from K_n onto K_m in the case when n≤m. © 2009 Wiley Periodicals, Inc. J Graph Theory 65: 35–60, 2010.     

Trading crossings for handles and crosscaps

Let c_k = cr_k (G) denote the minimum number of edge crossings when a graph G is drawn on an orientable surface of genus k. The (orientable) crossing sequence c_o, c₁,c₂…encodes the trade‐off between adding handles and decreasing crossings. We focus on sequences of the type c_o > c₁ > c₂ = 0; equivalently, we study the planar and toroidal crossing number of doubly‐toroidal graphs. For every ? > 0 we construct graphs whose orientable crossing sequence satisfies c₁/c_o > 5/6??. In other words, we construct graphs where the addition of one handle can save roughly 1/6th of the crossings, but the addition of a second handle can save five times more crossings. We similarly define the non‐orientable crossing sequence ?₀,?₁,?₂, ··· for drawings on non‐orientable surfaces. We show that for every ?₀ > ?₁ > 0 there exists a graph with non‐orientable crossing sequence ?₀, ?₁, 0. We conjecture that every strictly‐decreasing sequence of non‐negative integers can be both an orientable crossing sequence and a non‐orientable crossing sequence (with different graphs). © 2001 John Wiley & Sons, Inc. J Graph Theory 38: 230–243, 2001     

A note on the first‐order logic of complete BL‐chains

In [10] it is claimed that the set of predicate tautologies of all complete BL‐chains and the set of all standard tautologies (i. e., the set of predicate formulas valid in all standard BL‐algebras) coincide. As noticed in [11], this claim is wrong. In this paper we show that a complete BL‐chain B satisfies all standard BL‐tautologies iff for any transfinite sequence (a_i: i ∈ I) of elements of B , the condition ∧_{i ∈ I} (a²_i ) = (∧_{i ∈ I} a_i)² holds in B . (© 2008 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Y‐rotation in k‐minimal quadrangulations on the projective plane

Let G be a quadrangulation on a surface, and let f be a face bounded by a 4‐cycle abcd. A face‐contraction of f is to identify a and c (or b and d) to eliminate f. We say that a simple quadrangulation G on the surface is k‐minimal if the length of a shortest essential cycle is k(≥3), but any face‐contraction in G breaks this property or the simplicity of the graph. In this article, we shall prove that for any fixed integer k≥3, any two k‐minimal quadrangulations on the projective plane can be transformed into each other by a sequence of Y‐rotations of vertices of degree 3, where a Y‐rotation of a vertex v of degree 3 is to remove three edges vv₁, vv₃, vv₅ in the hexagonal region consisting of three quadrilateral faces vv₁v₂v₃, vv₃v₄v₅, and vv₅v₆v₁, and to add three edges vv₂, vv₄, vv₆. Actually, every k‐minimal quadrangulation (k≥4) can be reduced to a (k?1)‐minimal quadrangulation by the operation called Möbius contraction, which is mentioned in Lemma 13. © 2011 Wiley Periodicals, Inc. J Graph Theory 69: 301–313, 2012     

Fuzzy topology representation for MV‐algebras

Let M be an MV‐algebra and Ω_M be the set of all σ ‐valuations from M into the MV‐unit interval. This paper focuses on the characterization of MV‐algebras using σ ‐valuations of MV‐algebras and proves that a σ ‐complete MV‐algebra is σ ‐regular, which means that a ≤ b if and only if v (a) ≤ v (b) for any v ∈ Ω_M. Then one can introduce in a natural way a fuzzy topology δ on Ω_M. The representation theorem forMV‐algebras is established by means of fuzzy topology. Some properties of fuzzy topology δ and its cut topology U are investigated (© 2009 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Low sets without subsets of higher many‐one degree

Given a reducibility ?_r, we say that an infinite set A is r‐introimmune if A is not r‐reducible to any of its subsets B with |A\B| = ∞. We consider the many‐one reducibility ?_m and we prove the existence of a low₁ m‐introimmune set in Π⁰₁ and the existence of a low₁ bi‐m‐introimmune set.     

Extending colorings of locally planar graphs

Suppose G is a graph embedded in S_g with width (also known as edge width) at least 264(2^g−1). If P ⊆ V(G) is such that the distance between any two vertices in P is at least 16, then any 5‐coloring of P extends to a 5‐coloring of all of G. We present similar extension theorems for 6‐ and 7‐chromatic toroidal graphs, for 3‐colorable large‐width graphs embedded on S_g with every face even‐sided, and for 4‐colorable large‐width Eulerian triangulations. © 2001 John Wiley & Sons, Inc. J Graph Theory 36: 105–116, 2001     

Characterization of g∞,σ‐integral operators

The application of the general tensor norms theory of Defant and Floret to the ideal of (p, σ)‐absolutely continuous operators of Matter, 0 < σ < 1, 1 ≤ p < ∞ leads to the study of g_p′,σ‐nuclear and g_p′,σ‐integral operators. Characterizations of such operators has been obtained previously in the case p > 1. In this paper we characterize the g_∞,σ‐nuclear and g_∞,σ‐integral operators by the existence of factorizations of some special kinds. (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)