William T. Trotter

Publications Available On-Line

159. Forcing the wheel, submitted, arxiv.org/abs/2304.0812v1(J. Hodor).
158. Concepts of dimension for convex geometries, SIAM J. Discrete Math., to appear, available at arxiv.org/abs/2303.08945 (with K. Knauer).
157. Boolean dimension and dim-boundedness: Planar cover graph with zero, submitted but available at arxiv.org/abs/2206.06942 (with H. S. Blake and P. Micek).
156. Dimension is polynomial in height for posets with planar cover graphs, J. Combin. Theory Ser. B 165 (2024), 164 - 196 (with J. Kozik and P. Micek).
155. Fractional local dimension, Order 38 (2021) 329 - 350 (with H. C. Smith).
154. Planar posets that are accessible from below have dimension at most 6, Order, to appear but published online June 2, 2020 (with C. Biro, B. Bosek, H. C. Smith, R. Yang and S. J. Young).
153. Random bipartite posets and extremal problems, Acta Math. Hungarica 161 (2020), 618 - 646 (with C. Biro, P. Hamburger, H. Kierstead, A. Por and R. Wang).
152. Boolean dimension, components and blocks, Order 37 (2020) 287 - 298 (with T. Meszaros and P. Micek).
151. Local dimension is unbounded for planar posets, Electronic Journal of Combinatorics 27 (2020), P4.28 (with B. Bosek and J. Grytczuk).
150. Comparing Dushnik-Miller dimension, boolean dimension and local dimension, Order 37 (2020), 243 - 269 (with F. Barrera-Cruz, T. Prag and H. C. Smith).
149. Dimension for posets and chromatic number for graphs, in 50 Years of Combinatorics, Graph Theory and Computing, F. Chung, et al., eds., Chapman and Hall (2019), 73 - 96.
148. The graph of critical pairs of a crown, Order 36 (2019), 621 - 652 (with F. Barrera-Cruz, R. Garcia, P. Harris, B. Kubik, S. Talbott, H. C. Smith and L. Taylor)).
147. Separating tree-chromatic number from path-chromatic number, J. Combinatorial Theory, Ser. B, 138 (2109), 206--218 (with F. Barrera-Cruz, S. Felsner, T. Meszaros, P. Micek, H. C. Smith and L. Taylor).
146. The dimension of posets which have planar cover graphs and exclude two long incomparable chains, J. Combin. Theory, Ser. A, 164 (2019), 1--23 (With D. Howard, N. Streib, B. Walczak and R. Wang).
145. Dimension and cut vertices: An application of Ramsey theory, in Connections in Discrete Mathematics, S. Butler, et al., eds, Cambridge University Press (2018), 187--199 (with B. Walczak and R. Wang).
144. Burling graphs, chromatic number and orthogonal tree-decompositions, Electronic Journal of Combinatorics, 25 (2017), P 1.35 (with S. Felsner, G. Joret, P. Micek and V. Wiechert).
143. Trees and circle orders, Abh. Math. Semin. Univ. Hambg, 87 (2017), 445--454.
142. Boolean dimension and local dimension, Electronic Notes in Discrete Mathematics, 61 (2017), 1047--1053 (with B. Walczak).
141. On the dimension of posets with cover graphs of tree-width 2, Order 34 (2017), 185 - 234 (with G. Joret, P. Micek, R. Wang and V. Wiechert).
140. Forcing posets with large dimension to contain large standard examples Graphs and Combinatorics 32 (2016), 861 - 880 (with C. Biro, P. Hamburger and A. Por.
139. Posets and VPG graphs, Order 33 (2016), 101--119 (with E. Cohen, M. C. Golumbic and R. Wang).
138. Dimension and matchings in comparability graphs and incomparability graphs, Order 33 (2016), 101 - 119. 2015 (with R. Wang).
137. Planar posets, dimension, breadth and the number of minimal elements Order 33 (2016), 333 - 346 (with R. Wang)
136. Tree-width and dimension, Combinatorica 36 (2016), 431 - 450 (with G.Joret, P. Micek, K. G. Milans, B. Walczak and R. Wang).
135. First-Fit coloring on interval graphs has performance ratio at least 5, European J. Combinatorics 51 (2016), 236 - 254. (with H. A. Kierstead and D. Smith).
134. The dimension of posets with planar cover graphs, Graphs and Combinatorics 31 (2015), 927 - 939 (with S. Felsner and V. Wiechert).
133. Incidence posets and cover graphs, Order 31 (2014), 279-287 (with R. Wang).
132. Triangle-free intersection graphs of line segements with large chromatic number, J. Combinatorial Theory Series B 105 (2014), 6-10 (with A. Pawlik, J. Kozik, T. Krawczyk, M. Lason, P. Micek and B. Walczak).
131. Hamiltonian cycles and symmetric chains in boolean lattices, Graphs and Combinatorics, 30 (2014), 1565-1586 (with N. Streib).
130. An extremal problem on crossing vectors, J. Combinatorial Theory Series A, 128 (2014), 41-55 (with M. Lason, P. Micek, N. Streib and B. Walczak).
129. Dimension and height for posets with planar cover graphs, European J. Combinatorics 35 (2014), 474-489 (with N. Streib).
128. Triangle-free intersection graphs with large chromatic number, Discrete and computational Geometry 50 (2013), 714 - 726 (with A. Pawkik, J. Kozik, T. Krawczyk, M. Lason, P. Micek and B. Walczak).
127. Online dimension for posets excluding two long incomparable chains, Order 30 (2013), 1-12 (with S. Felsner and T. Krawczyk).
126. A combinatorial approach to height sequences of finite partially ordered sets, Discrete Math., Vol. 311 (2011), 563-569 (with C. Biro).
125. Online Linear Discrepancy, in An Irregular Mind, Szemeredi is 70, I. Baranyi and J. Solymosi, eds., Bolyai Soc. Mathematical Studies, Vol. 20 (2010), 343 - 357 (with M. T. Keller and N. Streib.
124. On the size of maximal antichains and the number of pairwise disjoint maximal chains, Discrete Math., 310 (2010) 2890 - 2894 (with D. M. Howard).
123. Adjacency posets of planar graphs, Discrete Mathematics, 310 (2010) 1097 - 1104 (with S. Felsner and C. M. Li).
122. Intersection graphs of pseudosegments: chordal graphs, J. Graph Algorithms and Applications, 14 (2010), 199 - 220 (with C. Dangelmayr and S. Felsner).
121. Interval Partitions and Stanley Depth, J. Combinatorial Theory, A, 117 (2010), 475 - 482 (with C. Biro, D. M. Howard, M. T. Keller and S. Y. Young).
120. Segment orders, Discrete and Computational Geometry, 43 (2010), 680 - 704 (with C. Biro).
119. Bar k -Visibility Graphs, J. Graph Algorithms and Applications, 11 (2007), 45 - 59 (with A. Dean, W. Evans, E. Gethner, J. Laison and M. Safari).
118. Posets and Planar Graphs, J. Graph Theory 47 (2005), 273--284 (with S. Felsner).
117. A new approach to correlation inequalities, Discrete Math. 257 (2002), 311 - 327 (with G. R. Brightwell).
116. Containment orders for similar ellipses with a common center, Discrete Math. 256 (2002), 129 - 136 (with P. C. Fishburn).
115. A note on graph pebbling, Graphs and Combinatorics 18 (2002), 219 - 225 (with A. Czygrinow, G. Hurlbert and H. A. Kierstead).
114. Competitive colorings of oriented graphs, Electronic Journal of Combinatorics 8 (2001) no.2, Research Paper 12 (with H. A. Kierstead).
113. Spanning trees of bounded degree, Electronic Journal of Combinatorics 8 (2001) no. 1, Research Paper 33 (with A. Czygrinow, G. Fan, G. Hurlbert and H. A. Kierstead).
112. Dimension, graph and hypergraph coloring, Order 17 (2000), 167-177 (with S. Felsner).
111. Interval orders and dimension, Discrete Math. 213 (2000), 179-188 (with H. A. Kierstead).
110. Ramsey theory and partially ordered sets, in Contemporary Trends in Discrete Mathmatics, R. L. Graham, et al., eds., Dimacs Series in Discrete Mathematics and Theoretical Computer Science 49 (1999), 337--347.
109. The maximum number of edges in a graph of bounded dimension, with applications to ring theory, Discrete Math. 201 (1999), 5--19 (with G. Agnarsson and S. Felsner).
108. Finite three dimensional partial orders which are not sphere orders, Discrete Math. 201 (1999), 101--132 (with S. Felsner and P. C. Fishburn).
107. Split semiorders, Discrete Math. 195 (1999), 111--126 (with P. C. Fishburn).
106. Geometric containment orders: A survey, Order 15 (1998-99), 167--182 (with P. C. Fishburn).
105. Ramsey theory and sequences of random variables, Probability, Combinatorics and Computing 7 (1998), 221--238 (with P. M. Winkler).
104. Dimensions of split semiorders Order 14 (1997), 171--178 (with P. C. Fishburn).
103. New perspectives on interval orders and interval graphs, in Surveys in Combinatorics, R. A. Bailey, ed., London Mathematical Society Lecture Note Series 241 (1997), 237--286.
102. Applications of the probabilistic method to partially ordered sets, in The Mathematics of Paul Erdos, II, R. L.Graham and J.Nesetril, eds., Algorithms and Combinatorics, Vol. 14, Springer Verlag, Berlin (1997), 214--228.
101. The order dimension of planar maps, SIAM J. Discrete Math. 10 (1997), 515--528 (with G. R. Brightwell).
100. Graphs and partially ordered sets: recent results and new directions, Congressus Numerantium 116 (1996), 253--278.
99. On-line and first-fit colorings of graphs which do not induce P5, SIAM J. Discrete Math. 8 (1995), 485-498 (with H. Kierstead and S. Penrice).
98. Partially ordered sets, in Handbook of Combinatorics, R. L. Graham, M. Groetschel, L. Lovasz, eds., Elsevier, Amsterdam, 1995, 433--480.

Balancing pairs and the cross product conjecture

96. interval orders and alpha-sequences of sets, Discrete Math. 144 (1995), 23--31 (with S. Felsner).
95. Incidence posets of trees in posets of large dimension, Order 11 (1994), 159-168 (with G. Brightwell).
94. The dimension of suborders of the boolean lattice, Order 11 (1994), 127- 134 (with G. Brightwell, H. Kierstead and A. Kostochka).
93. On the fractional dimension of partially ordered sets, Discrete Math. 136 (1994), 101-117 (with S. Felsner).
92. Planar graph coloring with an uncooperative partner, J. Graph Theory 18 (1994), 569-584 (with H. Kierstead).
91. Progress and new directions in dimension theory for finite partially ordered sets, in Extremal Problems for Finite Sets , P. Frankl, Z. Furedi, G. Katona and D. Miklos, eds., Bolyai Soc. Math. Studies 3 (1994), 457-477.
90. On the poset of all posets on n elements, Discrete Applied Math. 50 (1994), 111-123 (with R. A. Brualdi and H. C. Jung).
89. On-line coloring and recursive graph theory, SIAM J. Discrete Math. 7 (1994), 72-89 (with H. Kierstead and S. Penrice).
88. On the game chromatic number of some classes of Graphs, Ars Combinatoria 35 (1993), 143-150 (with U. Faigle, W. Kern and H. Kierstead).
87. Posets with large dimension and relatively few critical pairs, Order 10 (1993) 317-328 (with P. Fishburn).
86. Balancing pairs in partially ordered sets, in Combinatorics, Paul Erdos is Eighty, Bolyai Society Mathematical Studies, 1993, 145-157 (with S. Felsner).
85. Induced matchings in cubic graphs, J. Graph Theory 17 (1993), 151-160 (with P. Horak and He Qing).
84. The order dimension of convex polytopes, SIAM J. Discrete Math. 6 (1993), 230-245 (with G. Brightwell).
83. Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures, Discrete Math. 113 (1993) 191-205 (with J. Schmerl).
82. Balance theorems for height-2 posets, Order 9 (1992) 43-53 (with W. Gehrlein and P. Fishburn).
81. Large regular graphs with no induced 2K_2's, Graphs and Combinatorics 8 (1992) 165-197 (with M. Paoli, G. W. Peck, and D. West).
80. The dimension of cycle-free orders, Order 9 (1992) 103-110 (with H. Kierstead and J. Qin).
79. Colorful induced subgraphs, Discrete Math. 101 (1992) 165-169 (with H. Kierstead).
78. Dimensions of hypergraphs, J. Comb. Theory B 56 (1992) 278-295 (with P. Fishburn).

77. On-line graph coloring, in On-Line Algorithms , L. McGeoch and D. Sleator, eds., DIMACS Series in Discrete Mathematics and Theoretical Computer Science (1992) 85-92 (with H. Kierstead).
76. Linear extensions of semiorders: A maximization problem, Discrete Math. 103 (1992), 25-40 (with P. Fishburn).
75. On the number of different distances, Discrete and Computational Geometry 7 (1992), 1-11 (with F. R. K. Chung and E. Szemeredi).
74. Fibres and ordered set coloring, J. Comb. Theory A 58 (1991) 158-164 (with D. Duffus and H. Kierstead).
73. Interval orders and shift graphs, in Sets, Graphs and Numbers , A. Hajnal and V. T. Sos, eds., Colloq. Math. Soc. Janos Bolyai 60 (1991) 297-313 (with Z. Furedi, P. Hajnal and V. Rodl).
72. The dimension of random ordered sets, Random Structures and Algorithms 2 (1991), 253-275 (with P. Erdos and H. Kierstead).
71. A note on removable pairs, in Graph Theory, Combinatorics and Applications, Vol. 2 , Y. Alavl et al., eds., John Wiley (1991), 739-742 (with H. Kierstead).
70. Angle orders and zeroes, Order 7 (1990), 213-217 (with P. Fishburn).
69. The maximal number of edges in 2K_2-free graphs, Discrete Math. 81 (1990), 129-135 (with F. R. K. Chung, A. Gyarfas, and Z. Tuza).
68. The number of depth-first searches of an ordered set, Order 6 (1989), 295-303 (with H. Kierstead).
67. An on-line graph coloring algorithm with sublinear performance ratio, Discrete Math. 75 (1989), 319-325 (with L. Lovasz and M. Saks).
66. Super-greedy linear extensions of ordered sets, in Combinatorial Mathematics , G. Bloom et al., eds., Annals of NY Acad. Sci. 555 (1989), 262- 271 (with H. Kierstead).
65. On-line partitioning of partially ordered sets, College Mathematics Journal 20 (1989), 124-131.
64. Problems and conjectures in the combinatorial theory of ordered sets, Annals of Discrete Math. 41 (1989), 401-416.
63. Threshold tolerance graphs, J. Graph Theory 12 (1988), 343-362 (with C. Monma, M. Saks, and B. Reed).
62. Explicit matchings in the middle two levels of a boolean algebra, Order 5 (1988), 163-171 (with H. Kierstead).
61. Interval graphs, interval orders, and their generalizations, in Applications of Discrete Mathematics , R. Ringeisen and F. Roberts, eds., SIAM, Philadelphia, PA (1988), 45-58.
60. Representing an ordered set as the intersection of super-greedy linear extensions, Order 4 (1987), 293-311 (with H. Kierstead and B. Zhou).
59. A note on ranking functions, Discrete Math. 67 (1987), 307-309 (with V. Rodl).
58. Poset boxicity of graphs, Discrete Math. 64 (1987), 105-107 (with D. West).
57. Regressions and monotone chains II: The poset of integer intervals, Order 4 , (1987), 217-223 (with N. Alon and D. West).
56. Arithmetic progressions in partially ordered sets, Order 4 , (1987), 37-42 (with P. Winkler).
55. A ramsey-theoretic problem for finite ordered sets, Discrete Math. 63 (1987), 217-223 (with H. Kierstead).
54. A generalization of threshold graphs with tolerance, Congressus Numerantium 55 (1986) 187-197 (with C. Monma and B. Reed).
53. Inequalities for the greedy dimension of ordered sets, Order 2 (1985), 145-164 (with H. Kierstead).
52. Angle Orders, Order 1 (1985), 333-343 (with P. Fishburn).
51. Graphs and orders in ramsey theory and in dimension theory, in Graphs and Order , I. Rival, ed., Reidel (1985), 351-394 (with M. Paoli and J. Walker).
50. Tiling bounded open sets with squares that touch the boundary, in Discrete Geometry and Convexity , J. Malkevitch, ed., N.Y. Acad. Sci. (1985), 304-322.
49. The dimension of the cartesian product of partial orders, Discrete Math. 53 (1985), 255-263.
48. For t >= 3, every t-dimensional partial order can be embedded in a t+1- irreducible partial order, in Finite and Infinite Sets , A. Hajnal, L. Lovasz, and V. T. Sos, eds., Colloq. Math. Soc. J. Bolyal 37 (1984), 711-732 (with J. Ross).
47. The maximum number of edges in a strongly connected oriented graph without long directed paths, Congressus Numerantium 45 (1984), 19-25 (with M. Paoli).
46. Triangle-free graphs with restricted bandwidth, in Progress in Graph Theory, A. Bondy and R. Murty, eds., Academic Press (1984), 175-190 (with F. R. K. Chung).
45. The chromatic number of graphs with locally small chromatic number, Combinatorica 4 (1984), 183-185 (with H. Kierstead and E. Szemeredi).
44. Unit distances in the euclidean plane, in Graph Theory and Combinatorics, B. Bollobas, ed., Academic Press (1984), 293-303 (with J. Spencer and E. Szemeredi).
43. Tolerance graphs, Discrete Applied Math. 8 (1984), 157-170 (with C. Monma and M. Golumbic).
42. A theory of dimension for recursive ordered sets, Order 1 (1984), 67-82 (with H. Kierstead and G. McNulty).
41. Regressions and monotone chains: A ramsey-type extremal problem for partial orders, Combinatorica 4 (1984), 117-119 (with D. West, P. Schor and G. W. Peck).
40. A sperner theorem on unrelated chains of subsets, J. Comb. Theory A 36 (1984), 124-127 (with J. Griggs and J. Stahl).
39. The interval number of a complete multipartite graph, Discrete Applied Math. 18 (1984), 163--189 (with L. Hopkins and D. West).
38. Extremal problems in discrete geometry, Combinatorica 3 (1983), 381-392 (with E. Szemeredi).
37. A combinatorial distinction between the euclidean and projective planes, European J. of Comb. 4 (1983), 385-394 (with E. Szemeredi).
36. Recent progress in problems in discrete geometry, in Graphs and Other Combinatorial Topics, Tuebner-Texte Zur Mathematik 59 (1983), 316-319 (with E. Szemeredi).
35. Graphs and Partially Ordered Sets, in Selected Topics in Graph Theory II, R. Wilson and L. Beineke, eds., Academic Press (1983), 237-268.
34. On determinism versus non-determinism and related problems, in Proceedings of the 24th Annual Symposium on Foundations of Computer Science (1983), 429- 438 (with W. Paul, N.Pippenger and E. Szemeredi).
33. The Ramsey number of a graph with bounded maximum degree, J. of Comb. Theory B 34 (1983), 239-243 (with V. Chvatal, V. Rodl), and E.Szemeredi).
32. Every t-irreducible partial order is a subposet of a t+1-irreducible partial order, Annals of Discrete Math. 17 (1983), 613-621 (with J.Ross).
31. Dimension theory for ordered sets, in Proceedings of the Symposium on Ordered Sets, I. Rival et al., eds., Reidel Publishing (1982), 171-212 (with D. Kelly).
30. A combinatorial problem involving graphs and matrices, Discrete Math. 39 (1982), 87-101 (with T. Monroe).
29. An extremal problem in recursive combinatorics, Congressus Numerantium 33 (1981), 143-153 (with H. Kierstead).
28. Stacks and splits of partially ordered sets, Discrete Math. 35 (1981), 220-256.
27. A bound on the interval number of a complete multipartite graph, in The Theory and Applications of Graphs, G. Chartrand et al., eds., Wiley Interscience (1981), 397-407 (with L. Hopkins).
26. Partially ordered sets with equal rank and dimension, Congressus Numerantium 29 (1980), 627-637 (with S. Maurer and I. Rabinovitch).
25. A generalization of Turan's theorem to directed graphs, Discrete Math. 32 (1980), 167-189 (with S. Maurer and I. Rabinovitch).
24. Large minimal realizers of a partial order II, Discrete Math. 31 (1980), 297-314 (with S. Maurer and I.Rabinovitch).
23. A forbidden subgraph characterization of Roberts' inequality for boxicity, Discrete Math. 28 (1979), 303-313.
22. On double and multiple interval graphs, J. Graph Theory 3} (1979), 205-211 (with F. Harary).
21. When the cartesian product of directed cycles is hamiltonian, J. Graph Theory 2 (1979), 137-142 (with P. Erdos).
20. Some combinatorial problems for permutations, Congressus Numerantium 19 (1978), 619-632.
19. Combinatorial problems in dimension theory for partially ordered sets, in Problemes Combinatoires et Theorie des Graphes, Colloque Internationeaux C.N.R.S. 260 (1978), 403-406.
18. Order preserving embeddings of aographs, in Theory and Applications of Graphs, Springer-Verlag Vol. 642 (1978), 572-579.
17. The dimension of a comparability graph, Proc. Amer. Math. Soc. 60 (1976), 35-38 (with J. Moore and D. Sumner).
16. On the complexity of posets, Discrete Math. 16 (1976), 71-82 (with K. Bogart).
15. Maximal dimensional partially ordered sets III: A characterization of Hiraguchi's inequality for interval dimension, Discrete Math. 15 (1976), 389-400 (with K. Bogart).
14. Characterization problems for graphs, partially ordered sets, lattices, and families of sets, Discrete Math. 16 (1976), 361-381 (with J. Moore).
13. Some theorems on graphs and posets, Discrete Math. 15 (1976), 79-84 (with J. Moore).
12. The dimension of planar posets, J. Comb. Theory B 21 (1977), 51-67 (with J. Moore).
11. A generalization of Hiraguchi's inequality for posets, J. Comb. Theory A 20 (1976), 114-123.
10. A forbidden subposet characterization of an order dimension inequality, Math. Systems Theory 10 (1976), 91-96.
9. A bound on the dimension of interval orders, J. Comb. Theory A 21 (1976), 319-238 (with K.Bogart and I. Rabinovitch).
8. A note on Dilworth's embedding theorem, Proc. Amer. Math. Soc. 52 (1975), 33-39.
7. Embedding finite posets in cubes, Discrete Math. 12 (1975), 165-172.
6. Irreducible posets with arbitrarily large height exist, J. Comb. Theory A 17 (1974), 337-344.
5. Inequalities in dimension theory for posets, Proc. Amer. Math. Soc. 47 (1975), 311-316.
4. Dimension of the crown S_n^k, Discrete Math. 8 (1974), 85-103.
3. Maximal dimensional partially ordered sets II, Discrete Math. 5 (1973), 33-44 (with K. Bogart).
2. A decomposition theorem for collections of universal subcontinua, Colloq. Math. 23 (1971), 233-239.
1. Characterization of the finite partition property for a collection of universal subcontinua, Proc. Amer. Math. Soc. 25 (1970), 760-762.

Updated January 28, 2018.