Julian Pfeifle

Preprints
Publications

Research interests: Discrete and combinatorial geometry

Preprints

• with Benjamin Matschke and Vincent Pilaud:
  Prodsimplicial Neighborly Polytopes
  
  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.
  
  
  
• An explicit construction for neighborly centrally symmetric polytopes
  
  We give an explicit construction, based on Hadamard matrices, for an infinite series of floor{sqrt{d}/2}-neighborly centrally symmetric d-dimensional polytopes with 4d vertices. This appears to be the best explicit version yet of a recent probabilistic result due to Linial and Novik, who proved the existence of such polytopes with a neighborliness of d/400.
  
  

Publications

• 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), accepted for publication
  
  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
   J. Combinatorial Theory, Ser. A, accepted for publication (2009)
  
  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., accepted for publication 2009
  
  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.

Last modified: December 14, 2009
julian.pfeifle@upc.edu