-
Weak coloring numbers of minor-closed graph classes
Authors:
Jędrzej Hodor,
Hoang La,
Piotr Micek,
Clément Rambaud
Abstract:
We study the growth rate of weak coloring numbers of graphs excluding a fixed graph as a minor. Van den Heuvel et al. (European J. of Combinatorics, 2017) showed that for a fixed graph $X$, the maximum $r$-th weak coloring number of $X$-minor-free graphs is polynomial in $r$. We determine this polynomial up to a factor of $\mathcal{O}(r \log r)$. Moreover, we tie the exponent of the polynomial to…
▽ More
We study the growth rate of weak coloring numbers of graphs excluding a fixed graph as a minor. Van den Heuvel et al. (European J. of Combinatorics, 2017) showed that for a fixed graph $X$, the maximum $r$-th weak coloring number of $X$-minor-free graphs is polynomial in $r$. We determine this polynomial up to a factor of $\mathcal{O}(r \log r)$. Moreover, we tie the exponent of the polynomial to a structural property of $X$, namely, $2$-treedepth. As a result, for a fixed graph $X$ and an $X$-minor-free graph $G$, we show that $\mathrm{wcol}_r(G)= \mathcal{O}(r^{\mathrm{td}(X)-1}\mathrm{log}\ r)$, which improves on the bound $\mathrm{wcol}_r(G) = \mathcal{O}(r^{g(\mathrm{td}(X))})$ given by Dujmović et al. (SODA, 2024), where $g$ is an exponential function. In the case of planar graphs of bounded treewidth, we show that the maximum $r$-th weak coloring number is in $\mathcal{O}(r^2\mathrm{log}\ r$), which is best possible.
△ Less
Submitted 5 July, 2024;
originally announced July 2024.
-
Quickly excluding an apex-forest
Authors:
Jędrzej Hodor,
Hoang La,
Piotr Micek,
Clément Rambaud
Abstract:
We give a short proof that for every apex-forest $X$ on at least two vertices, graphs excluding $X$ as a minor have layered pathwidth at most $2|V(X)|-3$. This improves upon a result by Dujmović, Eppstein, Joret, Morin, and Wood (SIDMA, 2020). Our main tool is a structural result about graphs excluding a forest as a rooted minor, which is of independent interest. We develop similar tools for treed…
▽ More
We give a short proof that for every apex-forest $X$ on at least two vertices, graphs excluding $X$ as a minor have layered pathwidth at most $2|V(X)|-3$. This improves upon a result by Dujmović, Eppstein, Joret, Morin, and Wood (SIDMA, 2020). Our main tool is a structural result about graphs excluding a forest as a rooted minor, which is of independent interest. We develop similar tools for treedepth and treewidth. We discuss implications for Erdős-Pósa properties of rooted models of minors in graphs.
△ Less
Submitted 26 April, 2024;
originally announced April 2024.
-
Treewidth is Polynomial in Maximum Degree on Graphs Excluding a Planar Induced Minor
Authors:
Édouard Bonnet,
Jędrzej Hodor,
Tuukka Korhonen,
Tomáš Masařík
Abstract:
A graph $G$ contains a graph $H$ as an induced minor if $H$ can be obtained from $G$ by vertex deletions and edge contractions. We show that for every $k$-vertex planar graph $H$, every graph $G$ excluding $H$ as an induced minor has treewidth at most $Δ(G)^{2^{O(k)}}$ where $Δ(G)$ denotes the maximum degree of $G$. Previously, Korhonen [JCTB '23] has shown the upper bound of…
▽ More
A graph $G$ contains a graph $H$ as an induced minor if $H$ can be obtained from $G$ by vertex deletions and edge contractions. We show that for every $k$-vertex planar graph $H$, every graph $G$ excluding $H$ as an induced minor has treewidth at most $Δ(G)^{2^{O(k)}}$ where $Δ(G)$ denotes the maximum degree of $G$. Previously, Korhonen [JCTB '23] has shown the upper bound of $k^{O(1)} 2^{Δ(G)^5}$ whose dependence in $Δ(G)$ is exponential. More precisely, we show that every graph $G$ excluding as induced minors a $k$-vertex planar graph and a $q$-vertex graph has treewidth at most $k^{O(1)} \cdot Δ(G)^{f(q)}$ with $f(q) = 2^{O(q)}$. A direct consequence of our result is that for every hereditary graph class $\mathcal C$, if graphs of $\mathcal C$ have treewidth bounded by a function of their maximum degree, then they in fact have treewidth polynomial in their maximum degree.
△ Less
Submitted 13 December, 2023;
originally announced December 2023.
-
Boolean dimension of a Boolean lattice
Authors:
Marcin Briański,
Jędrzej Hodor,
Hoang La,
Piotr Micek,
Katzper Michno
Abstract:
For every integer $n$ with $n \geq 6$, we prove that the Boolean dimension of a poset consisting of all the subsets of $\{1,\dots,n\}$ equipped with the inclusion relation is strictly less than $n$.
For every integer $n$ with $n \geq 6$, we prove that the Boolean dimension of a poset consisting of all the subsets of $\{1,\dots,n\}$ equipped with the inclusion relation is strictly less than $n$.
△ Less
Submitted 31 July, 2023;
originally announced July 2023.
-
The grid-minor theorem revisited
Authors:
Vida Dujmović,
Robert Hickingbotham,
Jędrzej Hodor,
Gweanël Joret,
Hoang La,
Piotr Micek,
Pat Morin,
Clément Rambaud,
David R. Wood
Abstract:
We prove that for every planar graph $X$ of treedepth $h$, there exists a positive integer $c$ such that for every $X$-minor-free graph $G$, there exists a graph $H$ of treewidth at most $f(h)$ such that $G$ is isomorphic to a subgraph of $H\boxtimes K_c$. This is a qualitative strengthening of the Grid-Minor Theorem of Robertson and Seymour (JCTB 1986), and treedepth is the optimal parameter in s…
▽ More
We prove that for every planar graph $X$ of treedepth $h$, there exists a positive integer $c$ such that for every $X$-minor-free graph $G$, there exists a graph $H$ of treewidth at most $f(h)$ such that $G$ is isomorphic to a subgraph of $H\boxtimes K_c$. This is a qualitative strengthening of the Grid-Minor Theorem of Robertson and Seymour (JCTB 1986), and treedepth is the optimal parameter in such a result. As an example application, we use this result to improve the upper bound for weak coloring numbers of graphs excluding a fixed graph as a minor.
△ Less
Submitted 6 July, 2023;
originally announced July 2023.
-
The depth of Tsirelson's norm
Authors:
Kevin Beanland,
Jędrzej Hodor
Abstract:
Tsirelson's norm $\|\cdot \|_T$ on $c_{00}$ is defined as the supremum over a certain collection of iteratively defined, monotone increasing norms $\|\cdot \|_k$. For each positive integer $n$, the value $j(n)$ is the least integer $k$ such that for all $x \in \mathbb{R}^n$ (here $\mathbb{R}^n$ is considered as a subspace of $c_{00}$), $\|x\|_T = \|x\|_k$. In 1989 Casazza and Shura asked what is t…
▽ More
Tsirelson's norm $\|\cdot \|_T$ on $c_{00}$ is defined as the supremum over a certain collection of iteratively defined, monotone increasing norms $\|\cdot \|_k$. For each positive integer $n$, the value $j(n)$ is the least integer $k$ such that for all $x \in \mathbb{R}^n$ (here $\mathbb{R}^n$ is considered as a subspace of $c_{00}$), $\|x\|_T = \|x\|_k$. In 1989 Casazza and Shura asked what is the order of magnitude of $j(n)$. It is known that $j(n) \in \mathcal{O}(\sqrt{n})$. We show that this bound is tight, that is, $j(n) \in Ω(\sqrt{n})$. Moreover, we compute the tight order of magnitude for some norms being modifications of the original Tsirelson's norm.
△ Less
Submitted 17 June, 2023;
originally announced June 2023.
-
Forcing the Wheel
Authors:
Jędrzej Hodor,
William T. Trotter
Abstract:
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 diagrams, especially with the concepts of planarity and treewidth. Joret and Micek conjectured that if $P$ is a poset with a planar cover graph, then the dimension of $P$ is bounded in terms of the number of minimal elem…
▽ More
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 diagrams, especially with the concepts of planarity and treewidth. Joret and Micek conjectured that if $P$ is a poset with a planar cover graph, then the dimension of $P$ is bounded in terms of the number of minimal elements of $P$ and the treewidth of the cover graph of $P$. We settle this conjecture in the affirmative by strengthening a recent breakthrough result [14] by Blake, Micek, and Trotter, who proved that for each poset $P$ admitting a planar cover graph and a unique minimal element we have $\mathrm{dim}(P) \leq 2 \mathrm{se}(P) + 2$, namely, we prove that $\mathrm{dim}(P) \leq 2 \mathrm{wheel}(P) + 2$.
△ Less
Submitted 17 April, 2023;
originally announced April 2023.
-
Counting Unions of Schreier Sets
Authors:
Kevin Beanland,
Dmitriy Gorovoy,
Jȩdrzej Hodor,
Daniil Homza
Abstract:
A subset of positive integers $F$ is a Schreier set if it is non-empty and $|F|\leqslant \min F$ (here $|F|$ is the cardinality of $F$). For each positive integer $k$, we define $k\mathcal{S}$ as the collection of all the unions of at most $k$ Schreier sets. Also, for each positive integer $n$, let $(k\mathcal{S})^n$ be the collection of all sets in $k\mathcal{S}$ with the maximum element equal to…
▽ More
A subset of positive integers $F$ is a Schreier set if it is non-empty and $|F|\leqslant \min F$ (here $|F|$ is the cardinality of $F$). For each positive integer $k$, we define $k\mathcal{S}$ as the collection of all the unions of at most $k$ Schreier sets. Also, for each positive integer $n$, let $(k\mathcal{S})^n$ be the collection of all sets in $k\mathcal{S}$ with the maximum element equal to $n$. It is well-known that the sequence $(|(1\mathcal{S})^n|)_{n=1}^\infty$ is the Fibbonacci sequence. In particular, the sequence satisfies a linear recurrence. We generalize this statement, namely, we show that the sequence $(|(k\mathcal{S})^n|)_{n=1}^\infty$ satisfies a linear recurrence for every positive $k$.
△ Less
Submitted 25 August, 2023; v1 submitted 2 November, 2022;
originally announced November 2022.
-
Reconfiguring Independent Sets on Interval Graphs
Authors:
Marcin Briański,
Stefan Felsner,
Jędrzej Hodor,
Piotr Micek
Abstract:
We study reconfiguration of independent sets in interval graphs under the token sliding rule. We show that if two independent sets of size $k$ are reconfigurable in an $n$-vertex interval graph, then there is a reconfiguration sequence of length $\mathcal{O}(k\cdot n^2)$. We also provide a construction in which the shortest reconfiguration sequence is of length $Ω(k^2\cdot n)$.
As a counterpart…
▽ More
We study reconfiguration of independent sets in interval graphs under the token sliding rule. We show that if two independent sets of size $k$ are reconfigurable in an $n$-vertex interval graph, then there is a reconfiguration sequence of length $\mathcal{O}(k\cdot n^2)$. We also provide a construction in which the shortest reconfiguration sequence is of length $Ω(k^2\cdot n)$.
As a counterpart to these results, we also establish that $\textsf{Independent Set Reconfiguration}$ is PSPACE-hard on incomparability graphs, of which interval graphs are a special case.
△ Less
Submitted 7 May, 2021;
originally announced May 2021.
