Given a graph G whose set of vertices is a Polish space X, the weak Borel chromatic number of G is the least size of a family of pairwise disjoint G -independent Borel sets that covers all of X. Here a set of vertices of a graph G is independent if no two vertices in the set are connected by an edge.We show that it is consistent with an arbitrarily large size of the continuum that every (...) closed graph on a Polish space either has a perfect clique or has a weak Borel chromatic number of at most ℵ1. We observe that some weak version of Todorcevic's Open Coloring Axiom for closed colorings follows from MA.Slightly weaker results hold for Fσ-graphs. In particular, it is consistent with an arbitrarily large size of the continuum that every locally countable Fσ-graph has a Borel chromatic number of at most ℵ1.We refute various reasonable generalizations of these results to hypergraphs. (shrink)

Journal of Mathematical Logic, Ahead of Print. We construct bounded degree acyclic Borel graphs with large Borel chromatic number using a graph arising from Ramsey theory and limits of expander sequences.

We construct bounded degree acyclic Borel graphs with large Borel chromatic number using a graph arising from Ramsey theory and limits of expander sequences.

We show that there is an antichain basis for neither the class of non-potentially closed Borel subsets of the plane under Borel rectangular reducibility nor the class of analytic graphs of uncountable Borel chromatic number under Borel reducibility.

We show that if add(null) = c, then the globally Baire and universally measurable chromatic numbers of the graph of any Borel function on a Polish space are equal and at most three. In particular, this holds for the graph of the unilateral shift on [N]N, although its Borel chromatic number is N₀. We also show that if add(null) = c, then the universally measurable chromatic number of every treeing of a measure amenable (...) equivalence relation is at most three. In particular, this holds for "the" minimum analytic graph G₀ with uncountable Borel (and Baire measurable) chromatic number. In contrast, we show that for all κ ∈ {2, 3...., N₀. c}, there is a treeing of E₀ with Borel and Baire measurable chromatic number κ. Finally, we use a Glimm—Effros style dichotomy theorem to show that every basis for a non-empty initial segment of the class of graphs of Borel functions of Borel chromatic number at least three contains a copy of (R<N, ⊇). (shrink)

We characterize Borel line graphs in terms of 10 forbidden induced subgraphs, namely the nine finite graphs from the classical result of Beineke together with a 10th infinite graph associated with the equivalence relation $\mathbb {E}_0$ on the Cantor space. As a corollary, we prove a partial converse to the Feldman–Moore theorem, which allows us to characterize all locally countable Borel line graphs in terms of their Borel chromatic numbers.

We give classical proofs, strengthenings, and generalizations of Lecomte’s characterizations of analytic ω-dimensional hypergraphs with countable Borel chromatic number.

For each infinite cardinalκ, the set of algebraic hypergraphs having chromatic number no larger thanκis decidable.

We generalize the [Formula: see text] dichotomy to doubly-indexed sequences of analytic digraphs. Under a mild definability assumption, we use this generalization to characterize the family of Borel actions of tsi Polish groups on Polish spaces that can be decomposed into countably-many Borel actions admitting complete Borel sets that are lacunary with respect to an open neighborhood of the identity. We also show that if the group in question is non-archimedean, then the inexistence of such a decomposition (...) yields a special kind of continuous embedding of [Formula: see text] into the corresponding orbit equivalence relation. (shrink)

A recursive graph is a graph whose vertex and edge sets are recursive. A highly recursive graph is a recursive graph that also has the following property: one can recursively determine the neighbors of a vertex. Both of these have been studied in the literature. We consider an intermediary notion: Let A be a set. An A-recursive graph is a recursive graph that also has the following property: one can recursively-in-A determine the neighbors of a vertex. We show that, if (...) A is r.e. and not recursive, then there exists A-recursive graphs that are 2-colorable but not recursively k-colorable for any k. This is false for highly-recursive graphs but true for recursive graphs. Hence A-recursive graphs are closer in spirit to recursive graphs than to highly recursive graphs. (shrink)

The number of discriminable colours is often assumed to be of the order of several million but the extent of detectable chromatic diversity present in individual natural scenes is an open question. Here, the aim was to estimate the number of discriminable colours seen in natural scenes. Hyperspectral data were obtained from a set of natural scenes over the range 400 - 720 nm at 10 nm intervals (Nascimento et al, 2002 Journal of the Optical Society of (...) America A 19 1484 - 1490) and the representation of each scene in CIELAB space computed for all pixels of the image. The number of discriminable colours was estimated by counting the number of unit volumes in the three-dimensional volume defined by the scene when represented in CIELAB space. We found that the number of discriminable colours estimated in a scene could vary by an order of magnitude from scene to scene, but rarely exceeded 105, indicating a limited chromatic diversity. (shrink)

Summary The twofold objective of this study is (1) to identify and give a brief review of the historical development of the various designs of early (pre-1850) telescope eyepieces, and (2) to determine by measurements and calculations the axial and lateral chromatic aberrations of a number of extant eyepieces from that period in order to provide basic data on which to judge the relative quality of different eyepiece forms. Eight distinct types of eyepieces containing one to five lens (...) elements are discussed and illustrated. The second objective was addressed by measuring the focal lengths of the individual lens elements and the lens spacings in each eyepiece. The data were processed by a ray-tracing program that yields the chromatic aberration (CA) and focal length of each of the eyepieces. Twenty-one telescopes from that period were studied in this way. Similar calculations were also made using data available in the literature on several additional historic telescopes. The conclusions drawn from the data are: (1) Telescopes with Galilean eyepieces have a smaller CA than those with Keplerian or Huygens eyepieces. (2) The two-lens Keplerian terrestrial eyepieces are demonstrated to have larger axial and lateral CA than any of the other eyepiece types. (3) Calculations from examples of telescopes by Divini and Campani for which data were available indicate that while the axial CAs of the two were the same, Campani's instrument had a much smaller lateral CA. (4) Five element eyepieces were found to be better corrected for CA than the early four-lens systems that replaced them. (5) This study tends to confirm the speculation that the reason makers of early achromatic telescopes overcorrected the objective lenses was to compensate for the CA of the eyepieces. (shrink)

Summary The twofold objective of this study is (1) to identify and give a brief review of the historical development of the various designs of early (pre-1850) telescope eyepieces, and (2) to determine by measurements and calculations the axial and lateral chromatic aberrations of a number of extant eyepieces from that period in order to provide basic data on which to judge the relative quality of different eyepiece forms. Eight distinct types of eyepieces containing one to five lens (...) elements are discussed and illustrated. The second objective was addressed by measuring the focal lengths of the individual lens elements and the lens spacings in each eyepiece. The data were processed by a ray-tracing program that yields the chromatic aberration (CA) and focal length of each of the eyepieces. Twenty-one telescopes from that period were studied in this way. Similar calculations were also made using data available in the literature on several additional historic telescopes. The conclusions drawn from the data are: (1) Telescopes with Galilean eyepieces have a smaller CA than those with Keplerian or Huygens eyepieces. (2) The two-lens Keplerian terrestrial eyepieces are demonstrated to have larger axial and lateral CA than any of the other eyepiece types. (3) Calculations from examples of telescopes by Divini and Campani for which data were available indicate that while the axial CAs of the two were the same, Campani's instrument had a much smaller lateral CA. (4) Five element eyepieces were found to be better corrected for CA than the early four-lens systems that replaced them. (5) This study tends to confirm the speculation that the reason makers of early achromatic telescopes overcorrected the objective lenses was to compensate for the CA of the eyepieces. (shrink)

We introduce a reducibility preordering between classes of countable structures, each class containing only structures of a given similarity type (which is allowed to vary from class to class). Though we sometimes work in a slightly larger context, we are principally concerned with the case where each class is an invariant Borel class (i.e. the class of all models, with underlying set $= \omega$, of an $L_{\omega_1\omega}$ sentence; from this point of view, the reducibility can be thought of as (...) a (rather weak) sort of $L_{\omega_1\omega}$-interpretability notion). We prove a number of general results about this notion, but our main thrust is to situate various mathematically natural classes with respect to the preordering, most notably classes of algebraic structures such as groups and fields. (shrink)

We introduce a natural generalization of Borel's Conjecture. For each infinite cardinal number $\kappa$, let ${\sf BC}_{\kappa}$ denote this generalization. Then ${\sf BC}_{\aleph_0}$ is equivalent to the classical Borel conjecture. Assuming the classical Borel conjecture, $\neg{\sf BC}_{\aleph_1}$ is equivalent to the existence of a Kurepa tree of height $\aleph_1$. Using the connection of ${\sf BC}_{\kappa}$ with a generalization of Kurepa's Hypothesis, we obtain the following consistency results: 1. If it is consistent that there is a 1-inaccessible (...) cardinal then it is consistent that ${\sf BC}_{\aleph_1}$.2. If it is consistent that ${\sf BC}_{\aleph_1}$, then it is consistent that there is an inaccessible cardinal.3. If it is consistent that there is a 1-inaccessible cardinal with $\omega$ inaccessible cardinals above it, then $\neg{\sf BC}_{\aleph_{\omega}} + (\forall n < \omega){\sf BC}_{\aleph_n}$ is consistent.4. If it is consistent that there is a 2-huge cardinal, then it is consistent that ${\sf BC}_{\aleph_{\omega}}$.5. If it is consistent that there is a 3-huge cardinal, then it is consistent that ${\sf BC}_{\kappa}$ for a proper class of cardinals $\kappa$ of countable cofinality. (shrink)

Visual percepts frequently appear chromatically rich, yet their paucity in reportable information has led to widely accepted minimalist models of vision. The discrepancy may be resolved by positing that the richness of natural scenes is reflected in phenomenal consciousness but not in detail in the phenomenal judgments upon which reports about qualia are based. Conceptual awareness (including phenomenal judgments) arises from neural mechanisms that categorize objects, and also from mechanisms that conceptually characterize textural properties of pre-categorically segmented regions in the (...) visual field. Experimental evidence suggests that complex images instigate the generation of so-called ensemble phenomenal judgments. These involve concepts that categorize global attributes of segmented areas but carry no information pertaining to details. It is then argued that there are cogent reasons for believing that phenomenal percepts (i.e. qualia) arising from chromatically complex stimuli cohere in this ensemble sense with both the stimulus and with the resulting ensemble phenomenal judgments. Thus, spatially detailed retinal images are deemed to yield correspondingly detailed phenomenal experiences that are in turn conceptually apprehended via a relatively small number of ensemble phenomenal judgments. Lastly, it is suggested that the bridge locus for chromatically rich phenomenal experiences is most plausibly located early in the cortical visual pathway. (shrink)

We give an affirmative answer to the following question: Is any Borel subset of a Cantor set C a sum of a countable number of pairwise disjoint h-homogeneous subspaces that are closed in X? It follows that every Borel set \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${X \subset {\bf R}^n}$$\end{document} can be partitioned into countably many h-homogeneous subspaces that are Gδ-sets in X.

We prove a number of results about countable Borel equivalence relations with forcing constructions and arguments. These results reveal hidden regularity properties of Borel complete sections on certain orbits. As consequences they imply the nonexistence of Borel complete sections with certain features.

We formulate a Borel version of a corollary of Furman's superrigidity theorem for orbit equivalence and present a number of applications to the theory of countable Borel equivalence relations. In particular, we prove that the orbit equivalence relations arising from the natural actions of on the projective planes over the various p-adic fields are pairwise incomparable with respect to Borel reducibility.

Boykin and Jackson recently introduced a property of countable Borel equivalence relations called Borel boundedness, which they showed is closely related to the union problem for hyperfinite equivalence relations. In this paper, we introduce a family of properties of countable Borel equivalence relations which correspond to combinatorial cardinal characteristics of the continuum in the same way that Borel boundedness corresponds to the bounding number. We analyze some of the basic behavior of these properties, showing, e.g., (...) that the property corresponding to the splitting number coincides with smoothness. We then settle many of the implication relationships between the properties; these relationships turn out to be closely related to (but not the same as) the Borel Tukey ordering on cardinal characteristics. (shrink)

A number of results have been obtained concerning Borel structures starting with Silver and Friedman followed by Harrington, Shelah, Marker, and Louveau. Friedman also initiated the model theory of Borel (in fact totally Borel) structures. By this we mean the study of the class of Borel models of a given first-order theory. The subject was further investigated by Steinhorn. The present work is meant to go further in this direction. It is based on the assumption (...) that the study of the class of, say, countable models of a theory reduces to analyzing a single $\omega_1$-saturated model. The question then arises as to when such a model can be totally Borel. We present here a partial answer to this problem when the theory under investigation is superstable. (shrink)

We prove Borel superrigidity results for suitably chosen actions of groups of the form SL2, where {p1, …, pt} is a finite nonempty set of primes, and present a number of applications to the theory of countable Borel equivalence relations. In particular, for each prime q, we prove that the orbit equivalence relations arising from the natural actions of SL2 on the projective lines ℚp ∪ {∞}, p ≠ q, over the various p-adic fields are pairwise incomparable (...) with respect to Borel reducibility. (shrink)

We study the possible values of the cofinality invariant for various Borel ideals on the natural numbers. We introduce the notions of a fragmented and gradually fragmented ideal and prove a dichotomy for fragmented ideals. We show that every gradually fragmented ideal has cofinality consistently strictly smaller than the cardinal invariant and produce a model where there are uncountably many pairwise distinct cofinalities of gradually fragmented ideals.

We consider decompositions of the real line into pairwise disjoint Borel pieces so that each piece is closed under addition. How many pieces can there be? We prove among others that the number of pieces is either at most 3 or uncountable, and we show that it is undecidable in and even in the theory if the number of pieces can be uncountable but less than the continuum. We also investigate various versions: what happens if we drop (...) the Borelness requirement, if we replace addition by multiplication, if the pieces are subgroups, if we partition (0, ∞), and so on. (shrink)

It is shown to be consistent that the reals are covered by ℵ1 meagre sets yet there is a Baire class 1 function which cannot be covered by fewer than ℵ2 continuous functions. A new cardinal invariant is introduced which corresponds to the least number of continuous functions required to cover a given function. This is characterized combinatorially. A forcing notion similar to, but not equivalent to, superperfect forcing is introduced.

Let $\mathcal {I}$ be an ideal on $\omega $. For $f,\,g\in \omega ^{\omega }$ we write $f \leq _{\mathcal {I}} g$ if $f(n) \leq g(n)$ for all $n\in \omega \setminus A$ with some $A\in \mathcal {I}$. Moreover, we denote $\mathcal {D}_{\mathcal {I}}=\{f\in \omega ^{\omega }: f^{-1}[\{n\}]\in \mathcal {I} \text { for every } n\in \omega \}$ (in particular, $\mathcal {D}_{\mathrm {Fin}}$ denotes the family of all finite-to-one functions).We examine cardinal numbers $\mathfrak {b}(\geq _{\mathcal {I}}\cap (\mathcal {D}_{\mathcal {I}} \times \mathcal {D}_{\mathcal (...) {I}}))$ and $\mathfrak {b}(\geq _{\mathcal {I}}\cap (\mathcal {D}_{\mathrm {Fin}}\times \mathcal {D}_{\mathrm {Fin}}))$ describing the smallest sizes of unbounded from below with respect to the order $\leq _{\mathcal {I}}$ sets in $\mathcal {D}_{\mathrm {Fin}}$ and $\mathcal {D}_{\mathcal {I}}$, respectively. For a maximal ideal $\mathcal {I}$, these cardinals were investigated by M. Canjar in connection with coinitial and cofinal subsets of the ultrapowers.We show that $\mathfrak {b}(\geq _{\mathcal {I}}\cap (\mathcal {D}_{\mathrm {Fin}} \times \mathcal {D}_{\mathrm {Fin}})) =\mathfrak {b}$ for all ideals $\mathcal {I}$ with the Baire property and that $\aleph _1 \leq \mathfrak {b}(\geq _{\mathcal {I}}\cap (\mathcal {D}_{\mathcal {I}} \times \mathcal {D}_{\mathcal {I}})) \leq \mathfrak {b}$ for all coanalytic weak P-ideals (this class contains all $\bf {\Pi ^0_4}$ ideals). What is more, we give examples of Borel (even $\bf {\Sigma ^0_2}$ ) ideals $\mathcal {I}$ with $\mathfrak {b}(\geq _{\mathcal {I}}\cap (\mathcal {D}_{\mathcal {I}} \times \mathcal {D}_{\mathcal {I}}))=\mathfrak {b}$ as well as with $\mathfrak {b}(\geq _{\mathcal {I}}\cap (\mathcal {D}_{\mathcal {I}} \times \mathcal {D}_{\mathcal {I}})) =\aleph _1$.We also study cardinals $\mathfrak {b}(\geq _{\mathcal {I}}\cap (\mathcal {D}_{\mathcal {J}} \times \mathcal {D}_{\mathcal {K}}))$ describing the smallest sizes of sets in $\mathcal {D}_{\mathcal {K}}$ not bounded from below with respect to the preorder $\leq _{\mathcal {I}}$ by any member of $\mathcal {D}_{\mathcal {J}}\!$. Our research is partially motivated by the study of ideal-QN-spaces: those cardinals describe the smallest size of a space which is not ideal-QN. (shrink)

As an artist I admittedly scrutinize all of the theories related to the arts closely. I do this for a number of reasons. The obvious one is that I have a deeply felt personal relationship with the subject matter. Less obvious is my experience in general. My early research was motivated by a desire to discover the historical circumstances that led to the difficulty in fitting visual art into the discussions I encountered. Generally, it seemed that the dominant framework (...) trivialized what I considered the most important aspects of the creative process. Over time I concluded that developing an interdisciplinary approach offered the best option for expanding views, although it is not an easy task. Establishing areas of commonality across a range of disciplines must somehow accommodate the ways in which each has developed a research agenda that seems to serve its core needs. In consciousness studies, for example, we have a field that relies heavily on scientific research and humanistic methodologies when building the philosophical models scholars use to structure theories. This methodology is not only removed from the nuts and bolts of art, it is also easily manipulated in discourse on art due to the ease with which we can fit aspects of art into the philosophical framework. Clearly this approach fits nicely with philosophically defined concepts such as meaning, emotion, and other elusive modes. In addition, using the well-honed categories aids in bracketing themes such as metaphor, interpretation, subjectivity, language and history. Nonetheless, in reading through the studies, I repeatedly conclude that the voices of practitioners need to be included to a greater degree. (shrink)

This is a continuation of the paper [J. Symb. Log. 87 (2022), 1065–1092]. For an ideal $\mathcal {I}$ on $\omega $ we denote $\mathcal {D}_{\mathcal {I}}=\{f\in \omega ^{\omega }: f^{-1}[\{n\}]\in \mathcal {I} \text { for every } n\in \omega \}$ and write $f\leq _{\mathcal {I}} g$ if $\{n\in \omega :f(n)>g(n)\}\in \mathcal {I}$, where $f,g\in \omega ^{\omega }$. We study the cardinal numbers $\mathfrak {b}(\geq _{\mathcal {I}}\cap (\mathcal {D}_{\mathcal {I}} \times \mathcal {D}_{\mathcal {I}}))$ describing the smallest sizes of subsets of $\mathcal (...) {D}_{\mathcal {I}}$ that are unbounded from below with respect to $\leq _{\mathcal {I}}$. In particular, we examine the relationships of $\mathfrak {b}(\geq _{\mathcal {I}}\cap (\mathcal {D}_{\mathcal {I}} \times \mathcal {D}_{\mathcal {I}}))$ with the dominating number $\mathfrak {d}$. We show that, consistently, $\mathfrak {b}(\geq _{\mathcal {I}}\cap (\mathcal {D}_{\mathcal {I}} \times \mathcal {D}_{\mathcal {I}}))>\mathfrak {d}$ for some ideal $\mathcal {I}$, however $\mathfrak {b}(\geq _{\mathcal {I}}\cap (\mathcal {D}_{\mathcal {I}} \times \mathcal {D}_{\mathcal {I}}))\leq \mathfrak {d}$ for all analytic ideals $\mathcal {I}$. Moreover, we give example of a Borel ideal with $\mathfrak {b}(\geq _{\mathcal {I}}\cap (\mathcal {D}_{\mathcal {I}} \times \mathcal {D}_{\mathcal {I}}))=\operatorname {\mathrm {add}}(\mathcal {M})$. (shrink)

Journal of Mathematical Logic, Ahead of Print. Let [math] be an integer. We show that the set of real numbers that are Poisson generic in base [math] is [math]-complete in the Borel hierarchy of subsets of the real line. Furthermore, the set of real numbers that are Borel normal in base [math] and not Poisson generic in base [math] is complete for the class given by the differences between [math] sets. We also show that the effective versions of (...) these results hold in the effective Borel hierarchy. (shrink)

We prove that, for any natural number \, we can find a finite alphabet \ and a finitary language L over \ accepted by a one-counter automaton, such that the \-power $$\begin{aligned} L^\infty :=\{ w_0w_1\ldots \in \Sigma ^\omega \mid \forall i\in \omega ~~w_i\in L\} \end{aligned}$$is \-complete. We prove a similar result for the class \.

We prove consistent, assuming there is a supercompact cardinal, that there is a singular strong limit cardinalμ, of cofinalityω, such that everyμ+-chromatic graphXonμ+has an edge colouringcofXintoμcolours for which every vertex colouringgofXinto at mostμmany colours has ag-colour class on whichctakes every value.The paper also contains some generalisations of the above statement in whichμ+is replaced by other cardinals >μ.

We discuss mathematical and physical arguments against continuity and in favor of discreteness, with particular emphasis on the ideas of Émile Borel.

Let [Formula: see text] be an integer. We show that the set of real numbers that are Poisson generic in base [Formula: see text] is [Formula: see text]-complete in the Borel hierarchy of subsets of the real line. Furthermore, the set of real numbers that are Borel normal in base [Formula: see text] and not Poisson generic in base [Formula: see text] is complete for the class given by the differences between [Formula: see text] sets. We also show (...) that the effective versions of these results hold in the effective Borel hierarchy. (shrink)

We consider several kinds of partition relations on the set ${\mathbb{R}}$ of real numbers and its powers, as well as their parameterizations with the set ${[\mathbb{N}]^{\mathbb{N}}}$ of all infinite sets of natural numbers, and show that they hold in some models of set theory. The proofs use generic absoluteness, that is, absoluteness under the required forcing extensions. We show that Solovay models are absolute under those forcing extensions, which yields, for instance, that in these models for every well ordered partition (...) of ${\mathbb{R}^\mathbb{N}}$ there is a sequence of perfect sets whose product lies in one piece of the partition. Moreover, for every finite partition of ${[\mathbb{N}]^{\mathbb{N}} \times \mathbb{R}^{\mathbb{N}}}$ there is ${X \in [\mathbb{N}]^{\mathbb{N}}}$ and a sequence ${\{P_{k} : k \in \mathbb{N}\}}$ of perfect sets such that the product ${[X]^{\mathbb{N}} \times \prod_{k}^{\infty}P_{k}}$ lies in one piece of the partition, where ${[X]^{\mathbb{N}}}$ is the set of all infinite subsets of X. The proofs yield the same results for Borel partitions in ZFC, and for more complex partitions in any model satisfying a certain degree of generic absoluteness. (shrink)

We prove consistent, assuming there is a supercompact cardinal, that there is a singular strong limit cardinal $\mu$ , of cofinality $\omega$ , such that every $\mu^{+}$ -chromatic graph X on $\mu^{+}$ has an edge colouring c of X into $\mu$ colours for which every vertex colouring g of X into at most $\mu$ many colours has a g-colour class on which c takes every value. The paper also contains some generalisations of the above statement in which $\mu^{+}$ is (...) replaced by other cardinals < $\mu$. (shrink)

Reviewed Works:Edwin W. Miller, On a Property of Families of Sets.Ben Dushnik, E. W. Miller, Partially Ordered Sets.P. Erdos, Some Set-theoretical Properties of Graphs.G. Fodor, Proof of a Conjecture of P. Erdos.P. Erdos, R. Rado, A Partition Calculus in Set Theory.P. Erdos, R. Rado, Intersection Theorems for Systems of Sets.A. Hajnal, Some Results and Problems on Set Theory.P. Erdos, A. Hajnal, On a Property of Families of Sets.A. Hajnal, Proof of a Conjecture of S. Ruziewicz.P. Erdos, A. Hajnal, R. Rado, (...) Partition Relations for Cardinal Numbers.P. Erdos, A. Hajnal, On a Problem of B. Jonsson.P. Erdos, A. Hajnal, On Chromatic Number of Graphs and Set-Systems. (shrink)

We sketch the ideas behind the use of chromatic numbers in establishing descriptive set-theoretic dichotomy theorems.

May the same graph admit two different chromatic numbers in two different universes? How about infinitely many different values? and can this be achieved without changing the cardinals structure? In this paper, it is proved that in Gödel’s constructible universe, for every uncountable cardinal $$\mu $$ below the first fixed-point of the $$\aleph $$ -function, there exists a graph $$\mathcal G_\mu $$ satisfying the following.

A cylindric algebra atom structure is said to be strongly representable if all atomic cylindric algebras with that atom structure are representable. This is equivalent to saying that the full complex algebra of the atom structure is a representable cylindric algebra. We show that for any finite n >3, the class of all strongly representable n-dimensional cylindric algebra atom structures is not closed under ultraproducts and is therefore not elementary. Our proof is based on the following construction. From an arbitrary (...) undirected, loop-free graph Γ, we construct an n-dimensional atom structure E(Γ), and prove, for infinite Γ, that E(Γ) is a strongly representable cylindric algebra atom structure if and only if the chromatic number of Γ is infinite. A construction of Erdős shows that there are graphs (k < ω)with infinite chromatic number, but having a non-principal ultraproduct $\prod _D\Gamma _k $ whose chromatic number is just two. It follows that $E(\Gamma _k )$ is strongly representable (each k < ω) but $\Pi _D E(\Gamma _k)$ is not. (shrink)

We show that there exist 2 ℵ 0 equational classes of Boolean algebras with operators that are not generated by the complex algebras of any first-order definable class of relational structures. Using a variant of this construction, we resolve a long-standing question of Fine, by exhibiting a bimodal logic that is valid in its canonical frames, but is not sound and complete for any first-order definable class of Kripke frames (a monomodal example can then be obtained using simulation results of (...) Thomason). The constructions use the result of Erd $\H{o}$ s that there are finite graphs with arbitrarily large chromatic number and girth. (shrink)

We explore a general method based on trees of elementary submodels in order to present highly simplified proofs to numerous results in infinite combinatorics. While countable elementary submodels have been employed in such settings already, we significantly broaden this framework by developing the corresponding technique for countably closed models of size continuum. The applications range from various theorems on paradoxical decompositions of the plane, to coloring sparse set systems, results on graph chromatic number and constructions from point-set topology. (...) Our main purpose is to demonstrate the ease and wide applicability of this method in a form accessible to anyone with a basic background in set theory and logic. (shrink)

It is shown that if ZF is consistent, then so is ZFC + GCH + "There is a graph with cardinality ℵ 2 and chromatic number ℵ 2 such that every subgraph of cardinality ≤ ℵ 1 has chromatic number ≤ ℵ 0 ". This partially answers a question of Erdos and Hajnal.

It is consistent relative to an inaccessible cardinal that ZF+DC holds, and the hypergraph of isosceles triangles on $\mathbb {R}^2$ has countable chromatic number while the hypergraph of isosceles triangles on $\mathbb {R}^3$ has uncountable chromatic number.

The relationship of Grundy and chromatic numbers of graphs in the context of Reverse Mathematics is investi-gated.