Search

A triangular tile latching system consists of a set Σ of equilateral triangular tiles with at least one latchable side and an attachment rule which permits two tiles to get latched along a latchable side. In this paper we determine the language generated by a triangular tile latching system in terms of planar graphs. [ABSTRACT FROM AUTHOR]

This article explores the Erdős-Szekeres conjecture, a mathematical problem concerning geometric patterns in sets of points. The conjecture was proposed in 1935 and has been the focus of extensive research. Various mathematicians, including Tóth, Valtr, and Suk, have made significant contributions to proving the conjecture. Suk's proof is described as a moment of brilliance in applying the right tools. The article concludes with a quote from Erdős emphasizing the importance of an open mind in mathematics. [Extracted from the article]

For sets of n points, n even, in general position in the plane, we consider straight-line drawings of perfect matchings on them. It is well known that such sets admit at least C n / 2 different plane perfect matchings, where C n / 2 is the n/2-th Catalan number. Generalizing this result we are interested in the number of drawings of perfect matchings which have k crossings. We show the following results. (1) For every k ≤ 1 64 n 2 - 35 32 n n + 1225 64 n , any set with n points, n sufficiently large, admits a perfect matching with exactly k crossings. (2) There exist sets of n points where every perfect matching has at most 5 72 n 2 - n 4 crossings. (3) The number of perfect matchings with at most k crossings is superexponential in n if k is superlinear in n. (4) Point sets in convex position minimize the number of perfect matchings with at most k crossings for k = 0 , 1 , 2 , and maximize the number of perfect matchings with n / 2 2 crossings and with n / 2 2 - 1 crossings. [ABSTRACT FROM AUTHOR]

The following Ramsey-type question is one of the central problems in combinatorial geometry. Given a collection of certain geometric objects in the plane (e.g. segments, rectangles, convex sets, arcwise connected sets) of size n, what is the size of the largest subcollection in which either any two elements have a nonempty intersection, or any two elements are disjoint? We prove that there exists an absolute constant c>0 such that if C is a collection of n curves in the plane, then C contains at least nc elements that are pairwise intersecting, or n c elements that are pairwise disjoint. This resolves a problem raised by Alon, Pach, Pinchasi, Radoičić and Sharir, and Fox and Pach. Furthermore, as any geometric object can be arbitrarily closely approximated by a curve, this shows that the answer to the aforementioned question is at least nc for any collection of n geometric objects. [ABSTRACT FROM AUTHOR]

Proto-exact categories , introduced by Dyckerhoff and Kapranov, are a generalization of Quillen exact categories which provide a framework for defining algebraic K-theory and Hall algebras in a non-additive setting. This formalism is well-suited to the study of categories whose objects have strong combinatorial flavor. In this paper, we show that the categories of modules over semirings and hyperrings - algebraic structures which have gained prominence in tropical geometry - carry proto-exact structures. In the first part, we prove that the category of modules over a semiring is equipped with a proto-exact structure; modules over an idempotent semiring have a strong connection to matroids. We also prove that the category of algebraic lattices L has a proto-exact structure, and furthermore that the subcategory of L consisting of finite lattices is equivalent to the category of finite B -modules as proto-exact categories, where B is the Boolean semifield. We also discuss some relations between L and geometric lattices (simple matroids) from this perspective. In the second part, we prove that the category of modules over a hyperring has a proto-exact structure. In the case of finite modules over the Krasner hyperfield K , a well-known relation between finite K -modules and finite incidence geometries yields a combinatorial interpretation of exact sequences. [ABSTRACT FROM AUTHOR]

Based on previous work on the IDT solver, enhanced geometrical capabilities have been developed to handle accurate modeling of pressurized water reactors (PWRs). This work particularly focuses on the tridimensional model of the control rods. We propose a transport-based model to avoid the control rod cusping effect generated by homogenizations. Due to the geometry of a PWR core, the height of a node generally ranges from 10 to 20 cm. On the other hand, the control rods move along the vertical direction within the PWR core with axial steps of 1 to 2 cm. As a result, a control rod cluster may be partially inserted into a set of Cartesian nodes, thus requiring a heterogeneous representation of the cross sections along z. In traditional three-dimensional (3-D) transport codes, piecewise distributed cross sections are not allowed within a single node. Consequently, despite the heterogeneous nature, the node has to be homogenized. Because of sharp axial heterogeneity, the cross sections cannot be represented by polynomial expansions at the interface between the control rod tip and the water. Currently, the solvers of APOLLO3® do not allow for nonconformal geometries along the z-axis, i.e., all two-dimensional regions have the same number of planes. Lately, high-fidelity transport-based core solvers have dealt with this issue by proposing flux-weighting homogenization techniques. Nevertheless, the simple homogenization triggers a discontinuity in the first derivative of the curve representing the variation of the fundamental eigenvalue as the control rods are inserted into the reactor. This nonphysical phenomenon is known as the control rod cusping effect. Several numerical remedies have been proposed over the years to remove it. For instance, in diffusion, the PN or SPN method, and Fanning and Palmiotti have proposed a heterogeneous variational nodal method (VNM). Another heterogeneous VNM was developed by Smith et al. in 2003. In this method, each heterogeneous node is split into subelements with uniform cross sections. The flux is then developed by finite spatial trial functions. The nodal functional is constructed by the functional of all subelements in the node. In this work, discrete ordinates linear short characteristics are applied to 3-D heterogeneous Cartesian cells (HCCs). To ensure accurate representation of the control rod movements, each heterogeneous node, represented by a HCC, is the combination of an inner local tridimensional grid and a set of cylinders representing the fuel rod in its exact shape. The new geometrical model generates local nonconforming geometries. Spatial integrals over the HCC are performed using modular tridimensional ray tracing. The ray-tracing technique is based on the combinatorial geometry composed of cylinders and the local XYZ grid. In this manner, a single HCC can be equipped with several local steps to follow exactly the axial displacement of the control rod. The IDT provides a conformal 3-D Cartesian mesh with heterogeneous nonconformal 3-D nodes to eliminate such an issue. Each node represents a geometrical pattern named HCC. Neither a homogenization procedure nor a mesh adjustment is needed by taking advantage of the geometrical model provided by the HCC. Numerical results show that the HCC transport model can eliminate the cusping effect and obtain accurate power distribution with relatively higher efficiency and accuracy. [ABSTRACT FROM AUTHOR]

We investigate two fundamental questions intersecting coding theory and combinatorial geometry, with emphasis on their connections. These are the problem of computing the asymptotic density of MRD codes in the rank metric, and the Critical Problem for combinatorial geometries by Crapo and Rota. In the first part of the paper, we use methods from semifield theory to derive two lower bounds for the density function of full-rank, square MRD codes. The first bound is sharp when the matrix size is a prime number and the underlying field is sufficiently large, while the second bound applies to the binary field. We then take a new look at the Critical Problem for combinatorial geometries, approaching it from a qualitative, often asymptotic, viewpoint. We illustrate the connection between this very classical problem and that of computing the asymptotic density of MRD codes. Finally, in the third part of the paper we study the asymptotic density of some special families of codes in the rank metric, including the symmetric, alternating, and Hermitian ones. In particular, we show that the optimal codes in these three contexts are sparse. [ABSTRACT FROM AUTHOR]

Estimating covering functionals of convex bodies is not only interesting for its own, but also an important part of Chuanming Zong's program to attack Hadwiger's covering conjecture, a long-standing open problem from Discrete and Combinatorial Geometry. In general, it is difficult to determine exact values of the covering functionals of a convex body by theoretical analysis. Therefore we propose a global optimization algorithm based on the geometric branch-and-bound method. Numerical experiments have been carried out to estimate covering functionals of the Euclidean unit disc. [ABSTRACT FROM AUTHOR]

We improve the current best bound for distinct distances on non-ruled algebraic surfaces in R 3 . In particular, we show that n points on such a surface span Ω (n 32 / 39 - ε) distinct distances, for any ε > 0 . Our proof adapts the proof of Székely for the planar case, which is based on the crossing lemma. As part of our proof for distinct distances on surfaces, we also obtain new results for distinct distances between circles in R 3 . Consider two point sets of respective sizes m and n, such that each set lies on a distinct circle in R 3 . We characterize the cases when the number of distinct distances between the two sets can be O (m + n) . This includes a new configuration with a small number of distances. In any other case, we prove that the number of distinct distances is Ω (min { m 2 / 3 n 2 / 3 , m 2 , n 2 }) . [ABSTRACT FROM AUTHOR]

Strong blocking sets and their counterparts, minimal codes, have attracted much attention in the past few years. Combining the concatenating construction of codes with a geometric insight into the minimality condition, we explicitly provide infinite families of small strong blocking sets, whose size is linear in the dimension of the ambient projective spaces. As a byproduct, small saturating sets are obtained. [ABSTRACT FROM AUTHOR]

What is the maximum number of intersections of the boundaries of a simple m-gon and a simple n-gon? This is a basic question in combinatorial geometry, and the answer is easy if at least one of m and n is even: If both m and n are even, then every pair of sides may cross and so the answer is mn. If exactly one polygon, say the n-gon, has an odd number of sides, it can intersect each side of the m-gon polygon at most n - 1 times; hence there are at most m n - m intersections. It is not hard to construct examples that meet these bounds. If both m and n are odd, the best known construction has m n - (m + n) + 3 intersections, and it is conjectured that this is the maximum. However, the best known upper bound is only m n - (m + ⌈ n / 6 ⌉) , for m ≥ n . We prove a new upper bound of m n - (m + n) + C for some constant C, which is optimal apart from the value of C. [ABSTRACT FROM AUTHOR]

We study the combinatorial geometry of a random closed multicurve on a surface of large genus g and of a random square-tiled surface of large genus g. We prove that primitive components γ 1 , ⋯ , γ k of a random multicurve m 1 γ 1 + ⋯ + m k γ k represent linearly independent homology cycles with asymptotic probability 1 and that all its weights m i are equal to 1 with asymptotic probability 2 / 2 . We prove analogous properties for random square-tiled surfaces. In particular, we show that all conical singularities of a random square-tiled surface belong to the same leaf of the horizontal foliation and to the same leaf of the vertical foliation with asymptotic probability 1. We show that the number of components of a random multicurve and the number of maximal horizontal cylinders of a random square-tiled surface of genus g are both very well approximated by the number of cycles of a random permutation for an explicit non-uniform measure on the symmetric group of 3 g - 3 elements. In particular, we prove that the expected value of these quantities has asymptotics (log (6 g - 6) + γ) / 2 + log 2 as g → ∞ , where γ is the Euler–Mascheroni constant. These results are based on our formula for the Masur–Veech volume Vol Q g of the moduli space of holomorphic quadratic differentials combined with deep large genus asymptotic analysis of this formula performed by A. Aggarwal and with the uniform asymptotic formula for intersection numbers of ψ -classes on M ¯ g , n for large g proved by A. Aggarwal in 2020. [ABSTRACT FROM AUTHOR]

In this article, the concept of applied algebra of sets and a standard disjunctive basis of an applied algebra of sets are introduced. The algorithm for constructing a standard disjunctive basis is described. By analogy with Buchberger's algorithm in the polynomial ideal theory and Knuth-Bendix's algorithm in the theory of semigroups of words, it is called the critical pair/completion algorithm. Examples of various applied algebras of sets are provided. They include the algebra of finite sets in realization on ordered lists, the Lebesgue algebra of sets on the number axis, algebra of linear semi-algebraic sets on a plane, and algebra of circles on a plane called the Euler algebra. Implementation of the critical pair/completion algorithm is also considered. The main result of the study is that the presence of a standard disjunctive basis makes it possible to construct time-efficient (polynomial) algorithms for solving basic problems in applied algebras of sets, such as the representation problem, membership problem, equality problem, emptiness problem, etc. Algorithms in the algebra of linear semi-algebraic sets on a plane and the Euler algebra on a plane can be extended to more general applied algebras of sets. [ABSTRACT FROM AUTHOR]

Karasev [16] conjectured that for every set of r blue lines, r green lines, and r red lines in the plane, there exists a partition of them into r colorful triples whose induced triangles intersect. We disprove this conjecture for every r and extend the counterexamples to higher dimensions. [ABSTRACT FROM AUTHOR]

Let P be a set of n points in general position in the plane.The Second Selection Lemma states that for any family of Θ(n3)\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\Theta(n^3)$$\end{document} triangles spanned by P, there exists a point of the plane that lies in a constant fraction of them.For families of Θ(n3-α)\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\Theta(n^{3-\alpha})$$\end{document} triangles, with 0≤α≤1\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$0\le \alpha \le 1$$\end{document}, there might not be a point in more than Θ(n3-2α)\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\Theta(n^{3-2\alpha})$$\end{document} of those triangles.An empty triangle of P is a triangle spanned by Pnot containing any point of P in its interior. Bárány conjectured that there exists an edgespanned by P that is incident to a super-constant number of empty triangles of P. The number of empty trianglesof P might be as low as Θ(n2)\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\Theta(n^2)$$\end{document}; in such a case, on average, every edge spanned by P is incident to a constant numberof empty triangles. The conjecture of Bárány suggests that for the class of empty triangles the above upper boundmight not hold. In this paper we show that, somewhat surprisingly,the above upper bound does in fact hold for empty triangles.Specifically, we show that for any integer n and real number 0≤α≤1\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$0\leq \alpha \leq 1$$\end{document} there exists a point set of size n with Θ(n3-α)\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$\Theta(n^{3-\alpha})$$\end{document} empty triangles such that any point of the plane is only in O(n3-2α)\documentclass[12pt]{minimal}\usepackage{amsmath}\usepackage{wasysym}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{amsbsy}\usepackage{mathrsfs}\usepackage{upgreek}\setlength{\oddsidemargin}{-69pt}\begin{document}$$O(n^{3-2\alpha})$$\end{document} empty triangles. [ABSTRACT FROM AUTHOR]

Given a planar straight-line graph G = (V , E) in R 2 , a circumscribing polygon of G is a simple polygon P whose vertex set is V, and every edge in E is either an edge or an internal diagonal of P. A circumscribing polygon is a polygonization for G if every edge in E is an edge of P. We prove that every arrangement of n disjoint line segments in the plane has a subset of size Ω (n) that admits a circumscribing polygon, which is the first improvement on this bound in 20 years. We explore relations between circumscribing polygons and other problems in combinatorial geometry, and generalizations to R 3 . We show that it is NP-complete to decide whether a given graph G admits a circumscribing polygon, even if G is 2-regular. Settling a 30-year old conjecture by Rappaport, we also show that it is NP-complete to determine whether a geometric matching admits a polygonization. [ABSTRACT FROM AUTHOR]

We do not add (g) to HT ht but we record this inequality. Suppose HT ht Then, the tropical hypersurface of I f i is defined by the equation Graph HT ht This equation defines a classical hyperplane, which introduces linearity into the tropical prevariety defined by the I G i . [Extracted from the article]

Multicellular organization with precise spatial definition is essential to various biological processes, including morphogenesis, development, and healing in vascular and other tissues. Gradients and patterns of chemoattractants are well‐described guides of multicellular organization, but the influences of 3D geometry of soft hydrogels are less well defined. Here, the discovery of a new mode of endothelial cell self‐organization guided by combinatorial effects of stiffness and geometry, independent of protein or chemical patterning, is described. Endothelial cells in 2 kPa microwells are found to be ≈30 times more likely to migrate to the edge to organize in ring‐like patterns than in stiff 35 kPa microwells. This organization is independent of curvature and significantly more pronounced in 2 kPa microwells with aspect ratio (perimeter/depth) < 25. Physical factors of cells and substrates that drive this behavior are systematically investigated and a mathematical model that explains the organization by balancing the dynamic interaction between tangential cytoskeletal tension, cell–cell, and cell–substrate adhesion is presented. These findings demonstrate the importance of combinatorial effects of geometry and stiffness in complex cellular organization that can be leveraged to facilitate the engineering of bionics and integrated model organoid systems with customized nutrient vascular networks. [ABSTRACT FROM AUTHOR]

Solving polynomial equations inevitably faces many severe challenges, such as easily occupying storage space and demanding prohibitively expensive computation resources. There has been considerable interest in exploiting the sparsity to improve computation efficiency, since asymmetry phenomena are prevalent in scientific and engineering fields, especially as most of the systems in real applications have sparse representations. In this paper, we propose an efficient parallel hybrid algorithm for constructing a Dixon matrix. This approach takes advantage of the asymmetry (i.e., sparsity) in variables of the system and introduces a heuristics strategy. Our method supports parallel computation and has been implemented on a multi-core system. Through time-complexity analysis and extensive benchmarks, we show our new algorithm has significantly reduced computation and memory overhead. In addition, performance evaluation via the Fermat–Torricelli point problem demonstrates its effectiveness in combinatorial geometry optimizations. [ABSTRACT FROM AUTHOR]

In this paper, we first present a criterion for the real stability of recursive polynomials by applying the characterization of Borcea and Brändén concerning linear operators preserving stability. As applications, we derive some real stability results occurred in the literature in a unified manner. Moreover, we prove the real-rootedness of peak polynomials in bicolored dyck paths and ternary polynomials. Second, based on the h -polynomials from combinatorial geometry, we use real stability to get two criteria for interlacing property of zeros between a polynomial and its reciprocal polynomial, which in particular imply the alternatingly increasing property of the original polynomial or its reciprocal polynomial. These criteria extend a result of Brändén and Solus and unify such properties for many combinatorial polynomials, including ascent polynomials for k -ary words, descent polynomials on signed Stirling permutations and colored permutations, q -analog of descent polynomials on colored permutations and descent polynomials on color-signed permutations. Furthermore, we also obtain a recurrence relation and zero-interlacing property of q -analog of descent polynomials on colored permutations that extend some results of Brändén and Brenti. In addition, as an application of weak Hurwitz stability, we get the alternatingly increasing property and zero-interlacing property for two kinds of peak polynomials on the dual set of Stirling permutations. [ABSTRACT FROM AUTHOR]

Every generic linear functional f on a convex polytope P induces an orientation on the graph of P. From the resulting directed graph one can define a notion of f‐arborescence and f‐monotone path on P, as well as a natural graph structure on the vertex set of f‐monotone paths. These concepts are important in geometric combinatorics and optimization. This paper bounds the number of f‐arborescences, the number of f‐monotone paths, and the diameter of the graph of f‐monotone paths for polytopes P in terms of their dimension and number of vertices or facets. [ABSTRACT FROM AUTHOR]

Domain-specific programming frameworks are usually effective to simplify the development of large-scale applications on supercomputers. This paper introduces a parallel programming framework named JCOGIN for particle transport on combinatorial geometry. JCOGIN provides a combinatorial geometry data model and a patch-based parallel computing model to manage the data distribution in parallel computing and implements the hybrid parallelism of the domain decomposition and the particle parallelism on MPI/OpenMP to overcome the bottleneck of huge memory demand and long computational time. The application programming interface of JCOGIN can support users to quickly develop their parallel particle transport applications. Based on this framework, users only need to write serial codes for large-scale numerical simulations on modern supercomputers. The parallel efficiency of applications based on JCOGIN can reach up to 80% on hundreds of thousands of CPU cores. [ABSTRACT FROM AUTHOR]

• Proved several lower and upper bounds on the Voronoi games on simple and convex polygons. Almost all are tight. • Devised optimal strategies for the games on convex polygons in poly-log linear and linear time for the players. • Extended the results on the bounds on the Voronoi games on polyhedra in R 3. • Polynomial-time strategies for both the players are devised for Voronoi games on convex polyhedra with restrictions. • Computed common intersection of ellipses in O (n log ⁡ n) time. The competitive facility location problem is the problem of determining facility locations involving multiple players to optimize their various gains. The Voronoi game is a competitive facility location problem on a given arena played by two players, the server and the adversary. The players alternately take turns, one or more times, to place their facilities in the arena with a predetermined set of n clients , where both facilities and clients are denoted by points, to maximize some resource gain. The Voronoi game on a polygon P is a type of competitive facility location problem where n clients are located on the boundary of P. The server, Alice, and adversary, Bob, are respectively in the interior and the exterior of the polygon P at locations A and B , respectively. Additionally, the metrics for Alice and Bob are the internal and external geodesic distances for the polygon P , respectively. In this paper, we present some surprising results on the Voronoi games on polygons. We prove lower and upper bounds of ⌈ n / 3 ⌉ and n − 1 respectively in the single-round game for the number of clients won by the server for n clients. Both bounds are tight. In the process, we show that in some convex polygons, the adversary wins no more than k clients in a k -round Voronoi game for any k ≤ n. Consequentially, the adversary Bob does not have a guaranteed good winning strategy even for the simpler case of convex polygons, i.e., there exist convex polygons such that no placement of B guarantees more than k clients in the k -round game. We also design O (n log 2 ⁡ n + m log ⁡ n) and O (n + m) time algorithms to compute the optimal locations for the server and the adversary respectively to maximize their client counts where the convex polygon has size m. Moreover, we present an O (n log ⁡ n) time algorithm to compute the common intersection of a set of n ellipses. This is needed in our algorithm and may be of independent interest. Lastly, we present some results on the Voronoi games, where the arena is a convex polytope. The server and adversary are respectively in the interior and exterior of P , and the clients are on the polytope boundary. [ABSTRACT FROM AUTHOR]

A Helly-type theorem for diameter provides a bound on the diameter of the intersection of a finite family of convex sets in Rd given some information on the diameter of the intersection of all sufficiently small subfamilies. We prove fractional and colorful versions of a long-standing conjecture by B\'ar\'any, Katchalski, and Pach. We also show that a Minkowski norm admits an exact Helly-type theorem for diameter if and only if its unit ball is a polytope and prove a colorful version for those that do. Finally, we prove Helly-type theorems for the property of "containing k colinear integer points. [ABSTRACT FROM AUTHOR]

The quantum symmetric simple exclusion process (Q-SSEP) is a model for quantum stochastic dynamics of fermions hopping along the edges of a graph with Brownian noisy amplitudes and driven out-of-equilibrium by injection-extraction processes at a few vertices. We present a solution for the invariant probability measure of the one dimensional Q-SSEP in the infinite size limit by constructing the steady correlation functions of the system density matrix and quantum expectation values. These correlation functions code for a rich structure of fluctuating quantum correlations and coherences. Although our construction does not rely on the standard techniques from the theory of integrable systems, it is based on a remarkable interplay between the permutation groups and polynomials. We incidentally point out a possible combinatorial interpretation of the Q-SSEP correlation functions via a surprising connexion with geometric combinatorics and the associahedron polytopes. [ABSTRACT FROM AUTHOR]

The quantum symmetric simple exclusion process (Q-SSEP) is a model for quantum stochastic dynamics of fermions hopping along the edges of a graph with Brownian noisy amplitudes and driven out-of-equilibrium by injection-extraction processes at a few vertices. We present a solution for the invariant probability measure of the one dimensional Q-SSEP in the infinite size limit by constructing the steady correlation functions of the system density matrix and quantum expectation values. These correlation functions code for a rich structure of fluctuating quantum correlations and coherences. Although our construction does not rely on the standard techniques from the theory of integrable systems, it is based on a remarkable interplay between the permutation groups and polynomials. We incidentally point out a possible combinatorial interpretation of the Q-SSEP correlation functions via a surprising connexion with geometric combinatorics and the associahedron polytopes. [ABSTRACT FROM AUTHOR]

In algebraic, topological, and geometric combinatorics, inequalities among the coefficients of combinatorial polynomials are frequently studied. Recently, a notion called the alternatingly increasing property, which is stronger than unimodality, was introduced. In this paper, we relate the alternatingly increasing property to real-rootedness of the symmetric decomposition of a polynomial to develop a systematic approach for proving the alternatingly increasing property for several classes of polynomials. We apply our results to strengthen and generalize real-rootedness, unimodality, and alternatingly increasing results pertaining to colored Eulerian and derangement polynomials, Ehrhart |$h^\ast$| -polynomials for lattice zonotopes, |$h$| -polynomials of barycentric subdivisions of doubly Cohen–Macaulay level simplicial complexes, and certain local |$h$| -polynomials for subdivisions of simplices. In particular, we prove two conjectures of Athanasiadis. [ABSTRACT FROM AUTHOR]

Structural and chemical properties of InAs/AlSb interfaces have been studied by transmission electron microscopy. InAs/AlSb multilayers were grown by molecular beam epitaxy with different growth sequences at interfaces. The out-of-plane strain, determined using high resolution microscopy and geometrical phase analysis, has been related to the chemical composition of the interfaces analyzed by high angle annular dark field imaging. Considering the local strain and chemistry, we estimated the interface composition and discussed the mechanisms of interface formation for the different growth sequences. In particular, we found that the formation of the tensile AlAs-type interface is spontaneously favored due to its high thermal stability compared to the InSb-type interface. We also showed that the interface composition could be tuned using an appropriate growth sequence. [ABSTRACT FROM AUTHOR]

We prove a new Elekes-Szabó type estimate on the size of the intersection of a Cartesian product A × B × C with an algebraic surface { f = 0 } over the reals. In particular, if A , B , C are sets of N real numbers and f is a trivariate polynomial, then either f has a special form that encodes additive group structure (for example, f (x , y , x) = x + y − z), or A × B × C ∩ { f = 0 } has cardinality O (N 12 / 7). This is an improvement over the previous bound O (N 11 / 6). We also prove an asymmetric version of our main result, which yields an Elekes-Ronyai type expanding polynomial estimate with exponent 3/2. This has applications to questions in combinatorial geometry related to the Erdős distinct distances problem. Like previous approaches to the problem, we rephrase the question as an L 2 estimate, which can be analyzed by counting additive quadruples. The latter problem can be recast as an incidence problem involving points and curves in the plane. The new idea in our proof is that we use the order structure of the reals to restrict attention to a smaller collection of proximate additive quadruples. [ABSTRACT FROM AUTHOR]

We study problems related to colouring families of bottomless rectangles in the plane, in an attempt to improve the polychromatic k-colouring number m k ⁎. This number is the smallest m such that any collection of bottomless rectangles can be k -coloured so that any m -fold covered point is covered by all k colours. We show that for many families of bottomless rectangles, such as unit-width bottomless rectangles, or bottomless rectangles whose left corners lie on a line, m k ⁎ is linear in k. We present the lower bound m k ⁎ ≥ 2 k − 1 for general families. We also investigate semi-online colouring algorithms, which need not colour each vertex immediately, but must maintain a proper colouring. We prove that for many sweeping orders, for any positive integers m , k , there is no semi-online algorithm that can k -colour bottomless rectangles presented in that order, so that any m -fold covered point is covered by at least two colours. This holds even for translates of quadrants, and is a corollary of a stronger result for arborescence colourings: Any semi-online colouring algorithm that colours an arborescence presented in post-order may produce arbitrarily long monochromatic paths. [ABSTRACT FROM AUTHOR]

Consider a realization of a graph in the space with straight segments representing edges. Let us assign a stress for every its edge. In case if at every vertex of the graph the stresses sum up to zero, we say that the realization is a tensegrity. Some realizations possess non-zero tensegrities while the others do not. In this paper we study necessary and sufficient existence conditions for tensegrities in the plane. For an arbitrary graph we write down these conditions in terms of projective "meet-join" operations. [ABSTRACT FROM AUTHOR]

The literature contains quite a few theorems on subdividing the volume of a convex body by a system of cones and on the possibility to circumscribe the body about a polytope of one type or another. See R. N. Karasev, "Topological methods in combinatorial geometry," Russian Math. Surveys, 63, No. 6, 1031–1078 (2008) for a survey of similar results. In the following, we also prove theorems of this kind. As a limit case, we obtain well-known theorems on inscribed polytopes. [ABSTRACT FROM AUTHOR]

This is an expository paper about the fundamental mathematical notion of starshapedness, emphasizing the geometric, analytical, combinatorial, and topological properties of starshaped sets and their broad applicability in many mathematical fields. The authors decided to approach the topic in a very broad way since they are not aware of any related survey-like publications dealing with this natural notion. The concept of starshapedness is very close to that of convexity, and it is needed in fields like classical convexity, convex analysis, functional analysis, discrete, combinatorial and computational geometry, differential geometry, approximation theory, PDE, and optimization; it is strongly related to notions like radial functions, section functions, visibility, (support) cones, kernels, duality, and many others. We present in a detailed way many definitions of and theorems on the basic properties of starshaped sets, followed by survey-like discussions of related results. At the end of the article, we additionally survey a broad spectrum of applications in some of the above mentioned disciplines. [ABSTRACT FROM AUTHOR]

We extend, in significant ways, the theory of truncated boolean representable simplicial complexes introduced in 2015. This theory, which includes all matroids, represents the largest class of finite simplicial complexes for which combinatorial geometry can be meaningfully applied. [ABSTRACT FROM AUTHOR]

In 2015, Guth [Math. Proc. Cambridge Philos. Soc., 159 (2015), pp. 459{469] proved that for any set of k-dimensional bounded complexity varieties in Rd and for any positive integer D, there exists a polynomial of degree at most D whose zero set divides Rd into open connected sets so that only a small fraction of the given varieties intersect each of these sets. Guth's result generalized an earlier result of Guth and Katz [Ann. Math., 181 (2015), pp. 155{190] for points. Guth's proof relies on a variant of the Borsuk-Ulam theorem, and for k > 0, it is unknown how to obtain an explicit representation of such a partitioning polynomial and how to construct it efficiently. In particular, it is unknown how to effectively construct such a polynomial for bounded-degree algebraic curves (or even lines) in R³. We present an efficient algorithmic construction for this setting. Given a set of n input algebraic curves and a positive integer D, we efficiently construct a decomposition of space into O(D3 log3 D) open "cells," each of which meets O(n=D2) curves from the input. The construction time is O(n²). For the case of lines in 3-space, we present an improved implementation whose running time is O(n4/3 polylog n). The constant of proportionality in both time bounds depends on D and the maximum degree of the polynomials defining the input curves. As an application, we revisit the problem of eliminating depth cycles among nonvertical lines in 3-space, recently studied by Aronov and Sharir [Discrete Comput. Geom., 59 (2018), pp. 725{741] and show an algorithm that cuts n such lines into O(n3/2+ɛ) pieces that are depth-cycle free for any · > 0. The algorithm runs in O(n3/2+ɛ) time, which is a considerable improvement over the previously known algorithms. [ABSTRACT FROM AUTHOR]

The vertical depth relation among n pairwise openly disjoint triangles in 3-space may contain cycles. We show that, for any ε > 0 , the triangles can be cut into O (n 3 / 2 + ε) connected semialgebraic pieces, whose description complexity depends only on the choice of ε , such that the depth relation among these pieces is now a proper partial order. This bound is nearly tight in the worst case. The pieces can be constructed efficiently. This work extends the recent study by two of the authors (Discrete Comput. Geom. 59(3), 725–741 (2018)) on eliminating depth cycles among lines in 3-space. Our approach is again algebraic, and makes use of a recent variant of the polynomial partitioning technique, due to Guth (Math. Proc. Camb. Philos. Soc. 159(3), 459–469 (2015)), which leads to a recursive algorithm for cutting the triangles. In contrast to the case of lines, our analysis here is considerably more involved, due to the two-dimensional nature of the objects being cut, so additional tools, from topology and algebra, need to be brought to bear. Our result makes significant progress towards resolving a decades-old open problem in computational geometry, motivated by hidden-surface removal in computer graphics. In addition, we generalize our bound to well-behaved patches of two-dimensional algebraic surfaces of constant degree. [ABSTRACT FROM AUTHOR]

What is the minimum number of colors that always suffice to color every planar set of points such that any disk that contains enough points contains two points of different colors? It is known that the answer to this question is either three or four. We show that three colors always suffice if the condition must be satisfied only by disks that contain a fixed point. Our result also holds, and is even tight, when instead of disks we consider their topological generalization, namely, pseudo-disks, with a nonempty intersection. Our solution uses the equivalence that a hypergraph can be realized by stabbed pseudo-disks if and only if it is ABAB-free. These hypergraphs are defined in a purely abstract, combinatorial way, and our proof that they are 3-chromatic is also combinatorial. [ABSTRACT FROM AUTHOR]

The boundary of some well known algebro-geometric moduli spaces is described by highlighting the recursive combinatorial properties in connection with tropical and non-Archimedean geometry. [ABSTRACT FROM AUTHOR]

We study the 3-dimensional combinatorial Yamabe flow in hyperbolic background geometry. For a triangulation of a 3-manifold, we prove that if the number of tetrahedra incident to each vertex is at least 23, then there exist real or virtual ball packings with vanishing (extended) combinatorial scalar curvature, i.e., the total (extended) solid angle at each vertex is equal to 4π. In this case, if such a ball packing is real, then the (extended) combinatorial Yamabe flow converges exponentially fast to that ball packing. Moreover, we prove that there is no real or virtual ball packing with vanishing (extended) combinatorial scalar curvature if the number of tetrahedra incident to each vertex is at most 22. [ABSTRACT FROM AUTHOR]

We introduce a simple logical inference structure we call a ``spanoid"" (generalizing the notion of a matroid), which captures well-studied problems in several areas. These include combinatorial geometry (point-line incidences), algebra (arrangements of hypersurfaces and ideals), statistical physics (bootstrap percolation), network theory (gossip/infection processes) and coding theory. We initiate a thorough investigation of spanoids, from computational and structural viewpoints, focusing on parameters relevant to the applications areas above and, in particular, to questions regarding locally correctable codes (LCCs). One central parameter we study is the ``rank"" of a spanoid, extending the rank of a matroid and related to the dimension of codes. This leads to one main application of our work, establishing the first known barrier to improving the nearly 20-year old bound of Katz--Trevisan (KT) on the dimension of LCCs. On the one hand, we prove that the KT bound (and its more recent refinements) holds for the much more general setting of spanoid rank. On the other hand we show that there exist (random) spanoids whose rank matches these bounds. Thus, to significantly improve the known bounds one must step out of the spanoid framework. Another parameter we explore is the ``functional rank"" of a spanoid, which captures the possibility of turning a given spanoid into an actual code. The question of the relationship between rank and functional rank is one of the main questions we raise as it may reveal new avenues for constructing new LCCs (perhaps even matching the KT bound). As a first step, we develop an entropy relaxation of functional rank to create a small constant gap and amplify it by tensoring to construct a spanoid whose functional rank is smaller than rank by a polynomial factor. This is evidence that the entropy method we develop can prove polynomially better bounds than KT-type methods on the dimension of LCCs. To facilitate the above results we also develop some basic structural results on spanoids including an equivalent formulation of spanoids as set systems and properties of spanoid products. We feel that given these initial findings and their motivations, the abstract study of spanoids merits further investigation. We leave plenty of concrete open problems and directions. [ABSTRACT FROM AUTHOR]

We present new triangulations of the m = 4 amplituhedron relevant for scattering amplitudes in planar N = 4 super-Yang-Mills, obtained directly from the combinatorial definition of the geometry. Using the "sign flip" characterization of the amplituhedron, we reproduce the canonical forms for the all-multiplicity next-to-maximally helicity violating (NMHV) and next-to-next-to-maximally helicity violating (N2MHV) tree-level as well as the NMHV one-loop cases, without using any input from traditional amplitudes methods. Our results provide strong evidence for the equivalence of the original definition of the amplituhedron [1] and the topological one [2], and suggest a new path forward for computing higher loop amplitudes geometrically. In particular, we realize the NMHV one-loop amplituhedron as the intersection of two amplituhedra of lower dimensionality, which is reflected in the novel structure of the corresponding canonical form. [ABSTRACT FROM AUTHOR]

For a positive integer d, a set of points in d-dimensional Euclidean space is called almost-equidistant if for any three points from the set, some two are at unit distance. Let f(d) denote the largest size of an almost-equidistant set in d-space. It is known that f (2) = 7 , f (3) = 10 , and that the extremal almost-equidistant sets are unique. We give independent, computer-assisted proofs of these statements. It is also known that f (5) ≥ 16 . We further show that 12 ≤ f (4) ≤ 13 , f (5) ≤ 20 , 18 ≤ f (6) ≤ 26 , 20 ≤ f (7) ≤ 34 , and f (9) ≥ f (8) ≥ 24 . Up to dimension 7, our work is based on various computer searches, and in dimensions 6–9, we give constructions based on the known construction for d = 5 . For every dimension d ≥ 3 , we give an example of an almost-equidistant set of 2 d + 4 points in the d-space and we prove the asymptotic upper bound f (d) ≤ O (d 3 / 2) . [ABSTRACT FROM AUTHOR]

We study the moduli space AS g of Artin-Schreier curves of genus g over an algebraically closed field k of positive characteristic p. The moduli space is partitioned into strata, which are irreducible. Each stratum parameterizes Artin-Schreier curves whose ramification divisors have the same coefficients. We construct deformations of these curves to study the relations between those strata. As an application, when p = 3 , we prove that AS g is connected for all g. When p > 3 , it turns out that AS g is connected for a sufficiently large value of g. In the course of our work, we answer a question of Pries and Zhu about how a combinatorial graph determines the geometry of AS g. [ABSTRACT FROM AUTHOR]

What is the minimum number of colors that always suffice to color every planar set of points such that any disk that contains enough points contains two points of different colors? It is known that the answer to this question is either three or four. We show that three colors always suffice if the condition must be satisfied only by disks that contain a fixed point. Our result also holds, and is even tight, when instead of disks we consider their topological generalization, namely, pseudo-disks, with a nonempty intersection. Our solution uses the equivalence that a hypergraph can be realized by stabbed pseudo-disks if and only if it is ABAB-free. These hypergraphs are defined in a purely abstract, combinatorial way, and our proof that they are 3-chromatic is also combinatorial. [ABSTRACT FROM AUTHOR]

We prove the main result that a groupoid of order n is an idempotent and k-translatable quasigroup if and only if its multiplication is given by x · y = (a x + b y) (mod n) , where a + b = 1 (mod n) , a + b k = 0 (mod n) and (k , n) = 1 . We describe the structure of various types of idempotent k-translatable quasigroups, some of which are connected with affine geometry and combinatorial algebra, and their parastrophes. We prove that such parastrophes are also idempotent k-translatable quasigroups and determine when they are of the same type as the original quasigroup. In addition, we find several different necessary and sufficient conditions making a k-translatable quasigroup quadratical. [ABSTRACT FROM AUTHOR]