Abstract. Let [Formula: see text] be a finite set. A family [Formula: see text] of subsets of [Formula: see text] is called a convex geometry with ground set [Formula: see text] if (1) [Formula: see text]; (2) [Formula: see text] whenever [Formula: see text]; and (3) if [Formula: see text] and [Formula: see text], there is an element [Formula: see text] such that [Formula: see text]. As a nonempty family of sets, a convex geometry has a well defined [Formula: see text]-dimension. In the literature, a second parameter, called the convex dimension, has been defined expressly for these structures. Partially ordered by inclusion, a convex geometry is also a poset, and four additional dimension parameters have been defined for this larger class, called the Dushnik–Miller dimension, Boolean dimension, local dimension, and fractional dimension, respectively. For each pair of these six dimension parameters, we investigate whether there is an infinite class of convex geometries on which one parameter is bounded and the other is not.

Several classical constructions illustrate the fact that the chromatic number of a graph may be arbitrarily large compared to its clique number. However, until very recently no such construction was known for intersection graphs of geometric objects in the plane. We provide a general construction that for any arc-connected compact set $$X$$ in $$\mathbb{R }^2$$ that is not an axis-aligned rectangle and for any positive integer $$k$$ produces a family $$\mathcal{F }$$ of sets, each obtained by an independent horizontal and vertical scaling and translation of $$X$$ , such that no three sets in $$\mathcal{F }$$ pairwise intersect and $$\chi (\mathcal{F })>k$$ . This provides a negative answer to a question of Gyárfás and Lehel for L-shapes. With extra conditions we also show how to construct a triangle-free family of homothetic (uniformly scaled) copies of a set with arbitrarily large chromatic number. This applies to many common shapes, like circles, square boundaries or equilateral L-shapes. Additionally, we reveal a surprising connection between coloring geometric objects in the plane and on-line coloring of intervals on the line.

This is a sequel to a previous paper entitled The Order Dimension of Convex Polytopes, by the same authors [SIAM J. Discrete Math., 6 (1993), pp. 230--245]. In that paper, we considered the poset {{\bf P}\protect\boldmath$_M\!\!\!$} formed by taking the vertices, edges, and faces of a 3-connected planar map {\bf M}, ordered by inclusion, and showed that the order dimension of {{\bf P}\protect\boldmath$_M\!\!\!$} is always equal to 4. In this paper, we show that if {\bf M} is any planar map, then the order dimension of {{\bf P}\protect\boldmath$_M\!\!\!$} is still at most 4.

For a graph H, let ${\text{Forb}}( H )$ be the class of graphs that do not induce H, and let $P_5 $ be the path on five vertices. In this article, we answer two questions of Gyárfás and Lehel. First, we show that there exists a function $f( \omega )$ such that for any graph $G \in \,{\text{Forb}}( P_5 )$, the on-line coloring algorithm First-Fit uses at most $f( \omega ( G ) )$ colors on G, where $\omega ( G )$ is the clique size of G. Second, we show that there exists an on-line algorithm A that will color any graph $G \in \,{\text{Forb}}( P_5 )$ with a number of colors exponential in $\omega ( G )$. Finally, we extend some of our results to larger classes of graphs defined in terms of a list of forbidden subgraphs.

An on-line vertex coloring algorithm receives the vertices of a graph in some externally determined order, and, whenever a new vertex is presented, the algorithm also learns to which of the previously presented vertices the new vertex is adjacent. As each vertex is received, the algorithm must make an irrevocable choice of a color to assign the new vertex, and it makes this choice without knowledge of future vertices. A class of graphs $\Gamma $ is said to be on-line $\chi$-bounded if there exists an on-line algorithm A and a function f such that A uses at most $f( \omega ( G ) )$ colors to properly color any graph G in $\Gamma $. If H is a graph, let Forb$( H )$ denote the class of graphs that do not induce H. The goal of this paper is to establish that Forb$( T )$ is on-line $\chi$-bounded for every radius-2 tree T. As a corollary, the authors answer a question of Schmerl’s the authors show that every recursive cocomparability graph can be recursively colored with a number of colors that depends only on its clique number.

With a convex polytope ${\text{M}}$ in $\mathbb{R}^3$, a partially ordered set ${\text{P}}_{\text{M}} $ is associated whose elements are the vertices, edges, and faces of ${\text{M}}$ ordered by inclusion. This paper shows that the order dimension of ${\text{P}}_{\text{M}} $ is exactly 4 for every convex polytope ${\text{M}}$. In fact, the subposet of ${\text{P}}_{\text{M}} $ determined by the vertices and faces is critical in the sense that deleting any element leaves a poset of dimension 3.

We show that, for multi-tape Turing machines, non-deterministic linear time is more powerful than deterministic linear time. We also discuss the prospects for extending this result to more general Turing machines.