Ramsey's theorem with sums or unions

Using Hindman's theorem as a strong pigeonhole principle, we prove strengthened versions of Ramsey's theorem and of various generalizations of Ramsey's theorem due to Nash-Williams, Galvin and Prikry, and Silver.     

Some bounds for the Ramsey-Paris-Harrington numbers

It has recently been discovered that a certain variant of Ramsey's theorem cannot be proved in first-order Peano arithmetic although it is in fact a true theorem. In this paper we give some bounds for the “Ramsey-Paris-Harrington numbers” associated with this variant of Ramsey's theorem, involving coloring of pairs. In the course of the investigation we also study certain weaker and stronger partition relations.     

Partition theorems for unary algebras

Those unary algebras (A, ?) (A a set, ? a mapping from A into A) are characterized for which an analog of Ramsey's theorem holds.     

Ramsey’s theorem for trees: the polarized tree theorem and notions of stability

We formulate a polarized version of Ramsey’s theorem for trees. For those exponents greater than 2, both the reverse mathematics and the computability theory associated with this theorem parallel that of its linear analog. For pairs, the situation is more complex. In particular, there are many reasonable notions of stability in the tree setting, complicating the analysis of the related results.     

A canonical partition relation for finite subsets of ω

We prove a canonical partition relation for finite subsets of ω that generalizes Hindman's theorem in much the same way that the Erdös-Rado canonical partition relation generalizes Ramsey's theorem. As an application of this we establish a generalized pigeon-hole principle for infinite dimensional vector spaces over the two element field.     

The polarized Ramsey’s theorem

We study the effective and proof-theoretic content of the polarized Ramsey’s theorem, a variant of Ramsey’s theorem obtained by relaxing the definition of homogeneous set. Our investigation yields a new characterization of Ramsey’s theorem in all exponents, and produces several combinatorial principles which, modulo bounding for formulas, lie (possibly not strictly) between Ramsey’s theorem for pairs and the stable Ramsey’s theorem for pairs. We are grateful to D. Hirschfeldt, A. Montalbán, and R. Soare for making our collaboration possible and for helpful comments and suggestions. We thank J. Schmerl for first bringing the subject of polarized partitions to our attention and J. Mileti for his generous insights. We also thank one anonymous referee for valuable observations and corrections. The first author was partially supported by an NSF Graduate Research Fellowship.     

Product integrals II: Contour integrals

This paper continues the joint work of the authors begun in the article “On Strong Product Integration” [J. Functional Analysis, submitted]. We consider product integrals along contours; the point of view and development is analogous to the usual complex variable theory of ordinary contour integrals. Our main results are Theorem 2.3 (homotopy invariance of product integrals, an analog of Cauchy's integral theorem) and Theorem 3.4 (an analog of Cauchy's integral formula or the residue theorem).     

Induced partition properties of combinatorial cubes

An induced version of the partition theorem for parameter-sets of R. L. Graham and B. L. Rothschild (Trans. Amer. Math. Soc.159 (1971), 257–291) is proven. This theorem generalizes the Graham-Rothschild theorem in the same way as the partition theorem for finite hypergraphs (F. G. Abramson and L. A. Harrington, J. Symblic Logic43 (1978), 572–600 and J. Ne?et?il and V. Rödl; J. Combin. Theory Ser. A22 (1977), 289–312; 34 (1983), 183–201) generalizes Ramsey's theorem. Some applications are given, e.g., an induced version of the Rado-Folkman-Sanders theorem and an induced version of the partition theorem for finite Boolean lattices. Also it turns out that the partition theorem for finite hypergraphs is an easy consequence of the induced partition theorem for parameter-sets.     

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.     

The complexity of the equivalence and equation solvability problems over nilpotent rings and groups

It is proved that the equation solvability problem can be solved in polynomial time for finite nilpotent rings. Ramsey’s theorem is employed in the proof. Then, using the same technique, a theorem of Goldmann and Russell is reproved: the equation solvability problem can be solved in polynomial time for finite nilpotent groups.     

Extremal problems,partition theorems,symmetric hypergraphs

We compare extremal theorems such as Turán’s theorem with their corresponding partition theorems such as Ramsey’s theorem. We derive a general inequality involving chromatic number and independence number of symmetric hypergraphs. We give applications to Ramsey numbers and to van der Waerden numbers.     

Enumeration of coloured plane trees with a given type partition

Tutte's result for the number of planted plane trees with a given degree partition is rederived by a variety of methods and in particular by a simple piecewise construction technique. A theorem of Gordon and Temple is applied in order to give a general relationship between the number of planted plane trees and the number of rooted plane trees and the degree partition restriction is generalised to type partition. The piecewise construction method is successfully used to derive the number of planted plane trees with a given 2-colour degree partition, also derived by Tutte, and an algorithm for the k-coloured case is developed. This algorithm may be used to obtain more specific results. These models are relevant to the statistical mechanics of polymers and this is discussed briefly.     

Ambarzumian’s Theorem for a Sturm-Liouville Boundary Value Problem on a Star-Shaped Graph

Ambarzumian’s theorem describes the exceptional case in which the spectrum of a single Sturm-Liouville problem on a finite interval uniquely determines the potential. In this paper, an analog of Ambarzumian’s theorem is proved for the case of a Sturm-Liouville problem on a compact star-shaped graph. This case is also exceptional and corresponds to the Neumann boundary conditions at the pendant vertices and zero potentials on the edges.__________Translated from Funktsional’nyi Analiz i Ego Prilozheniya, Vol. 39, No. 2, pp. 78–81, 2005Original Russian Text Copyright © by V. N. Pivovarchik     

Hurwitz' theorem implies Rouché's theorem

It is well known that Hurwitz's theorem is easily proved from Rouché's theorem. We show that conversely, Rouché's theorem is readily proved from Hurwitz' theorem. Since Hurwitz' theorem is easily proved from the formula giving the number of roots of an analytic function, our result thus gives also a simple proof of Rouché's theorem.     

Helly-type theorems for pseudoline arrangements in P2

We prove duals of Radon's theorem, Helly's theorem, Carathéodory's theorem, and Kirchberger's theorem for arrangements of pseudolines in the real projective plane, which generalize the original versions of those theorems for plane configurations of points. We also prove a topological generalization of the pseudoline-dual of Helly's theorem.     

Position dependent and stochastic thinning of point processes

A short probabilistic proof of Kallenberg's theorem [2] on thinning of point processes is given. It is extended to the case where the probability of deletion of a point depends on the position of the point and is itself random. The proof also leads easily to a statement about the rate of convergence in Renyi's theorem on thinning a renewal process.     

On Fermat's last theorem and the Bernoulli numbers

Using Kummer's criteria we show that if the first case of Fermat's last theorem fails for the prime p, then there exist irregular pairs satisfying certain relations.     

An embedding theorem for regular Mal'tsev categories

In this paper, we obtain a non-abelian analogue of Lubkin's embedding theorem for abelian categories. Our theorem faithfully embeds any small regular Mal'tsev category $\mathbb{C}$ in an n-th power of a particular locally finitely presentable regular Mal'tsev category. The embedding preserves and reflects finite limits, isomorphisms and regular epimorphisms, as in the case of Barr's embedding theorem for regular categories. Furthermore, we show that we can take n to be the (cardinal) number of subobjects of the terminal object in $\mathbb{C}$.     

On Saint Venant's compatibility conditions and Poincaré's lemma

Saint Venant's theorem constitutes a classical characterization of smooth matrix fields as linearized strain tensor fields. This theorem has been extended to matrix fields with components in $L^2$ by the second author and P. Ciarlet, Jr. in 2005. One objective of this Note is to further extend this characterization to matrix fields whose components are only in $H^{\mathrm{?1}}$. Another objective is to demonstrate that Saint Venant's theorem is in fact nothing but the matrix analog of Poincaré's lemma. To cite this article: C. Amrouche et al., C. R. Acad. Sci. Paris, Ser. I 342 (2006).     

Remark on Wielandt's visibility theorem

A short proof is given of Wielandt's visibility theorem, using a special case of a theorem of Rédei, which was proved in an elementary way by Lóvasz and Schriver.