• ### Assortment optimisation under a general discrete choice model: A tight analysis of revenue-ordered assortments(1606.01371)

Feb. 21, 2019 cs.DS, math.OC
The assortment problem in revenue management is the problem of deciding which subset of products to offer to consumers in order to maximise revenue. A simple and natural strategy is to select the best assortment out of all those that are constructed by fixing a threshold revenue $\pi$ and then choosing all products with revenue at least $\pi$. This is known as the revenue-ordered assortments strategy. In this paper we study the approximation guarantees provided by revenue-ordered assortments when customers are rational in the following sense: the probability of selecting a specific product from the set being offered cannot increase if the set is enlarged. This rationality assumption, known as regularity, is satisfied by almost all discrete choice models considered in the revenue management and choice theory literature, and in particular by random utility models. The bounds we obtain are tight and improve on recent results in that direction, such as for the Mixed Multinomial Logit model by Rusmevichientong et al. (2014). An appealing feature of our analysis is its simplicity, as it relies only on the regularity condition. We also draw a connection between assortment optimisation and two pricing problems called unit demand envy-free pricing and Stackelberg minimum spanning tree: These problems can be restated as assortment problems under discrete choice models satisfying the regularity condition, and moreover revenue-ordered assortments correspond then to the well-studied uniform pricing heuristic. When specialised to that setting, the general bounds we establish for revenue-ordered assortments match and unify the best known results on uniform pricing.
• ### Nowhere Dense Graph Classes and Dimension(1708.05424)

Jan. 31, 2019 math.CO, cs.DM
Nowhere dense graph classes provide one of the least restrictive notions of sparsity for graphs. Several equivalent characterizations of nowhere dense classes have been obtained over the years, using a wide range of combinatorial objects. In this paper we establish a new characterization of nowhere dense classes, in terms of poset dimension: A monotone graph class is nowhere dense if and only if for every $h \geq 1$ and every $\epsilon > 0$, posets of height at most $h$ with $n$ elements and whose cover graphs are in the class have dimension $\mathcal{O}(n^{\epsilon})$.
• ### A tight Erd\H{o}s-P\'osa function for wheel minors(1710.06282)

July 5, 2018 math.CO, cs.DM
Let $W_t$ denote the wheel on $t+1$ vertices. We prove that for every integer $t \geq 3$ there is a constant $c=c(t)$ such that for every integer $k\geq 1$ and every graph $G$, either $G$ has $k$ vertex-disjoint subgraphs each containing $W_t$ as minor, or there is a subset $X$ of at most $c k \log k$ vertices such that $G-X$ has no $W_t$ minor. This is best possible, up to the value of $c$. We conjecture that the result remains true more generally if we replace $W_t$ with any fixed planar graph $H$.
• ### Progress on the adjacent vertex distinguishing edge colouring conjecture(1804.06104)

April 17, 2018 math.CO, cs.DM
A proper edge colouring of a graph is adjacent vertex distinguishing if no two adjacent vertices see the same set of colours. Using a clever application of the Local Lemma, Hatami (2005) proved that every graph with maximum degree $\Delta$ and no isolated edge has an adjacent vertex distinguishing edge colouring with $\Delta + 300$ colours, provided $\Delta$ is large enough. We show that this bound can be reduced to $\Delta + 19$. This is motivated by the conjecture of Zhang, Liu, and Wang (2002) that $\Delta + 2$ colours are enough for $\Delta \geq 3$.
• ### Seymour's conjecture on 2-connected graphs of large pathwidth(1801.01833)

Feb. 14, 2018 math.CO, cs.DM
We prove the conjecture of Seymour (1993) that for every apex-forest $H_1$ and outerplanar graph $H_2$ there is an integer $p$ such that every 2-connected graph of pathwidth at least $p$ contains $H_1$ or $H_2$ as a minor. An independent proof was recently obtained by Dang and Thomas.
• ### Burling graphs, chromatic number, and orthogonal tree-decompositions(1703.07871)

Jan. 29, 2018 math.CO
A classic result of Asplund and Gr\"unbaum states that intersection graphs of axis-aligned rectangles in the plane are $\chi$-bounded. This theorem can be equivalently stated in terms of path-decompositions as follows: There exists a function $f:\mathbb{N}\to\mathbb{N}$ such that every graph that has two path-decompositions such that each bag of the first decomposition intersects each bag of the second in at most $k$ vertices has chromatic number at most $f(k)$. Recently, Dujmovi\'c, Joret, Morin, Norin, and Wood asked whether this remains true more generally for two tree-decompositions. In this note we provide a negative answer: There are graphs with arbitrarily large chromatic number for which one can find two tree-decompositions such that each bag of the first decomposition intersects each bag of the second in at most two vertices. Furthermore, this remains true even if one of the two decompositions is restricted to be a path-decomposition. This is shown using a construction of triangle-free graphs with unbounded chromatic number due to Burling, which we believe should be more widely known.
• ### Orthogonal Tree Decompositions of Graphs(1701.05639)

Oct. 25, 2017 math.CO
This paper studies graphs that have two tree decompositions with the property that every bag from the first decomposition has a bounded-size intersection with every bag from the second decomposition. We show that every graph in each of the following classes has a tree decomposition and a linear-sized path decomposition with bounded intersections: (1) every proper minor-closed class, (2) string graphs with a linear number of crossings in a fixed surface, (3) graphs with linear crossing number in a fixed surface. Here `linear size' means that the total size of the bags in the path decomposition is $O(n)$ for $n$-vertex graphs. We then show that every $n$-vertex graph that has a tree decomposition and a linear-sized path decomposition with bounded intersections has $O(\sqrt{n})$ treewidth. As a corollary, we conclude a new lower bound on the crossing number of a graph in terms of its treewidth. Finally, we consider graph classes that have two path decompositions with bounded intersections. Trees and outerplanar graphs have this property. But for the next most simple class, series parallel graphs, we show that no such result holds.
• ### Planar posets have dimension at most linear in their height(1612.07540)

Sept. 23, 2017 math.CO, cs.DM
We prove that every planar poset $P$ of height $h$ has dimension at most $192h + 96$. This improves on previous exponential bounds and is best possible up to a constant factor. We complement this result with a construction of planar posets of height $h$ and dimension at least $(4/3)h-2$.
• ### Smaller Extended Formulations for the Spanning Tree Polytope of Bounded-genus Graphs(1604.07976)

Jan. 9, 2017 math.CO, cs.DM
We give an $O(g^{1/2} n^{3/2} + g^{3/2} n^{1/2})$-size extended formulation for the spanning tree polytope of an $n$-vertex graph embedded on a surface of genus $g$, improving on the known $O(n^2 + g n)$-size extended formulations following from Wong and Martin.
• ### Sparsity and dimension(1507.01120)

Jan. 9, 2017 math.CO, cs.DM
We prove that posets of bounded height whose cover graphs belong to a fixed class with bounded expansion have bounded dimension. Bounded expansion, introduced by Ne\v{s}et\v{r}il and Ossona de Mendez as a model for sparsity in graphs, is a property that is naturally satisfied by a wide range of graph classes, from graph structure theory (graphs excluding a minor or a topological minor) to graph drawing (e.g. graphs with bounded book thickness). Therefore, our theorem generalizes a number of results including the most recent one for posets of bounded height with cover graphs excluding a fixed graph as a topological minor. We also show that the result is in a sense best possible, as it does not extend to nowhere dense classes; in fact, it already fails for cover graphs with locally bounded treewidth.
• ### Pathwidth and nonrepetitive list coloring(1601.01886)

Oct. 2, 2016 math.CO, cs.DM
A vertex coloring of a graph is nonrepetitive if there is no path in the graph whose first half receives the same sequence of colors as the second half. While every tree can be nonrepetitively colored with a bounded number of colors (4 colors is enough), Fiorenzi, Ochem, Ossona de Mendez, and Zhu recently showed that this does not extend to the list version of the problem, that is, for every $\ell \geq 1$ there is a tree that is not nonrepetitively $\ell$-choosable. In this paper we prove the following positive result, which complements the result of Fiorenzi et al.: There exists a function $f$ such that every tree of pathwidth $k$ is nonrepetitively $f(k)$-choosable. We also show that such a property is specific to trees by constructing a family of pathwidth-2 graphs that are not nonrepetitively $\ell$-choosable for any fixed $\ell$.
• ### The excluded minors for isometric realizability in the plane(1511.08054)

Sept. 16, 2016 math.CO, math.MG, cs.DM
Let $G$ be a graph and $p \in [1, \infty]$. The parameter $f_p(G)$ is the least integer $k$ such that for all $m$ and all vectors $(r_v)_{v \in V(G)} \subseteq \mathbb{R}^m$, there exist vectors $(q_v)_{v \in V(G)} \subseteq \mathbb{R}^k$ satisfying $$\|r_v-r_w\|_p=\|q_v-q_w\|_p, \ \text{ for all }\ vw\in E(G).$$ It is easy to check that $f_p(G)$ is always finite and that it is minor monotone. By the graph minor theorem of Robertson and Seymour, there are a finite number of excluded minors for the property $f_p(G) \leq k$. In this paper, we determine the complete set of excluded minors for $f_\infty(G) \leq 2$. The two excluded minors are the wheel on $5$ vertices and the graph obtained by gluing two copies of $K_4$ along an edge and then deleting that edge. We also show that the same two graphs are the complete set of excluded minors for $f_1(G) \leq 2$. In addition, we give a family of examples that show that $f_\infty$ is unbounded on the class of planar graphs and $f_\infty$ is not bounded as a function of tree-width.
• ### $K_{4}$-Minor-Free Induced Subgraphs of Sparse Connected Graphs(1605.04730)

May 17, 2016 math.CO, cs.DM
We prove that every connected graph $G$ with $m$ edges contains a set $X$ of at most $\frac{3}{16}(m + 1)$ vertices such that $G-X$ has no $K_4$ minor, or equivalently, has treewidth at most $2$. This bound is best possible. Connectivity is essential: If $G$ is not connected then only a bound of $\frac{1}{5}m$ can be guaranteed.
• ### On the dimension of posets with cover graphs of treewidth $2$(1406.3397)

May 4, 2016 math.CO
In 1977, Trotter and Moore proved that a poset has dimension at most $3$ whenever its cover graph is a forest, or equivalently, has treewidth at most $1$. On the other hand, a well-known construction of Kelly shows that there are posets of arbitrarily large dimension whose cover graphs have treewidth $3$. In this paper we focus on the boundary case of treewidth $2$. It was recently shown that the dimension is bounded if the cover graph is outerplanar (Felsner, Trotter, and Wiechert) or if it has pathwidth $2$ (Bir\'o, Keller, and Young). This can be interpreted as evidence that the dimension should be bounded more generally when the cover graph has treewidth $2$. We show that it is indeed the case: Every such poset has dimension at most $1276$.
• ### Reducing the rank of a matroid(1211.4853)

Sept. 5, 2015 cs.DM, cs.DS
We consider the rank reduction problem for matroids: Given a matroid M and an integer k, find a minimum size subset of elements of M whose removal reduces the rank of M by at least k. When M is a graphical matroid this problem is the minimum k-cut problem, which admits a 2-approximation algorithm. In this paper we show that the rank reduction problem for transversal matroids is essentially at least as hard to approximate as the densest k-subgraph problem. We also prove that, while the problem is easily solvable in polynomial time for partition matroids, it is NP-hard when considering the intersection of two partition matroids. Our proof shows, in particular, that the maximum vertex cover problem is NP-hard on bipartite graphs, which answers an open problem of B. Simeone.
• ### Tree-width and dimension(1301.5271)

Feb. 25, 2015 math.CO, cs.DM
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 graph theory parameter tree-width by proving that the dimension of a finite poset is bounded in terms of its height and the tree-width of its cover graph.
• ### Nonrepetitive Colouring via Entropy Compression(1112.5524)

June 13, 2014 math.CO, cs.DM
A vertex colouring of a graph is \emph{nonrepetitive} if there is no path whose first half receives the same sequence of colours as the second half. A graph is nonrepetitively $k$-choosable if given lists of at least $k$ colours at each vertex, there is a nonrepetitive colouring such that each vertex is coloured from its own list. It is known that every graph with maximum degree $\Delta$ is $c\Delta^2$-choosable, for some constant $c$. We prove this result with $c=1$ (ignoring lower order terms). We then prove that every subdivision of a graph with sufficiently many division vertices per edge is nonrepetitively 5-choosable. The proofs of both these results are based on the Moser-Tardos entropy-compression method, and a recent extension by Grytczuk, Kozik and Micek for the nonrepetitive choosability of paths. Finally, we prove that every graph with pathwidth $k$ is nonrepetitively $O(k^{2})$-colourable.
• ### Coloring planar graphs with three colors and no large monochromatic components(1303.2487)

April 8, 2014 math.CO, cs.DM
We prove the existence of a function $f :\mathbb{N} \to \mathbb{N}$ such that the vertices of every planar graph with maximum degree $\Delta$ can be 3-colored in such a way that each monochromatic component has at most $f(\Delta)$ vertices. This is best possible (the number of colors cannot be reduced and the dependence on the maximum degree cannot be avoided) and answers a question raised by Kleinberg, Motwani, Raghavan, and Venkatasubramanian in 1997. Our result extends to graphs of bounded genus.
• ### Hitting all Maximal Independent Sets of a Bipartite Graph(1208.5589)

Dec. 27, 2013 cs.DS, cs.CC
We prove that given a bipartite graph G with vertex set V and an integer k, deciding whether there exists a subset of V of size k hitting all maximal independent sets of G is complete for the class Sigma_2^P.
• ### Hitting and Harvesting Pumpkins(1105.2704)

Dec. 13, 2013 cs.DS
The "c-pumpkin" is the graph with two vertices linked by c>0 parallel edges. A c-pumpkin-model in a graph G is a pair A,B of disjoint subsets of vertices of G, each inducing a connected subgraph of G, such that there are at least c edges in G between A and B. We focus on covering and packing c-pumpkin-models in a given graph: On the one hand, we provide an FPT algorithm running in time 2^O(k) n^O(1) deciding, for any fixed c>0, whether all c-pumpkin-models can be covered by at most k vertices. This generalizes known single-exponential FPT algorithms for Vertex Cover and Feedback Vertex Set, which correspond to the cases c=1,2 respectively. On the other hand, we present a O(log n)-approximation algorithm for both the problems of covering all c-pumpkin-models with a smallest number of vertices, and packing a maximum number of vertex-disjoint c-pumpkin-models.
• ### Excluded Forest Minors and the Erd\H{o}s-P\'osa Property(1204.5192)

May 23, 2013 math.CO, cs.DM
A classical result of Robertson and Seymour states that the set of graphs containing a fixed planar graph $H$ as a minor has the so-called Erd\H{o}s-P\'osa property; namely, there exists a function $f$ depending only on $H$ such that, for every graph $G$ and every positive integer $k$, the graph $G$ has $k$ vertex-disjoint subgraphs each containing $H$ as a minor, or there exists a subset $X$ of vertices of $G$ with $|X| \leq f(k)$ such that $G - X$ has no $H$-minor. While the best function $f$ currently known is exponential in $k$, a $O(k \log k)$ bound is known in the special case where $H$ is a forest. This is a consequence of a theorem of Bienstock, Robertson, Seymour, and Thomas on the pathwidth of graphs with an excluded forest-minor. In this paper we show that the function $f$ can be taken to be linear when $H$ is a forest. This is best possible in the sense that no linear bound is possible if $H$ has a cycle.
• ### A linear-time algorithm for finding a complete graph minor in a dense graph(1202.2624)

April 24, 2013 math.CO, cs.DM, cs.DS
Let g(t) be the minimum number such that every graph G with average degree d(G) \geq g(t) contains a K_{t}-minor. Such a function is known to exist, as originally shown by Mader. Kostochka and Thomason independently proved that g(t) \in \Theta(t*sqrt{log t}). This article shows that for all fixed \epsilon > 0 and fixed sufficiently large t \geq t(\epsilon), if d(G) \geq (2+\epsilon)g(t) then we can find this K_{t}-minor in linear time. This improves a previous result by Reed and Wood who gave a linear-time algorithm when d(G) \geq 2^{t-2}.
• ### Sorting under Partial Information (without the Ellipsoid Algorithm)(0911.0086)

Jan. 21, 2013 cs.DM, cs.DS
We revisit the well-known problem of sorting under partial information: sort a finite set given the outcomes of comparisons between some pairs of elements. The input is a partially ordered set P, and solving the problem amounts to discovering an unknown linear extension of P, using pairwise comparisons. The information-theoretic lower bound on the number of comparisons needed in the worst case is log e(P), the binary logarithm of the number of linear extensions of P. In a breakthrough paper, Jeff Kahn and Jeong Han Kim (J. Comput. System Sci. 51 (3), 390-399, 1995) showed that there exists a polynomial-time algorithm for the problem achieving this bound up to a constant factor. Their algorithm invokes the ellipsoid algorithm at each iteration for determining the next comparison, making it impractical. We develop efficient algorithms for sorting under partial information. Like Kahn and Kim, our approach relies on graph entropy. However, our algorithms differ in essential ways from theirs. Rather than resorting to convex programming for computing the entropy, we approximate the entropy, or make sure it is computed only once, in a restricted class of graphs, permitting the use of a simpler algorithm. Specifically, we present: - an O(n^2) algorithm performing O(log n log e(P)) comparisons; - an O(n^2.5) algorithm performing at most (1+ epsilon) log e(P) + O_epsilon (n) comparisons; - an O(n^2.5) algorithm performing O(log e(P)) comparisons. All our algorithms can be implemented in such a way that their computational bottleneck is confined in a preprocessing phase, while the sorting phase is completed in O(q) + O(n) time, where q denotes the number of comparisons performed.
• ### Empty pentagons in point sets with collinearities(1207.3633)

July 16, 2012 math.CO, cs.DM, cs.CG
An empty pentagon in a point set P in the plane is a set of five points in P in strictly convex position with no other point of P in their convex hull. We prove that every finite set of at least 328k^2 points in the plane contains an empty pentagon or k collinear points. This is optimal up to a constant factor since the (k-1)x(k-1) grid contains no empty pentagon and no k collinear points. The previous best known bound was doubly exponential.
• ### An Improved Bound for First-Fit on Posets Without Two Long Incomparable Chains(1111.2370)

June 15, 2012 math.CO
It is known that the First-Fit algorithm for partitioning a poset P into chains uses relatively few chains when P does not have two incomparable chains each of size k. In particular, if P has width w then Bosek, Krawczyk, and Szczypka (SIAM J. Discrete Math., 23(4):1992--1999, 2010) proved an upper bound of ckw^{2} on the number of chains used by First-Fit for some constant c, while Joret and Milans (Order, 28(3):455--464, 2011) gave one of ck^{2}w. In this paper we prove an upper bound of the form ckw. This is best possible up to the value of c.