Planarity and duality of finite and infinite graphs

We present a short proof of the following theorems simultaneously: Kuratowski's theorem, Fary's theorem, and the theorem of Tutte that every 3-connected planar graph has a convex representation. We stress the importance of Kuratowski's theorem by showing how it implies a result of Tutte on planar representations with prescribed vertices on the same facial cycle as well as the planarity criteria of Whitney, MacLane, Tutte, and Fournier (in the case of Whitney's theorem and MacLane's theorem this has already been done by Tutte). In connection with Tutte's planarity criterion in terms of non-separating cycles we give a short proof of the result of Tutte that the induced non-separating cycles in a 3-connected graph generate the cycle space. We consider each of the above-mentioned planarity criteria for infinite graphs. Specifically, we prove that Tutte's condition in terms of overlap graphs is equivalent to Kuratowski's condition, we characterize completely the infinite graphs satisfying MacLane's condition and we prove that the 3-connected locally finite ones have convex representations. We investigate when an infinite graph has a dual graph and we settle this problem completely in the locally finite case. We show by examples that Tutte's criterion involving non-separating cycles has no immediate extension to infinite graphs, but we present some analogues of that criterion for special classes of infinite graphs.     

Unique prime factorization for infinite tensor product factors

In this article, we investigate a unique prime factorization property for infinite tensor product factors. We provide several examples of type II and III factors which satisfy this property, including all free product factors with diffuse free product components. In the type III setting, this is the first classification result for infinite tensor product non-amenable factors. Our proof is based on Popa's intertwining techniques and a characterization of relative amenability on the continuous cores.     

Wiener's lemma for infinite matrices with polynomial off-diagonal decay

In this Note, we give a simple elementary proof to Wiener's lemma for infinite matrices with polynomial off-diagonal decay. To cite this article: Q. Sun, C. R. Acad. Sci. Paris, Ser. I 340 (2005).     

Construction of pseudo-isometries for treelike hyperbolic 3-manifolds of infinite volume

We introduce a family of rigid hyperbolic 3-manifolds of infinite volume with possibly infinitely many ends: the treelike manifolds. These manifolds generalize a family of constructive non compact surfaces – the equational surfaces – for which the homeomorphism problem is decidable. The proof of rigidity relies firstly on Thurston's theorem of compactness of the Teichmüller space of acylindrical compact 3-manifolds, and secondly, on Sullivan's rigidity theorem. To cite this article: O. Ly, C. R. Acad. Sci. Paris, Ser. I 337 (2003).     

Rank-axiomatic characterizations of independence systems

Motivated by the rank-axiomatic definitions of a matroid and Woodall's characterization of independence systems [6] we provide an abstract framework for general independence systems in terms of their rank function.     

Elements of infinite filtrations in generalized cohomology theories on the category of spectra

This paper is devoted to the proof of a criterion for the existence of elements of infinite filtrations for an arbitrary generalized theory of cohomology of infinite complexes (or on the category of spectra).Translated from Matematicheskie Zametki, Vol. 11, No. 6, pp. 699–704, June, 1972.     

Some infinite classes of Hadamard matrices

Some results of Williamson [Duke Math. J., 11 1944, Bull. Amer. Math. Soc., 53 1947] and Wallis (J. Combinatorial Theory, 6 1969] are considerably improved to establish that in each case referred to, the same stated condition or conditions, which according to either of the authors give rise to one Hadamard matrix, actually imply the existence of an infinite series of Hadamard matrices. Also proved is the existence of some infinite series of Williamson's matrices, which coupled with the interesting findings of Turyn [J. Combinatorial Theory Ser. A, 16 1974] establish the existence of infinitely many more series of Hadamard matrices than those known so far.     

Correction to: On a decomposition for infinite stochastic matrices

An error in the proof to theorem 1 in: On a decomposition for infinite transition matrices, Queueing Systems 27 (1997) 127–130, is corrected. This revised version was published online in June 2006 with corrections to the Cover Date.     

Duality of infinite graphs

Some basic results on duality of infinite graphs are established and it is proven that a block has a dual graph if and only if it is planar and any two vertices are separated by a finite edge cut. Also, the graphs having predual graphs are characterized completely and it is shown that if $\text{G}{}^1$ is a dual and predual graph of G, then G and $\text{G}{}^1$ can be represented as geometric dual graphs. The uniqueness of dual graphs is investigated, in particular, Whitney's 2-isomorphism theorem is extended to infinite graphs. Finally, infinite minimal cuts in dual graphs are studied and the characterization (in terms of planarity and separation properties) of the graphs having dual graphs satisfying conditions on the infinite cuts, as well, is included.     

Some techniques for constructing infinite families of BIBD'S

Hadamard systems and balanced weighing systems, generalizing Hadamard matrices and balanced weighing matrices respectively, are defined and their properties are examined. Some of these systems are constructed and then used in constructing infinite families of BIBD's.     

Differential variational inequalities in infinite banach spaces

In this paper, we consider a new differential variational inequality (DVI, for short) which is composed of an evolution equation and a variational inequality in infinite Banach spaces. This kind of problems may be regarded as a special feedback control problem. Based on the Browder's theorem and the optimal control theory, we show the existence of solutions to the mentioned problem.     

The limb analysis of countably infinite electrical networks

A method, called “limb analysis,” for analyzing certain countably infinite electrical networks was developed in a prior publication. It consisted of two parts, a graph-theoretic decomposition of the network and an analysis wherein Kirchhoff's node and loop laws were applied. The present paper is primarily devoted to proving that every countable network possesses the required graphtheoretic decomposition. In addition, it also establishes a sufficient set of conditions under which the analytic portion of limb analysis has a solution.     

Gregory's converging double sequence: A new look at the controversy between huygens and gregory over the “analytical” quadrature of the circle

As is well known, upon publication of his Vera circuli et hyperbolae quadratura (Padua 1667), James Gregory became involved in a bitter controversy with Christiaan Huygens over the truth of one of his major propositions. It stated that the area of a sector of a central conic cannot be expressed “analytically” in terms of the areas of an inscribed triangle and a circumscribed quadrilateral. Huygens objected to Gregory's method of proof, and expressed doubts as to its validity. As Gregory's iterative limiting process, employing an infinite double sequence, uses a combination of geometric and harmonic means, one may apply to it methods developed by the young Gauss for dealing with a similar process based on the combination of arithmetic and geometric means. This yields both the Leibnizian series forπ/4 and the product found by Vie`te for2/π, and thus serves to illuminate the structure of Gregory's procedure and the nature of Huygens' criticism.     

Elementary submodels in infinite combinatorics

The use of elementary submodels is a simple but powerful method to prove theorems, or to simplify proofs in infinite combinatorics. First we introduce all the necessary concepts of logic, then we prove classical theorems using elementary submodels. We also present a new proof of Nash-Williams’s theorem on cycle decomposition of graphs, and finally we improve a decomposition theorem of Laviolette concerning bond-faithful decompositions of graphs.     

Choice functions and well-orderings over the infinite binary tree

We give a new proof showing that it is not possible to define in monadic second-order logic (MSO) a choice function on the infinite binary tree. This result was first obtained by Gurevich and Shelah using set theoretical arguments. Our proof is much simpler and only uses basic tools from automata theory. We show how the result can be used to prove the inherent ambiguity of languages of infinite trees. In a second part we strengthen the result of the non-existence of an MSO-definable well-founded order on the infinite binary tree by showing that every infinite binary tree with a well-founded order has an undecidable MSO-theory.     

Computation of an infinite integral using series acceleration

A numerical computation in crystallography involves an infinite integral depending on one parameter. In a recent article in this journal this computational problem is addressed using Romberg’s method and tools for error control. One observe numerical difficulties with the reported approach both near the parameter’s endpoints and near the parameter interval’s midpoint. In this short note we will present an alternative approach making use of a known infinite series formulation of the problem at hand and a simple and efficient series acceleration technique. If some care is taken to avoid cancellations the numerical results are excellent for all values of the parameter. AMS subject classification 65B05, 65B10, 65D30     

Local continuity modulus for wiener and infinite dimensional OU processes

In this paper, we gave a proof for the local continuity modulus theorem of the Wiener process, i.e., $$\mathop {\lim }\limits_{t \to 0} \mathop {\sup }\limits_{0 \leqslant s \leqslant t} |W(s)|/(2s\log \log (1/s))^{1/2} = 1$$ a.s. This result was given by Csörgö and Révész (1981), but the proof gets them nowhere. We also gave a similar local continuity modulus result for the infinite dimensional OU processes.     

Nearly perfect systems and effective generalizations of Shidlovski's Theorem

An effective proof of Shidlovski's Theorem is presented. The proof utilizes partial differential operators. A number of generalizations of Shidlovski's Theorem are proven, including results about approximation at more than one point. Additionally, partial differential equations are considered. The new methods give a particularly direct proof of Shidlovski's Theorem.     

Hypergraphs and Whitney's theorem on edge-isomorphisms of graphs

This paper presents a new proof of Whitney's theorem on edge-isomorphisms of graphs and extends Whitney's theorem to hypergraphs. Whitney's theorem asserts that any two edge-isomorphic graphs of order at least 5 have their edge-isomorphism induced by a node-isomorphism isomorphism. Previous results of Gardner and of Berge and Rado are used.