Recent zbMATH articles in MSC 52Bhttps://www.zbmath.org/atom/cc/52B2021-03-30T15:24:00+00:00WerkzeugA periodic isoperimetric problem related to the unique games conjecture.https://www.zbmath.org/1455.600292021-03-30T15:24:00+00:00"Heilman, Steven"https://www.zbmath.org/authors/?q=ai:heilman.steven-mSummary: We prove the endpoint case of a conjecture of \textit{S. Khot} and \textit{D. Moshkovitz} [in: Proceedings of the 48th annual ACM SIGACT symposium on theory of computing, STOC '16, Cambridge, MA, USA, June 19--21, 2016. New York, NY: Association for Computing Machinery (ACM). 63--76 (2016; Zbl 1373.68240)] related to the unique games conjecture, less a small error. Let \(n\geq 2\). Suppose a subset \(\Omega\) of \(n\)-dimensional Euclidean space \(\mathbb{R}^n\) satisfies \(-\Omega=\Omega^c\) and \(\Omega+v=\Omega^c\) (up to measure zero sets) for every standard basis vector \(v\in\mathbb{R}^n\). For any \(x=(x_1,\dots,x_n)\in\mathbb{R}^n\) and for any \(q\geq 1\), let \(||x||^q_q=|x_1|^q+\cdots+|x_n|^q\) and let \(\gamma_n(x)=(2\pi)^{-n/2}e^{-||x||^2_2/2}\). For any \(x\in\partial\Omega\), let \(N(x)\) denote the exterior normal vector at \(x\) such that \(\Vert N(x)\Vert_2=1\). Let \(B=\{x\in\mathbb{R}^n:\sin(\pi(x_1+\cdots+x_n))\geq 0\}\). Our main result shows that \(B\) has the smallest Gaussian surface area among all such subsets \(\Omega\), less a small error: \(\int_{\partial\Omega}\gamma_n(x)\mathrm{d}x\geq (1-6\times 10^{-9})\int_{\partial B}\gamma_n(x)\mathrm{d}x+\int_{\partial\Omega}\left(1-\frac{||N(x)||_1}{\sqrt n}\right)\gamma_n(x)\mathrm{d}x\). In particular, \(\int_{\partial\Omega}\gamma_n(x)\mathrm{d}x\geq(1-6\times 10^{-9})\int_{\partial B}\gamma_n(x)\mathrm{d}x\). Standard arguments extend these results to a corresponding weak inequality for noise stability. Removing the factor \(6\times 10^{-9}\) would prove the endpoint case of the Khot-Moshkovitz conjecture. Lastly, we prove a Euclidean analogue of the Khot and Moshkovitz conjecture. The full conjecture of Khot and Moshkovitz provides strong evidence for the truth of the unique games conjecture, a central conjecture in theoretical computer science that is closely related to the P versus NP problem. So, our results also provide evidence for the truth of the unique games conjecture. Nevertheless, this paper does not prove any case of the unique games conjecture.Lattice simplices with a fixed positive number of interior lattice points: a nearly optimal volume bound.https://www.zbmath.org/1455.520102021-03-30T15:24:00+00:00"Averkov, Gennadiy"https://www.zbmath.org/authors/?q=ai:averkov.gennadiy"Krümpelmann, Jan"https://www.zbmath.org/authors/?q=ai:krumpelmann.jan-alexander"Nill, Benjamin"https://www.zbmath.org/authors/?q=ai:nill.benjaminGiven a \textit{lattice polytope} \(P \subseteq \mathbb{R}^d\) with a positive number \(k = \#\left(\mathrm{int}(P) \cap \mathbb{Z}^d\right) \geq 1\) of interior lattice points in \(P\), the problem of deriving a sharp upper bound on its volume can be traced back to a work of \textit{D. Hensley} [Pac. J. Math. 105, 183--191 (1983; Zbl 0471.52006)].
In recent years, this problem has received a lot of attention, not only because of its natural appeal but also from its connections to integer programming and toric geometry.
For the precise formulation of the main conjecture that is tackled in the paper at hand, define \(p(d,k)\) and \(s(d,k)\) as the maximal volume of a lattice polytope and lattice simplex in \(\mathbb{R}^d\), respectively, with a given number \(k\geq1\) of interior lattice points.
The conjecture is that \(p(d,k) = s(d,k) = \mathrm{vol}(S_{d,k})\), where \(S_{d,k}\) denotes the so-called Zaks-Perles-Wills-simplex.
The volume of these simplices \(S_{d,k}\) is a linear function in \(k\), but a quadratic function in the number \(s_d\), which denotes an element in the double-exponentially growing \textit{Sylvester sequence} \((s_i)_{i=1,2,\dots}\).
The main result of the paper is to show that \(\mathrm{vol}(S_{d,k}) \leq s(d,k) \leq (d+1)\mathrm{vol}(S_{d,k})\).
This major advance solves said problem for the class of lattice simplices up to a linear factor in the dimension \(d\), and thus further supports the main conjecture.
The methods are based on the combination of the many insights regarding \(p(d,k)\) and \(s(d,k)\) that have been collected over the years, and in particular on a generalization of the elegant \textit{sum-product-inequalities} on the barycentric coordinates of an interior lattice point of a lattice simplex.
Reviewer: Matthias Schymura (Lausanne)Efficient explicit constructions of multipartite secret sharing schemes.https://www.zbmath.org/1455.942072021-03-30T15:24:00+00:00"Chen, Qi"https://www.zbmath.org/authors/?q=ai:chen.qi"Tang, Chunming"https://www.zbmath.org/authors/?q=ai:tang.chunming"Lin, Zhiqiang"https://www.zbmath.org/authors/?q=ai:lin.zhiqiangSummary: Multipartite secret sharing schemes are those having a multipartite access structure, in which the set of participants is divided into several parts and all participants in the same part play an equivalent role. Secret sharing schemes for multipartite access structures have received considerable attention due to the fact that multipartite secret sharing can be seen as a natural and useful generalization of threshold secret sharing.
This work deals with efficient and explicit constructions of ideal multipartite secret sharing schemes, while most of the known constructions are either inefficient or randomized. Most ideal multipartite secret sharing schemes in the literature can be classified as either hierarchical or compartmented. The main results are the constructions for ideal hierarchical access structures, a family that contains every ideal hierarchical access structure as a particular case such as the disjunctive hierarchical threshold access structure and the conjunctive hierarchical threshold access structure, and the constructions for compartmented access structures with upper bounds and compartmented access structures with lower bounds, two families of compartmented access structures.
On the basis of the relationship between multipartite secret sharing schemes, polymatroids, and matroids, the problem of how to construct a scheme realizing a multipartite access structure can be transformed to the problem of how to find a representation of a matroid from a presentation of its associated polymatroid. In this paper, we give efficient algorithms to find representations of the matroids associated to the three families of multipartite access structures. More precisely, based on know results about integer polymatroids, for each of the three families of access structures, we give an efficient method to find a representation of the integer polymatroid over some finite field, and then over some finite extension of that field, we give an efficient method to find a presentation of the matroid associated to the integer polymatroid. Finally, we construct ideal linear schemes realizing the three families of multipartite access structures by efficient methods.
For the entire collection see [Zbl 1428.94009].An FPTAS for the volume of some \(\mathcal{V} \)-polytopes -- it is hard to compute the volume of the intersection of two cross-polytopes.https://www.zbmath.org/1455.682732021-03-30T15:24:00+00:00"Ando, Ei"https://www.zbmath.org/authors/?q=ai:ando.ei"Kijima, Shuji"https://www.zbmath.org/authors/?q=ai:kijima.shujiA \(\mathcal{V} \)-polytope is a convex hull of a finite point set in \(\mathbb{R}^n\). A particular type of \(\mathcal{V} \)-polytope, called ``knapsack dual polytope'' is defined as \(P_{a}=\text{conv}\{\pm e_1, \pm e_2, ..., \pm e_n, a\}\), \(a\in \mathbb{Z}^n_{\geq 0}\). The authors constructively prove the following theorem: For any \(\varepsilon\), \((0 <\varepsilon <1)\), there is a deterministic algorithm that computes \(\hat{V}\) satisfying \(|1- \frac{\text{Vol}(P_a)}{\hat{V}}| \leq \varepsilon\) in \(O(n^{10}\varepsilon^{-6})\) time. This is the first result on designing a fully polynomial time approximation scheme for computing the volume of a \(\mathcal{V} \)-polytope, which is known to be \#P-hard.
Reviewer: Gabriela Cristescu (Arad)Computing the integer points of a polyhedron. II: Complexity estimates.https://www.zbmath.org/1455.520122021-03-30T15:24:00+00:00"Jing, Rui-Juan"https://www.zbmath.org/authors/?q=ai:jing.rui-juan"Moreno Maza, Marc"https://www.zbmath.org/authors/?q=ai:moreno-maza.marcSummary: Let \(K\) be a polyhedron in \(\mathbb R^d\), given by a system of \(m\) linear inequalities, with rational number coefficients bounded over in absolute value by \(L\). In this series of two papers, we propose an algorithm for computing an irredundant representation of the integer points of \(K\), in terms of ``simpler'' polyhedra, each of them having at least one integer point. Using the terminology of W. Pugh: for any such polyhedron \(P\), no integer point of its grey shadow extends to an integer point of \(P\). We show that, under mild assumptions, our algorithm runs in exponential time w.r.t. \(d\) and in polynomial w.r.t \(m\) and \(L\). We report on a software experimentation. In this series of two papers, the first one [the authors, ibid. 10490, 225--241 (2017; Zbl 1455.52011)] presents our algorithm and the second one discusses our complexity estimates.
For the entire collection see [Zbl 1371.68008].Computing the integer points of a polyhedron. I: Algorithm.https://www.zbmath.org/1455.520112021-03-30T15:24:00+00:00"Jing, Rui-Juan"https://www.zbmath.org/authors/?q=ai:jing.rui-juan"Moreno Maza, Marc"https://www.zbmath.org/authors/?q=ai:moreno-maza.marcSummary: Let \(K\) be a polyhedron in \(\mathbb R^d\), given by a system of \(m\) linear inequalities, with rational number coefficients bounded over in absolute value by \(L\). In this series of two papers, we propose an algorithm for computing an irredundant representation of the integer points of \(K\), in terms of ``simpler'' polyhedra, each of them having at least one integer point. Using the terminology of W. Pugh: for any such polyhedron \(P\), no integer point of its grey shadow extends to an integer point of \(P\). We show that, under mild assumptions, our algorithm runs in exponential time w.r.t. \(d\) and in polynomial w.r.t \(m\) and \(L\). We report on a software experimentation. In this series of two papers, the first one presents our algorithm and the second one [Zbl 1455.52012] discusses our complexity estimates.
For the entire collection see [Zbl 1371.68008].An excursion through discrete differential geometry. AMS short course on discrete differential geometry, San Diego, CA, USA, January 8--9, 2018.https://www.zbmath.org/1455.530452021-03-30T15:24:00+00:00"Crane, Keenan (ed.)"https://www.zbmath.org/authors/?q=ai:crane.keenanPublisher's description: Discrete Differential Geometry (DDG) is an emerging discipline at the boundary between mathematics and computer science. It aims to translate concepts from classical differential geometry into a language that is purely finite and discrete, and can hence be used by algorithms to reason about geometric data. In contrast to standard numerical approximation, the central philosophy of DDG is to faithfully and exactly preserve key invariants of geometric objects at the discrete level. This process of translation from smooth to discrete helps to both illuminate the fundamental meaning behind geometric ideas and provide useful algorithmic guarantees.
This volume is based on lectures delivered at the 2018 AMS Short Course ``Discrete Differential Geometry,'' held January 8--9, 2018, in San Diego, California.
The papers in this volume illustrate the principles of DDG via several recent topics: discrete nets, discrete differential operators, discrete mappings, discrete conformal geometry, and discrete optimal transport.
The articles of this volume will be reviewed individually.Fat-wedge filtration and decomposition of polyhedral products.https://www.zbmath.org/1455.550072021-03-30T15:24:00+00:00"Iriye, Kouyemon"https://www.zbmath.org/authors/?q=ai:iriye.kouyemon"Kishimoto, Daisuke"https://www.zbmath.org/authors/?q=ai:kishimoto.daisukeLet \(K\) be a finite simplicial complex with vertex set \([m]=\{1,\dots,m\}\).
For a sequence \((X_i,A_i)\) of pairs of spaces indexed by \(i\in[m]\), the polyhedral product \(\mathcal{Z}_K(X,A)\) is defined as \(\bigcup_{\sigma\in K}(X,A)^\sigma\), where \((X,A)^\sigma=Y_1\times\cdots\times Y_m\subset X_1\times\cdots\times X_m\); here \(Y_i=X_i\) if \(i\in\sigma\) and \(Y_i=A_i\) if \(i\not\in\sigma\).
This technical construction is interesting since, e.g., moment angle complexes, arrangements of real coordinate subspaces and their complements arise as special cases; moreover, cohomology rings and fundamental groups of polyhedral products occur in commutative algebra and geometric group theory.
The authors obtain general structural information about the homotopy types of polyhedral products, strengthening results of Bahri, Bendersky, Cohen, and Gitler [\textit{A. Bahri} et al., Adv. Math. 225, No. 3, 1634--1668 (2010; Zbl 1197.13021)].
The main focus is on the case where each \(X_i\) is a cone over the base space \(A_i\).
In a second train of thought the authors investigate what happens if the Alexander dual of \(K\) satisfies certain combinatorial properties (e.g., shellability) which imply (sequential) Cohen-Macaulayness.
Reviewer: Michael Joswig (Berlin)On classification of toric surface codes of dimension seven.https://www.zbmath.org/1455.140552021-03-30T15:24:00+00:00"Hussain, Naveed"https://www.zbmath.org/authors/?q=ai:hussain.naveed"Luo, Xue"https://www.zbmath.org/authors/?q=ai:luo.xue"Yau, Stephen S.-T."https://www.zbmath.org/authors/?q=ai:yau.stephen-shing-toung"Zhang, Mingyi"https://www.zbmath.org/authors/?q=ai:zhang.mingyi"Zuo, Huaiqing"https://www.zbmath.org/authors/?q=ai:zuo.huaiqingFollowing previous work on the classification of low-dimensional toric surface codes by \textit{S. S. T. Yau} and \textit{H. Zuo} [Appl. Algebra Eng. Commun. Comput. 20, No. 2, 175--185 (2009; Zbl 1174.94029)] and \textit{X. Luo} et al. [Finite Fields Appl. 33, 90--102 (2015; Zbl 1394.14017)] the main results of the paper under review extend the classification, up to monomial equivalence, of toric surface codes of dimension less than or equal to \(7\), with the monomial equivalence of some pairs of toric codes in this range still undetermined.
Reviewer: Felipe Zaldívar (Ciudad de México)The complete enumeration of 4-polytopes and 3-spheres with nine vertices.https://www.zbmath.org/1455.520082021-03-30T15:24:00+00:00"Firsching, Moritz"https://www.zbmath.org/authors/?q=ai:firsching.moritzSummary: We describe an algorithm to enumerate polytopes. This algorithm is then implemented to give a complete classification of combinatorial spheres of dimension 3 with 9 vertices and decide polytopality of those spheres. In order to decide polytopality, we generate polytopes by adding suitable points to polytopes with less than 9 vertices and therefore realize as many as possible of the combinatorial spheres as polytopes. For the rest, we prove non-realizability with techniques from oriented matroid theory. This yields a complete enumeration of all combinatorial types of 4-dimensional polytopes with 9 vertices. It is shown that all of those combinatorial types are rational: They can be realized with rational coordinates. We find 316 014 combinatorial spheres on 9 vertices. Of those, 274 148 can be realized as the boundary complex of a four-dimensional polytope and the remaining 41 866 are non-polytopal.Local orientation-preserving symmetry preserving operations on polyhedra.https://www.zbmath.org/1455.050632021-03-30T15:24:00+00:00"Goetschalckx, Pieter"https://www.zbmath.org/authors/?q=ai:goetschalckx.pieter"Coolsaet, Kris"https://www.zbmath.org/authors/?q=ai:coolsaet.kris"Van Cleemput, Nico"https://www.zbmath.org/authors/?q=ai:van-cleemput.nicolasSummary: Unifying approaches by amongst others Archimedes, Kepler, Goldberg, Caspar and Klug, Coxeter, and Conway, and extending on a previous formalization of the concept of local symmetry preserving (lsp) operations, we introduce a formal definition of local operations on plane graphs that preserve orientation-preserving symmetries, but not necessarily orientation-reversing symmetries. This operations include, e.g., the chiral Goldberg and Conway operations as well as all lsp operations. We prove the soundness of our definition as well as introduce an invariant which can be used to systematically construct all such operations. We also show sufficient conditions for an operation to preserve the connectedness of the plane graph to which it is applied.Counting integral points in polytopes via numerical analysis of contour integration.https://www.zbmath.org/1455.520092021-03-30T15:24:00+00:00"Hirai, Hiroshi"https://www.zbmath.org/authors/?q=ai:hirai.hiroshi"Oshiro, Ryunosuke"https://www.zbmath.org/authors/?q=ai:oshiro.ryunosuke"Tanaka, Ken'ichiro"https://www.zbmath.org/authors/?q=ai:tanaka.kenichiroSummary: In this paper, we address the problem of counting integer points in a rational polytope described by \(P(\mathbf{y}) = \{\mathbf{x} \in \mathbb{R}^m: A\mathbf{x}= \mathbf{y}, \, \mathbf{x} \geq 0\}\), where \(A\) is an \(n \times m\) integer matrix and \(\mathbf{y}\) is an \(n\)-dimensional integer vector. We study the \(Z\) transformation approach initiated in works by Brion and Vergne, Beck, and Lasserre and Zeron from the numerical analysis point of view and obtain a new algorithm on this problem. If \(A\) is nonnegative, then the number of integer points in \(P(\mathbf{y})\) can be computed in \(O(\operatorname{poly} (n,m, \| \mathbf{y} \|_\infty)(\| \mathbf{y} \|_\infty + 1)^n)\) time and \(O(\operatorname{poly} (n,m, \| \mathbf{y} \|_\infty))\) space. This improves, in terms of space complexity, a naive DP algorithm with \(O((\| \mathbf{y} \|_\infty + 1)^n)\)-size dynamic programming table. Our result is based on the standard error analysis of the numerical contour integration for the inverse \(Z\) transform and establishes a new type of an inclusion-exclusion formula for integer points in \(P(\mathbf{y})\).
We apply our result to hypergraph \(\mathbf{b}\)-matching and obtain an \(O(\operatorname{poly}(n,m,\|\mathbf{b}\|_\infty)(\|\mathbf{b}\|_\infty + 1)^{(1-1/k)n}\) time algorithm for counting \(\mathbf{b}\)-matchings in a \(k\)-partite hypergraph with \(n\) vertices and \(m\) hyperedges. This result is viewed as a \(\mathbf{b}\)-matching generalization of the classical result by Ryser for \(k= 2\) and its multipartite extension by Björklund and Husfeldt.Toric log del Pezzo surfaces with one singularity.https://www.zbmath.org/1455.140982021-03-30T15:24:00+00:00"Dais, Dimitrios I."https://www.zbmath.org/authors/?q=ai:dais.dimitrios-iSummary: This paper focuses on the classification (up to isomorphism) of all toric log Del Pezzo surfaces with exactly one singularity, and on the description of how they are embedded as intersections of finitely many quadrics into suitable projective spaces.The diagonal of the associahedra.https://www.zbmath.org/1455.180142021-03-30T15:24:00+00:00"Masuda, Naruki"https://www.zbmath.org/authors/?q=ai:masuda.naruki"Thomas, Hugh"https://www.zbmath.org/authors/?q=ai:thomas.hugh-ross"Tonks, Andy"https://www.zbmath.org/authors/?q=ai:tonks.andy"Vallette, Bruno"https://www.zbmath.org/authors/?q=ai:vallette.brunoThis paper has a threefold purpose.
\begin{itemize}
\item[1.] to introduce a general machinery to solve the problem of the approximation of the diagonal of \textit{face-coherent families of polytopes} (\S 2),
\item[2.] to give a complete proof for the case of the \textit{associahedra} (Theorem 1), and
\item[3.] to popularize the resulting \textit{magical formula} (Theorem 2).
\end{itemize}
The problem of the approximation of the diagonal of the associahedra lies at the crossroads of three clusters of domains.
\begin{itemize}
\item[1.] There are mathematicians inclined to apply it in their work of computing the homology of fibered spaces in algebraic topology [\textit{E. H. Brown jun.}, Ann. Math. (2) 69, 223--246 (1959; Zbl 0199.58201); \textit{A. Prouté}, Repr. Theory Appl. Categ. 2011, No. 21, 99 p. (2011; Zbl 1245.55007)], to construct tensor products of string field theories [\textit{M. R. Gaberdiel} and \textit{B. Zwiebach}, Nucl. Phys., B 505, No. 3, 569--624 (1997; Zbl 0911.53044); Phys. Lett., B 410, No. 2--4, 151--159 (1997; Zbl 0911.53046)], or to consider the product of Fukaya \(\mathcal{A}_{\infty}\)-categories in symplectic geometry [\textit{P. Seidel}, Fukaya categories and Picard-Lefschetz theory. Zürich: European Mathematical Society (EMS) (2008; Zbl 1159.53001); \textit{L. Amorim}, Int. J. Math. 28, No. 4, Article ID 1750026, 38 p. (2017; Zbl 1368.53057)].
\item[2.] The analogous result is known, within the kingdom of operad theory and homotopical algebra, in the differential graded context [\textit{S. Saneblidze} and \textit{R. Umble}, Homology Homotopy Appl. 6, No. 1, 363--411 (2004; Zbl 1069.55015); \textit{L. J. Billera} and \textit{B. Sturmfels}, Ann. Math. (2) 135, No. 3, 527--549 (1992; Zbl 0762.52003)].
\item[3.] This result is appreciated conceptualy as a new development in the theory of \textit{fiber polytopes} [loc. cit.] by combinatorists and
discrete geometers.
\end{itemize}
The possible ways of iteraring a binary product are to be encoded by planar binary trees, the associativity relation being interpreted as an order relation, which encouraged Dov Tamari to introduce the so-called \textit{Tamari lattice} [\textit{D. Tamari}, Nieuw Arch. Wiskd., III. Ser. 10, 131--146 (1962; Zbl 0109.24502)]. These lattices are to be realized by associahedra in the sense that their \(1\)-skeleton is the Hasse diagram of the Tamari lattice [\textit{C. Ceballos} et al., Combinatorica 35, No. 5, 513--551 (2015; Zbl 1389.52013)]. For loop spaces, composition fails to be strictly associative due to the different parametrizations, but this failure is governed by an infinite sequence of higher homotopies, which was made precise by \textit{J. D. Stasheff} [Trans. Am. Math. Soc. 108, 275--292, 293--312 (1963; Zbl 0114.39402)], introducing a family of curvilinear polytopes called the \textit{Stascheff polytopes}, whose combinatorics coincides with the associahedra. Stascheff's work opened the door to the study of homotopical algebra by means of operad-like objects, summoning [\textit{J. M. Boardman} and \textit{R. M. Vogt}, Homotopy invariant algebraic structures on topological spaces. Berlin-Heidelberg-New York: Springer-Verlag (1973; Zbl 0285.55012)] and [\textit{J. P. May}, The geometry of iterated loop spaces. Berlin-Heidelberg-New York: Springer-Verlag (1972; Zbl 0244.55009)] in particular, the latter of which introduced the \textit{little disks} operads playing a key role in many domains nowadays. In dimension \(1\), this gives the \textit{little intervals} operad, a finite-dimensional topological operad pervious to Stascheff's theory, whose operad structure is given by scaling a configuration of intervals in order to insert it into another interval. So far there has been no operad structure on any family of convex polytopal realizations of the associahedra in the literature, though there should be a rainbow bridge
between operad theory as well as homotopy theories on the one hand and combinatorics as well as discrete geometry on the other.
Since the set-theoretic diagonal of a polytope fails to be cellular in general, the authors need to find a \textit{cellular approximation to the
diagonal}, that is to say, a cellular map from the polytope to its cartesian square homotopic to the diagonal. For a coherent family of polytopes, it is highly challenging to find a family of diagonals compatible with the combinatorics of faces. In the case of the first face-coherent family of polytopes, the geometric simplices, such a diagronal map is given by the classical \textit{Alexander-Whitney map} [\textit{S. Eilenberg} and \textit{J. A. Zilber}, Am. J. Math. 75, 200--204 (1953; Zbl 0050.17301); \textit{N. E. Steenrod}, Ann. Math. (2) 48, 290--320 (1947; Zbl 0030.41602)]. For the next family given by cubes, a coassociative approximation to the diagonal is straightforward [\textit{J.-P. Serre}, Ann. Math. (2) 54, 425--505 (1951; Zbl 0045.26003)]. The associahedra form the face-coherent family of polytopes coming next in terms of further truncations of the simplices or of combinatorial complexity. While a face of a simplex or a cube is a simplex or a cube of lower dimension, a face of an associahedra is a product of associahedra of lower dimensions, which makes the problem of the
approximation of the diagonal in this turn highly intricate. The two-fold principal result of the paper (Theorem 1) is an explicit operad structure on the \textit{Loday realizations} of the associahedra together with a compatible approximation to the diagonal.
There is a dichotomy between pointwise and cellular formulas. To investigate
their relationship and to make precise the various face-coherent properties,
the authors introduce the \textit{category of polytopes with subdivision}. The
definition of the diagonal maps comes from the theory of fiber polytopes so
that an induced polytopal subdivision of the associahedra is obtained, for
which the authors establishes a magical formula in the verbalism of Jean-Louis
Loday. It is made up of the pairs of cells of matching dimensions and
comparable order under the Tamari order (Theorem 2).
A synopsis of the paper consisting of four sections goes as follows. \S 1
recalls the main relevant notions, introducing the category of polytopes in
which the authors work. \S 2 gives a canonical definition of the diagonal map
for positively oriented polytopes, addressing their cellular properties. \S 3
endows the family of Loday realizations of the associahedra with a
nonsymmetric operad structure compatible with the diagonal maps. \S 4
establishes the magical celluar formula for the diagonal map of the associahedra.
Reviewer: Hirokazu Nishimura (Tsukuba)