Some remarks on a question of D. H. Fremlin regarding ε-density

We show the relative consistency of ℵ₁ satisfying a combinatorial property considered by David Fremlin (in the question DU from his list) in certain choiceless inner models. This is demonstrated by first proving the property is true for Ramsey cardinals. In contrast, we show that in ZFC, no cardinal of uncountable cofinality can satisfy a similar, stronger property. The questions considered by D. H. Fremlin are if families of finite subsets of ω₁ satisfying a certain density condition necessarily contain all finite subsets of an infinite subset of ω₁, and specifically if this and a stronger property hold under MA + ?CH. Towards this we show that if MA + ?CH holds, then for every family ? of ℵ₁ many infinite subsets of ω₁, one can find a family ? of finite subsets of ω₁ which is dense in Fremlins sense, and does not contain all finite subsets of any set in ?. We then pose some open problems related to the question. Received: 2 June 1999 / Revised version: 2 February 2000 / Published online: 18 July 2001     

Simple proof of the existence of restricted ramsey graphs by means of a partite construction

By means of a partite construction we present a short proof of the Galvin Ramsey property of the class of all finite graphs and of its strengthening proved in [5]. We also establish a generalization of those results. Further we show that for every positive integerm there exists a graphH which is Ramsey forK _m and does not contain two copies ofK _m with more than two vertices in common.     

The Ulam number of infinite graphs

The following is a conjecture of Ulam: In any partition of the integer lattice on the plane into uniformly bounded sets, there exists a set that is adjacent to at least six other sets. Two sets are adjacent if each contain a vertex of the same unit square. This problem is generalized as follows. Given any uniformly bounded partitionP of the vertex set of an infinite graphG with finite maximum degree, letP (G) denote the graph obtained by letting each set of the partition be a vertex ofP (G) where two vertices ofP (G) are adjacent if and only if the corresponding sets have an edge between them. The Ulam number ofG is defined as the minimum of the maximum degree ofP (G) where the minimum is taken over all uniformly bounded partitionsP. We have characterized the graphs with Ulam number 0, 1, and 2. Restricting the partitions of the vertex set to connected subsets, we obtain the connected Ulam number ofG. We have evaluated the connected Ulam numbers for several infinite graphs. For instance we have shown that the connected Ulam number is 4 ifG is an infinite grid graph. We have settled the Ulam conjecture for the connected case by proving that the connected Ulam number is 6 for an infinite triangular grid graph. The general Ulam conjecture is equivalent to proving that the Ulam number of the infinite triangular grid graph equals 6. We also describe some interesting geometric consequences of the Ulam number, mainly concerning good drawings of infinite graphs.     

{\Pi^1_2} -comprehension and the property of Ramsey

We show that a theory of autonomous iterated Ramseyness based on second order arithmetic (SOA) is proof-theoretically equivalent to ${\Pi^1_2}$ -comprehension. The property of Ramsey is defined as follows. Let X be a set of real numbers, i.e. a set of infinite sets of natural numbers. We call a set H of natural numbers homogeneous for X if either all infinite subsets of H are in X or all infinite subsets of H are not in X. X has the property of Ramsey if there exists a set which is homogeneous for X. The property of Ramsey is considered in reverse mathematics to compare the strength of subsystems of SOA. To characterize the system of ${\Pi^1_2}$ -comprehension in terms of Ramseyness we introduce a system of autonomous iterated Ramseyness, called R-calculus. We augment the language of SOA with additional set terms (called R-terms) ${R\vec{x}X\phi(\vec{x},X)}$ for each first order formula ${\phi(\vec{x},X)}$ (where φ may contain further R-terms). The R-calculus is a system which comprises comprehension for all first order formulas (which may contain R-terms or other set parameters) and defining axioms for the R-terms which claim that for each ${\vec{x}}$ , we can remove finitely many elements from the set ${R\vec{x}X\phi(\vec{x},X)}$ such that the remaining set is homogeneous for ${\{{X}{\phi(\vec{x},X)\}}}$ . We show that the R-calculus proves the same ${\Pi^1_1}$ -sentences as the system of ${\Pi^1_2}$ -comprehension.     

Sharp thresholds for Ramsey properties of strictly balanced nearly bipartite graphs

For a given graph F we consider the family of (finite) graphs G with the Ramsey property for F, that is the set of such graphs G with the property that every two‐coloring of the edges of G yields a monochromatic copy of F. For F being a triangle Friedgut, Rödl, Ruciński, and Tetali (2004) established the sharp threshold for the Ramsey property in random graphs. We present a simpler proof of this result which extends to a more general class of graphs F including all cycles. The proof is based on Friedgut's criteria (1999) for sharp thresholds and on the recently developed container method for independent sets in hypergraphs by Saxton and Thomason and by Balogh, Morris and Samotij. The proof builds on some recent work of Friedgut et al. who established a similar result for van der Waerden's theorem.     

On Series of Ordinals and Combinatorics

This paper deals mainly with generalizations of results in finitary combinatorics to infinite ordinals. It is well-known that for finite ordinals ∑_bT<αβ is the number of 2-element subsets of an α-element set. It is shown here that for any well-ordered set of arbitrary infinite order type α, ∑_bT<αβ is the ordinal of the set M of 2-element subsets, where M is ordered in some natural way. The result is then extended to evaluating the ordinal of the set of all n-element subsets for each natural number n ≥ 2. Moreover, series ∑_β<αf(β) are investigated and evaluated, where α is a limit ordinal and the function f belongs to a certain class of functions containing polynomials with natural number coefficients. The tools developed for this result can be extended to cover all infinite α, but the case of finite α appears to be quite problematic.     

Angle orders and zeros

An angle order is a partially ordered set whose points can be mapped into unbounded angular regions in the plane such that x is less than y in the partial order if and only if x's angular region is properly included in y's. The zero augmentation of a partially ordered set adds one point to the set that is less than all original points. We prove that there are finite angle orders whose augmentations are not angle orders. The proof makes extensive use of Ramsey theory.     

Coding into Ramsey sets

In [6] W. T. Gowers formulated and proved a Ramsey-type result which lies at the heart of his famous dichotomy for Banach spaces. He defines the notion of weakly Ramsey set of block sequences of an infinite dimensional Banach space and shows that every analytic set of block sequences is weakly Ramsey. We show here that Gowers’ result follows quite directly from the fact that all G_δ sets are weakly Ramsey, if the Banach space does not contain c₀, and from the fact that all F_σδ sets are weakly Ramsey, in the case of an arbitrary Banach space. We also show that every result obtained by the application of Gowers’ theorem to an analytic set can also be obtained by applying the Theorem to a F_σδ set (or to a G_δ set if the space does not contain c₀). This fact explains why the only known applications of this technique are based on very low-ranked Borel sets (open, closed, F_σ, or G_δ).     

Holomorphic functions on strict inductive limits

We study strict inductive limits of Fréchet Montel (FM) spaces and reflexive Fréchet (RF) spaces and we obtain some interesting examples in the theory of infinite dimensional holomorphy. P_M(^kE′) and P_HY(^kE′) will denote respectively the set of all k-homogeneous polynomials on E′ that are bounded on bounded sets and the set of all k-homogeneous polynomials on E′ that are continuous on compact sets. ?_SM(^kE′) is the space of all symetric k -multilinear mappings from E′ × ... × E′ into C that are bounded on bounded sets. H_HY(E′) will denote the set of all G-analytic functions on E′ that are continuous on the compact subsets of E′.     

The irredundant ramsey number s(3, 7)

The irredundant Ramsey number s(m, n) is the smallest p such that for every graph G with p vertices, either G contains an n-element irredundant set or its complement G contains an m-element irredundant set. Cockayne, Hattingh, and Mynhardt have given a computer-assisted proof that s(3, 7) = 18. The purpose of this paper is to give a self-contained proof of this result. © 1995 John Wiley & Sons, Inc.     

A mathematical proof of S. Shelah’s theorem on the measure problem and related results

Recently, S. Shelah proved that an inaccessible cardinal is necessary to build a model of set theory in which every set of reals is Lebesgue measurable. We give a simpler and metamathematically free proof of Shelah's result. As a corollary, we get an elementary proof of the following result (without choice axiom): assume there exists an uncountable well ordered set of reals, then there exists a non-measurable set of reals. We also get results about Baire property,K _σ-regularity and Ramsey property.     

Factorizations of infinite sequences in semigroups

It follows from the Ramsey theorem that every infinite sequence of elements of a finite semigroup has an infinite factorization of the form x, e, e, e, ..., where e is an idempotent of the semigroup. We describe all semigroups with this property and with its analog for two-sided infinite sequences.     

Ramsey unsaturated and saturated graphs

A graph is Ramsey unsaturated if there exists a proper supergraph of the same order with the same Ramsey number, and Ramsey saturated otherwise. We present some conjectures and results concerning both Ramsey saturated and unsaturated graphs. In particular, we show that cycles C_n and paths P_n on n vertices are Ramsey unsaturated for all n ≥ 5. © 2005 Wiley Periodicals, Inc.     

Two remarks on the Burr–Erdős conjecture

The Ramsey number r(H) of a graph H is the minimum positive integer N such that every two-coloring of the edges of the complete graph K_N on N vertices contains a monochromatic copy of H. A graph H is d-degenerate if every subgraph of H has minimum degree at most d. Burr and Erdős in 1975 conjectured that for each positive integer d there is a constant c_d such that r(H)≤c_dn for every d-degenerate graph H on n vertices. We show that for such graphs , improving on an earlier bound of Kostochka and Sudakov. We also study Ramsey numbers of random graphs, showing that for d fixed, almost surely the random graph G(n,d/n) has Ramsey number linear in n. For random bipartite graphs, our proof gives nearly tight bounds.     

Computable Ramsey’s theorem for pairs needs infinitely many $$\Pi ^0_2$$ sets

In Ramsey’s Theorem and Recursion Theory, Theorem 4.2, Jockusch proved that for any computable k-coloring of pairs of integers, there is an infinite \(\Pi ^0_2\) homogeneous set. The proof used a countable collection of \(\Pi ^0_2\) sets as potential infinite homogeneous sets. In a remark preceding the proof, Jockusch stated without proof that it can be shown that there is no computable way to prove this result with a finite number of \(\Pi ^0_2\) sets. We provide a proof of this claim, showing that there is no computable way to take an index for an arbitrary computable coloring and produce a finite number of indices of \(\Pi ^0_2\) sets with the property that one of those sets will be homogeneous for that coloring. While proving this result, we introduce n-trains as objects with useful combinatorial properties which can be used as approximations to infinite \(\Pi ^0_2\) sets.     

On the Size‐Ramsey Number of Hypergraphs

The size‐Ramsey number of a graph G is the minimum number of edges in a graph H such that every 2‐edge‐coloring of H yields a monochromatic copy of G. Size‐Ramsey numbers of graphs have been studied for almost 40 years with particular focus on the case of trees and bounded degree graphs. We initiate the study of size‐Ramsey numbers for k‐uniform hypergraphs. Analogous to the graph case, we consider the size‐Ramsey number of cliques, paths, trees, and bounded degree hypergraphs. Our results suggest that size‐Ramsey numbers for hypergraphs are extremely difficult to determine, and many open problems remain.     

On a Question of Erdős and Ulam

Ulam asked in 1945 if there is an everywhere dense rational set, i.e., 1 a point set in the plane with all its pairwise distances rational. Erdős conjectured that if a set S has a dense rational subset, then S should be very special. The only known types of examples of sets with dense (or even just infinite) rational subsets are lines and circles. In this paper we prove Erdős’ conjecture for algebraic curves by showing that no irreducible algebraic curve other than a line or a circle contains an infinite rational set.     

On Commutativity and Centrality in Infinite Rings

We show that if R is an infinite ring such that XY ∩ YX ≠ ? for all infinite subsets X and Y, then R is commutative. We also prove that in an infinite ring R, an element a ∈ R is central if and only if aX ∩ Xa ≠ ? for all infinite subsets X.     

Partitions and pairwise sums and products

A seven cell partition of N is constructed with the property that no infinite set has all of its pairwise sums and products in any one cell. A related Ramsey Theory question is shown to have different answers for two and three cell partitions.