Posets with cover graph of pathwidth two have bounded dimension (Q304175): Difference between revisions
From MaRDI portal
Created a new Item |
Changed an Item |
||
Property / review text | |||
The dimension of an ordered set \(P\) with order relation \(\leq \) is the smallest number of total orders whose intersection is the order \(\leq \). Let \(G=(V,E)\) be a graph, let \(T\) be a tree and let \({\mathcal V} =(V_t )_{t\in T}\) be a family of subsets \(V_t \subseteq V\) indexed by the tree \(T\). Then \((T,{\mathcal V}) \) is called a tree-decomposition of \(G\) iff \(V=\bigcup _{t\in T} V_t \), every edge of \(G\) is a subset of a set \(V_t \), and, if \(t_1\), \(t_2\), \(t_3 \) are vertices of \(T\) such that \(t_2 \) lies on the unique path from \(t_1 \) to \(t_3 \) in \(T\), then \(V_{t_1 } \cap V_{t_3} \subseteq V_{t_2} \). The width of a tree decomposition is \(\max _{t\in T} |V_t |-1\). The treewidth \(\mathrm{tw}(G)\) is the smallest width of a tree-decomposition of \(G\). A path-decomposition is a tree-decomposition in which \(T\) is a path and the pathwidth of a graph is the smallest width of a path-decomposition of \(G\). It has been long known that, if \(P\) is a connected ordered set whose cover graph has treewidth \(1\) (that is, it is a tree), then its dimension is at most \(3\). Moreover, there are ordered sets of arbitrarily high dimension whose cover graph has pathwidth \(3\), which leaves path- and treewidth \(2\) as the last cases to consider. The authors show that the dimension of an ordered set whose cover graph has pathwidth at most \(2\) is at most \(17\). They also note that the cover graph of any ordered set that contains the standard example \(S_5 \) has treewidth at least \(3\) and that it has been proved in [\textit{G. Joret} et al., ``On the dimension of posets with cover graphs of treewidth 2'', Order (to appear), \url{doi:10.1007/s11083-016-9395-y}] that the dimension of an ordered set whose cover graph has treewidth at most \(2\) is at most \(1276\). | |||
Property / review text: The dimension of an ordered set \(P\) with order relation \(\leq \) is the smallest number of total orders whose intersection is the order \(\leq \). Let \(G=(V,E)\) be a graph, let \(T\) be a tree and let \({\mathcal V} =(V_t )_{t\in T}\) be a family of subsets \(V_t \subseteq V\) indexed by the tree \(T\). Then \((T,{\mathcal V}) \) is called a tree-decomposition of \(G\) iff \(V=\bigcup _{t\in T} V_t \), every edge of \(G\) is a subset of a set \(V_t \), and, if \(t_1\), \(t_2\), \(t_3 \) are vertices of \(T\) such that \(t_2 \) lies on the unique path from \(t_1 \) to \(t_3 \) in \(T\), then \(V_{t_1 } \cap V_{t_3} \subseteq V_{t_2} \). The width of a tree decomposition is \(\max _{t\in T} |V_t |-1\). The treewidth \(\mathrm{tw}(G)\) is the smallest width of a tree-decomposition of \(G\). A path-decomposition is a tree-decomposition in which \(T\) is a path and the pathwidth of a graph is the smallest width of a path-decomposition of \(G\). It has been long known that, if \(P\) is a connected ordered set whose cover graph has treewidth \(1\) (that is, it is a tree), then its dimension is at most \(3\). Moreover, there are ordered sets of arbitrarily high dimension whose cover graph has pathwidth \(3\), which leaves path- and treewidth \(2\) as the last cases to consider. The authors show that the dimension of an ordered set whose cover graph has pathwidth at most \(2\) is at most \(17\). They also note that the cover graph of any ordered set that contains the standard example \(S_5 \) has treewidth at least \(3\) and that it has been proved in [\textit{G. Joret} et al., ``On the dimension of posets with cover graphs of treewidth 2'', Order (to appear), \url{doi:10.1007/s11083-016-9395-y}] that the dimension of an ordered set whose cover graph has treewidth at most \(2\) is at most \(1276\). / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Bernd S. W. Schröder / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 06A07 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 05C25 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 6619132 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
poset | |||
Property / zbMATH Keywords: poset / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
pathwidth | |||
Property / zbMATH Keywords: pathwidth / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
cover graph | |||
Property / zbMATH Keywords: cover graph / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
dimension | |||
Property / zbMATH Keywords: dimension / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
treewidth | |||
Property / zbMATH Keywords: treewidth / rank | |||
Normal rank |
Revision as of 23:37, 27 June 2023
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Posets with cover graph of pathwidth two have bounded dimension |
scientific article |
Statements
Posets with cover graph of pathwidth two have bounded dimension (English)
0 references
24 August 2016
0 references
The dimension of an ordered set \(P\) with order relation \(\leq \) is the smallest number of total orders whose intersection is the order \(\leq \). Let \(G=(V,E)\) be a graph, let \(T\) be a tree and let \({\mathcal V} =(V_t )_{t\in T}\) be a family of subsets \(V_t \subseteq V\) indexed by the tree \(T\). Then \((T,{\mathcal V}) \) is called a tree-decomposition of \(G\) iff \(V=\bigcup _{t\in T} V_t \), every edge of \(G\) is a subset of a set \(V_t \), and, if \(t_1\), \(t_2\), \(t_3 \) are vertices of \(T\) such that \(t_2 \) lies on the unique path from \(t_1 \) to \(t_3 \) in \(T\), then \(V_{t_1 } \cap V_{t_3} \subseteq V_{t_2} \). The width of a tree decomposition is \(\max _{t\in T} |V_t |-1\). The treewidth \(\mathrm{tw}(G)\) is the smallest width of a tree-decomposition of \(G\). A path-decomposition is a tree-decomposition in which \(T\) is a path and the pathwidth of a graph is the smallest width of a path-decomposition of \(G\). It has been long known that, if \(P\) is a connected ordered set whose cover graph has treewidth \(1\) (that is, it is a tree), then its dimension is at most \(3\). Moreover, there are ordered sets of arbitrarily high dimension whose cover graph has pathwidth \(3\), which leaves path- and treewidth \(2\) as the last cases to consider. The authors show that the dimension of an ordered set whose cover graph has pathwidth at most \(2\) is at most \(17\). They also note that the cover graph of any ordered set that contains the standard example \(S_5 \) has treewidth at least \(3\) and that it has been proved in [\textit{G. Joret} et al., ``On the dimension of posets with cover graphs of treewidth 2'', Order (to appear), \url{doi:10.1007/s11083-016-9395-y}] that the dimension of an ordered set whose cover graph has treewidth at most \(2\) is at most \(1276\).
0 references
poset
0 references
pathwidth
0 references
cover graph
0 references
dimension
0 references
treewidth
0 references