The cardinality of the separated vertex set of a multidimensional cube

An n-dimensional cube and the sphere inscribed into it are considered. The conjecture of A. Ben-Tal, A. Nemirovski, and C. Roos states that each tangent hyperplane to the sphere strictly separates not more than 2 ⁿ⁻² cube vertices. In this paper this conjecture is proved for n ≤ 6. New examples of hyperplanes separating exactly 2 ⁿ⁻² cube vertices are constructed for any n. It is proved that hyperplanes orthogonal to radius vectors of cube vertices separate less than 2 ⁿ⁻² cube vertices for n ≥ 3.     

The Four-in-a-Tree Problem in Triangle-Free Graphs

The three-in-a-tree algorithm of Chudnovsky and Seymour decides in time O(n ⁴) whether three given vertices of a graph belong to an induced tree. Here, we study four-in- a-tree for triangle-free graphs. We give a structural answer to the following question: what does a triangle-free graph look like if no induced tree covers four given vertices? Our main result says that any such graph must have the “same structure”, in a sense to be defined precisely, as a square or a cube. We provide an O(nm)-time algorithm that given a triangle-free graph G together with four vertices outputs either an induced tree that contains them or a partition of V(G) certifying that no such tree exists. We prove that the problem of deciding whether there exists a tree T covering the four vertices such that at most one vertex of T has degree at least 3 is NP-complete.     

Order Structure on the Algebra of Permutations and of Planar Binary Trees

Let X _n be either the symmetric group on n letters, the set of planar binary n-trees or the set of vertices of the (n – 1)-dimensional cube. In each case there exists a graded associative product on _n0 K[X _n]. We prove that it can be described explicitly by using the weak Bruhat order on S _n, the left-to-right order on planar trees, the lexicographic order in the cube case.     

The Expected Volume of a Tetrahedron whose Vertices are Chosen at Random in the Interior of a Cube

We calculate E[V ₄(C)], the expected volume of a tetrahedron whose vertices are chosen randomly (i.e. independently and uniformly) in the interior of C, a cube of unit volume. We find

A Characterization of Graphs with No Cube Minor

In this paper it is shown that any 4-connected graph that does not contain a minor isomorphic to the cube is a minor of the line graph of V_n for some n6 or a minor of one of five graphs. Moreover, there exists a unique 5-connected graph on at least 8 vertices with no cube minor and a unique 4-connected graph with a vertex of degree at least 8 with no cube minor. Further, it is shown that any graph with no cube minor is obtained from 4-connected such graphs by 0-, 1-, and 2-summing, and 3-summing over a specified triangles.     

Discrete nonlinear hyperbolic equations. Classification of integrable cases

We consider discrete nonlinear hyperbolic equations on quad-graphs, in particular on ?². The fields are associated with the vertices and an equation of the form Q(x ₁, x ₂, x ₃, x ₄) = 0 relates four vertices of one cell. The integrability of equations is understood as 3D-consistency, which means that it is possible to impose equations of the same type on all faces of a three-dimensional cube so that the resulting system will be consistent. This allows one to extend these equations also to the multidimensional lattices ? ^N . We classify integrable equations with complex fields x and polynomials Q multiaffine in all variables. Our method is based on the analysis of singular solutions.     

Asymptotics for Euclidean minimal spanning trees on random points

Summary Asymptotic results for the Euclidean minimal spanning tree onn random vertices inR ^d can be obtained from consideration of a limiting infinite forest whose vertices form a Poisson process in allR ^d. In particular we prove a conjecture of Robert Bland: the sum of thed'th powers of the edge-lengths of the minimal spanning tree of a random sample ofn points from the uniform distribution in the unit cube ofR ^d tends to a constant asn.Whether the limit forest is in fact a single tree is a hard open problem, relating to continuum percolation.Research supported by N.S.F. Grants MCS87-11426 and MCS 90-01710Research supported in part by N.S.F. Grant DMS88-12868, A.F.O.S.R. Grant 89-0301, ARO Grant DAAL03-89-G-0092 and NSA Grant MDA-904-H-2034     

The degree sequence of Fibonacci and Lucas cubes

The Fibonacci cube Γ_n is the subgraph of the n-cube induced by the binary strings that contain no two consecutive 1’s. The Lucas cube Λ_n is obtained from Γ_n by removing vertices that start and end with 1. It is proved that the number of vertices of degree k in Γ_n and Λ_n is and , respectively. Both results are obtained in two ways, since each of the approaches yields additional results on the degree sequences of these cubes. In particular, the number of vertices of high resp. low degree in Γ_n is expressed as a sum of few terms, and the generating functions are given from which the moments of the degree sequences of Γ_n and Λ_n are easily computed.     

An ‘odd’ formula for the volume of three-dimensional lattice polyhedra

Let be the tiling of R ³ with unit cubes whose vertices belong to the fundamental lattice L ₁ of points with integer coordinates. Denote by L _n the lattice consisting of all points x in R ³ such that nx belongs to L ₁. When the vertices of a polyhedron P in R ³ are restricted to lie in L ₁ then there is a formula which relates the volume of P to the numbers of all points of two lattices L ₁ and L _n lying in the interior and on the boundary of P. In the simplest case of the lattices L ₁ and L ₂ there are 27 points in each cube from whose relationships to the polyhedron P must be examined. In this note we present a new formula for the volume of lattice polyhedra in R ³ which involves only nine points in each cube of : one from L ₂ and eight belonging to L ₄. Another virtue of our formula is that it does not employ any additional parameters, such as the Euler characteristic.     

Ramsey numbers of cubes versus cliques

The cube graph Q _n is the skeleton of the n-dimensional cube. It is an n-regular graph on 2 ⁿ vertices. The Ramsey number r(Q _n ;K _s ) is the minimum N such that every graph of order N contains the cube graph Q _n or an independent set of order s. In 1983, Burr and Erd?s asked whether the simple lower bound r(Q _n ;K _s )≥(s?1)(2 ⁿ ?1)+1 is tight for s fixed and n sufficiently large. We make progress on this problem, obtaining the first upper bound which is within a constant factor of the lower bound.     

Three‐dimensional quadratic nonconforming brick element

A new nonconforming brick element with quadratic convergence for the energy norm is introduced. The nonconforming element consists of on a cube [?1,1]³, and 14 degree of freedom (DOF). Two types of DOF are introduced. One consists of the value at the eight vertices and six face‐centroids and the other consists of the value at the eight vertices and the integration value of six faces. Error estimates of optimal order are derived in both broken energy and norms for second‐order elliptic problems. If a genuine hexahedron, which is not a parallelepiped, is included in the partition, the proposed element is also convergent, but with a lower order. Copyright © 2013 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq 30: 158–174, 2014     

The number of k-colorings of a graph on a fixed surface

We prove that, for every fixed surface S, there exists a largest positive constant c such that every 5-colorable graph with n vertices on S has at least c·2ⁿ distinct 5-colorings. This is best possible in the sense that, for each sufficiently large natural number n, there is a graph with n vertices on S that has precisely c·2ⁿ distinct 5-colorings. For the sphere the constant c is , and for each other surface, it is a finite problem to determine c. There is an analogous result for k-colorings for each natural number k>5.     

Random polytopes in thed-dimensional cube

LetC ^d be the set of vertices of ad-dimensional cube,C ^d ={(x ₁, ...,x _d ):x _i =±1}. Let us choose a randomn-element subsetA(n) ofC ^d . Here we prove that Prob (the origin belongs to the convA(2d+x2d))=(x)+o(1) ifx is fixed andd . That is, for an arbitrary>0 the convex hull of more than (2+)d vertices almost always contains 0 while the convex hull of less than (2-)d points almost always avoids it.     

Vertex and Edge Orbits of Fibonacci and Lucas Cubes

The Fibonacci cube \({\Gamma_{n}}\) is obtained from the n-cube Q _n by removing all the vertices that contain two consecutive 1s. If, in addition, the vertices that start and end with 1 are removed, the Lucas cube \({\Lambda_{n}}\) is obtained. The number of vertex and edge orbits, the sets of the sizes of the orbits, and the number of orbits of each size, are determined for the Fibonacci cubes and the Lucas cubes under the action of the automorphism group. In particular, the set of vertex orbit sizes of \({\Lambda_{n}}\) is \({\{k \geq 1; k |n\} \cup \{k \geq 18; k |2n\}}\), the number of vertex orbits of \({\Lambda_{n}}\) of size k, where k is odd and divides n, is equal to \({\sum_{d | k} \mu (\frac{k}{d})F_{\lfloor{\frac{d}{2}}\rfloor+2}}\), and the number of edge orbits of \({\Lambda_{n}}\) is equal to the number of vertex orbits of \({\Gamma_{n-3}}\). Dihedral transformations of strings and primitive strings are essential tools to prove these results.     

The treewidth and pathwidth of hypercubes

The d-dimensional hypercube, H_d, is the graph on 2^d vertices, which correspond to the 2^dd-vectors whose components are either 0 or 1, two of the vertices being adjacent when they differ in just one coordinate. The notion of Hamming graphs (denoted by ) generalizes the notion of hypercubes: The vertices correspond to the q^dd-vectors where the components are from the set {0,1,2,…,q-1}, and two of the vertices are adjacent if and only if the corresponding vectors differ in exactly one component. In this paper we show that the and the .     

Lambert Cubes Generating Discrete Reflection Groups

A Lambert cube Q(α,β,γ) is a combinatorial cube with dihedral angles α, β, and γ assigned to the three mutually noncomplanar edges and right angles at the remaining edges. In this paper, we classify the Lambert cubes in S³, $\mathbb{E}^3 $ , and $\mathbb{H}^3 $ such that the group G ^Q generated by the reflections with respect to the faces of a cube Q is discrete.     

A Note on the Minimal Volume of Almost Cubic Parallelepipeds

   Abstract. We prove that the best way to reduce the volume of the n -dimensional unit cube by a linear transformation that maps each of the main vertices

Rhombi inscribed in simple closed curves

We show that given any simple closed curveJ in ² and any lineL, the curveJ contains the four vertices of some rhombusR with two sides parallel toL. Furthermore, the cyclic order of the vertices ofR agrees with their cyclic order onJ. We also show that the diameters of the rhombi so produced (one for each lineL) may be bounded away from zero.     

A combinatorial approach for Keller's conjecture

The statement, that in a tiling by translates of ann-dimensional cube there are two cubes having common (n-1)-dimensional faces, is known as Keller's conjecture. We shall prove that there is a counterexample for this conjecture if and only if the following graphs _n has a 2 ⁿ size clique. The 4 ⁿ vertices of _n aren-tuples of integers 0, 1, 2, and 3. A pair of thesen-tuples are adjacent if there is a position at which the difference of the corresponding components is 2 modulo 4 and if there is a further position at which the corresponding components are different. We will give the size of the maximal cliques of _n forn5.     

Lebesgue constants of multiple de la Vallée-Poussin sums over polyhedra

One considers linear summation methods for the multiple Fourier series the multidimensional analogues of the de la Vallé-Poussin sums. The summation of the Fourier series is carried out over the homotheties of an m-dimensional starshaped polyhedron . It is shown that if has rational vertices, then the Lebesgue constants of the considered methods, with the accuracy of O((p+1)^–1. log^m–1 (n+2)) are equal to where is the Fourier transform of the function . The exact value of the principal term of the Lebesgue constant is computed in two particular cases: 1) is obtained from an m-dimensional cube by means of a linear nonsingular transformation; 2) =0. is an m-dimensional simplex.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 125, pp. 154–165, 1983.