On the Π11‐separation principle

We study the proof‐theoretic strength of the Π₁¹‐separation axiom scheme, and we show that Π₁¹‐separation lies strictly in between the Δ₁¹‐comprehension and Σ₁¹‐choice axiom schemes over RCA₀. (© 2008 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Claw‐free 3‐connected P11‐free graphs are hamiltonian

We show that every 3‐connected claw‐free graph which contains no induced copy of P₁₁ is hamiltonian. Since there exist non‐hamiltonian 3‐connected claw‐free graphs without induced copies of P₁₂ this result is, in a way, best possible. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 111–121, 2004     

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

Multi‐term π‐institutions and their equivalence

The notion of a multi‐term π‐institution is introduced and a criterion for the equivalence of two multi‐term π‐institutions in terms of their categories of theories is proved. Moreover, a counterexample that shows that this criterion is false for arbitrary π‐institutions is given. (© 2006 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

On ε‐biased generators in NC0

Cryan and Miltersen (Proceedings of the 26th Mathematical Foundations of Computer Science, 2001, pp. 272–284) recently considered the question of whether there can be a pseudorandom generator in NC⁰, that is, a pseudorandom generator that maps n‐bit strings to m‐bit strings such that every bit of the output depends on a constant number k of bits of the seed. They show that for k = 3, if m ≥ 4n + 1, there is a distinguisher; in fact, they show that in this case it is possible to break the generator with a linear test, that is, there is a subset of bits of the output whose XOR has a noticeable bias. They leave the question open for k ≥ 4. In fact, they ask whether every NC⁰ generator can be broken by a statistical test that simply XORs some bits of the input. Equivalently, is it the case that no NC⁰ generator can sample an ε‐biased space with negligible ε? We give a generator for k = 5 that maps n bits into cn bits, so that every bit of the output depends on 5 bits of the seed, and the XOR of every subset of the bits of the output has bias 2. For large values of k, we construct generators that map n bits to bits such that every XOR of outputs has bias . We also present a polynomial‐time distinguisher for k = 4,m ≥ 24n having constant distinguishing probability. For large values of k we show that a linear distinguisher with a constant distinguishing probability exists once m ≥ Ω(2^kn^?k/2?). Finally, we consider a variant of the problem where each of the output bits is a degree k polynomial in the inputs. We show there exists a degree k = 2 pseudorandom generator for which the XOR of every subset of the outputs has bias 2^?Ω(n) and which maps n bits to Ω(n²) bits. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

A note on parameter free Π1‐induction and restricted exponentiation

We characterize the sets of all Π₂ and all $\mathcal {B}(\Sigma _{1})We characterize the sets of all Π₂ and all $\mathcal {B}(\Sigma _{1})$ (= Boolean combinations of Σ₁) theorems of IΠ^?₁ in terms of restricted exponentiation, and use these characterizations to prove that both sets are not deductively equivalent. We also discuss how these results generalize to n > 0. As an application, we prove that a conservation theorem of Beklemishev stating that IΠ^?_{n + 1} is conservative over IΣ^?_n with respect to $\mathcal {B}(\Sigma _{n+1})$ sentences cannot be extended to Π_{n + 2} sentences. © 2011 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim     

Σ‐algebraically compact modules and ‐compact cardinals

We prove that the property characterizes Σ‐algebraically compact modules if is not ω‐measurable. Moreover, under a large cardinal assumption, we show that over any ring R where is not ω‐measurable, any free module M of ω‐measurable rank satisfies , hence the assumption on cannot be dropped in general (e.g., over small non‐right perfect rings). In this way, we extend results from a recent paper by Simion Breaz 4 .     

Properly Σ2 minimal degrees and 0″ complementation

We show that there exists a properly Σ₂ minimal (Turing) degree b , and moreover that b can be chosen to join with 0 ′ to 0 ″ – so that b is a 0 ″ complement for every degree a such that 0 ′ ≤ a < 0 ″. (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

On effective σ‐boundedness and σ‐compactness

We prove several dichotomy theorems which extend some known results on σ‐bounded and σ‐compact pointsets. In particular we show that, given a finite number of $\Delta ^{1}_{1}$ equivalence relations $\mathrel {\mathsf {F}}_1,\dots ,\mathrel {\mathsf {F}}_n$, any $\Sigma ^{1}_{1}$ set A of the Baire space either is covered by compact $\Delta ^{1}_{1}$ sets and lightface $\Delta ^{1}_{1}$ equivalence classes of the relations $\mathrel {\mathsf {F}}_i$, or A contains a superperfect subset which is pairwise $\mathrel {\mathsf {F}}_i$‐inequivalent for all i = 1, …, n. Further generalizations to $\Sigma ^{1}_{2}$ sets A are obtained.     

Judiciously 3‐partitioning 3‐uniform hypergraphs

Bollobás, Reed, and Thomason proved every 3‐uniform hypergraph ? with m edges has a vertex‐partition V()=V₁?V₂?V₃ such that each part meets at least edges, later improved to 0.6m by Halsegrave and improved asymptotically to 0.65m+o(m) by Ma and Yu. We improve this asymptotic bound to , which is best possible up to the error term, resolving a special case of a conjecture of Bollobás and Scott.     

Maximal σ‐polynomials of connected 3‐chromatic graphs

In the set of graphs of order n and chromatic number k the following partial order relation is defined. One says that a graph G is less than a graph H if c_i(G) ≤ c_i(H) holds for every i, k ≤ i ≤ n and at least one inequality is strict, where c_i(G) denotes the number of i‐color partitions of G. In this paper the first ? n/2 ? levels of the diagram of the partially ordered set of connected 3‐chromatic graphs of order n are described. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 210–222, 2003     

Graphs with Few 3‐Cliques and 3‐Anticliques are 3‐Universal

For given integers we ask whether every large graph with a sufficiently small number of k‐cliques and k‐anticliques must contain an induced copy of every l‐vertex graph. Here we prove this claim for with a sharp bound. A similar phenomenon is established as well for tournaments with .     

Categorical abstract algebraic logic: Gentzen π ‐institutions and the deduction‐detachment property

Given a π ‐institution I , a hierarchy of π ‐institutions I ^{(n )} is constructed, for n ≥ 1. We call I ^{(n )} the n‐th order counterpart of I . The second‐order counterpart of a deductive π ‐institution is a Gentzen π ‐institution, i.e. a π ‐institution associated with a structural Gentzen system in a canonical way. So, by analogy, the second order counterpart I ⁽²⁾ of I is also called the “Gentzenization” of I . In the main result of the paper, it is shown that I is strongly Gentzen , i.e. it is deductively equivalent to its Gentzenization via a special deductive equivalence, if and only if it has the deduction‐detachment property . (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Minimal extensions of Π01 classes

A minimal extension of a Π⁰₁ class P is a Π⁰₁ class Q such that P ? Q, Q – P is infinite, and for any Π⁰₁ class R, if P ? R ? Q, then either R – P is finite or Q – R is finite; Q is a nontrivial minimal extension of P if in addition P and Q′ have the same Cantor‐Bendixson derivative. We show that for any class P which has a single limit point A, and that point of degree ≤ 0 , P admits a nontrivial minimal extension. We also show that as long as P is infinite, then P does not admit any decidable nontrivial minimal extension Q. (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Some examples of homotopy Π-algebras

The homotopy Π-algebra of a pointed topological space, X, consists of the homotopy groups of X together with the additional structure of the primary homotopy operations. We extend two well-known results for homotopy groups to homotopy Π-algebras and look at some examples illustrating the depth of structure on homotopy groups; from graded group to graded Lie ring, to Π-algebra and beyond. We also describe an abstract Π-algebra and give three abstract Π-algebra structures on the homotopy groups of the loop space of X which can be realized as the homotopy Π-algebras of three different spaces.     

The 8π‐problem for radially symmetric solutions of a chemotaxis model in the plane

The existence, uniqueness and large time behaviour of radially symmetric solutions to a chemotaxis system in the plane ?² are studied either for the critical value of the mass equal to 8π or in the subcritical case. Copyright © 2006 John Wiley & Sons, Ltd.     

Large ‐ or ‐Minors in 3‐Connected Graphs

There are numerous results bounding the circumference of certain 3‐connected graphs. There is no good bound on the size of the largest bond (cocircuit) of a 3‐connected graph, however. Oporowski, Oxley, and Thomas (J Combin Theory Ser B 57 (1993), 2, 239–257) proved the following result in 1993. For every positive integer k, there is an integer such that every 3‐connected graph with at least n vertices contains a ‐ or ‐minor. This result implies that the size of the largest bond in a 3‐connected graph grows with the order of the graph. Oporowski et al. obtained a huge function iteratively. In this article, we first improve the above authors' result and provide a significantly smaller and simpler function . We then use the result to obtain a lower bound for the largest bond of a 3‐connected graph by showing that any 3‐connected graph on n vertices has a bond of size at least . In addition, we show the following: Let G be a 3‐connected planar or cubic graph on n vertices. Then for any , G has a ‐minor with , and thus a bond of size at least .     

Characterization of ‐like and c0‐like equivalence relations

In this paper, notions of ‐like and c₀‐like equivalence relations are introduced. We characterize the positions of ‐like and c₀‐like equivalence relations in the Borel reducibility hierarchy by comparing them with equivalence relations and .     

Jump inversions of algebraic structures and Σ‐definability

It is proved that for every countable structure and a computable successor ordinal α there is a countable structure which is ‐least among all countable structures such that is Σ‐definable in the αth jump . We also show that this result does not hold for the limit ordinal . Moreover, we prove that there is no countable structure with the degree spectrum for .     

Codiameters of 3‐connected 3‐domination critical graphs

A graph G is 3‐domination critical if its domination number γ is 3 and the addition of any edge decreases γ by 1. Let G be a 3‐connected 3‐domination critical graph of order n. In this paper, we show that there is a path of length at least n?2 between any two distinct vertices in G and the lower bound is sharp. © 2002 John Wiley & Sons, Inc. J Graph Theory 39: 76–85, 2002