The size Ramsey number of trees with bounded degree

The size Ramsey number r?(G, H) of graphs G and H is the smallest integer r? such that there is a graph F with r? edges and if the edge set of F is red-blue colored, there exists either a red copy of G or a blue copy of H in F. This article shows that r?(T_nd, T_nd) ? c · d² · n and c · n³ ? r?(K_n, T_nd) ? c(d)·n³ log n for every tree T_nd on n vertices. and maximal degree at most d and a complete graph K_n on n vertices. A generalization will be given. Probabilistic method is used throught this paper. © 1993 John Wiley Sons, Inc.     

Minimal Simplicial Self-maps of the 2-Sphere

For any d (resp. for almost all d) we compute the least number (d) of vertices which a triangulation K of the 2-sphere (resp. any other orientable surface) must have in order that there exists a degree d simplicial map from K to the 4-vertex 2-sphere. We also prove an analogous result for uniquely 4-colourable Ks.     

Completely unimodal numberings of a simple polytope

A completely unimodal numbering of the m vertices of a simple d-dimensional polytope is a numbering 0, 1, …,m−1 of the vertices such that on every k-dimensional face (2≤k≤d) there is exactly one local minimum (a vertex with no lower-numbered neighbors on that face). Such numberings are abstract objective functions in the sense of Adler and Saigal [1]. It is shown that a completely unimodal numbering of the vertices of a simple polytope induces a shelling of the facets of the dual simplicial polytope. The h-vector of the dual simplicial polytope is interpreted in terms of the numbering (with respect to using a local-improvement algorithm to locate the vertex numbered 0). In the case that the polytope is combinatorially equivalent to a d-dimensional cube, a ‘successor-tuple’ for each vertex is defined which carries the crucial information of the numbering for local-improvement algorithms. Combinatorial properties of these d-tuples are studied. Finally the running time of one particular local-improvement algorithm, the Random Algorithm, is studied for completely unimodal numberings of the d-cube. It is shown that for a certain class of numberings (which includes the example of Klee and Minty [8] showing that the simplex algorithm is not polynomial and all Hamiltonian saddle-free injective pseudo-Boolean functions [6]) this algorithm has expected running time that is at worst quadratic in the dimension d.     

Toric Rings Arising from Cyclic Polytopes

Let d and n be positive integers with n ≥ d + 1 and 𝒫 ? ? ^d an integral cyclic polytope of dimension d with n vertices, and let K[𝒫] = K[?_≥0𝒜_𝒫] denote its associated semigroup K-algebra, where 𝒜_𝒫 = {(1, α) ∈ ? ^d+1: α ∈ 𝒫} ∩ ? ^d+1 and K is a field. In the present paper, we consider the problem when K[𝒫] is Cohen–Macaulay by discussing Serre's condition (R ₁), and we give a complete characterization when K[𝒫] is Gorenstein. Moreover, we study the normality of the other semigroup K-algebra K[Q] arising from an integral cyclic polytope, where Q is a semigroup generated by its vertices only.     

Lattices on simplicial partitions

In this paper, (d+1)-pencil lattices on simplicial partitions in R^d are studied. The barycentric approach naturally extends the lattice from a simplex to a simplicial partition, providing a continuous piecewise polynomial interpolant over the extended lattice. The number of degrees of freedom is equal to the number of vertices of the simplicial partition. The constructive proof of this fact leads to an efficient computer algorithm for the design of a lattice.     

Distortion coefficients for cryptocontractions

For complex Hilbert space H of d dimensions and for any number K ? 1, we may define m(K, d) as the least number with the following property: if 6p(T)6 ? K for all polynomials p mapping the complex unit disk into itself, then the operator T may be made a contraction by changing to a new norm |·|, derived from an inner product, such that

$\text{6h6 ? |h| ?m(K,d)6h6 (h∈H).}$

It is a long-standing open question whether m(K, d) has a finite bound independent of d. The present paper studies this and related questions and provides, in particular, an explicit estimate for m(K,d)—which, however, grows with d.     

On simplices in diameter graphs in ℝ4

Agraph G is a diameter graph in ?^d if its vertex set is a finite subset in ?^d of diameter 1 and edges join pairs of vertices a unit distance apart. It is shown that if a diameter graph G in ?⁴ contains the complete subgraph K on five vertices, then any triangle in G shares a vertex with K. The geometric interpretation of this statement is as follows. Given any regular unit simplex on five vertices and any regular unit triangle in ?⁴, then either the simplex and the triangle have a common vertex or the diameter of the union of their vertex sets is strictly greater than 1.

     

Construction and Analysis of Projected Deformed Products

We introduce a deformed product construction for simple polytopes in terms of lower-triangular block matrix representations. We further show how Gale duality can be employed for the construction and the analysis of deformed products such that specified faces (e.g., all the k-faces) are “strictly preserved” under projection. Thus, starting from an arbitrary neighborly simplicial (d?2)-polytope Q on n?1 vertices, we construct a deformed n-cube, whose projection to the last d coordinates yields a neighborly cubical d -polytope. As an extension of the cubical case, we construct matrix representations of deformed products of (even) polygons (DPPs) which have a projection to d-space that retains the complete $(\lfloor\tfrac{d}{2}\rfloor-1)We introduce a deformed product construction for simple polytopes in terms of lower-triangular block matrix representations. We further show how Gale duality can be employed for the construction and the analysis of deformed products such that specified faces (e.g., all the k-faces) are “strictly preserved” under projection. Thus, starting from an arbitrary neighborly simplicial (d−2)-polytope Q on n−1 vertices, we construct a deformed n-cube, whose projection to the last d coordinates yields a neighborly cubical d -polytope. As an extension of the cubical case, we construct matrix representations of deformed products of (even) polygons (DPPs) which have a projection to d-space that retains the complete (?\tfracd2?-1)(\lfloor\tfrac{d}{2}\rfloor-1) -skeleton.     

Every Simplicial Polytope with at Most d + 4 Vertices Is a Quotient of a Neighborly Polytope

We show that every simplicial d-polytope with d+4 vertices is a quotient of a neighborly (2d+4)-polytope with 2d+8 vertices, using the technique of affine Gale diagrams. The result is extended to matroid polytopes. Received September 27, 1995.     

Two combinatorial properties of a class of simplicial polytopes

Letf(P _s ^d ) be the set of allf-vectors of simpliciald-polytopes. ForP a simplicial 2d-polytope let Σ(P) denote the boundary complex ofP. We show that for eachf ∈f(P _s ^d ) there is a simpliciald-polytopeP withf(P)=f such that the 11 02 simplicial diameter of Σ(P) is no more thanf ₀(P)−d+1 (one greater than the conjectured Hirsch bound) and thatP admits a subdivision into a simpliciald-ball with no new vertices that satisfies the Hirsch property. Further, we demonstrate that the number of bistellar operations required to obtain Σ(P) from the boundary of ad-simplex is minimum over the class of all simplicial polytopes with the samef-vector. This polytopeP will be the one constructed to prove the sufficiency of McMullen's conditions forf-vectors of simplicial polytopes.     

Strongly simplicial vertices of powers of trees

For a tree T and an integer k?1, it is well known that the kth power T^k of T is strongly chordal and hence has a strong elimination ordering of its vertices. In this note we obtain a complete characterization of strongly simplicial vertices of T^k, thereby characterizing all strong elimination orderings of the vertices of T^k.     

Colourful Simplicial Depth

Inspired by Barany’s Colourful Caratheodory Theorem, we introduce a colourful generalization of Liu's simplicial depth. We prove a parity property and conjecture that the minimum colourful simplicial depth of any core point in any d-dimensional configuration is d² + 1 and that the maximum is d^d+1 + 1. We exhibit configurations attaining each of these depths, and apply our results to the problem of bounding monochrome (non-colourful) simplicial depth.     

Involutory decomposition of a group and twisted subsets with few involutions

A subset K of some group C is called twisted if 1 ∈ K and x, y ∈ K implies that xy ^?1 x belongs to K. We use the concept of twisted subset to investigate and generalize the concept of involutory decomposition of a group. A group is said to admit involutory decomposition if it contains some involution such that the group is the product of the centralizer of the involution and the set of elements inverted by the involution. We study the twisted subsets with at most one involution. We prove that if a twisted subset has no involutions at all then it generates a subgroup of odd order.     

Minimal ordered triangulations of surfaces

A finite simplicial complex is orderable if its simplices are the chains of a poset. For each closed surface an orderable triangulation is given that is minimal with respect to the number of vertices. The construction of minimal ordered triangulations implies that for each surface S the minimal number of vertices of a bipartite graph, which has a quadrilateral embedding into S, is equal to b(S) = ?4 + (16 – 8χ)^1/2?, where χ is the Euler characteristic of S.     

An Upper and a Lower Bound Theorem for Combinatorial 4-Manifolds

In this paper we prove two inequalities. The first one gives a lower bound for the Euler characteristic of a tight combinatorial 4-manifold M under the additional assumptions that |M| is 1-connected, that M is a subcomplex of H (M) , and that H (M) is a centrally symmetric and simplicial d -polytope. The second inequality relates the Euler characteristic with the number of vertices of a combinatorial 4-manifold admitting a fixed-point free involution. Furthermore, we construct a new and highly symmetric 12-vertex triangulation of S ² x S ² realizing equality in each of these inequalities. Received January 23, 1996, and in revised form September 13, 1996.     

On the connectivity of unit distance graphs

For a number fieldK , consider the graphG(K^d), whose vertices are elements ofK ^d, with an edge between any two points at (Euclidean) distance 1. We show thatG(K²) is not connected whileG(K^d) is connected ford 5. We also give necessary and sufficient conditions for the connectedness ofG(K³) andG(K⁴).     

On Synge-type angle condition for <Emphasis Type="Italic">d</Emphasis>-simplices

The maximum angle condition of J. L. Synge was originally introduced in interpolation theory and further used in finite element analysis and applications for triangular and later also for tetrahedral finite element meshes. In this paper we present some of its generalizations to higher-dimensional simplicial elements. In particular, we prove optimal interpolation properties of linear simplicial elements in ? ^d that degenerate in some way.     

Lagrange interpolation and finite element superconvergence

We consider the finite element approximation of the Laplacian operator with the homogeneous Dirichlet boundary condition, and study the corresponding Lagrange interpolation in the context of finite element superconvergence. For d‐dimensional Q_k‐type elements with d ≥ 1 and k ≥ 1, we prove that the interpolation points must be the Lobatto points if the Lagrange interpolation and the finite element solution are superclose in H¹ norm. For d‐dimensional P_k‐type elements, we consider the standard Lagrange interpolation—the Lagrange interpolation with interpolation points being the principle lattice points of simplicial elements. We prove for d ≥ 2 and k ≥ d + 1 that such interpolation and the finite element solution are not superclose in both H¹ and L² norms and that not all such interpolation points are superconvergence points for the finite element approximation. © 2003 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 20: 33–59, 2004.     

Bichromaticity of bipartite graphs

Let B be a bipartite graph with edge set E and vertex bipartition M, N. The bichromaticity β(B) is defined as the maximum number β such that a complete bipartite graph on β vertices is obtainable from B by a sequence of identifications of vertices of M or vertices of N. Let μ = max{∣M∣, ∣N∣}. Harary, Hsu, and Miller proved that β(B) ≥ μ + 1 and that β(T) = μ + 1 for T an arbitrary tree. We prove that β(B) ≤ μ + ∣E∣/μ yielding a simpler proof that β(T) = μ + 1. We also characterize graphs for which K_{μ, 2} is obtainable by such identifications. For Q_K. the graph of the K-dimensional cube, we obtain the inequality 2^K?1 + 2 ≤ β(Q_K) ≤ 2^K?1 + K, the upper bound attainable iff K is a power of 2.     

Hirsch polytopes with exponentially long combinatorial segments

In their paper proving the Hirsch bound for flag normal simplicial complexes, Adiprasito and Benedetti (Math Oper Res 39(4):1340–1348, 2014) define the notion of combinatorial segment. The study of the maximal length of these objects provides the upper bound \(O(n2^d)\) for the diameter of any normal pure simplicial complex of dimension d with n vertices, and the Hirsch bound \(n-d+1\) if the complexes are moreover flag. In the present article, we propose a formulation of combinatorial segments which is equivalent but more local, by introducing the notions of monotonicity and conservativeness of dual paths in pure simplicial complexes. We use these definitions to investigate further properties of combinatorial segments. Besides recovering the two stated bounds, we show a refined bound for banner complexes, and study the behavior of the maximal length of combinatorial segments with respect to two usual operations, namely join and one-point suspension. Finally, we show the limitations of combinatorial segments by constructing pure normal simplicial complexes in which all combinatorial segments between two particular facets achieve the length \(\Omega (n2^{d})\). This includes vertex-decomposable—therefore Hirsch—polytopes.