Equipartite graphs

A graph G of even order is weakly equipartite if for any partition of its vertex set into subsets V ₁ and V ₂ of equal size the induced subgraphs G[V ₁] and G[V ₂] are isomorphic. A complete characterization of (weakly) equipartite graphs is derived. In particular, we show that each such graph is vertex-transitive. In a subsequent paper, we use these results to characterize equipartite polytopes, a geometric analogue of equipartite graphs. Supported by Research Plan MSM 4977751301 of the Czech Ministry of Education. The Institute for Theoretical Computer Science is supported by Czech Ministry of Education as projects LN00A056 and 1M0545. Support by the Fulbright Senior Specialist Program for his stay in Pilsen in summer 2003 is acknowleged.     

Gelfand-Tsetlin polytopes and Feigin-Fourier-Littelmann-Vinberg polytopes as marked poset polytopes

Stanley (1986) showed how a finite partially ordered set gives rise to two polytopes, called the order polytope and chain polytope, which have the same Ehrhart polynomial despite being quite different combinatorially. We generalize his result to a wider family of polytopes constructed from a poset P with integers assigned to some of its elements.Through this construction, we explain combinatorially the relationship between the Gelfand-Tsetlin polytopes (1950) and the Feigin-Fourier-Littelmann-Vinberg polytopes (2010, 2005), which arise in the representation theory of the special linear Lie algebra. We then use the generalized Gelfand-Tsetlin polytopes of Berenstein and Zelevinsky (1989) to propose conjectural analogues of the Feigin-Fourier-Littelmann-Vinberg polytopes corresponding to the symplectic and odd orthogonal Lie algebras.     

Equipartite gregarious 6- and 8-cycle systems

A k-cycle decomposition of a complete multipartite graph is said to be gregarious if each k-cycle in the decomposition has its vertices in k different partite sets. Equipartite gregarious 3-cycle systems are 3-GDDs, and necessary and sufficient conditions for their existence are known (see for instance the CRC Handbook of Combinatorial Designs, 1996, C.J. Colbourn, J.H. Dinitz (Eds.), Section III 1.3). The cases of equipartite and of almost equipartite 4-cycle systems were recently dealt with by Billington and Hoffman. Here, for both 6-cycles and for 8-cycles, we give necessary and sufficient conditions for existence of a gregarious cycle decomposition of the complete equipartite graph K_n(a) (with n parts, n?6 or n?8, of size a).     

Note dual polytopes of rational convex polytopes

LetP ^d be a rational convex polytope with dimP=d such that the origin of ^d is contained in the interiorP – P ofP. In this paper, from a viewpoint of enumeration of certain rational points inP (which originated in Ehrhart's work), a necessary and sufficient condition for the dual polytopeP ^dual ofP to be integral is presented.This research was performed while the author was staying at Massachusetts Institute of Technology during the 1988–89 academic year.     

Algebraic shifting of cyclic polytopes and stacked polytopes

Gil Kalai introduced the shifting-theoretic upper bound relation as a method to generalize the g-theorem for simplicial spheres by using algebraic shifting. We will study the connection between the shifting-theoretic upper bound relation and combinatorial shifting. Also, we will compute the exterior algebraic shifted complex of the boundary complex of the cyclic d-polytope as well as of a stacked d-polytope. It will turn out that, in both cases, the exterior algebraic shifted complex coincides with the symmetric algebraic shifted complex.     

Neighborly polytopes

A 2m-polytopeQ isneighborly if eachm vertices ofQ determine a face. It is shown that the combinatorial structure of a neighborly 2m-polytope determines the combinatorial structure of every subpolytope. We develop a construction of “sewing a vertex onto a polytope”, which, when applied to a neighborly 2m-polytope, yields a neighborly 2m-polytope with one more, vertex. Using this construction, we show that the numberg(2m+β,2m) of combinatorial types of neighborly 2m-polytopes with 2m+β vertices grows superexponentially as β→∞ (m≧2 fixed) and asm→∞ (β≧4 fixed).     

Hamilton Cycle Rich 2-Factorization of Complete Equipartite Graphs-II

For any given two 2-factors G and H of a complete p-partite graph K(m, p), with m vertices in each partite set, we prove the existence of a 2-factorization of K(m, p), in which one 2-factor is isomorphic to G, another 2-factor is isomorphic to H and the remaining 2-factors are hamilton cycles. Further, we prove the corresponding result for K(m, p) ? I, where I is a 1-factor of K(m, p), when K(m, p) is an odd regular graph. In fact our results together with the results of McCauley and Rodger settled the problem of 2-factorization of K(m, p), when two of the 2-factors are isomorphic to the given two 2-factors and the remaining 2-factors are hamilton cycles except for (m, p)?=?(m, 2).     

Hypergraph polytopes

We investigate a family of polytopes introduced by E.M. Feichtner, A. Postnikov and B. Sturmfels, which were named nestohedra. The vertices of these polytopes may intuitively be understood as constructions of hypergraphs. Limit cases in this family of polytopes are, on the one end, simplices, and, on the other end, permutohedra. In between, as notable members one finds associahedra and cyclohedra. The polytopes in this family are investigated here both as abstract polytopes and as realized in Euclidean spaces of all finite dimensions. The later realizations are inspired by J.D. Stasheff ?s and S. Shnider?s realizations of associahedra. In these realizations, passing from simplices to permutohedra, via associahedra, cyclohedra and other interesting polytopes, involves truncating vertices, edges and other faces. The results presented here reformulate, systematize and extend previously obtained results, and in particular those concerning polytopes based on constructions of graphs, which were introduced by M. Carr and S.L. Devadoss.     

Flow polytopes and the graph of reflexive polytopes

We suggest defining the structure of an unoriented graph R_d on the set of reflexive polytopes of a fixed dimension d. The edges are induced by easy mutations of the polytopes to create the possibility of walks along connected components inside this graph. For this, we consider two types of mutations: Those provided by performing duality via nef-partitions, and those arising from varying the lattice. Then for d≤3, we identify the flow polytopes among the reflexive polytopes of each single component of the graph R_d. For this, we present for any dimension d≥2 an explicit finite list of quivers giving all d-dimensional reflexive flow polytopes up to lattice isomorphism. We deduce as an application that any such polytope has at most 6(d−1) facets.     

Indecomposable polytopes

The notions of local similarity and decomposability are extended to the class of geometric graphs. These, in turn, are used to produce new sufficient conditions for indecomposability of polytopes. A simple example is given of two combinatorially equivalent 3-polytopes, one decomposable, and the other not. The content of this paper is an extension of a part of a Ph.D. thesis [3], written by the author under the supervision of Professor M. A. Perles at the Hebrew University of Jerusalem, and submitted in April 1979.     

Inside-out polytopes

We present a common generalization of counting lattice points in rational polytopes and the enumeration of proper graph colorings, nowhere-zero flows on graphs, magic squares and graphs, antimagic squares and graphs, compositions of an integer whose parts are partially distinct, and generalized latin squares. Our method is to generalize Ehrhart's theory of lattice-point counting to a convex polytope dissected by a hyperplane arrangement. We particularly develop the applications to graph and signed-graph coloring, compositions of an integer, and antimagic labellings.     

Equipartite Gregarious 5-Cycle Systems and Other Results

A k-cycle decomposition of a complete multipartite graph is said to be gregarious if each k-cycle in the decomposition has its vertices in k different partite sets. Equipartite 3-cycle systems are 3-GDDs (and so are automatically gregarious), and necessary and sufficient conditions for their existence are known. The cases of equipartite gregarious 4-, 6- and 8-cycle systems have also been dealt with (using techniques that could be applied in the case of any even length cycle). Here we give necessary and sufficient conditions for the existence of a gregarious 5-cycle decomposition of the complete equipartite graph K_m(n) (in effect the first odd length cycle case for which the gregarious constraint has real meaning). In doing so, we also define some general cyclic constructions for the decomposition of certain complete equipartite graphs into gregarious p-cycles (where p is an odd prime).     

Decomposing Complete Equipartite Graphs into Closed Trails of Length k

Necessary conditions for a simple connected graph G to admit a decomposition into closed trails of length k ≥ 3 are that G is even and its total number of edges is a multiple of k. In this paper we show that these conditions are sufficient in the case when G is the complete equipartite graph having at least three parts, each of the same size.     

Weights on polytopes

Theg-theorem describes the possible face-vectors of a simple polytopeP. Much of the author's proof of the necessity of its conditions, while working within the polytope algebra π, in fact only used the spaces of weights onP. Even though this proof was conceptually easier than the original, which employed techniques from algebraic geometry, nevertheless the properties of π which are needed still require some effort to establish, despite a recent simpler approach to π itself. In the earlier paper, doubt was expressed about whether two basic results could be proved directly for weights; later, it appeared that there might also be a possible problem concerning an alternative definition of the product of certain weights. In this paper these questions are settled, in the context of developing an independent theory of an algebra Ω of weights on polytopes. Since the construction of Ω is more approachable than that of π, a yet easier proof of theg-theorem is now available.     

Eulerian abstract polytopes

The classical theory of regular convex polytopes has inspired many combinatorial analogues. In this article, we examine two of them, the eulerian posets and the abstract regular polytopes, and see what the overlap between the concepts is. It is shown that a section regular polytope is eulerian if and only if it is spherical, or it has even rank and is locally spherical. Equivelar polytopes of rank less than 4 are eulerian, and some progress is made towards a characterisation of equivelar eulerian posets in higher rank. In particular, necessary conditions are given for an equivelar quotient of a cube or a torus to be eulerian.     

Hamiltonian simple polytopes

We show that for everyn> n _o (d) (n even ifd is odd) there exists a simpled-polytope withn vertices, whose graph admits a Hamiltonian circuit. The result sharpens and earlier lower bound due to Victor Klee.