Better bounds for poset dimension and boxicity
HTML articles powered by AMS MathViewer
- by Alex Scott and David R. Wood PDF
- Trans. Amer. Math. Soc. 373 (2020), 2157-2172 Request permission
Abstract:
The dimension of a poset $P$ is the minimum number of total orders whose intersection is $P$. We prove that the dimension of every poset whose comparability graph has maximum degree $\Delta$ is at most $\Delta \log ^{1+o(1)} \Delta$. This result improves on a 30-year old bound of Füredi and Kahn and is within a $\log ^{o(1)}\Delta$ factor of optimal. We prove this result via the notion of boxicity. The boxicity of a graph $G$ is the minimum integer $d$ such that $G$ is the intersection graph of $d$-dimensional axis-aligned boxes. We prove that every graph with maximum degree $\Delta$ has boxicity at most $\Delta \log ^{1+o(1)} \Delta$, which is also within a $\log ^{o(1)}\Delta$ factor of optimal. We also show that the maximum boxicity of graphs with Euler genus $g$ is $\Theta (\sqrt {g \log g})$, which solves an open problem of Esperet and Joret and is tight up to a constant factor.References
- Abhijin Adiga, Diptendu Bhowmick, and L. Sunil Chandran, Boxicity and poset dimension, SIAM J. Discrete Math. 25 (2011), no. 4, 1687–1698. MR 2873210, DOI 10.1137/100786290
- Abhijin Adiga and L. Sunil Chandran, Representing a cubic graph as the intersection graph of axis-parallel boxes in three dimensions, SIAM J. Discrete Math. 28 (2014), no. 3, 1515–1539. MR 3262593, DOI 10.1137/120861795
- Abhijin Adiga, L. Sunil Chandran, and Rogers Mathew, Cubicity, degeneracy, and crossing number, European J. Combin. 35 (2014), 2–12. MR 3090481, DOI 10.1016/j.ejc.2013.06.021
- E. Asplund and B. Grünbaum, On a coloring problem, Math. Scand. 8 (1960), 181–188. MR 144334, DOI 10.7146/math.scand.a-10607
- Michael J. Bannister, William E. Devanny, Vida Dujmović, David Eppstein, and David R. Wood, Track layouts, layered path decompositions, and leveled planarity, Algorithmica 81 (2019), no. 4, 1561–1583. MR 3936168, DOI 10.1007/s00453-018-0487-5
- Hans L. Bodlaender, A partial $k$-arboretum of graphs with bounded treewidth, Theoret. Comput. Sci. 209 (1998), no. 1-2, 1–45. MR 1647486, DOI 10.1016/S0304-3975(97)00228-4
- James Perkins Burling, On coloring problems of families of polytopes, Ph.D. thesis, University of Colorado, 1965.
- Justin H. C. Chan and Jonathan Jedwab, Constructions and nonexistence results for suitable sets of permutations, J. Combin. Theory Ser. A 148 (2017), 183–196. MR 3603319, DOI 10.1016/j.jcta.2016.12.006
- L. Sunil Chandran, Mathew C. Francis, and Naveen Sivadasan, Boxicity and maximum degree, J. Combin. Theory Ser. B 98 (2008), no. 2, 443–445. MR 2389609, DOI 10.1016/j.jctb.2007.08.002
- L. Sunil Chandran and Naveen Sivadasan, Boxicity and treewidth, J. Combin. Theory Ser. B 97 (2007), no. 5, 733–744. MR 2344136, DOI 10.1016/j.jctb.2006.12.004
- Zhi-Zhong Chen, New bounds on the edge number of a $k$-map graph, J. Graph Theory 55 (2007), no. 4, 267–290. MR 2336801, DOI 10.1002/jgt.20237
- Zhi-Zhong Chen, Michelangelo Grigni, and Christos H. Papadimitriou, Map graphs, J. ACM 49 (2002), no. 2, 127–138. MR 2147819, DOI 10.1145/506147.506148
- Charles J. Colbourn, Suitable permutations, binary covering arrays, and Paley matrices, Algebraic design theory and Hadamard matrices, Springer Proc. Math. Stat., vol. 133, Springer, Cham, 2015, pp. 29–42. MR 3440525, DOI 10.1007/978-3-319-17729-8_{3}
- Vida Dujmović, David Eppstein, and David R. Wood, Structure of graphs with locally restricted crossings, SIAM J. Discrete Math. 31 (2017), no. 2, 805–824. MR 3639571, DOI 10.1137/16M1062879
- Vida Dujmović, Pat Morin, and David R. Wood, Layered separators in minor-closed graph classes with applications, J. Combin. Theory Ser. B 127 (2017), 111–147. MR 3704658, DOI 10.1016/j.jctb.2017.05.006
- Ben Dushnik, Concerning a certain set of arrangements, Proc. Amer. Math. Soc. 1 (1950), 788–796. MR 38922, DOI 10.1090/S0002-9939-1950-0038922-4
- P. Erdős, H. A. Kierstead, and W. T. Trotter, The dimension of random ordered sets, Random Structures Algorithms 2 (1991), no. 3, 253–275. MR 1109694, DOI 10.1002/rsa.3240020302
- P. Erdős and L. Lovász, Problems and results on $3$-chromatic hypergraphs and some related questions, Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erdős on his 60th birthday), Vol. II, Colloq. Math. Soc. János Bolyai, Vol. 10, North-Holland, Amsterdam, 1975, pp. 609–627. MR 0382050
- Louis Esperet, Boxicity of graphs with bounded degree, European J. Combin. 30 (2009), no. 5, 1277–1280. MR 2514650, DOI 10.1016/j.ejc.2008.10.003
- Louis Esperet, Boxicity and topological invariants, European J. Combin. 51 (2016), 495–499. MR 3398874, DOI 10.1016/j.ejc.2015.07.020
- Louis Esperet, Box representations of embedded graphs, Discrete Comput. Geom. 57 (2017), no. 3, 590–606. MR 3614774, DOI 10.1007/s00454-016-9837-8
- Louis Esperet and Gwenaël Joret, Boxicity of graphs on surfaces, Graphs Combin. 29 (2013), no. 3, 417–427. MR 3053591, DOI 10.1007/s00373-012-1130-x
- Louis Esperet and Veit Wiechert, Boxicity, poset dimension, and excluded minors, Electron. J. Combin. 25 (2018), no. 4, Paper No. 4.51, 11. MR 3907782, DOI 10.37236/7787
- Stefan Felsner and Mathew C. Francis, Contact representations of planar graphs with cubes, Computational geometry (SCG’11), ACM, New York, 2011, pp. 315–320. MR 2919622, DOI 10.1145/1998196.1998250
- Z. Füredi and J. Kahn, On the dimensions of ordered sets of bounded degree, Order 3 (1986), no. 1, 15–20. MR 850394, DOI 10.1007/BF00403406
- Daniel J. Harvey and David R. Wood, Parameters tied to treewidth, J. Graph Theory 84 (2017), no. 4, 364–385. MR 3623383, DOI 10.1002/jgt.22030
- Hugh Hind, Michael Molloy, and Bruce Reed, Colouring a graph frugally, Combinatorica 17 (1997), no. 4, 469–482. MR 1645682, DOI 10.1007/BF01195001
- Gwenaël Joret, Piotr Micek, Patrice Ossona de Mendez, and Veit Wiechert, Nowhere dense graph classes and dimension, arXiv:1708.05424, 2017. To appear in Combinatorica.
- Gwenaël Joret, Piotr Micek, Kevin G. Milans, William T. Trotter, Bartosz Walczak, and Ruidong Wang, Tree-width and dimension, Combinatorica 36 (2016), no. 4, 431–450. MR 3537035, DOI 10.1007/s00493-014-3081-8
- Gwenaël Joret, Piotr Micek, William T. Trotter, Ruidong Wang, and Veit Wiechert, On the dimension of posets with cover graphs of treewidth 2, Order 34 (2017), no. 2, 185–234. MR 3669250, DOI 10.1007/s11083-016-9395-y
- Gwenaël Joret, Piotr Micek, and Veit Wiechert, Planar posets have dimension at most linear in their height, SIAM J. Discrete Math. 31 (2017), no. 4, 2754–2790. MR 3738844, DOI 10.1137/17M111300X
- Gwenaël Joret, Piotr Micek, and Veit Wiechert, Sparsity and dimension, Combinatorica 38 (2018), no. 5, 1129–1148. MR 3884782, DOI 10.1007/s00493-017-3638-4
- H. A. Kierstead, On the order dimension of $1$-sets versus $k$-sets, J. Combin. Theory Ser. A 73 (1996), no. 2, 219–228. MR 1370130
- Stephen G. Kobourov, Giuseppe Liotta, and Fabrizio Montecchiani, An annotated bibliography on 1-planarity, Comput. Sci. Rev. 25 (2017), 49–67. MR 3697129, DOI 10.1016/j.cosrev.2017.06.002
- Piotr Micek and Veit Wiechert, Topological minors of cover graphs and dimension, J. Graph Theory 86 (2017), no. 3, 295–314. MR 3697925, DOI 10.1002/jgt.22127
- János Pach and Géza Tóth, Graphs drawn with few crossings per edge, Combinatorica 17 (1997), no. 3, 427–439. MR 1606052, DOI 10.1007/BF01215922
- B. A. Reed, Tree width and tangles: a new connectivity measure and some applications, Surveys in combinatorics, 1997 (London), London Math. Soc. Lecture Note Ser., vol. 241, Cambridge Univ. Press, Cambridge, 1997, pp. 87–162. MR 1477746, DOI 10.1017/CBO9780511662119.006
- Fred S. Roberts, On the boxicity and cubicity of a graph, Recent Progress in Combinatorics (Proc. Third Waterloo Conf. on Combinatorics, 1968) Academic Press, New York, 1969, pp. 301–310. MR 0252268
- Marcus Schaefer, The graph crossing number and its variants: A survey, Electron. J. Combin., #DS21, 2017. https://www.combinatorics.org/DS21
- Edward R. Scheinerman, INTERSECTION CLASSES AND MULTIPLE INTERSECTION PARAMETERS OF GRAPHS, ProQuest LLC, Ann Arbor, MI, 1984. Thesis (Ph.D.)–Princeton University. MR 2633485
- J. Spencer, Minimal scrambling sets of simple orders, Acta Math. Acad. Sci. Hungar. 22 (1971/72), 349–353. MR 292722, DOI 10.1007/BF01896428
- Noah Streib and William T. Trotter, Dimension and height for posets with planar cover graphs, European J. Combin. 35 (2014), 474–489. MR 3090518, DOI 10.1016/j.ejc.2013.06.017
- Carsten Thomassen, Interval representations of planar graphs, J. Combin. Theory Ser. B 40 (1986), no. 1, 9–20. MR 830590, DOI 10.1016/0095-8956(86)90061-4
- William T. Trotter, Combinatorics and partially ordered sets, Johns Hopkins Series in the Mathematical Sciences, Johns Hopkins University Press, Baltimore, MD, 1992. Dimension theory. MR 1169299
- William T. Trotter, Graphs and partially ordered sets: recent results and new directions, Congr. Numer. 116 (1996), 253–278. Surveys in graph theory (San Francisco, CA, 1995). MR 1411256
- William T. Trotter Jr., A characterization of Roberts’ inequality for boxicity, Discrete Math. 28 (1979), no. 3, 303–313. MR 548629, DOI 10.1016/0012-365X(79)90137-7
- Bartosz Walczak, Minors and dimension, J. Combin. Theory Ser. B 122 (2017), 668–689. MR 3575223, DOI 10.1016/j.jctb.2016.09.001
- Ruidong Wang, Combinatorial problems for graphs and partially ordered sets, Ph.D. thesis, Georgia Tech, 2015. http://hdl.handle.net/1853/54483
Additional Information
- Alex Scott
- Affiliation: Mathematical Institute, University of Oxford, Oxford OX2 6GG, United Kingdom
- MR Author ID: 334830
- Email: scott@maths.ox.ac.uk
- David R. Wood
- Affiliation: School of Mathematics, Monash University, Melbourne, Australia
- MR Author ID: 635262
- Email: david.wood@monash.edu
- Received by editor(s): June 17, 2018
- Received by editor(s) in revised form: August 8, 2019
- Published electronically: October 18, 2019
- Additional Notes: The first author was supported by a Leverhulme Trust Research Fellowship
The second author was supported by the Australian Research Council - © Copyright 2019 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 373 (2020), 2157-2172
- MSC (2010): Primary 05C62, 06A07
- DOI: https://doi.org/10.1090/tran/7962
- MathSciNet review: 4068293