 with Arnau Padrol, Polygons as sections of higherdimensional
polytopes. Electronic Journal of Combinatorics (2015), 124
We show that every heptagon is a section of a 3polytope with 6 vertices.
This implies that every ngon with n≥7 can be obtained as a section of a
(2+floor(n/7))dimensional polytope with at most ceil(6n/7) vertices; and
provides a geometric proof of the fact that every nonnegative
n times m matrix of rank 3 has nonnegative
rank not larger than ceil(6 min(n,m)/7). This result has been independently
proved, algebraically, by Shitov (J. Combin. Theory Ser. A 122,
2014).
 with Vincent Pilaud and Francisco Santos:
Polytopality and Cartesian products of graphs, Israel J. Math 192 (2012), 121142.
We study the question of polytopality of graphs: when is a given graph the graph of a polytope? We first review the known necessary conditions for a graph to be polytopal, and we present three families of graphs which satisfy all these conditions, but which nonetheless are not graphs of polytopes.
Our main contribution concerns the polytopality of Cartesian products of nonpolytopal graphs. On the one hand, we show that products of simple polytopes are the only simple polytopes whose graph is a product. On the other hand, we provide a general method to construct (nonsimple) polytopal products whose factors are not polytopal.
 with Benjamin
Matschke and Vincent Pilaud:
Prodsimplicial Neighborly
Polytopes, Discrete Comput. Geom. 46 (No. 1), 100131 (2011),
We introduce PSN polytopes,
whose kskeleton is
combinatorially equivalent to that of a product of r simplices. They simultaneously
generalize both neighborly and neighborly cubical polytopes. We
construct PSN polytopes by three different methods, the most versatile
of which is an extension of Sanyal & Ziegler's ``projecting
deformed products'' construction to products of arbitrary simple
polytopes. For general r and k, the lowest dimension we achieve
is 2k+r+1. Using topological obstructions
similar to those introduced by Sanyal to bound the number of vertices
of Minkowski sums, we show that this dimension is minimal if we
moreover require the PSN polytope to be obtained as a projection of a
polytope combinatorially equivalent to the product of r simplices, when the dimensions of
these simplices are all large compared to k.
 with Arnau PadrolSureda, Guillem PerarnauLlobet and
Victor Muntès,
Overlapping Community Search for Social Networks,
26th IEEE Congress on Data Engineering (ICDE 2010)
Efficient graph clustering (or partitioning) has become a
crucial operation for many different purposes, ranging from social
network and web analysis to data graph mining or graph summarization.
Although it has been shown that communities are usually overlapping,
most of the literature related to community search on graphs or
networks has focused on finding nonintersecting groupings of the
nodes. In addition, taking into account the size of modern data sets,
most of them typically rely on prohibitively expensive computations. In
this paper, we present a novel approach to find communities in large
graphs: we implicitly map the nodes into a virtual multidimensional
vector space where communities can be easily represented and detected.
With this objective, we propose a new fitness function that evaluates
the quality of a community without penalizing those nodes that
are significantly linked to nodes in another community, as it happens
in some previous proposals. With this, overlapping communities come to
the surface naturally. In addition, our algorithm does not require to
preassume a certain size or number for the communities, since this
information has to be extracted from the graph structure itself. We
show that our proposal outperforms previous ones in terms of execution
time, especially for very large graphs like those representing social
networks, or the Wikipedia, containing more than 10^8 nodes and edges.
 Gale duality bounds
for roots of polynomials with nonnegative coefficients
Journal of Combinatorial Theory, Series A 117 (2010), pp. 248271
We bound the location of roots of polynomials that have
nonnegative
coefficients with respect to a fixed but arbitrary basis of the vector
space of
polynomials of degree at most $d$. For this, we interpret the basis
polynomials
as vector fields in the real plane, and at each point in the plane
analyze the
combinatorics of the Gale dual vector configuration. This approach
permits us
to incorporate arbitrary linear equations and inequalities among the
coefficients in a unified manner to obtain more precise bounds on the
location
of roots. We apply our technique to bound the location of roots of
Ehrhart and
chromatic polynomials. Finally, we give an explanation for the
clustering seen
in plots of roots of random polynomials.
 with Federico Ardila,
Matthias Beck, Serkan Hosten and Kim
Seashore,
Root polytopes and growth
series of root lattices
Siam J. Discrete Math. 25 (2011), pp. 360378
The convex hull of the roots of a classical root lattice is called a
root
polytope. We determine explicit unimodular triangulations of the
boundaries of
the root polytopes associated to the root lattices A_n, C_n, and D_n,
and
compute their fand hvectors. This leads us to recover formulae for
the growth
series of these root lattices, which were first conjectured by
ConwayMallowsSloane and BaakeGrimm and proved by ConwaySloane and
Bacherde
la HarpeVenkov.
 with Clemens Huemer and Ferran Hurtado,
The Rotation Graph of kary
Trees is Hamiltonian,
Information Processing Letters 109 (2), 124129, 2008.
 Dissections,
Homcomplexes and the Cayley trick
J. Combinatorial Theory, Ser. A 114,
No.3, 483504 (2007)
We show that certain canonical realizations of the
complexes
Hom(G,H) and Hom_+(G,H) of (partial) graph homomorphisms studied by
Babson and Kozlov are in fact instances of the polyhedral Cayley trick.
For G a complete graph, we then characterize when a canonical
projection of these complexes is itself again a complex, and exhibit
several wellknown objects that arise as cells or subcomplexes of such
projected Homcomplexes: the dissections of a convex polygon into
kgons, Postnikov's generalized permutohedra, staircase triangulations,
the complex dual to the lower faces of a cyclic polytope, and the graph
of weak compositions of an integer into a fixed number of summands.
 with Matthias Beck, Jesús A. De Loera,
Mike Develin, and
Richard P. Stanley:
Coefficients and Roots of Ehrhart
Polynomials; also in pdf
(large)
Contemp. Math. 374 (2004) 1536 (Proceedings of the Summer
Research
Conference on Integer Points in Polyhedra, July 13  July 17, 2003 in
Snowbird,
Utah).
The Ehrhart polynomial of a convex lattice polytope
counts
integer
points in
integral dilates of the polytope. We present new linear inequalities
satisfied
by the coefficients of Ehrhart polynomials and relate them to known
inequalities. We also investigate the roots of Ehrhart polynomials. We
prove
that for fixed d, there exists a bounded region of C
containing
all roots of Ehrhart polynomials of dpolytopes, and that all
real
roots of these polynomials lie in [d, \lfloor d/2
\rfloor). In
contrast, we prove that when the dimension d is not fixed the
positive
real roots can be arbitrarily large. We finish with an experimental
investigation of the Ehrhart polynomials of cyclic polytopes and
0/1polytopes.
 Long
monotone paths on simple 4polytopes (February, 2004)
Israel J. Math. 150 (2005), 333355
The Monotone Upper Bound Problem (Klee, 1965) asks if
the
number
M(d,n) of vertices in a monotone path along edges of a ddimensional
polytope with n facets can be as large as conceivably possible: Is
M(d,n) = M_{ubt}(d,n), the maximal number of vertices that a
dpolytope with n facets can have according to the Upper Bound
Theorem? We show that in dimension d=4, the answer is ``yes'', despite
the fact that it is ``no'' if we restrict ourselves to the
dualtocyclic polytopes. For each n>=5, we exhibit a realization of
a
polartoneighborly 4dimensional polytope with n facets and a
Hamilton path through its vertices that is monotone with respect to a
linear objective function. This constrasts an earlier result, by which
no polartoneighborly 6dimensional polytope with 9 facets admits a
monotone Hamilton path.
 with Günter
M. Ziegler:
On the Monotone Upper
Bound Problem
Experimental Mathematics 13
No. 1 (2004), 111
The Monotone Upper Bound Problem asks for the maximal
number
M(d,n) of
vertices on a strictlyincreasing edgepath on a simple dpolytope with
n
facets. More specifically, it asks whether the upper bound
M(d,n)<=M_{ubt}(d,n)
provided by McMullen's (1970) Upper Bound Theorem is tight, where
M_{ubt}(d,n)
is the number of vertices of a dualtocyclic dpolytope with n facets.
It was recently shown that the upper bound M(d,n)<=M_{ubt}(d,n)
holds with
equality for small dimensions (d<=4: Pfeifle, 2003) and for small
corank
(n<=d+2: Gärtner et al., 2001). Here we prove that it is not
tight in
general: In dimension d=6 a polytope with n=9 facets can have
M_{ubt}(6,9)=30
vertices, but not more than 26 <= M(6,9) <= 29 vertices can lie
on a
strictlyincreasing edgepath. The proof involves classification
results about neighborly polytopes, Kalai's
(1988) concept of abstract objective functions, the HoltKlee
conditions
(1998), explicit enumeration, Welzl's (2001) extended Gale diagrams,
randomized
generation of instances, as well as nonrealizability proofs via a
version of
the Farkas lemma.
 with Günter
M. Ziegler:
Many Triangulated
3Spheres
Mathematische
Annalen 330 (2004) No.4,
829837
We construct 2^{\Omega(n^{5/4})} combinatorial types of
triangulated 3spheres on n vertices. Since by a result of Goodman and
Pollack (1986) there are no more than 2^{O(n log n)} combinatorial
types of simplicial 4polytopes, this proves that asymptotically, there
are far more combinatorial types of triangulated 3spheres than of
simplicial 4polytopes on n vertices. This complements results of Kalai
(1988), who had proved a similar statement about dspheres and
(d+1)polytopes for fixed d >= 4.
 with Jörg Rambau:
Computing triangulations using oriented matroids, ZIB preprint ZR
0202
in Algebra,
Geometry, and Software Systems, Michael Joswig and Nobuki
Takayama, eds., Springer 2003
Oriented matroids are combinatorial structures
that
encode the combinatorics of point configurations. The set of all
triangulations of a point configuration depends only on its oriented
matroid. We survey the most important ingredients necessary to exploit
oriented matroids as a data structure for computing all triangulations
of a point configuration, and report on experience with an
implementation of these concepts in the software package TOPCOM. Next, we briefly
overview the construction and an application of the secondary polytope
of a point configuration, and calculate some examples that illustrate
how our tools were integrated into the polymake
framework.


 Kalai's
squeezed 3spheres are polytopal
Discrete
& Computational Geometry 27 (2002) No. 3, 395407 (DOI:
10.1007/s0045400100743)
In 1988, Kalai extended a construction of Billera and
Lee to
produce many triangulated (d1)spheres. In fact, in view of
upper bounds on the number of simplicial dpolytopes by Goodman and
Pollack, he derived that for every dimension d>=5, most of
these (d1)spheres are not polytopal. However, for d=4, this
reasoning fails. We can now show that, as already conjectured by
Kalai, all of his 3spheres are in fact polytopal. Moreover, we can now
give a shorter proof of Hebble & Lee's
2000 result that
the
dual graphs of these 4polytopes are Hamiltonian. Therefore, the
polars of these Kalai polytopes yield another family supporting
Barnette's conjecture that all simple 4polytopes admit a
Hamiltonian circuit.
Electronic Publications
 You can see some nice secondary polytopes in the EG Models
Archive, under Discrete Mathematics/Polytopes/Secondary Polytopes.
 Here is my PhD thesis Extremal
Constructions for Polytopes and Spheres, written at TU Berlin. My
advisor was
Prof. Günter M. Ziegler.