James sequences and Dependent Choices

We prove James's sequential characterization of (compact) reflexivity in set‐theory ZF + DC , where DC is the axiom of Dependent Choices. In turn, James's criterion implies that every infinite set is Dedekind‐infinite, whence it is not provable in ZF . Our proof in ZF + DC of James' criterion leads us to various notions of reflexivity which are equivalent in ZFC but are not equivalent in ZF . We also show that the weak compactness of the closed unit ball of a (simply) reflexive space does not imply the Boolean Prime Ideal theorem : this solves a question raised in [6]. (© 2005 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Lebesgue’s dominated convergence theorem in Bishop’s style

We present a constructive proof in Bishop’s style of Lebesgue’s dominated convergence theorem in the abstract setting of ordered uniform spaces. The proof generalises to this setting a classical proof in the framework of uniform lattices presented by Hans Weber in [Uniform lattices. II: order continuity and exhaustivity, Annali di Matematica pura ed applicata, (IV) CLXV (1993) 133-158].     

The Arc‐Weighted Version of the Second Neighborhood Conjecture

Seymour conjectured that every oriented simple graph contains a vertex whose second neighborhood is at least as large as its first. Seymour's conjecture has been verified in several special cases, most notably for tournaments by Fisher  6 . One extension of the conjecture that has been used by several researchers is to consider vertex‐weighted digraphs. In this article we introduce a version of the conjecture for arc‐weighted digraphs. We prove the conjecture in the special case of arc‐weighted tournaments, strengthening Fisher's theorem. Our proof does not rely on Fisher's result, and thus can be seen as an alternate proof of said theorem.     

An algebraic certificate for Budan’s theorem

The existing algorithms to construct the real closure of an ordered field involve very high complexities. These algorithms are based on Sturm’s theorem which we suspect to be one reason for the complexities since all known proofs of Sturm’s theorem use Rolle’s theorem which is problematic in a constructive context.Therefore we propose to replace the use of Sturm’s theorem by Budan’s theorem. In this paper we present as a first step in this direction an algebraic certificate for Budan’s theorem. An algebraic certificate is a certain kind of proof of a statement. In particular, it is an algorithm which produces, from an arbitrary data in the premise of the statement, explicit (in)equalities which express the conclusion.     

Walker's Cancellation Theorem

Walker's cancellation theorem says that, if B ⊕ Z is isomorphic to C ⊕ Z in the category of abelian groups, then B is isomorphic to C. We construct an example in a diagram category of abelian groups where the theorem fails. As a consequence, the original theorem does not have a constructive proof even if B and C are subgroups of the free abelian group on two generators. Both of these results contrast with a group whose endomorphism ring has stable range one, which allows a constructive proof of cancellation and also a proof in any diagram category.     

Computing the Wedderburn decomposition of group algebras by the Brauer-Witt theorem

We present an alternative constructive proof of the Brauer-Witt theorem using the so-called strongly monomial characters that gives rise to an algorithm for computing the Wedderburn decomposition of semisimple group algebras of finite groups.

     

Some Special Tauberian Theorems for Fourier Type Integrals and Eigenfunction Expansions of Sturm-Liouville Equations on the Whole Line

We offer a new proof of a special Tauberian theorem for Fourier type integrals. This Tauberian theorem was already considered by us in the papers [1] and [2]. The idea of our initial proof was simple, but the details were complicated because we used Bochner's definition of generalized Fourier transform for functions of polynomial growth. In the present paper we work with L. Schwartz's generalization. This leads to significant simplification. The paper consists of six sections. In Section 1 we establish an integral representation of functions of polynomial growth (subjected to some Tauberian conditions), in Section 2 we prove our main Tauberian theorems (Theorems 2.1 and 2.2.), using the integral representation of Section 1, in Section 3 we study the asymptotic behavior of M. Riesz's means of functions of polynomial growth, in Sections 4 and 5 we apply our Tauberian theorems to the problem of equiconvergence of eigenfunction expansions of Sturm-Liouville equations and expansion in ordinary Fourier integrals, and in Section 6 we compare our general equiconvergence theorems of Sections 4 and 5 with the well known theorems on eigenfunction expansions in classical orthogonal polynomials. In some sense this paper is a re-made survey of our results obtained during the period 1953-58. Another proof of our Tauberian theorem and some generalization can be found in the papers [3] and [4].     

The swap of integral and limit in constructive mathematics

Integration within constructive, especially intuitionistic mathematics in the sense of L. E. J. Brouwer, slightly differs from formal integration theories: Some classical results, especially Lebesgue's dominated convergence theorem, have tobe substituted by appropriate alternatives. Although there exist sophisticated, but rather laborious proposals, e.g. by E. Bishop and D. S. Bridges (cf. [2]), the reference to partitions and the Riemann‐integral, also with regard to the results obtained by R. Henstock and J. Kurzweil (cf. [9], [12]), seems to give a better direction. Especially, convergence theorems can be proved by introducing the concept of “equi‐integrability”. The paper is strongly motivated by Brouwer's result that each function fully defined on a compact interval has necessarily to be uniformly continuous. Nevertheless, there are, with only one exception (a corollary of Theorem 4.2), no references to the fan‐theorem or to bar‐induction. Therefore, the whole paper can be read within the setting of Bishop's access to constructive mathematics. Nothing of genuine full‐fledged Brouwerian intuitionism is used for the main results in this note (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Comparison of Picard groups in dimension 1

We compare two Picard groups in dimension 1. Our proofs are constructive and the results generalize a theorem of J. Sands [11]. (© 2008 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Komlós's tiling theorem via graphon covers

Komlós [Komlós: Tiling Turán Theorems, Combinatorica, 2000] determined the asymptotically optimal minimum-degree condition for covering a given proportion of vertices of a host graph by vertex-disjoint copies of a fixed graph H, thus essentially extending the Hajnal–Szemerédi theorem that deals with the case when H is a clique. We give a proof of a graphon version of Komlós's theorem. To prove this graphon version, and also to deduce from it the original statement about finite graphs, we use the machinery introduced in [Hladký, Hu, Piguet: Tilings in graphons, arXiv:1606.03113]. We further prove a stability version of Komlós's theorem.     

Limit theorems on locally compact Abelian groups

We prove limit theorems for row sums of a rowwise independent infinitesimal array of random variables with values in a locally compact Abelian group. First we give a proof of Gaiser's theorem [4, Satz 1.3.6], since it does not have an easy access and it is not complete. This theorem gives sufficient conditions for convergence of the row sums, but the limit measure cannot have a nondegenerate idempotent factor. Then we prove necessary and sufficient conditions for convergence of the row sums, where the limit measure can be also a nondegenerate Haar measure on a compact subgroup. Finally, we investigate special cases: the torus group, the group of p ‐adic integers and the p ‐adic solenoid. (© 2008 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

New constructions of hypohamiltonian and hypotraceable graphs

A graph G is hypohamiltonian/hypotraceable if it is not hamiltonian/traceable, but all vertex‐deleted subgraphs of G are hamiltonian/traceable. All known hypotraceable graphs are constructed using hypohamiltonian graphs; here we present a construction that uses so‐called almost hypohamiltonian graphs (nonhamiltonian graphs, whose vertex‐deleted subgraphs are hamiltonian with exactly one exception, see [15]). This construction is an extension of a method of Thomassen [11]. As an application, we construct a planar hypotraceable graph of order 138, improving the best‐known bound of 154 [8]. We also prove a structural type theorem showing that hypotraceable graphs possessing some connectivity properties are all built using either Thomassen's or our method. We also prove that if G is a Grinbergian graph without a triangular region, then G is not maximal nonhamiltonian and using the proof method we construct a hypohamiltonian graph of order 36 with crossing number 1, improving the best‐known bound of 46 [14].     

The computational content of Walras’ existence theorem

In [Y. Tanaka, Undecidability of the Uzawa equivalence theorem and LLPO, Appl. Math. Comput. 201 (2008) 378-383] Yasuhito Tanaka showed that Walras’ existence theorem implies the nonconstructive lesser limited principle of omniscience (LLPO); it follows that Walras’ existence theorem does not admit a constructive proof. We give a constructive proof of an approximate version of Walras’ existence theorem from which the full theorem can be recovered with an application of LLPO. We then push Uzawa’s equivalence theorem to the level of approximate solutions, before considering economies with at most one equilibrium.     

Normal hyperimaginaries

We introduce the notion of normal hyperimaginary and we develop its basic theory. We present a new proof of the Lascar-Pillay theorem on bounded hyperimaginaries based on properties of normal hyperimaginaries. However, the use of the Peter–Weyl theorem on the structure of compact Hausdorff groups is not completely eliminated from the proof. In the second part, we show that all closed sets in Kim-Pillay spaces are equivalent to hyperimaginaries and we use this to introduce an approximation of φ-types for bounded hyperimaginaries.     

The natural numbers in constructive set theory

Constructive set theory started with Myhill's seminal 1975 article [8]. This paper will be concerned with axiomatizations of the natural numbers in constructive set theory discerned in [3], clarifying the deductive relationships between these axiomatizations and the strength of various weak constructive set theories. (© 2008 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

A short proof of rigidity of convex polytopes

We present a much simplified proof of Dehn’s theorem on the infinitesimal rigidity of convex polytopes. Our approach is based on the ideas of Trushkina [1] and Schramm [2].     

On generalizing Takahashi’s nonconvex minimization theorem

We present a simple proof of vectorial Takahashi’s nonconvex minimization theorem based on Gopfert, Tammer and Zalinescu [A. Gopfert, C. Tammer, C. Zalinescu, On the vectorial Ekeland’s variational principle and minimal points in product spaces, Nonlinear Anal. 39 (2000) 909–922; C. Tammer, A variational principle and a fixed point theorem, in: System Modelling and Optimization (Compiegne, 1993), in: Lecture Notes in Control and Inform. Sci., vol. 197, Springer, London, 1994, pp. 248–257].     

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     

On Wainer's notation for a minimal subrecursive inaccessible ordinal

We show the following results on Wainer's notation for a minimal subrecursive inaccessible ordinal τ: First, we give a constructive proof of the collapsing theorem. Secondly, we prove that the slow-growing hierarchy and the fast-growing hierarchy up to τ have elementary properties on increase and domination, which completes Wainer's proof that τ is a minimal subrecursive inaccessible. Our results are obtained by showing a strong normalization theorem for the term structure of the notation. MSC: 03D20, 03F15.