A hierarchy of Turing degrees of divergence bounded computable real numbers

A real number x is f-bounded computable (f-bc, for short) for a function f if there is a computable sequence (x_s) of rational numbers which converges to x f-bounded effectively in the sense that, for any natural number n, the sequence (x_s) has at most f(n) non-overlapping jumps of size larger than 2^-n. f-bc reals are called divergence bounded computable if f is computable. In this paper we give a hierarchy theorem for Turing degrees of different classes of f-bc reals. More precisely, we will show that, for any computable functions f and g, if there exists a constant γ>1 such that, for any constant c, f(nγ)+n+cg(n) holds for almost all n, then the classes of Turing degrees given by f-bc and g-bc reals are different. As a corollary this implies immediately the result of [R. Rettinger, X. Zheng, On the Turing degrees of the divergence bounded computable reals, in: CiE 2005, June 8–15, Amsterdam, The Netherlands, Lecture Notes in Computer Science, vol. 3526, 2005, Springer, Berlin, pp. 418–428.] that the classes of Turing degrees of d-c.e. reals and divergence bounded computable reals are different.     

Claw‐free graphs and 2‐factors that separate independent vertices

In this article, we prove that a line graph with minimum degree δ≥7 has a spanning subgraph in which every component is a clique of order at least three. This implies that if G is a line graph with δ≥7, then for any independent set S there is a 2‐factor of G such that each cycle contains at most one vertex of S. This supports the conjecture that δ≥5 is sufficient to imply the existence of such a 2‐factor in the larger class of claw‐free graphs. It is also shown that if G is a claw‐free graph of order n and independence number α with δ≥2n/α?2 and n≥3α³/2, then for any maximum independent set S, G has a 2‐factor with α cycles such that each cycle contains one vertex of S. This is in support of a conjecture that δ≥n/α≥5 is sufficient to imply the existence of a 2‐factor with α cycles, each containing one vertex of a maximum independent set. © 2011 Wiley Periodicals, Inc. J Graph Theory 69: 251–263, 2012     

On the index sets of Σ-subsets of the real numbers

We compute the levels of complexity in analytical and arithmetical hierarchies for the sets of the Σ-formulas defining in the hereditarily finite superstructure over the ordered field of the reals the classes of open, closed, clopen, nowhere dense, dense subsets of ? ⁿ , first category subsets in ? ⁿ as well as the sets of pairs of Σ-formulas corresponding to the relations of set equality and inclusion which are defined by them. It is also shown that the complexity of the set of the Σ-formulas defining connected sets is at least Π ₁ ¹ .     

Sparse pseudo‐random graphs are Hamiltonian

In this article we study Hamilton cycles in sparse pseudo‐random graphs. We prove that if the second largest absolute value λ of an eigenvalue of a d‐regular graph G on n vertices satisfies and n is large enough, then G is Hamiltonian. We also show how our main result can be used to prove that for every c >0 and large enough n a Cayley graph X (G,S), formed by choosing a set S of c log⁵ n random generators in a group G of order n, is almost surely Hamiltonian. © 2002 Wiley Periodicals, Inc. J Graph Theory 42: 17–33, 2003     

A note on the axiomatisation of real numbers

Is it possible to give an abstract characterisation of constructive real numbers? A condition should be that all axioms are valid for Dedekind reals in any topos, or for constructive reals in Bishop mathematics. We present here a possible first‐order axiomatisation of real numbers, which becomes complete if one adds the law of excluded middle. As an application of the forcing relation defined in [3, 2], we give a proof that the formula which specifies the maximum function is not provable in this theory. (© 2008 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Regular Action in Rings

Let R be a ring with identity, X(R) the set of all nonzero non-units of R and G(R) the group of all units of R. By considering left and right regular actions of G(R) on X(R), the following are investigated: (1) For a local ring R such that X(R) is a union of n distinct orbits under the left (or right) regular action of G(R) on X(R), if J ⁿ  ≠ 0 = J ⁿ⁺¹ where J is the Jacobson radical of R, then the set of all the distinct ideals of R is exactly {R, J, J ²,…, J ⁿ , 0}, and each orbit under the left regular action is equal to the one under the right regular action. (2) Such a ring R is left (and right) duo ring. (3) For the full matrix ring S of n × n matrices over a commutative ring R, the number of orbits under left regular action of G(S) on X(S) is equal to the number of orbits under right regular action of G(S) on X(S); the result also holds for the ring of n × n upper triangular matrices over R.     

Regularity Near a Contact Point for Flame Propagation

In this paper we study a free boundary problem, arising from a model for the propagation of laminar flames. Consider a cylindrical region S in ? ⁿ , and the following free boundary problem with Dirichlet data on ? S: u _t  = Δ u in {u > 0} ∩ S, |? u|=1 on ? {u > 0} ∩ S and u = 0 on ? S. We show that if there is a contact point of the free boundary {u = 0, |? u|=1} with ? S, then the free boundary approaches ? S tangentially and it turns out to be a graph of C ^{1+α, α} function near the contact point. In particular, the space normal is Hölder continuous.     

The size Ramsey number of trees with bounded degree

The size Ramsey number r?(G, H) of graphs G and H is the smallest integer r? such that there is a graph F with r? edges and if the edge set of F is red-blue colored, there exists either a red copy of G or a blue copy of H in F. This article shows that r?(T_nd, T_nd) ? c · d² · n and c · n³ ? r?(K_n, T_nd) ? c(d)·n³ log n for every tree T_nd on n vertices. and maximal degree at most d and a complete graph K_n on n vertices. A generalization will be given. Probabilistic method is used throught this paper. © 1993 John Wiley Sons, Inc.     

Nonnegative rank-preserving operators

Analogues of characterizations of rank-preserving operators on field-valued matrices are determined for matrices witheentries in certain structures $\text{S}$ contained in the nonnegative reals. For example, if $\text{S}$ is the set of nonnegative members of a real unique factorization domain (e.g. the nonnegative reals or the nonnegative integers), M is the set of m×n matrices with entries in $\text{S}$, and min(m,n)?4, then a “linear” operator on M preserves the “rank” of each matrix in M if and only if it preserves the ranks of those matrices in M of ranks 1, 2, and 4. Notions of rank and linearity are defined analogously to the field-valued concepts. Other characterizations of rank-preserving operators for matrices over these and other structures $\text{S}$ are also given.     

Some results on (k, μ)′-almost Kenmotsu manifolds

In this paper, we study the Weyl conformal curvature tensor 𝒲 and the concircular curvature tensor 𝒞 on a (k, μ)′-almost Kenmotsu manifold M²ⁿ⁺¹ of dimension greater than 3. We obtain that if M²ⁿ⁺¹ satisfies either R · 𝒲 = 0 or 𝒞 · 𝒞 = 0, then it is locally isometric to either the hyperbolic space ?²ⁿ⁺¹ (?1) or the Riemannian product ?ⁿ⁺¹(?4) × ?ⁿ.     

Multiple Phase Transitions in Long‐Range First‐Passage Percolation on Square Lattices

We consider a model of long‐range first‐passage percolation on the d‐dimensional square lattice ?d in which any two distinct vertices x,y ? ?^d are connected by an edge having exponentially distributed passage time with mean ‖ x – y ‖^α+o(1), where α > 0 is a fixed parameter and ‖·‖ is the l¹–norm on ?^d. We analyze the asymptotic growth rate of the set ß_t, which consists of all x ? ?^d such that the first‐passage time between the origin 0 and x is at most t as t → ∞. We show that depending on the values of α there are four growth regimes: (i) instantaneous growth for α < ^d, (ii) stretched exponential growth for α ? d,2d), (iii) superlinear growth for α ? (2d,2d + 1), and finally (iv) linear growth for α > 2d + 1 like the nearest‐neighbor first‐passage percolation model corresponding to α=∞. © 2015 Wiley Periodicals, Inc.     

Tree decompositions of graphs without large bipartite holes

A recent result of Condon, Kim, Kühn, and Osthus implies that for any , an n‐vertex almost r‐regular graph G has an approximate decomposition into any collections of n‐vertex bounded degree trees. In this paper, we prove that a similar result holds for an almost αn‐regular graph G with any α>0 and a collection of bounded degree trees on at most (1?o(1))n vertices if G does not contain large bipartite holes. This result is sharp in the sense that it is necessary to exclude large bipartite holes and we cannot hope for an approximate decomposition into n‐vertex trees. Moreover, this implies that for any α>0 and an n‐vertex almost αn‐regular graph G, with high probability, the randomly perturbed graph has an approximate decomposition into all collections of bounded degree trees of size at most (1?o(1))n simultaneously. This is the first result considering an approximate decomposition problem in the context of Ramsey‐Turán theory and the randomly perturbed graph model.     

Partial Regularity for Singular Solutions to the Monge‐Ampère Equation

We prove that solutions to the Monge‐Ampère inequality in ?ⁿ are strictly convex away from a singular set of Hausdorff (n‐1)‐dimensional measure zero. Furthermore, we show this is optimal by constructing solutions to det D²u = 1 with singular set of Hausdorff dimension as close as we like to n‐1. As a consequence we obtain W^2,1 regularity for the Monge‐Ampère equation with bounded right‐hand side and unique continuation for the Monge‐Ampère equation with sufficiently regular right‐hand side. © 2015 Wiley Periodicals, Inc.     

There is No Low Maximal D.C.E. Degree

We show that for any computably enumerable (c.e.) set A and any set L, if L is low and , then there is a c.e. splitting such that . In Particular, if L is low and n‐c.e., then is n‐c.e. and hence there is no low maximal n‐c.e. degree.     

Web‐compact spaces,Fréchet‐Urysohn groups and a Suslin closed graph theorem

A topological space X is strongly web‐compact if X admits a family {A_α: α ∈ ?^?} of relatively countably compact sets covering X and such that A_α ? A_β for α ≤ β. The main result of this paper states the following: Theorem A Let X and Y be topological groups and f a homomorphism between X and Y with closed graph. If X is Fréchet‐Urysohn and Baire and Y is strongly web‐compact, then f is continuous. This extends a result of Valdivia. We provide an example showing that the property of being strongly web‐compact is not productive. This applies to show that there are quasi‐Suslin spaces X whose product X × X is not quasi‐Suslin (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Cyclability of 3‐connected graphs

A subset S of vertices of a graph G is called cyclable in G if there is in G some cycle containing all the vertices of S. We denote by α(S, G) the number of vertices of a maximum independent set of G[S]. We prove that if G is a 3‐connected graph or order n and if S is a subset of vertices such that the degree sum of any four independent vertices of S is at least n + 2α(S, G) −2, then S is cyclable. This result implies several known results on cyclability or Hamiltonicity. © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 191–203, 2000     

Independent perfect domination sets in Cayley graphs

In this paper, we show that a Cayley graph for an abelian group has an independent perfect domination set if and only if it is a covering graph of a complete graph. As an application, we show that the hypercube Q_n has an independent perfect domination set if and only if Q_n is a regular covering of the complete graph K_n+1 if and only if n = 2^m ? 1 for some natural number m. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 213–219, 2001     

On the lattice property of the plane and some problems of Dirac,Motzkin and Erdős in combinatorial geometry

LetS be a set ofn non-collinear points in the Euclidean plane. It will be shown here that for some point ofS the number ofconnecting lines through it exceedsc · n. This gives a partial solution to an old problem of Dirac and Motzkin. We also prove the following conjecture of Erdős: If any straight line contains at mostn−x points ofS, then the number of connecting lines determined byS is greater thanc · x · n. Dedicated to Paul Erdős on his seventieth birthday     

On the complexity of axiomatizations of the class of representable quasi‐polyadic equality algebras

Using games, as introduced by Hirsch and Hodkinson in algebraic logic, we give a recursive axiomatization of the class RQPEA _α of representable quasi‐polyadic equality algebras of any dimension α. Following Sain and Thompson in modifying Andréka’s methods of splitting, to adapt the quasi‐polyadic equality case, we show that if Σ is a set of equations axiomatizing RPEA _n for $2< n <\omegaUsing games, as introduced by Hirsch and Hodkinson in algebraic logic, we give a recursive axiomatization of the class RQPEA _α of representable quasi‐polyadic equality algebras of any dimension α. Following Sain and Thompson in modifying Andréka’s methods of splitting, to adapt the quasi‐polyadic equality case, we show that if Σ is a set of equations axiomatizing RPEA _n for $2< n <\omega$ and $l< n,$ $k < n$, k′ < ω are natural numbers, then Σ contains infinitely equations in which ? occurs, one of + or · occurs, a diagonal or a permutation with index l occurs, more than k cylindrifications and more than k′ variables occur. © 2011 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim     

Vortex energy and 360° Néel walls in thin‐film micromagnetics

We study the vortex pattern in ultrathin ferromagnetic films of circular crosssection. The model is based on the following energy functional: for in‐plane magnetizations m: B² → S¹ in the unit disc . The avoidance of volume charges ? · m ≠ 0 in B² and surface charges m · ν ≠ 0 on δB² leads to the formation of a vortex in the limit ε → 0. At the level ε > 0 the vortex is regularized by the formation of a 360° Néel wall (a one‐dimensional transition layer with core of scale ε) concentrated along a radius of B². We derive the limiting energy of the vortex by matching upper and lower bounds. Our analysis on the lower bound is based on a dynamical system argument and an interpolation inequality with sharp leading‐order constant, while the upper bound uses the leading‐order energy for 360° Néel walls. © 2010 Wiley Periodicals, Inc.