
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 revenueordered assortments
strategy. In this paper we study the approximation guarantees provided by
revenueordered 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 envyfree pricing and Stackelberg minimum spanning
tree: These problems can be restated as assortment problems under discrete
choice models satisfying the regularity condition, and moreover revenueordered
assortments correspond then to the wellstudied uniform pricing heuristic. When
specialised to that setting, the general bounds we establish for
revenueordered assortments match and unify the best known results on uniform
pricing.

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})$.

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$ vertexdisjoint subgraphs each
containing $W_t$ as minor, or there is a subset $X$ of at most $c k \log k$
vertices such that $GX$ 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$.

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$.

We prove the conjecture of Seymour (1993) that for every apexforest $H_1$
and outerplanar graph $H_2$ there is an integer $p$ such that every 2connected
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.

A classic result of Asplund and Gr\"unbaum states that intersection graphs of
axisaligned rectangles in the plane are $\chi$bounded. This theorem can be
equivalently stated in terms of pathdecompositions as follows: There exists a
function $f:\mathbb{N}\to\mathbb{N}$ such that every graph that has two
pathdecompositions 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 treedecompositions. In this note we
provide a negative answer: There are graphs with arbitrarily large chromatic
number for which one can find two treedecompositions 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 pathdecomposition. This is shown using a construction of
trianglefree graphs with unbounded chromatic number due to Burling, which we
believe should be more widely known.

This paper studies graphs that have two tree decompositions with the property
that every bag from the first decomposition has a boundedsize 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 linearsized path
decomposition with bounded intersections: (1) every proper minorclosed 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 linearsized 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.

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)h2$.

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.

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.

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
pathwidth2 graphs that are not nonrepetitively $\ell$choosable for any fixed
$\ell$.

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_vr_w\_p=\q_vq_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 treewidth.

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 $GX$ 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.

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 wellknown 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$.

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 kcut problem, which admits a 2approximation 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 ksubgraph problem. We also
prove that, while the problem is easily solvable in polynomial time for
partition matroids, it is NPhard when considering the intersection of two
partition matroids. Our proof shows, in particular, that the maximum vertex
cover problem is NPhard on bipartite graphs, which answers an open problem of
B. Simeone.

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 treewidth by proving that
the dimension of a finite poset is bounded in terms of its height and the
treewidth of its cover graph.

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
5choosable. The proofs of both these results are based on the MoserTardos
entropycompression 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.

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
3colored 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.

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.

The "cpumpkin" is the graph with two vertices linked by c>0 parallel edges.
A cpumpkinmodel 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 cpumpkinmodels
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 cpumpkinmodels can be
covered by at most k vertices. This generalizes known singleexponential 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
cpumpkinmodels with a smallest number of vertices, and packing a maximum
number of vertexdisjoint cpumpkinmodels.

A classical result of Robertson and Seymour states that the set of graphs
containing a fixed planar graph $H$ as a minor has the socalled
Erd\H{o}sP\'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$ vertexdisjoint 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 forestminor. 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.

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 lineartime algorithm
when d(G) \geq 2^{t2}.

We revisit the wellknown 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
informationtheoretic 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), 390399, 1995) showed that there exists a polynomialtime
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.

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 (k1)x(k1) grid contains no empty pentagon and no k collinear
points. The previous best known bound was doubly exponential.

It is known that the FirstFit 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):19921999, 2010) proved an upper bound
of ckw^{2} on the number of chains used by FirstFit for some constant c, while
Joret and Milans (Order, 28(3):455464, 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.