Some Cardinal Arithmetic

Some time ago, Asaf Karagila wrote wonderful post wherein he shows that, even without assuming the axiom of choice one can always find four cardinals \(\mathfrak{p} \lt \mathfrak{q}\) and \(\mathfrak{r} \lt \mathfrak{s}\) such that \(\mathfrak{p}^{\mathfrak{r}} = \mathfrak{q}^{\mathfrak{s}}.\) In the comments, Harvey Friedman asks:

Your theorem is an example of an existential sentence about cardinals in the language with only \(\lt \) and exponentiation. Can you determine which sentences in that language are provable in ZF? More generally, expand the set of sentences about cardinals considered, obviously to include addition and multiplication, and perhaps alternating quantifiers.

After Peter Krautzberger’s tiny blogging challenge, I decided to spend 30 minutes thinking and writing about this…

… 

 

What is combinatorial set theory?

This is a very difficult question that I find myself pondering every so often. I once heard a story that Jim Baumgartner was asked this question at a major logic meeting where all areas — recursion theory, model theory, proof theory, etc. — were well represented and he responded that it was the only area of logic not represented there. Indeed, the best way to describe infinitary combinatorics is to describe what it isn’t, as in the introductory paragraph of Jim’s review of William’s book on the subject:

Combinatorial set theory is frequently distinguished from axiomatic set theory, although the distinction is becoming less and less clear all the time. If there is a difference, it is more one of method than substance. Axiomatic set theory uses the tools of mathematical logic, such as the method of ultrapowers and the theory of forcing and generic sets, while the methods of combinatorial set theory are purely “combinatorial” in nature. In practice, an argument of result is “combinatorial” if it is not overtly model-theoretic, topological, or measure-theoretic.1

I stumbled across the above review while seeking to find a reference for the anecdote about Jim at the meeting. I don’t remember where I got this story from, I may have read it somewhere or I may have heard it from somebody or Jim himself. I didn’t find a reference for the anecdote. However, I did find that Jim wrote some fantastic book reviews. One of the best is his review of Kunen’s classic set theory textbook, where he writes the following about Jech’s encyclopedic Set Theory:

Graduate students went without food to put a copy of this fat green book on their shelves.2

This was the first edition of Jech’s book, of course. The classic is now much fatter, yellow rather than green, and sufficiently affordable that graduate students can acquire a copy without excessive suffering.

  1. James E. Baumgartner, Review: Neil H. Williams, Combinatorial set theory. Bull. Amer. Math. Soc. (N.S.) 1 (1979), 217–219. [link]
  2. James E. Baumbarther, Review: Kenneth Kunen, Set theory. An introduction to independence proofs. J. Symb. Logic 51 (1986), 462–464. [link]
 

Envelope forcing

In a recent paper [1], Jared Corduan and I considered various notions of combinatorial indecomposability for finite ordinal powers of \(\omega.\) In this process, we uncovered two weak forms of Ramsey’s theorem for pairs (\(\newcommand{\RT}[2]{\mathsf{RT}^{#1}_{#2}}\RT2k\)):

  • The Weak Ramsey Theorem (\(\newcommand{\Wk}{\mathsf{W}}\Wk\RT2k\)). For every coloring \(c:\N^2\to\set{0,\dots,k-1}\) there are a color \(d \lt k\) and an infinite set \(H\) such that \[\set{y \in \N : c(x,y) = d}\] is infinite for every \(x \in H.\)
  • The Hyper-Weak Ramsey Theorem (\(\newcommand{\HWk}{\mathsf{HW}}\HWk\RT2k\)). For every coloring \(c:\N^2\to\set{0,\dots,k-1}\) there are a color \(d \lt k\) and an increasing function \(h:\N\to\N\) such that \[\bigcup_{x=h(i-1)}^{h(i)-1} \set{y \in \N : c(x,y) = d}\] is infinite for every \(i \in \N.\)

The first is equivalent to what we called the game indecomposability of the ordinal \(\omega^2,\) and the second is related to the lexicographic indecomposability of \(\omega^2.\) You can find out more about these notions of indecomposability in our paper, what I want to write about here is the forcing technique that we used to show that \(\HWk\RT22\) is \(\Pi^1_1\)-conservative over \(\mathsf{RCA}_0\) with \(\Sigma^0_2\)-induction and to separate the two principles \(\Wk\RT22\) and \(\HWk\RT22.\) I’ve been calling the method envelope forcing since the basic idea is to force over a larger model that envelops the original one rather than forcing over the ground model itself. In the following, I will give a brief tour of this method, skipping all the gory details (that can be found in our paper).

… 

 

A partition theorem for finite trees

In a recent paper [1], Steven Gubkin, Daniel McDonald, Manuel Rivera, and I stumbled across what appears to be a new result in Ramsey theory. As the title of our paper suggests, this result was not exactly our main goal. Nevertheless, the result is very interesting so I feel it is a good idea to give it some extra publicity by writing about it here. I will only talk about a special case of our result (the case of Corollary 5.5 where the tree presentation has no sum nodes) and I will present it in a slightly different light. Our proof is somewhat convoluted, one could even say that the result is an accidental byproduct of the main result of the paper on automorphism groups of countably categorical linear orders. Because of this, I don’t feel like I understand how our result fits in the spectrum of known results in Ramsey theory. It is my hope that some of you may be able to fill-in some of the missing links…

Our new partition theorem is about (finite) ordered rooted trees. There are unfortunately several definitions needed to conveniently state our result. Recall that a rooted tree is a connected acyclic graph with a distinguished vertex, the root of the tree. For every node \(t\) in a tree there is a unique path leading from \(t\) to the root. If \(t\) is not the root, the next node along this path is the parent of \(t;\) the other nodes adjacent to \(t\) are the child nodes of \(t,\) these are the nodes that \(t\) is the parent of. The root is the only node without a parent; node with no children is called a leaf node.

A homomorphism from a rooted tree \(U\) to a rooted tree \(T\) is a map \(h\) from nodes of \(U\) to nodes of \(T\) that preserves the root and the child-parent relationship. So \(h\) must send the root of \(U\) to the root of \(T\) and if \(u\) is the parent of \(u’\) in \(U\) then \(h(u)\) must be the parent of \(h(u’)\) in \(T.\) Note that \(h\) does not need to be one-to-one: two children \(u’,u”\) of \(u\) in \(U\) could be mapped to the same child of \(h(u)\) in \(T.\)

A rooted tree \(U\) can be lexicographically ordered by choosing a linear ordering on the children of each node. This induces a linear ordering of all nodes as follows: \(u \lt v\) when \(u\) is on the path leading from \(v\) to the root of \(U,\) or \(u’ \lt v’\) where \(u’\) and \(v’\) are the nodes along the paths leading from \(u\) and \(v\) to the root immediately before their greatest common ancestor (note that \(u’\) and \(v’\) are both children of this common ancestor so we can compare them). It is easy to check that this is indeed a linear ordering of the nodes of \(U.\) What will be important to us is that this induces a linear ordering of the set of leaves \(L\) of \(U\) and that the set of all leaves that descend from a node \(u\) of \(U\) form an interval of \(L.\) An ordered rooted tree is a rooted tree together with a lexicographic ordering.

Fix a rooted tree \(T.\) An ordered \(T\)-tree is an ordered rooted tree \(U\) together with a homomorphism \(h:U\to T\) with the property that \(h\) maps leaves of \(U\) to leaves of \(T.\) In other words, if \(h(u)\) has a child in \(T\) then \(u\) must also have a child in \(U.\) If \(U\) and \(V\) are ordered \(T\)-trees then \(\binom{U}{V}\) is the set of all ordered \(T\)-subtrees of \(U\) that are isomorphic to \(V\) (an isomorphism between ordered \(T\)-trees is required to preserve the root, the child-parent relation, the lexicographic ordering, as well as the homomorphism to the rooted tree \(T\)). Let \(U,V,W\) be ordered \(T\)-trees and let \(k\) be a positive integer, the partition relation \(W \to (U)^V_k\) means that:

For every coloring \(c:\binom{W}{V}\to\set{0,\dots,k-1}\) there are a color \(d \lt k\) and a \(U’ \in \binom{W}{U}\) such that \(c(V’) = d\) for all \(V’ \in \binom{U’}{V}.\)

Note that if we were dealing with plain sets instead of \(T\)-trees and \(\binom{X}{Y}\) denoted all subsets of \(X\) that are isomorphic to \(Y\) (i.e., have the same size as \(Y\)) then the above is exactly as in the statement of Ramsey’s theorem.

We are now ready to state our partition theorem for finite ordered rooted trees.

Theorem. Let \(T\) be a rooted tree. For all ordered \(T\)-trees \(U, V\) and every positive integer \(k,\) there is a \(T\)-tree \(W\) such that \(W \to (U)^V_k.\)

This result is particularly versatile. It implies some interesting results in Ramsey theory, though that can only be seen by coding certain structures into \(T\)-trees for some appropriate choice of \(T.\)

Ramsey’s theorem [5] is one of the consequences of our partition theorem. Let \(T\) be the rooted tree with two nodes — the root and one leaf. A \(T\)-tree is simply an ordered tree with a distinguished root and a certain number of leaves. Say \(U\) and \(V\) are \(T\)-trees with \(u\) and \(v\) leaves, respectively. Then an element \(V’\) of \(\binom{U}{V}\) consists of a selection of \(v\) leaves of \(U\) together with the root of \(U.\) In other words, if we forget about the root, \(\binom{U}{V}\) consists of all \(v\) element subsets of a set of size \(u\) — the set of leaves of \(U.\) So, if we completely forget about the tree structure, the theorem simply says that for all positive integers \(u,v\) and \(k,\) there is a positive integer \(w\) such that if the \(v\)-element subsets of a set of size \(w\) are colored with \(k\) colors, then there is a subset of size \(u\) all of whose \(v\)-element subsets are colored the same way. This is exactly the statement of Ramsey’s theorem!

The case where \(T\) consists of three nodes — the root, one leaf, and one intermediate node — was also considered by Rado [4] (see also Corollary 6.8 of [2]). A \(T\)-tree \(U\) is an ordered tree all of whose leaves are at distance \(2\) from the root. Again, the leaves of \(U\) form a set \(L\) of size \(u,\) say. The intermediate nodes of \(U\) impose some additional structure on this set, namely they determine a partition \(L\) where each part corresponds to the children of some intermediate node and the parts are ordered according to the ordering of \(U.\) Thus, the structure of \(U\) can be described by the sequence \(u_1,\dots,u_k\) of positive integers, where \(u_i\) is the number of children of the \(i\)-th intermediate node. Note that \(u = u_1 + \cdots + u_k.\) Suppose \(V\) is similarly described by the sequence \(v_1,\dots,v_\ell,\) and set \(v = v_1 + \cdots + v_\ell.\) Forgetting about the tree structure, \(\binom{U}{V}\) consists of all \(v\)-element subsets \(K\) of the partitioned set \(L\) such that the first \(v_1\) elements of \(K\) belong to the same part of \(L,\) the next \(v_2\) elements of \(K\) belong to a later part of \(L,\) and so on. This determines a corresponding ordered partition of \(K\) into \(\ell\) parts, where the \(j\)-th part has size \(v_j.\) When \(k = \ell,\) then the parts must match exactly and we recover some of the partition results for systems of sets that Rado considered in [4].

In [3], Nguyen Van Thé has found a very clever way to talk about partitioned sets as above and even more general systems of nested partitions. Nguyen Van Thé’s convexly ordered ultrametric spaces correspond to the special case of the theorem where \(T\) has a root, one leaf, and a certain number \(n-1\) of intermediate nodes. Recall that an ultrametric space is a metric space \((X,d)\) where the distance \(d\) satisfies the ultrametric inequality \(d(x,z) \leq \max(d(x,y),d(y,z))\) for all \(x,y,z \in X.\) The balls of radius \(r\) then form a partition of \(X\) into a certain number of parts. If \(X\) is moreover endowed with a linear order \({\lt}\) where each ball is an interval, then \((X,d,{\lt})\) is a convexly ordered ultrametric space.

A finite convexly ordered ultrametric space \((X,d,{\lt})\) whose distance function only takes values in the set \(\set{0,1,\dots,n}\) corresponds to a \(T\)-tree \(U\) as follows. The \(i\)-th level of \(U\) consists of all balls \[B_{n-i}(x) = \set{y \in X : d(x,y) \leq n-i};\] these are the nodes of \(U\) that get mapped by the \(T\)-tree homomorphism to the \(i\)-th node of \(T,\) where the root is numbered \(0\) and the leaf is numbered \(n.\) The edge relation on \(U\) is given by the inclusion relation among these balls; so the node corresponding \(B_{n-i-1}(x)\) is always a child of that which corresponds to \(B_{n-i}(x)\) for \(i \in \set{1,\dots,n}.\) Since balls of the same level are disjoint intervals of \(X,\) this induces a lexicographic ordering of the \(T\)-tree \(U.\) Since the balls of radius \(0\) are singletons, there is an obvious bijection between \(X\) and the leaves of \(U.\) The distance \(d\) can be read from the \(T\)-tree \(U\) by figuring the level of the greatest common ancestor of two leaf nodes of \(U.\) The correspondence just described also works backwards, from \(T\)-trees to finite convexly ordered ultrametric spaces with distances in \(\set{0,1,\dots,n}.\) Our theorem for \(T\)-trees thus corresponds exactly to Nguyen Van Thé’s partition theorem for this class of ultrametric spaces. Note that Nguyen Van Thé also considered more general sets of distances (including infinite sets) and he proves that these also have the Ramsey property; the infinite case is not a special case of our theorem but finite sets of distances behave exactly like \(\set{0,1,\dots,n}\) for some \(n.\)

We have not found existing results that correspond to cases where \(T\) is a branching rooted tree. It would be interesting to find more, but there is actually a more pressing matter that stems from our unusual proof. Our proof goes through a wonderful result of Kechris, Pestov, and Todorcevic [2] that ties structural Ramsey results with topological dynamics and model theory. Basically, we computed the automorphism groups of countably categorical linear orders with additional structure and found that these groups have the right dynamical properties to apply the results of Kechris, Pestov and Todorcevic. In particular, there is no known combinatorial proof of our partition theorem for \(T\)-trees! It would be very interesting to find one, especially one that would relate our result to some classical results in Ramsey theory…

References

[1] [doi] F. G. Dorais, S. Gubkin, D. McDonald, and M. Rivera, “Automorphism groups of countably categorical linear orders are extremely amenable,” Order.
[Bibtex]
@article {DoraisGubkinMcDonaldRivera,
AUTHOR = {Dorais, F. G. and Gubkin, S. and McDonald, D. and Rivera, M.},
TITLE = {Automorphism Groups of Countably Categorical Linear Orders are Extremely Amenable},
JOURNAL = {Order},
VOLUME = {},
YEAR = {},
NUMBER = {},
PAGES = {},
DOI = {10.1007/s11083-012-9252-6},
URL = {http://dx.doi.org/10.1007/s11083-012-9252-6},
NOTE = {to appear},
EPRINT = {1202.4092},
}
[2] [doi] A. S. Kechris, V. G. Pestov, and S. Todorcevic, “Fra\"\issé limits, Ramsey theory, and topological dynamics of automorphism groups,” Geom. funct. anal., vol. 15, iss. 1, pp. 106-189, 2005.
[Bibtex]
@article {KechrisPestovTodorcevic,
AUTHOR = {Kechris, A. S. and Pestov, V. G. and Todorcevic, S.},
TITLE = {Fra{\"\i}ss{\'e} limits, {R}amsey theory, and topological dynamics of automorphism groups},
JOURNAL = {Geom. Funct. Anal.},
FJOURNAL = {Geometric and Functional Analysis},
VOLUME = {15},
YEAR = {2005},
NUMBER = {1},
PAGES = {106--189},
ISSN = {1016-443X},
DOI = {10.1007/s00039-005-0503-1},
URL = {http://dx.doi.org/10.1007/s00039-005-0503-1},
EPRINT = {math/0305241},
}
[3] [doi] L. Nguyen Van Thé, “Ramsey degrees of finite ultrametric spaces, ultrametric Urysohn spaces and dynamics of their isometry groups,” European j. combin., vol. 30, iss. 4, pp. 934-945, 2009.
[Bibtex]
@article {NguyenVanThe,
AUTHOR = {Nguyen Van Th{\'e}, L.},
TITLE = {Ramsey degrees of finite ultrametric spaces, ultrametric {U}rysohn spaces and dynamics of their isometry groups},
JOURNAL = {European J. Combin.},
FJOURNAL = {European Journal of Combinatorics},
VOLUME = {30},
YEAR = {2009},
NUMBER = {4},
PAGES = {934--945},
ISSN = {0195-6698},
DOI = {10.1016/j.ejc.2008.07.007},
URL = {http://dx.doi.org/10.1016/j.ejc.2008.07.007},
EPRINT = {0710.2347},
}
[4] [doi] R. Rado, “Direct decomposition of partitions,” J. london math. soc., vol. 29, pp. 71-83, 1954.
[Bibtex]
@article {Rado,
AUTHOR = {Rado, R.},
TITLE = {Direct decomposition of partitions},
JOURNAL = {J. London Math. Soc.},
FJOURNAL = {Journal of the London Mathematical Society. Second Series},
VOLUME = {29},
YEAR = {1954},
PAGES = {71--83},
ISSN = {0024-6107},
DOI = {10.1112/jlms/s1-29.1.71},
URL = {http://dx.doi.org/10.1112/jlms/s1-29.1.71},
}
[5] [doi] F. P. Ramsey, “On a problem of formal logic,” Proc. lond. math. soc., vol. 30, pp. 264-286, 1930.
[Bibtex]
@article{Ramsey,
AUTHOR = {Ramsey, F. P.},
TITLE = {On a Problem of Formal Logic},
JOURNAL = {Proc. Lond. Math. Soc.},
FJOURNAL = {Proceedings of The London Mathematical Society},
VOLUME = {30},
YEAR = {1930},
PAGES = {264--286},
DOI = {10.1112/plms/s2-30.1.264},
URL = {http://dx.doi.org/10.1112/plms/s2-30.1.264},
}
 

Subposets of small dimension

Behind the scenes at Boole’s Rings, there was some talk on asking more open questions related to our research. I have three related problems that I would like to share. They are strikingly similar in nature, but they properly belong in three different branches of mathematics: the first problem is about finite combinatorics, the second problem is about reverse mathematics, and the third problem is about infinite combinatorics. To me they are three faces of the same question and I currently don’t know how to answer any of them.

Three Problems. Let $d \geq 2$:

  1. Let $F_d(n)$ denote the largest number such that every poset of size $n$ has a $d$-dimensional subposet of size $F_d(n)$. What is the asymptotic growth of $F_d(n)$?
  2. Every (countably) infinite poset has an infinite subposet of dimension at most $d$. What is the logical strength of this statement over $\mathsf{RCA}_0$?
  3. Is there an uncountable poset that has no uncountable $d$-dimensional subposet?

… 

 

On a theorem of Mycielski and Taylor

$\DeclareMathOperator{\cov}{cov}\newcommand{\meager}{\mathcal{M}}$

In 1964, Jan Mycielski [1] proved a wonderful theorem about independent sets in Polish spaces. He showed that if $X$ is an uncountable Polish space and $R_n$ is a meager subset of $X^n$ for each $n \geq 1$, then there is a perfect set $Z \subseteq X$ such that $(z_1,\dots,z_n) \notin R_n$ whenever $z_1,\dots,z_n$ are distinct elements of $Z$. In other words, $Z$ is $R_n$-independent for each $n \geq 1$. This is a wonderfully general theorem that has a multitude of applications.

One of my favorite theorems where Mycielski’s Theorem comes in handy is a remarkable partition theorem due to Fred Galvin [2].

Theorem (Galvin). Let $X$ be an uncountable Polish space and let $c:[X]^2\to\set{0,\dots,k-1}$ be a Baire measurable coloring where $k$ is a positive integer. Then $X$ has a perfect $c$-homogeneous subset.

Galvin proved a similar result for colorings of $[X]^3$, but with a weaker conclusion that triples from the perfect set take on at most two colors. Andreas Blass [3] then extended Galvin’s result to colorings of $[X]^n$, showing that there is a perfect set that takes on at most $(n-1)!$ colors.

Galvin’s result has many applications too. For example, Rafał Filipów and I used it in [4] it to show that if $X$ is a perfect Abelian Polish group, then $X$ contains a Marczewski null set $A$ such that the algebraic sum $A + A$ is not Marczewski measurable.

Alan Taylor [5] generalized the result to Baire measurable colorings $c:[X]^2\to\kappa$ where $\kappa$ is any cardinal smaller than $\cov(\meager)$. Doing so, Taylor similarly generalized Mycielski’s Theorem, but he only stated the result for binary relations. Recently, Rafał Filipów, Tomasz Natkaniec and I needed this generalization for relations of arbitrary arity. Unfortunately, the Mycielski–Taylor result has never been stated in full generality, so we included a proof in our paper [6]. I am copying this proof here because I think the result is of independent interest and our proof is a nice application of Cohen forcing. A nice consequence of this extended Mycielski–Taylor Theorem is that Blass’s result extends to Baire measurable colorings $c:[X]^n\to\kappa$ where $\kappa \lt \cov(\meager)$ in the same way that Taylor generalized Galvin’s result for partitions of pairs.

Theorem (Mycielski, Taylor). Let $X$ be an uncountable Polish space and let $\mathcal{R}$ be a family of fewer than $\cov(\meager)$ closed nowhere dense relations on $X$, i.e., each $R \in \mathcal{R}$ is a closed nowhere dense subset of $X^n$ for some $n = n(R)$. Then $X$ contains a perfect set which is $R$-independent for every $R \in \mathcal{R}$.

… 

[1] J. Mycielski, “Independent sets in topological algebras,” Fund. math., vol. 55, pp. 139-147, 1964.
[Bibtex]
@article {Mycielski,
AUTHOR = {Mycielski, Jan},
TITLE = {Independent sets in topological algebras},
JOURNAL = {Fund. Math.},
FJOURNAL = {Polska Akademia Nauk. Fundamenta Mathematicae},
VOLUME = {55},
YEAR = {1964},
PAGES = {139--147},
ISSN = {0016-2736},
MRCLASS = {08.40 (55.99)},
MRNUMBER = {0173645 (30 \#3855)},
MRREVIEWER = {Th. J. Dekker},
URL = {http://matwbn.icm.edu.pl/tresc.php?wyd=1&tom=55},
}
[2] F. Galvin, “Partition theorems for the real line,” Notices amer. math. soc., vol. 15, p. 660, 1968.
[Bibtex]
@article {Galvin,
AUTHOR = {Galvin, Fred},
TITLE = {Partition theorems for the real line},
JOURNAL = {Notices Amer. Math. Soc.},
FJOURNAL = {Notices of the American Mathematical Society},
VOLUME = {15},
YEAR = {1968},
PAGES = {660},
NOTE = {Erratum in volume 16 (1969), p.~1095},
}
[3] [doi] A. Blass, “A partition theorem for perfect sets,” Proc. amer. math. soc., vol. 82, iss. 2, pp. 271-277, 1981.
[Bibtex]
@article {Blass,
AUTHOR = {Blass, Andreas},
TITLE = {A partition theorem for perfect sets},
JOURNAL = {Proc. Amer. Math. Soc.},
FJOURNAL = {Proceedings of the American Mathematical Society},
VOLUME = {82},
YEAR = {1981},
NUMBER = {2},
PAGES = {271--277},
ISSN = {0002-9939},
CODEN = {PAMYAR},
MRCLASS = {03E15 (03E05 04A20 54H05)},
MRNUMBER = {609665 (83k:03063)},
DOI = {10.2307/2043323},
URL = {http://dx.doi.org/10.2307/2043323},
}
[4] F. G. Dorais and R. Filipów, “Algebraic sums of sets in Marczewski-Burstin algebras,” Real anal. exchange, vol. 31, iss. 1, pp. 133-142, 2005/06.
[Bibtex]
@article {DoraisFilipow,
AUTHOR = {Dorais, Fran{\c{c}}ois G. and Filip{\'o}w, Rafa{\l}},
TITLE = {Algebraic sums of sets in {M}arczewski-{B}urstin algebras},
JOURNAL = {Real Anal. Exchange},
FJOURNAL = {Real Analysis Exchange},
VOLUME = {31},
YEAR = {2005/06},
NUMBER = {1},
PAGES = {133--142},
ISSN = {0147-1937},
MRCLASS = {28A05 (39A70)},
MRNUMBER = {2218194 (2007h:28002)},
MRREVIEWER = {K. P. S. Bhaskara Rao},
URL = {http://projecteuclid.org/getRecord?id=euclid.rae/1149516801},
}
[5] A. D. Taylor, “Partitions of pairs of reals,” Fund. math., vol. 99, iss. 1, pp. 51-59, 1978.
[Bibtex]
@article {Taylor,
AUTHOR = {Taylor, Alan D.},
TITLE = {Partitions of pairs of reals},
JOURNAL = {Fund. Math.},
FJOURNAL = {Polska Akademia Nauk. Fundamenta Mathematicae},
VOLUME = {99},
YEAR = {1978},
NUMBER = {1},
PAGES = {51--59},
ISSN = {0016-2736},
MRCLASS = {04A20},
MRNUMBER = {0465873 (57 \#5759)},
MRREVIEWER = {Thomas J. Jech},
URL = {http://matwbn.icm.edu.pl/tresc.php?wyd=1&tom=99},
}
[6] F. G. Dorais, R. Filipów, and T. Natkaniec, “On some properties of Hamel bases and their applications to Marczewski measurable functions,” Preprint, 2011.
[Bibtex]
@article {DoraisFilipowNatkaniec,
AUTHOR = {Dorais, Fran{\c{c}}ois G. and Filip{\'o}w, Rafa{\l} and Natkaniec, Tomasz},
TITLE = {On some properties of {H}amel bases and their applications to {M}arczewski measurable functions},
JOURNAL = {preprint},
YEAR = {2011},
}
 

Uncountable perfect graphs

I have been fascinated with perfect graphs for many years. These graphs are very intensely studied in finite combinatorics and new wonderful properties of finite perfect graphs are discovered on a regular basis. However, it is still unclear whether or how these wonderful properties might extend to the countable and uncountable cases. There are several deep questions about this. One of the most interesting question is the consistency of Galvin’s Conjecture. I recently wrote a paper on this question [1]. Since I believe this and related questions deserve more attention, here is a brief survey of known results around Galvin’s Conjecture.

… 

[1] [doi] F. G. Dorais, “A note on conjectures of F. Galvin and R. Rado,” Canad. math. bull., 2011.
[Bibtex]
@article {Dorais,
AUTHOR = {Dorais, Fran{\c{c}}ois G.},
TITLE = {A note on conjectures of {F}. {G}alvin and {R}. {R}ado},
JOURNAL = {Canad. Math. Bull.},
FJOURNAL = {Canadian Mathematical Bulletin. Bulletin Canadien de Math\'ematiques},
YEAR = {2011},
DOI = {10.4153/CMB-2011-192-8},
URL = {http://dx.doi.org/10.4153/CMB-2011-192-8},
NOTE = {to appear},
EPRINT = {1110.6563},
}