Recent zbMATH articles in MSC 06https://zbmath.org/atom/cc/062023-09-22T14:21:46.120933ZWerkzeugThe \(h^\ast\)-polynomial of the order polytope of the zig-zag posethttps://zbmath.org/1517.050082023-09-22T14:21:46.120933Z"Coons, Jane Ivy"https://zbmath.org/authors/?q=ai:coons.jane-ivy"Sullivant, Seth"https://zbmath.org/authors/?q=ai:sullivant.sethSummary: We construct a family of shellings for the canonical triangulation of the order polytope of the zig-zag poset. This gives a new combinatorial interpretation for the coefficients in the numerator of the Ehrhart series of this order polytope in terms of the swap statistic on alternating permutations. We also offer an alternate proof of this result using the techniques of rank selection. Finally, we show that the sequence of coefficients of the numerator of this Ehrhart series is symmetric and unimodal.Successive vertex orderings of fully regular graphshttps://zbmath.org/1517.050892023-09-22T14:21:46.120933Z"Fang, Lixing"https://zbmath.org/authors/?q=ai:fang.lixing"Huang, Hao"https://zbmath.org/authors/?q=ai:huang.hao.4|huang.hao|huang.hao.1|huang.hao.2|huang.hao.3"Pach, János"https://zbmath.org/authors/?q=ai:pach.janos"Tardos, Gábor"https://zbmath.org/authors/?q=ai:tardos.gabor"Zuo, Junchi"https://zbmath.org/authors/?q=ai:zuo.junchiSummary: A graph \(G=(V,E)\) is called fully regular if for every independent set \(I\subset V\), the number of vertices in \(V\setminus I\) that are not connected to any element of \(I\) depends only on the size of \(I\). A linear ordering of the vertices of \(G\) is called successive if for every \(i\), the first \(i\) vertices induce a connected subgraph of \(G\). We give an explicit formula for the number of successive vertex orderings of a fully regular graph.
As an application of our results, we give alternative proofs of two theorems of \textit{R. Stanley} [``Counting `connected' edge orderings (shellings) of the complete graph'', \url{https://mathoverflow.net/questions/297411/counting-connected-edge-orderings-shellings-of-the-complete-graph}] and \textit{Y. Gao} and \textit{J. Peng} [J. Algebr. Comb. 54, No. 1, 17--37 (2021; Zbl 07380961)], determining the number of linear edge orderings of complete graphs and complete bipartite graphs, respectively, with the property that the first \(i\) edges induce a connected subgraph.
As another application, we give a simple product formula for the number of linear orderings of the hyperedges of a complete 3-partite 3-uniform hypergraph such that, for every \(i\), the first \(i\) hyperedges induce a connected subgraph. We found similar formulas for complete (non-partite) 3-uniform hypergraphs and in another closely related case, but we managed to verify them only when the number of vertices is small.Point functions on semilattieshttps://zbmath.org/1517.060012023-09-22T14:21:46.120933Z"Parvatov, N. G."https://zbmath.org/authors/?q=ai:parvatov.nikolai-georgievichSummary: Fundamental functions classes on semilatties are studied.A set-theoretic proof of the representation of MV-algebras by sheaveshttps://zbmath.org/1517.060022023-09-22T14:21:46.120933Z"Estrada, Alejandro"https://zbmath.org/authors/?q=ai:estrada.alejandro"Poveda, Yuri A."https://zbmath.org/authors/?q=ai:poveda.yuri-aSummary: In this paper, we provide a set-theoretic proof of the general representation theorem for MV-algebras, which was developed by \textit{E. J. Dubuc} and \textit{Y. A. Poveda} in 2010 [Ann. Pure Appl. Logic 161, No. 8, 1024--1046 (2010; Zbl 1229.06006)]. The theorem states that every MV-algebra is isomorphic to the MV-algebra of all global sections of its prime spectrum. We avoid using topos theory and instead rely on basic concepts from MV-algebras, topology and set theory.Two notions of MV-algebraic semisimplicity relative to fixed MV-chainshttps://zbmath.org/1517.060032023-09-22T14:21:46.120933Z"Lele, Celestin"https://zbmath.org/authors/?q=ai:lele.celestin"Nganou, Jean B."https://zbmath.org/authors/?q=ai:nganou.jean-bernard"Wagoum, Jean M."https://zbmath.org/authors/?q=ai:wagoum.jean-mSummary: We initiate a study of two general concepts of semisimplicity for MV-algebras by replacing the standard MV-algebra \([0,1]\) with an arbitrary MV-chain \(\mathbf{C}\). These generalised notions are called \(\mathbf{C}\)-semisimple MV-algebras and \(\mathfrak{m}\)-semisimple MV-algebras. We obtain several of their characterisations and explore in more-depth the case of perfect MV-chains.On lax protomodularity for \(\mathsf{Ord}\)-enriched categorieshttps://zbmath.org/1517.180042023-09-22T14:21:46.120933Z"Clementino, Maria Manuel"https://zbmath.org/authors/?q=ai:clementino.maria-manuel"Montoli, Andrea"https://zbmath.org/authors/?q=ai:montoli.andrea"Rodelo, Diana"https://zbmath.org/authors/?q=ai:rodelo.dianaSummary: Our main focus concerns a possible lax version of the algebraic property of protomodularity for \(\mathsf{Ord}\)-enriched categories. Having in mind the role of comma objects in the enriched context, we consider some of the characteristic properties of protomodularity with respect to comma objects instead of pullbacks. We show that the equivalence between protomodularity and certain properties on pullbacks also holds when replacing conveniently pullbacks by comma objects in any finitely complete category enriched in \(\mathsf{Ord}\), and propose to call lax protomodular such \(\mathsf{Ord}\)-enriched categories. We conclude by studying this sort of lax protomodularity for the category \(\mathsf{OrdAb}\) of preordered abelian groups, equipped with a suitable \(\mathsf{Ord}\)-enrichment, and show that \(\mathsf{OrdAb}\) fulfills the equivalent lax protomodular properties with respect to the weaker notion of \textit{precomma object}; we call such categories lax preprotomodular.On the topology of bi-cyclopermutohedrahttps://zbmath.org/1517.510102023-09-22T14:21:46.120933Z"Deshpande, Priyavrat"https://zbmath.org/authors/?q=ai:deshpande.priyavrat"Manikandan, Naageswaran"https://zbmath.org/authors/?q=ai:manikandan.naageswaran"Singh, Anurag"https://zbmath.org/authors/?q=ai:singh.anurag\textit{G. Yu. Panina} [Proc. Steklov Inst. Math. 288, No. 1, 132--144 (2015; Zbl 1322.51013)] has introduced an \((n-2)\)-dimensional regular CW complex whose \(k\)-cells are labeled by cyclically ordered partitions of \(\{1, 2, \ldots, n + 1\}]\) into \((n + 1-k)\) non-empty parts, where \((n + 1-k) > 2\) -- the boundary relations in the complex corresponding to the orientation preserving refinement of partitions -- called a cyclopermutohedron and denoted by \(CP_{n+1}\). Using discrete Morse theory, \textit{I. Nekrasov} et al. [Eur. J. Math. 2 , no. 3, 835--852 (2016; Zbl 1361.51015)] showed that the homology groups \(H_i(CP_{n+1})\) are torsion free for all \(i\geq 0\) and computed their Betti numbers.
\(CP_{n+1}\) admits a free \({\mathbb Z}_2\) action; the quotient space \(CP_{n+1}/{\mathbb Z}_2\) is called a bi-cyclopermutohedron and denoted by \(QP_{n+1}\). The aim of this paper is to compute the \({\mathbb Z}_2\)- and the \({\mathbb Z}\)-homology groups of \(QP_{n+1}\).
Reviewer: Victor V. Pambuccian (Glendale)Geometric inequalities for anti-blocking bodieshttps://zbmath.org/1517.520042023-09-22T14:21:46.120933Z"Artstein-Avidan, Shiri"https://zbmath.org/authors/?q=ai:artstein-avidan.shiri"Sadovsky, Shay"https://zbmath.org/authors/?q=ai:sadovsky.shay"Sanyal, Raman"https://zbmath.org/authors/?q=ai:sanyal.ramanA convex body \(K\subset\mathbb{R}^n_{+}\) is called anti-blocking if for all \(y\in K\) and \(x\in \mathbb{R}^n_{+}\) with \(x_i\leq y_i\) for all \(i=1,\dots,n\), it holds that \(x\in K\). By definitions, 1-unconditional convex bodies and anti-blocking bodies are in one-to-one correspondence. The class of locally anti-blocking bodies is defined to be those bodies in \(\mathbb{R}^n\) such that all of their orthants are anti-blocking.
In the present paper, the authors investigate the structure of locally anti-blocking bodies and use it to show various volume and mixed volume inequalities for this class of bodies. More precisely, they prove that Godbersen's conjecture, near-optimal bounds on Mahler volumes, Saint-Raymond-type inequalities on mixed volumes, and reverse Kleitman inequalities for mixed volumes all hold for the class of (locally) anti-blocking bodies.
Reviewer: Niufa Fang (Chongqing)Johnstone-Gleason covers for partially ordered setshttps://zbmath.org/1517.540092023-09-22T14:21:46.120933Z"Abashidze, Vakhtang"https://zbmath.org/authors/?q=ai:abashidze.vakhtangThe classical Gleason cover \(\tilde{X}\) of a compact Hausdorff space \(X\) is the Stone dual of the complete Boolean algebra of its regular closed sets. \(\tilde{X}\) is an extremally disconnected compact Hausdorff space equipped with a continuous surjection \(p \colon \tilde{X} \to X\) with the property that every other continuous surjection from an extremally disconnected compact Hausdorff space onto \(X\) factors through \(p\) [\textit{A. M. Gleason}, Ill. J. Math. 2, 482--489 (1958; Zbl 0083.17401)].
Several authors have introduced various generalizations of this construction to many classes of spaces (usually referred to as an \textit{absolute} of the space). Further, in 1980, Johnstone introduced a construction of the Gleason cover for an arbitrary elementary topos which in particular provides a certain version of absolute for any topological space and, more generally, for locales.
In the paper under review, the author investigates properties of the Gleason cover in case of arbitrary partially ordered sets with the Alexandroff topology, that is, (not necessarily sober) \(T_0\) Alexandroff spaces. First, the notion of co-local homeomorphism for such spaces is introduced, and it is proved that for every finite \(T_0\) topological space \(X\) there exists a unique irreducible co-local homeomorphism \(p \colon \tilde{X}\to X\) from a finite extremally disconnected space \(\tilde{X}\) onto \(X\). Next, this approach is extended to Alexandroff topologies of arbitrary partially ordered sets. When this topology is sober, the generalization is straightforward, it merely repeats that of the finite case. However, for non-sober topologies, the Gleason cover will not necessarily produce a spatial locale, let alone an Alexandroff space of some other poset.
The paper ends with characterizations of posets for which the Gleason cover of the corresponding Alexandroff space is itself Alexandroff. Namely, the following theorem is proved:
Theorem 4.13. The Gleason cover of an Alexandroff topological space \(X\) is an Alexandroff space iff for any \(x\in X\) and for any infinite antichain \(S \subseteq\, \uparrow\! x\) there exist \(y_1, y_2 \in S\) such that \(\, \uparrow\! y_1\ \cap \uparrow\! y_2 \neq \emptyset\).
Reviewer: Jorge Picado (Coimbra)New families of hyperbolic twisted torus knots with generalized torsionhttps://zbmath.org/1517.570062023-09-22T14:21:46.120933Z"Himeno, Keisuke"https://zbmath.org/authors/?q=ai:himeno.keisuke"Teragaito, Masakazu"https://zbmath.org/authors/?q=ai:teragaito.masakazuThe existence of an element of finite order precludes a group from being bi-ordered, but so does the existence of a set of conjugates of a non-trivial element whose product in some order is the identity. Finding such a product in the groups of various classes of hyperbolic twisted torus knots is the point of this work. Such an element is called a generalized torsion element. (It is known that all knot groups can be right-ordered.)
A twisted torus knot is, roughly speaking, a torus knot \(T(p, q)\) on which \(r\) adjacent strands have been cut, given \(s\) full right-handed twists and then reattached. The quadruple \(T(p, q; r, s)\) denotes such a twisted torus knot. Here \(p > q> 1\), \(r < q\) and \(s \geq 1\). The new families of hyperbolic twisted torus knots which the authors find whose groups contain generalized torsion elements are the following:
1. \(T(5m+2, 5; 3, 1)\) for \(m\geq 1\),
2. \(T(5m-2, 5; 3, 1)\) for \(m \geq 2\),
3. \(T(5m+2, 5; 4, 1)\) for \(m \geq 1\),
4. \(T(5m-2, 5; 4, 1)\) for \(m \geq 2\),
and for \(r\geq 2\),
1. \(T(r+2, r+1; r, s)\) for \(s \geq 2\),
2. \(T(m(r+1)+1, r+1; r, 2)\) for \(m \geq 2\),
3. \(T(2r+1, r+1; r, s)\) for \(s \geq 1\),
4. \(T(m(r+1)-1, r+1; r, 1)\) for \(m \geq 3\),
(Thus in these last \(4\) cases \(r\) can be arbitrarily large.)
As a consequence, none of these \(8\) families of knots have a group which can be bi-ordered.
The authors achieve their results by careful selection of certain presentations of the knot groups in question, and application of the following general lemma:
Lemma 3.2. Let \(G\) be a group generated by two elements \(x\) and \(y\), and let \(w\) consist of \(x^{\pm 1}\) and \(y\). Suppose that \(G\) is not abelian. If \([x, w] = 1\), then the commutator \([x, y]\) is a generalized torsion element in \(G\).
Reviewer: Lee P. Neuwirth (Princeton)The Scott model of PCF in univalent type theoryhttps://zbmath.org/1517.680692023-09-22T14:21:46.120933Z"de Jong, Tom"https://zbmath.org/authors/?q=ai:de-jong.tom-jSummary: We develop the Scott model of the programming language PCF in univalent type theory. Moreover, we work constructively and predicatively. To account for the non-termination in PCF, we use the lifting monad (also known as the partial map classifier monad) from topos theory, which has been extended to univalent type theory by Escardó and Knapp. Our results show that lifting is a viable approach to partiality in univalent type theory. Moreover, we show that the Scott model can be constructed in a predicative and constructive setting. Other approaches to partiality either require some form of choice or quotient inductive-inductive types. We show that one can do without these extensions.Synthetic topology in homotopy type theory for probabilistic programminghttps://zbmath.org/1517.680722023-09-22T14:21:46.120933Z"Bidlingmaier, Martin E."https://zbmath.org/authors/?q=ai:bidlingmaier.martin-e"Faissole, Florian"https://zbmath.org/authors/?q=ai:faissole.florian"Spitters, Bas"https://zbmath.org/authors/?q=ai:spitters.basSummary: The ALEA Coq library formalizes measure theory based on a variant of the Giry monad on the category of sets. This enables the interpretation of a probabilistic programming language with primitives for sampling from discrete distributions. However, continuous distributions have to be discretized because the corresponding measures cannot be defined on all subsets of their carriers. This paper proposes the use of synthetic topology to model continuous distributions for probabilistic computations in type theory. We study the initial \(\sigma\)-frame and the corresponding induced topology on arbitrary sets. Based on these intrinsic topologies, we define valuations and lower integrals on sets and prove versions of the Riesz and Fubini theorems. We then show how the Lebesgue valuation, and hence continuous distributions, can be constructed.Convexity and order in probabilistic call-by-name FPChttps://zbmath.org/1517.682172023-09-22T14:21:46.120933Z"Rennela, Mathys"https://zbmath.org/authors/?q=ai:rennela.mathysSummary: Kegelspitzen are mathematical structures coined by Keimel and Plotkin, in order to encompass the structure of a convex set and the structure of a dcpo. In this paper, we ask ourselves what are Kegelspitzen the model of. We adopt a categorical viewpoint and show that Kegelspitzen model stochastic matrices onto a category of domains. Consequently, Kegelspitzen form a denotational model of pPCF, an abstract functional programming language for probabilistic computing. We conclude the present work with a discussion of the interpretation of (probabilistic) recursive types, which are types for entities which might contain other entities of the same type, such as lists and trees.Simon's theorem for scattered wordshttps://zbmath.org/1517.683132023-09-22T14:21:46.120933Z"Carton, Olivier"https://zbmath.org/authors/?q=ai:carton.olivier"Pouzet, Maurice"https://zbmath.org/authors/?q=ai:pouzet.mauriceSummary: In this paper, we extend Simon's theorem to scattered words. We consider words whose length is a countable scattered linear orderings. We give an algebraic characterization of Boolean combinations of \(\preccurlyeq\)-upper sets where \(\preccurlyeq\) is the subword relation, also known as embedding on words.
For the entire collection see [Zbl 1398.68030].A fast and simple algorithm for identifying 2-monotonic positive Boolean functionshttps://zbmath.org/1517.684072023-09-22T14:21:46.120933Z"Makino, Kazuhisa"https://zbmath.org/authors/?q=ai:makino.kazuhisa"Ibaraki, Toshihide"https://zbmath.org/authors/?q=ai:ibaraki.toshihideSummary: Consider the problem of identifying \(\min T(f)\) and \(\max F(f)\) of a positive (i.e., monotone) Boolean function \(f\), by using membership queries only, where \(\min T(f)\) (\(\max F(f)\)) denotes the set of minimal true vectors (maximal false vectors) of \(f\). As the existence of a polynomial total time algorithm (i.e., polynomial time in the length of input and output) for this problem is still open, we consider here a restricted problem: given an unknown positive function \(f\) of \(n\) variables, decide whether \(f\) is 2-monotonic or not, and if \(f\) is 2-monotonic, output both \(\min T(f)\) and \(\max F(f)\). For this problem, we propose a simple algorithm, which is based on the concept of maximum latency, and show that it uses \(O(n^2 m)\) time and \(O(n^2 m)\) queries, where \(m=| \min T(f)|+| \max F(f)|\). This answers affirmatively the conjecture raised in [\textit{E. Boros} et al., Lect. Notes Comput. Sci. 557, 104--115 (1991; \url{doi:10.1007/3-540-54945-5_54}); SIAM J. Comput. 26, No. 1, 93--109 (1997; Zbl 0868.68095), contained in Zbl 0825.00117], and is an improvement over the two algorithms discussed therein: one uses \(O(n^3 m)\) time and \(O(n^3 m)\) queries, and the other uses \(O(nm^2+n^2 m)\) time and \(O(nm)\) queries.
For the entire collection see [Zbl 0856.00037].Group of information differences in the extended parastatistics of quantum nonextensive systemshttps://zbmath.org/1517.810322023-09-22T14:21:46.120933Z"Zaripov, R. G."https://zbmath.org/authors/?q=ai:zaripov.rinat-g(no abstract)Efficient public-key encryption with equality test from latticeshttps://zbmath.org/1517.941252023-09-22T14:21:46.120933Z"Li, Qinyi"https://zbmath.org/authors/?q=ai:li.qinyi"Boyen, Xavier"https://zbmath.org/authors/?q=ai:boyen.xavierSummary: Public-key encryption with equality (PKEET) test enables testing if two ciphertexts, possibly under two different public keys, encrypt the same messages. Recent research on PKEET considers the setting where the testing ability is delegated to semi-trusted parties to negate unfettered chosen-plaintext attacks. In this work, we revise and enhance the PKEET security model, and introduce a new property of unmaskability which further prevents an attacker from skirting the test. We then propose a simple and efficient PKEET system with adaptive chosen-ciphertext security, provably secure under our revised security model, from either plain or ring lattice assumptions. The construction adopts a direct approach which significantly departs from the existing way of building such systems. Compared with existing literature, our system relies on weaker learning-with-errors assumptions while also being more efficient and providing better security.Series parallel decomposition of a system of incompletely specified Boolean functionshttps://zbmath.org/1517.942172023-09-22T14:21:46.120933Z"Pottosin, Yu. V."https://zbmath.org/authors/?q=ai:pottosin.yu-v"Shestakov, E. A."https://zbmath.org/authors/?q=ai:shestakov.e-aSummary: The decomposition problem for a system of incompletely specified Boolean functions is considered. The concept of function dependence on some arguments is introduced for appreciating the complexity of decomposition components. A method for series parallel decomposition of a system of incompletely specified Boolean functions is suggested. The peculiarity of the method is that the arguments of components are not given and are found in the process of decomposition.Certificate complexity of elementary symmetric Boolean functionshttps://zbmath.org/1517.942202023-09-22T14:21:46.120933Z"Zhang, Jing"https://zbmath.org/authors/?q=ai:zhang.jing"Li, Yuan"https://zbmath.org/authors/?q=ai:li.yuanSummary: Boolean functions have important applications in information technology and computer science. Certificate complexity is an important combinatorial measure of Boolean function complexity. In this paper, we first introduce many concise and efficient notations then we study the elementary symmetric Boolean functions and obtain their certificate complexities when their degrees are odd or powers of 2. We show that both upper and lower bounds of certificate complexities can be attained.