A generalization of Ramsey's theorem for regular trees

An analog of Ramsey's theorem for regular trees is proved. The original theorem is a special case of it. It is shown that the denumerable case of Ramsey's theorem has no analog for binary trees.     

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.     

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.     

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.     

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.     

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.     

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.     

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.     

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.     

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.     

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.     

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.     

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.     

Fixed point theorems for precomplete numberings

In the context of his theory of numberings, Ershov showed that Kleene's recursion theorem holds for any precomplete numbering. We discuss various generalizations of this result. Among other things, we show that Arslanov's completeness criterion also holds for every precomplete numbering, and we discuss the relation with Visser's ADN theorem, as well as the uniformity or nonuniformity of the various fixed point theorems. Finally, we base numberings on partial combinatory algebras and prove a generalization of Ershov's theorem in this context.     

A generalization of theorems of Krasnoselskii and Juberg

In this paper, we use the author's diagram proof of Riesz's theorem together with special seminorms to show that two theorems proved by the author generalize a compact interpolation theorem of Krasnoselskii, and a compact interpolation theorem of Juberg.     

Quelques theoremes de dualite combinatoire

The purpose of this paper is to prevent some new and unified proofs of a number of known results in combinatorial programming: generalized versions of Minty's lemma, of Ford and Fulkerson's and Hoffman's theorems the length-width inequality and the strong complementary slackness theorem. All these results are derived from a “main duality theorem” which can be deduced from the duality theorem of linear programming or from more general results of convex analysis.     

On the extension of von Neumann-Aumann's theorem

We give a measurable selection theorem which generalizes von Neumann-Aumann's theorem when the domain of definition is an abstract measurable space and the range space is a Suslin space.As application we give a measurable implicit function theorem and a parametrized version of Choquet's theorem on integral representation.     

A short proof of Kneser's conjecture

In the paper a short proof is given for Kneser's conjecture. The proof is based on Borsuk's theorem and on a theorem of Gale.     

Extensions of Liouville theorems

The method of deriving Liouville's theorem for subharmonic functions in the plane from the corresponding Hadamard three-circles theorem is extended to a more general and abstract setting. Two extensions of Liouville's theorem for vector-valued holomorphic functions of several complex variables are also mentioned.     

Analytic proofs of a network feasibility theorem and a theorem of Fulkerson

We provide an elementary proff of Fulkerson's theorem which gives the permutation matrices as extreme points of a certain unbounded convex polyhedron. An adaptation of the proof also establishes an analogous feasibility theorem for network flows which has Fulkerson's theorem as a corollary.