67 citations · 180 across the 16 of their papers we have counts for
24 papers
Forcing the Wheel
Jędrzej Hodor, William T. Trotter
Over the past 10 years, there has been considerable interest in exploring questions connecting dimension for posets with graph theoretic properties of their cover graphs and order…
Concepts of Dimension for Convex Geometries
Kolja Knauer, William T. Trotter
Let be a finite set. A family of subsets of is called a convex geometry with ground set if (1) ; (2) whenever ; and (3)…
Boolean dimension and dim-boundedness: Planar cover graph with a zero
Heather Smith Blake, Piotr Micek, William T. Trotter
In 1989, Nešetřil and Pudlák posed the following challenging question: Do planar posets have bounded Boolean dimension? We show that every poset with a planar cover graph and a uni…
Random bipartite posets and extremal problems
Csaba Biró, Peter Hamburger, H. A. Kierstead +3
Previously, Erdős, Kierstead and Trotter investigated the dimension of random height~ partially ordered sets. Their research was motivated primarily by two goals: (1)~analyzing…
Dimension is polynomial in height for posets with planar cover graphs
Jakub Kozik, Piotr Micek, William T. Trotter
We show that height posets that have planar cover graphs have dimension . Previously, the best upper bound was . Planarity plays a key r…
Planar Posets that are Accessible from Below Have Dimension at Most 6
Csaba Biró, Bartłomiej Bosek, Heather C. Smith +3
Planar posets can have arbitrarily large dimension. However, a planar poset of height has dimension at most , while a planar poset with minimal elements has dimens…
Fractional Local Dimension
Heather C. Smith, William T. Trotter
The original notion of dimension for posets was introduced by Dushnik and Miller in 1941 and has been studied extensively in the literature. In 1992, Brightwell and Scheinerman dev…
Boolean Dimension, Components and Blocks
Tamás Mészáros, Piotr Micek, William T. Trotter
We investigate the behavior of Boolean dimension with respect to components and blocks. To put our results in context, we note that for Dushnik-Miller dimension, we have that if $\…
Local Dimension is Unbounded for Planar Posets
Bartłomiej Bosek, Jarosław Grytczuk, William T. Trotter
In 1981, Kelly showed that planar posets can have arbitrarily large dimension. However, the posets in Kelly's example have bounded Boolean dimension and bounded local dimension, le…
Comparing Dushnik-Miller Dimension, Boolean Dimension and Local Dimension
Fidel Barrera-Cruz, Thomas Prag, Heather Smith +2
The original notion of dimension for posets is due to Dushnik and Miller and has been studied extensively in the literature. Quite recently, there has been considerable interest in…
The Graph of Critical Pairs of a Crown
Fidel Barrera-Cruz, Rebecca Garcia, Pamela Harris +5
There is a natural way to associate with a poset a hypergraph , called the hypergraph of critical pairs, so that the dimension of is exactly equal to the chromatic numbe…
Boolean dimension and local dimension
William T. Trotter, Bartosz Walczak
Dimension is a standard and well-studied measure of complexity of posets. Recent research has provided many new upper bounds on the dimension for various structurally restricted cl…
Burling graphs, chromatic number, and orthogonal tree-decompositions
Stefan Felsner, Gwenaël Joret, Piotr Micek +2
A classic result of Asplund and Grünbaum states that intersection graphs of axis-aligned rectangles in the plane are -bounded. This theorem can be equivalently stated in terms o…
Separating Tree-chromatic number from Path-chromatic Number
Fidel Barrera-Cruz, Stefan Felsner, Tamás Mészáros +4
We apply Ramsey theoretic tools to show that there is a family of graphs which have tree-chromatic number at most~ while the path-chromatic number is unbounded. This resolves a…
Dimension of posets with planar cover graphs excluding two long incomparable chains
David M. Howard, Noah Streib, William T. Trotter +2
It has been known for more than 40 years that there are posets with planar cover graphs and arbitrarily large dimension. Recently, Streib and Trotter proved that such posets must h…
First-fit coloring on interval graphs has performance ratio at least 5
H. A. Kierstead, David A. Smith, W. T. Trotter
First-fit is the online graph coloring algorithm that considers vertices one at a time in some order and assigns each vertex the least positive integer not used already on a neighb…
Dimension and cut vertices: an application of Ramsey theory
William T. Trotter, Bartosz Walczak, Ruidong Wang
Motivated by quite recent research involving the relationship between the dimension of a poset and graph-theoretic properties of its cover graph, we show that for every ,…
On the dimension of posets with cover graphs of treewidth
Gwenaël Joret, Piotr Micek, William T. Trotter +2
In 1977, Trotter and Moore proved that a poset has dimension at most whenever its cover graph is a forest, or equivalently, has treewidth at most . On the other hand, a well…
Forcing Posets with Large Dimension to Contain Large Standard Examples
Csaba Biró, Peter Hamburger, Attila Pór +1
The dimension of a poset , denoted , is the least positive integer for which is the intersection of linear extensions of . The maximum dimension of a pos…
Incidence Posets and Cover Graphs
William T. Trotter, Ruidong Wang
We prove two theorems concerning incidence posets of graphs, cover graphs of posets and a related graph parameter. First, answering a question of Haxell, we show that the chromatic…
Tree-width and dimension
Gwenaël Joret, Piotr Micek, Kevin G. Milans +3
Over the last 30 years, researchers have investigated connections between dimension for posets and planarity for graphs. Here we extend this line of research to the structural grap…
Triangle-free geometric intersection graphs with large chromatic number
Arkadiusz Pawlik, Jakub Kozik, Tomasz Krawczyk +4
Several classical constructions illustrate the fact that the chromatic number of a graph can be arbitrarily large compared to its clique number. However, until very recently, no su…
Triangle-free intersection graphs of line segments with large chromatic number
Arkadiusz Pawlik, Jakub Kozik, Tomasz Krawczyk +4
In the 1970s, Erdos asked whether the chromatic number of intersection graphs of line segments in the plane is bounded by a function of their clique number. We show the answer is n…
An extremal problem on crossing vectors
Michał Lasoń, Piotr Micek, Noah Streib +2
For positive integers and , two vectors and from are called -crossing if there are two coordinates and such that and $B[j…