# Julian Pfeifle

Tel.: ++34 93 413 77 14
Fax: ++34 93 413 77 01
Email: julian.pfeifle@upc.edu

Research interests: Discrete and combinatorial geometry

## Preprints

• with Aaron M. Dall:
arXiv:1404.3876, A Polyhedral Proof of the Matrix Tree Theorem
The classical matrix tree theorem relates the number of spanning trees of a connected graph with the product of the nonzero eigenvalues of its Laplacian matrix. The class of regular matroids generalizes that of graphical matroids, and a generalization of the matrix tree theorem holds for this wider class. We give a new, geometric proof of this fact by showing via a dissect-and-rearrange argument that two combinatorially distinct zonotopes associated to a regular matroid have the same volume. Along the way we prove that for a regular oriented matroid represented by a unimodular matrix, the lattice spanned by its cocircuits coincides with the lattice spanned by the rows of the representation matrix. Finally, by extending our setup to the weighted case we give new proofs of recent results of~An et~al.\ on weighted graphs, and extend them to cover regular matroids. No use is made of the Cauchy-Binet Theorem nor divisor theory on graphs.

## Publications

• with Arnau Padrol, Polygons as sections of higher-dimensional polytopes. Electronic Journal of Combinatorics (2015), 1-24
We show that every heptagon is a section of a 3-polytope with 6 vertices. This implies that every n-gon 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), 121-142.
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 non-polytopal 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 (non-simple) polytopal products whose factors are not polytopal.

• with Benjamin Matschke and Vincent Pilaud:
Prodsimplicial Neighborly Polytopes, Discrete Comput. Geom. 46 (No. 1), 100-131 (2011),

We introduce PSN polytopes,  whose k-skeleton 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 Padrol-Sureda, Guillem Perarnau-Llobet 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 non-intersecting 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. 248-271

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. 360-378

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 f-and h-vectors. This leads us to recover formulae for the growth series of these root lattices, which were first conjectured by Conway-Mallows-Sloane and Baake-Grimm and proved by Conway-Sloane and Bacher-de la Harpe-Venkov.

• with Clemens Huemer and Ferran Hurtado,
The Rotation Graph of k-ary Trees is Hamiltonian,
Information Processing Letters 109 (2), 124-129, 2008.

• Dissections, Hom-complexes and the Cayley trick
J. Combinatorial Theory, Ser. A  114, No.3, 483--504 (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 well-known objects that arise as cells or subcomplexes of such projected Hom-complexes: the dissections of a convex polygon into k-gons, 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) 15-36 (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 d-polytopes, 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/1-polytopes.

• Long monotone paths on simple 4-polytopes (February, 2004)
Israel J. Math. 150 (2005), 333-355

The Monotone Upper Bound Problem (Klee, 1965) asks if the number M(d,n) of vertices in a monotone path along edges of a d-dimensional 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 d-polytope 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 dual-to-cyclic polytopes. For each n>=5, we exhibit a realization of a polar-to-neighborly 4-dimensional 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 polar-to-neighborly 6-dimensional 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), 1-11

The Monotone Upper Bound Problem asks for the maximal number M(d,n) of vertices on a strictly-increasing edge-path on a simple d-polytope 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 dual-to-cyclic d-polytope 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 strictly-increasing edge-path. The proof involves classification results about neighborly polytopes, Kalai's (1988) concept of abstract objective functions, the Holt-Klee conditions (1998), explicit enumeration, Welzl's (2001) extended Gale diagrams, randomized generation of instances, as well as non-realizability proofs via a version of the Farkas lemma.

• with Günter M. Ziegler:
Many Triangulated 3-Spheres
Mathematische Annalen 330 (2004) No.4, 829--837

We construct 2^{\Omega(n^{5/4})} combinatorial types of triangulated 3-spheres 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 4-polytopes, this proves that asymptotically, there are far more combinatorial types of triangulated 3-spheres than of simplicial 4-polytopes on n vertices. This complements results of Kalai (1988), who had proved a similar statement about d-spheres and (d+1)-polytopes for fixed d >= 4.

• with Jörg Rambau: Computing triangulations using oriented matroids, ZIB preprint ZR 02-02  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 3-spheres are polytopal
Discrete & Computational Geometry 27 (2002) No. 3, 395-407 (DOI: 10.1007/s00454-001-0074-3)

In 1988, Kalai extended a construction of Billera and Lee to produce many triangulated (d-1)-spheres. In fact, in view of upper bounds on the number of simplicial d-polytopes by Goodman and Pollack, he derived that for every dimension d>=5, most of these (d-1)-spheres are not polytopal. However, for d=4, this reasoning fails. We can now show that, as already conjectured by Kalai, all of his 3-spheres are in fact polytopal. Moreover, we can now give a shorter proof of Hebble & Lee's 2000 result that the dual graphs of these 4-polytopes are Hamiltonian. Therefore, the polars of these Kalai polytopes yield another family supporting Barnette's conjecture that all simple 4-polytopes 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.