McMullen's conditions and some lower bounds for general convex polytopes

We give a lower bound for the number of vertices of a generald-dimensional polytope with a given numberm ofi-faces for eachi = 0,..., d/2 – 1. The tightness of those bounds is proved using McMullen's conditions. Form greater than a small constant, those lower bounds are attained by simpliciali-neighbourly polytopes.     

Zigzags, railroads, and knots in fullerenes

Two connections between fullerene structures and alternating knots are established. Knots may appear in two ways: from zigzags, i.e., circuits (possibly self-intersecting) of edges running alternately left and right at successive vertices, and from railroads, i.e., circuits (possibly self-intersecting) of edge-sharing hexagonal faces, such that the shared edges occur in opposite pairs. A z-knot fullerene has only a single zigzag, doubly covering all edges: in the range investigated (n /= 38, all chiral, belonging to groups C(1), C(2), C(3), D(3), or D(5). An r-knot fullerene has a railroad corresponding to the projection of a nontrivial knot: examples are found for C(52) (trefoil), C(54) (figure-of-eight or Flemish knot), and, with isolated pentagons, at C(96), C(104), C(108), C(112), C(114). Statistics on the occurrence of z-knots and of z-vectors of various kinds, z-uniform, z-transitive, and z-balanced, are presented for trivalent polyhedra, general fullerenes, and isolated-pentagon fullerenes, along with examples with self-intersecting railroads and r-knots. In a subset of z-knot fullerenes, so-called minimal knots, the unique zigzag defines a specific Kekulé structure in which double bonds lie on lines of longitude and single bonds on lines of latitude of the approximate sphere defined by the polyhedron vertices.     

Facets for the cut cone I

We study facets of the cut coneC _n , i.e., the cone of dimension 1/2n(n – 1) generated by the cuts of the complete graph onn vertices. Actually, the study of the facets of the cut cone is equivalent in some sense to the study of the facets of the cut polytope. We present several operations on facets and, in particular, a lifting procedure for constructing facets ofC _n+1 from given facets of the lower dimensional coneC _n . After reviewing hypermetric valid inequalities, we describe the new class of cycle inequalities and prove the facet property for several subclasses. The new class of parachute facets is developed and other known facets and valid inequalities are presented.     

Every large set of equidistant (0, +1, −1)-vectors forms a sunflower

A theorem of Deza asserts that ifH ₁, ...,H _m ares-sets any pair of which intersects in exactlyd elements and ifm ≧s ² −s+2, then theH _i form aΔ-system, i.e. . In other words, every large equidistant (0, 1)-code of constant weight is trivial. We give a (0, +1, −1) analogue of this theorem.     

Addition patterns in carbon allotropes: independence numbers and d-codes in the Klein and related graphs

The problem of predicting stoichiometries and patterns of chemical addition to a carbon framework, subject solely to the restriction that each addend excludes neighboring sites up to some distance d, is equivalent to determination of d-codes of a graph, and for d = 2 to determination of maximum independent sets. Sizes, symmetries, and numbers of d-codes are found for the all-heptagon Klein graph (prototype for "plumber's nightmare" carbon) and for three related graphs. The independence number of the Klein graph is 23, which increases to 24 for a related, but sterically relaxed, all-heptagon network with the same number of vertices and modified adjacencies. Expansion of the Klein graph and its relaxed analogue by insertion of hexagonal faces to form leapfrog graphs also allows all heptagons to achieve their maximum of 3 addends. Consideration of the pi system that is the complement of the addition pattern imposes a closed-shell requirement on the adjacency spectrum, which typically reduces the size of acceptable independent sets. The closed-shell independence numbers of the Klein graph and its relaxed analogue are 18 and 20, respectively.     

Nonequilibrium phase transitions induced by multiplicative noise: effects of self-correlation

A recently introduced lattice model, describing an extended system which exhibits a reentrant (symmetry-breaking, second-order) noise-induced nonequilibrium phase transition, is studied under the assumption that the multiplicative noise leading to the transition is colored. Within an effective Markovian approximation and a mean-field scheme it is found that when the self-correlation time tau of the noise is different from zero, the transition is also reentrant with respect to the spatial coupling D. In other words, at variance with what one expects for equilibrium phase transitions, a large enough value of D favors disorder. Moreover, except for a small region in the parameter subspace determined by the noise intensity sigma and D, an increase in tau usually prevents the formation of an ordered state. These effects are supported by numerical simulations.     

On the solitaire cone and its relationship to multi-commodity flows

The classical game of Peg Solitaire has uncertain origins, but was certainly popular by the time of Louis XIV, and was described by Leibniz in 1710. The modern mathematical study of the game dates to the 1960s, when the solitaire cone was first described by Boardman and Conway. Valid inequalities over this cone, known as pagoda functions, were used to show the infeasibility of various peg games. In this paper we study the extremal structure of solitaire cones for a variety of boards, and relate their structure to the well studied metric cone. In particular we give:?1. an equivalence between the multicommodity flow problem with associated dual metric cone and a generalized peg game with associated solitaire cone;?2. a related NP-completeness result;?3. a method of generating large classes of facets;?4. a complete characterization of 0-1 facets;?5. exponential upper and lower bounds (in the dimension) on the number of facets;?6. results on the number of facets, incidence and adjacency relationships and diameter for small rectangular, toric and triangular boards;?7. a complete characterization of the adjacency of extreme rays, diameter, number of 2-faces and edge connectivity for rectangular toric boards. Received: July 1996 / Accepted: February 2000?Published online February 22, 2001     

Lego-like spheres and tori

Given a connected surface \({\mathbb {F}}^2\) with Euler characteristic \(\chi \) and three integers \(b>a\ge 1<k\), an \((\{a,b\};k)\)-\({\mathbb {F}}^2\) is a \({\mathbb {F}}^2\)-embedded graph, having vertices of degree only k and only a- and b-gonal faces. The main case are (geometric) fullerenes (5, 6; 3)-\({\mathbb {S}}^2\). By \(p_a\), \(p_b\) we denote the number of a-gonal, b-gonal faces. Call an \((\{a,b\};k)\)-map lego-admissible if either \(\frac{p_b}{p_a}\), or \(\frac{p_a}{p_b}\) is integer. Call it lego-like if it is either \(ab^f\)-lego map, or \(a^fb\)-lego map, i.e., the face-set is partitioned into \(\min (p_a,p_b)\) isomorphic clusters, legos, consisting either one a-gon and \(f=\frac{p_b}{p_a}\,b\)-gons, or, respectively, \(f=\frac{p_a}{p_b}\,a\)-gons and one b-gon; the case \(f=1\) we denote also by ab. Call a \((\{a,b\};k)\)-map elliptic, parabolic or hyperbolic if the curvature \(\kappa _b=1+\frac{b}{k}-\frac{b}{2}\) of b-gons is positive, zero or negative, respectively. There are 14 lego-like elliptic \((\{a,b\};k)\)-\({\mathbb {S}}^2\) with \((a,b)\ne (1,2)\). No \((\{1,3\};6)\)-\({\mathbb {S}}^2\) is lego-admissible. For other 7 families of parabolic \((\{a,b\};k)\)-\({\mathbb {S}}^2\), each lego-admissible sphere with \(p_a\le p_b\) is \(a^fb\) and an infinity (by Goldberg–Coxeter operation) of \(ab^f\)-spheres exist. The number of hyperbolic \(ab^f\,(\{a,b\};k)\)-\({\mathbb {S}}^2\) with \((a,b)\ne (1,3)\) is finite. Such \(a^f b\)-spheres with \(a\ge 3\) have \((a,k)=(3,4),(3,5),(4,3),(5,3)\) or (3, 3); their number is finite for each b, but infinite for each of 5 cases (a, k). Any lego-admissible \((\{a,b\};k)\)-\({\mathbb {S}}^2\) with \(p_b=2\le a\) is \(a^f b\). We list, explicitly or by parameters, lego-admissible \((\{a,b\};k)\)-maps among: hyperbolic spheres, spheres with \(a\in \{1,2\}\), spheres with \(p_b\in \{2,\frac{p_a}{2}\}\), Goldberg–Coxeter’s spheres and \((\{a,b\};k)\)-tori. We present extensive computer search of lego-like spheres: 7 parabolic (\(p_b\)-dependent) families, basic examples of all 5 hyperbolic \(a^fb\) (b-dependent) families with \(a\ge 3\), and lego-like \((\{a,b\};3)\)-tori.     

The cut cone III: On the role of triangle facets

The cut polytopeP _n is the convex hull of the incidence vectors of the cuts (i.e. complete bipartite subgraphs) of the complete graph onn nodes. A well known class of facets ofP _n arises from the triangle inequalities:x _ij +x _ik +x _jk ≤ 2 andx _ij -x _ik -x _jk ≤ 0 for 1 ≤i,j, k ≤n. Hence, the metric polytope M_n, defined as the solution set of the triangle inequalities, is a relaxation ofP _n . We consider several properties of geometric type for P_n, in particular, concerning its position withinM _n . Strengthening the known fact ([3]) thatP _n has diameter 1, we show that any set ofk cuts,k ≤ log₂ n, satisfying some additional assumption, determines a simplicial face ofM _n and thus, also, ofP _n . In particular, the collection of low dimension faces ofP _n is contained in that ofM _n . Among a large subclass of the facets ofP _n , the triangle facets are the closest ones to the barycentrum of P_n and we conjecture that this result holds in general. The lattice generated by all even cuts (corresponding to bipartitions of the nodes into sets of even cardinality) is characterized and some additional questions on the links between general facets ofP _n and its triangle facets are mentioned.