Expand all Collapse all | Results 1 - 2 of 2 |
1. CMB 2012 (vol 57 pp. 61)
2-dimensional Convexity Numbers and $P_4$-free Graphs For $S\subseteq\mathbb R^n$ a set
$C\subseteq S$ is an $m$-clique if the convex hull of no $m$-element subset of
$C$ is contained in $S$.
We show that there is essentially just one way to construct
a closed set $S\subseteq\mathbb R^2$ without an uncountable
$3$-clique that is not the union of countably many convex sets.
In particular, all such sets have the same convexity number;
that is, they
require the same number of convex subsets to cover them.
The main result follows from an analysis of the convex structure of closed
sets in $\mathbb R^2$ without uncountable 3-cliques in terms of
clopen, $P_4$-free graphs on Polish spaces.
Keywords:convex cover, convexity number, continuous coloring, perfect graph, cograph Categories:52A10, 03E17, 03E75 |
2. CMB 2011 (vol 56 pp. 317)
A Note on Conjectures of F. Galvin and R. Rado In 1968, Galvin conjectured that an uncountable poset $P$ is the
union of countably many chains if and only if this is true for every
subposet $Q \subseteq P$ with size $\aleph_1$. In 1981, Rado
formulated a similar conjecture that an uncountable interval graph $G$ is countably
chromatic if and only if this is true for every induced subgraph $H
\subseteq G$ with size $\aleph_1$. TodorÄeviÄ has shown
that Rado's Conjecture is consistent relative to the existence of a
supercompact cardinal, while the consistency of Galvin's Conjecture
remains open. In this paper, we survey and collect a variety of
results related to these two conjectures. We also show that the
extension of Rado's conjecture to the class of all chordal graphs is
relatively consistent with the existence of a supercompact cardinal.
Keywords:Galvin conjecture, Rado conjecture, perfect graph, comparability graph, chordal graph, clique-cover number, chromatic number Categories:03E05, 03E35, 03E55 |