Search

Let $G$ be a finite group of order $n$, and denote by $\rho(G)$ the product of element orders of $G$. The aim of this work is to provide some upper bounds for $\rho(G)$ depending only on $n$ and on its least prime divisor, when $G$ belongs to some classes of non-cyclic groups., Comment: 9 pages. To appear in Journal of Algebraic Combinatorics

We investigate the Castelnuovo-Mumford regularity and the multiplicity of the toric ring associated with a three-dimensional Ferrers diagram. In particular, in the rectangular case, we provide direct formulas for these two important invariants. Then, we compare these invariants for an accompanying pair of Ferrers diagrams under some mild conditions and bound the Castelnuovo-Mumford regularity for more general cases., Comment: Revised following the reviewer's suggestions. 27 pages and 6 figures. Comments are welcome

Unit square visibility graphs (USV) are described by axis-parallel visibility between unit squares placed in the plane. If the squares are required to be placed on integer grid coordinates, then USV become unit square grid visibility graphs (USGV), an alternative characterisation of the well-known rectilinear graphs. We extend known combinatorial results for USGV and we show that, in the weak case (i.e., visibilities do not necessarily translate into edges of the represented combinatorial graph), the area minimisation variant of their recognition problem is $${{\,\mathrm{{\textsf{N}}{\textsf{P}}}\,}}$$ N P -hard. We also provide combinatorial insights with respect to USV, and as our main result, we prove their recognition problem to be $${{\,\mathrm{{\textsf{N}}{\textsf{P}}}\,}}$$ N P -hard, which settles an open question.

In Szirmai (Ars Math Contemp 16:349–358, 2019) we proved that to each saturated congruent hyperball packing there exists a decomposition of the 3-dimensional hyperbolic space $$\mathbb {H}^3$$ H 3 into truncated tetrahedra. Therefore, in order to get a density upper bound for hyperball packings, it is sufficient to determine the density upper bound of hyperball packings in truncated simplices. In this paper we prove, using the above results and results of the papers Miyamoto (Topology 33(4): 613–629, 1994) and Szirmai (Mat Vesn 70(3): 211–221, 2018), that the density upper bound of the saturated congruent hyperball (hypersphere) packings related to the corresponding truncated tetrahedron cells is realized in regular truncated tetrahedra with density $$\approx 0.86338$$ ≈ 0.86338 . Furthermore, we prove that the density of locally optimal congruent hyperball arrangement in a regular truncated tetrahedron is not a monotonically increasing function of the height (radius) of the corresponding optimal hyperball, unlike the ball (sphere) and horoball (horosphere) packings.

The Eden cell growth model is a simple discrete stochastic process which produces a "blob" in $\mathbb{R}^d$: start with one cube in the regular grid, and at each time step add a neighboring cube uniformly at random. This process has been used as a model for the growth of aggregations, tumors, and bacterial colonies and the healing of wounds, among other natural processes. Here, we study the topology and local geometry of the resulting structure, establishing asymptotic bounds for Betti numbers. Our main result is that the Betti numbers grow at a rate between the conjectured rate of growth of the site perimeter and the actual rate of growth of the site perimeter. We also present the results of computational experiments on finer aspects of the geometry and topology, such as persistent homology and the distribution of shapes of holes., 34 pages, 11 figures, 5 tables; revisions in response to referee reports

We develop a nonstandard approach to exploring polynomials associated with peaks and runs of permutations. With the aid of a context-free grammar, or a set of substitution rules, one can perform a symbolic calculus, and the computation often becomes rather simple. From a grammar it follows at once a system of ordinary differential equations for the generating functions. Utilizing a certain constant property, it is even possible to deduce a single equation for each generating function. To bring the grammar to a combinatorial setting, we find a labeling scheme for up-down runs of a permutation, which can be regarded as a refined property, or the differentiability in a certain sense, in contrast to the usual counting argument for the recurrence relation. The labeling scheme also exhibits how the substitution rules arise in the construction of the combinatorial structures. Consequently, polynomials on peaks and runs can be dealt with in two ways, combinatorially or grammatically. The grammar also serves as a guideline to build a bijection between permutations and increasing trees that maps the number of up-down runs to the number of nonroot vertices of even degree. This correspondence can be adapted to left peaks and exterior peaks, and the key step of the construction is called the reflection principle., Revised version, 25 pages, 15 figures, to appear in J. Algebraic Combin

The convex hull of N independent random points chosen on the boundary of a simple polytope in $$ {\mathbb {R}}^n$$ R n is investigated. Asymptotic formulas for the expected number of vertices and facets, and for the expectation of the volume difference are derived. This is one of the first investigations leading to rigorous results for random polytopes which are neither simple nor simplicial. The results contrast existing results when points are chosen in the interior of a convex set.

In our previous work, we equipped quiver Grassmannians for nilpotent representations of the equioriented cycle with an action of an algebraic torus. We show here that the equivariant cohomology ring is acted upon by a product of symmetric groups and we investigate this permutation action via GKM techniques. In the case of (type A) flag varieties, or Schubert varieties therein, we recover Tymoczko’s results on permutation representations.

A permutation group G on a set $$\Omega $$ Ω is called orbit closed if every permutation of $$\Omega $$ Ω preserving the orbits of G in its action on the power set $$P(\Omega )$$ P ( Ω ) belongs to G. It is called a relation group if there exists a family $$R \subseteq P(\Omega )$$ R ⊆ P ( Ω ) such that G is the group of all permutations preserving R. We prove that if a finite orbit closed permutation group G is simple, or is a subgroup of a simple group, then it is a relation group. This result justifies our general conjecture that with a few exceptions every finite orbit closed group is a relation group. To obtain the result, we prove that most of the finite simple permutation groups are relation groups. We also obtain a complete description of those finite simple permutation groups that have regular sets, and prove that (with one exception) if a finite simple permutation group G is a relation group, then every subgroup of G is a relation group.

An animal is a planar shape formed by attaching congruent regular polygons along their edges. Usually, these polygons are a finite subset of tiles of a regular planar tessellation. These tessellations can be parameterized using the Schläfli symbol $$\{p,q\}$$ { p , q } , where p denotes the number of sides of the regular polygon forming the tessellation and q is the number of edges or tiles meeting at each vertex. If $$(p-2)(q-2)> 4$$ ( p - 2 ) ( q - 2 ) > 4 , $$=4$$ = 4 , or $$ < 4 , then the tessellation corresponds to the geometry of the hyperbolic plane, the Euclidean plane, or the sphere, respectively. In 1976, Harary and Harborth studied animals defined on regular tessellations of the Euclidean plane, finding extremal values for their vertices, edges, and tiles, when any one of these parameters is fixed. They named animals attaining these extremal values as extremal animals. Here, we study hyperbolic extremal animals. For each $$\{p,q\}$$ { p , q } corresponding to a hyperbolic tessellation, we exhibit a sequence of spiral animals and prove that they attain the minimum numbers of edges and vertices within the class of animals with n tiles. We also give the first results on enumeration of extremal hyperbolic animals by finding special sequences of extremal animals that are unique extremal animals, in the sense that any animal with the same number of tiles which is distinct up to isometries cannot be extremal.

Investigating the future value F(K, s, t) of a capital K invested between dates s and t, the “natural” condition $$F(K,s,t)\ge K$$ F ( K , s , t ) ≥ K has lost its naturality because of the strange fact of negative interest rates. This leads to the task of describing the possible solutions of the multiplicative Sincov equation $$f(s,u)=f(s,t)f(t,u)$$ f ( s , u ) = f ( s , t ) f ( t , u ) for $$s\le t\le u$$ s ≤ t ≤ u where $$f(s,t)=0$$ f ( s , t ) = 0 may happen. In this paper we solve this task and discuss connections to the theory of investments.

An (association) scheme is said to be Frobenius if it is the scheme of a Frobenius group. A scheme which has the same tensor of intersection numbers as some Frobenius scheme is said to be pseudofrobenius. We establish a necessary and sufficient condition for an imprimitive pseudofrobenius scheme to be Frobenius. We also prove strong necessary conditions for existence of an imprimitive pseudofrobenius scheme which is not Frobenius. As a byproduct, we obtain a sufficient condition for an imprimitive Frobenius group $G$ with abelian kernel to be determined up to isomorphism only by the character table of $G$. Finally, we prove that the Weisfeiler-Leman dimension of a circulant graph with $n$ vertices and Frobenius automorphism group is equal to $2$ unless $n\in \{p,p^2,p^3,pq,p^2q\}$, where $p$ and $q$ are distinct primes., 16 pages

For $${\varvec{a}} \in {\mathbb {R}}_{\ge 0}^{n}$$ a ∈ R ≥ 0 n , the Tesler polytope $${\text {Tes}}_{n}({\varvec{a}})$$ Tes n ( a ) is the set of upper triangular matrices with non-negative entries whose hook sum vector is $${\varvec{a}}$$ a . Motivated by a conjecture of Morales, we study the questions of whether the coefficients of the Ehrhart polynomial of $${\text {Tes}}_n(1,1,\dots ,1)$$ Tes n ( 1 , 1 , ⋯ , 1 ) are positive. We attack this problem by studying a certain function constructed by Berline–Vergne and its values on faces of a unimodularly equivalent copy of $${\text {Tes}}_n(1,1,\dots ,1)$$ Tes n ( 1 , 1 , ⋯ , 1 ) . We develop a method of obtaining the dot products appeared in formulas for computing Berline–Vergne’s function directly from facet normal vectors. Using this method together with known formulas, we are able to show Berline–Vergne’s function has positive values on codimension 2 and 3 faces of the polytopes we consider. As a consequence, we prove that the third and fourth coefficients of the Ehrhart polynomial of $${\text {Tes}}_{n}(1,\dots ,1)$$ Tes n ( 1 , ⋯ , 1 ) are positive. Using the Reduction Theorem by Castillo and the second author, we generalize the above result to all deformations of $${\text {Tes}}_{n}(1,\dots ,1)$$ Tes n ( 1 , ⋯ , 1 ) including all the integral Tesler polytopes.

We construct the first infinite families of locally 2-arc transitive graphs with the property that the automorphism group has two orbits on vertices and is quasiprimitive on exactly one orbit, of twisted wreath type. This work contributes to Giudici, Li and Praeger’s program for the classification of locally 2-arc transitive graphs by showing that the star normal quotient twisted wreath category also contains infinitely many graphs.

The Gelfand representation of $\mathcal{S}_n$ is the multiplicity-free direct sum of the irreducible representations of $\mathcal{S}_n$. In this paper, we use a result of Adin, Postnikov, and Roichman to find a recursive generating function for the Gelfand character. In order to find this generating function, we investigate descents of so-called $\lambda$-unimodal involutions.

In this note we report the classification of all symmetric 2-(36,15,6) designs that admit an automorphism of order 2 and their incidence matrices generate an extremal ternary self-dual code. It is shown that up to isomorphism, there exists only one such design, having a full automorphism group of order 24, and the ternary code spanned by its incidence matrix is equivalent to the Pless symmetry code., Comment: 12 pages

Let (W,S) be a Coxeter system. We introduce the boolean complex of involutions of W which is an analogue of the boolean complex of W studied by Ragnarsson and Tenner. By applying discrete Morse theory, we determine the homotopy type of the boolean complex of involutions for a large class of (W,S), including all finite Coxeter groups, finding that the homotopy type is that of a wedge of spheres of dimension |S| - 1. In addition, we find simple recurrence formulas for the number of spheres in the wedge., Comment: 17 pages, 6 figures

A set $$\mathcal {S}$$ S of points in $$\mathbb {R}^n$$ R n is called a rationally parameterizable hypersurface if there is vector function $$\varvec{\sigma }:\mathbb {R}^{n-1}\rightarrow \mathbb {R}^n$$ σ : R n - 1 → R n having as components rational functions defined on some common domain D such that $$\mathcal {S}=\{\varvec{\sigma }(\textbf{t}):\textbf{t}\in D\}$$ S = { σ ( t ) : t ∈ D } . A generalized n-dimensional polytope in $$\mathbb {R}^n$$ R n is a union of a finite number of convex n-dimensional polytopes in $$\mathbb {R}^n$$ R n . The Fourier–Laplace transform of such a generalized polytope $$\mathcal {P}$$ P in $$\mathbb {R}^n$$ R n is defined by $$F_{\mathcal {P}}(\textbf{z})=\int _{\mathcal {P}}e^{\textbf{z}\cdot \textbf{x}}\,\textbf{dx}$$ F P ( z ) = ∫ P e z · x dx . Let $$\gamma $$ γ be a fixed nonzero complex number. We prove that $$F_{\mathcal {P}_1}(\gamma \varvec{\sigma }(\textbf{t}))=F_{\mathcal {P}_2}(\gamma \varvec{\sigma }(\textbf{t}))$$ F P 1 ( γ σ ( t ) ) = F P 2 ( γ σ ( t ) ) for all $$\textbf{t} \in O$$ t ∈ O implies $$\mathcal {P}_1=\mathcal {P}_2$$ P 1 = P 2 if O is an open subset of D satisfying some well-defined conditions and we present similar results for the null set of the Fourier–Laplace transform of $$\mathcal {P}$$ P . Moreover we show that this theorem can be applied to quadric hypersurfaces that do not contain a line, but at least two points, i.e., in particular to spheres.

We study arrangements of intervals in $\mathbb{R}^2$ for which many pairs form trapezoids. We show that any set of intervals forming many trapezoids must have underlying algebraic structure, which we characterise. This leads to some unexpected examples of sets of intervals forming many trapezoids, where an important role is played by degree 2 curves., 14 pages, 11 figures

Let T d (n) be the set of d-ary rooted trees with n internal nodes. We give a method to construct a sequence (t n , n $\ge$ 0) where, for any n $\ge$ 1, t n has the uniform distribution in T d (n), and t n is constructed from t n--1 by the addition of a new node, and a rearrangement of the structure of t n--1. This method is inspired by R{\'e}my's algorithm which does this job in the binary case, but it is different from it. This provides a method for the random generation of a uniform d-ary tree in T d (n) with a cost linear in n.

For three distinct infinite families $$(R_m)$$ ( R m ) , $$(S_m)$$ ( S m ) , and $$(T_m)$$ ( T m ) of non-arithmetic 1-cusped hyperbolic Coxeter 3-orbifolds, we prove incommensurability for a pair of elements $$X_k$$ X k and $$Y_l$$ Y l belonging to the same sequence and for most pairs belonging two different ones. We investigate this problem first by means of the Vinberg space and the Vinberg form, a quadratic space associated to each of the corresponding fundamental Coxeter prism groups, which allows us to deduce some partial results. The complete proof is based on the analytic behavior of another commensurability invariant. It is given by the cusp density, and we prove and exploit its strict monotonicity.

We give a short proof of a result of Jordan and Tanigawa that a 4-connected graph which has a spanning planar triangulation as a proper subgraph is generically globally rigid in R^3. Our proof is based on a new sufficient condition for the so called vertex splitting operation to preserve generic global rigidity in R^d., Comment: Revision to v2: new results added in collaboration with Shin-ichi Tanigawa

Given a finite point set P in general position in the plane, a full triangulation of P is a maximal straight-line embedded plane graph on P. A partial triangulation of P is a full triangulation of some subset P' of P containing all extreme points in P. A bistellar flip on a partial triangulation either flips an edge (called edge flip), removes a non-extreme point of degree 3, or adds a point in P \ P' as vertex of degree 3. The bistellar flip graph has all partial triangulations as vertices, and a pair of partial triangulations is adjacent if they can be obtained from one another by a bistellar flip. The edge flip graph is defined with full triangulations as vertices, and edge flips determining the adjacencies. Lawson showed in the early seventies that these graphs are connected. The goal of this paper is to investigate the structure of these graphs, with emphasis on their vertex connectivity. For sets P of n points in the plane in general position, we show that the edge flip graph is inverted right perpendicularn/2 - 2inverted left perpendicular-vertex connected, and the bistellar flip graph is (n - 3)-vertex connected; both results are tight. The latter bound matches the situation for the subfamily of regular triangulations (i.e., partial triangulations obtained by lifting the points to 3-space and projecting back the lower convex hull), where (n - 3)-vertex connectivity has been known since the late eighties through the secondary polytope due to Gelfand, Kapranov, & Zelevinsky and Balinski's Theorem. For the edge flip-graph, we additionally show that the vertex connectivity is at least as large as (and hence equal to) the minimum degree (i.e., the minimum number of flippable edges in any full triangulation), provided that n is large enough. Our methods also yield several other results: (i) The edge flip graph can be covered by graphs of polytopes of dimension inverted right pependicularn/2 - 2inverted left pependicular (products of associahedra) and the bistellar flip graph can be covered by graphs of polytopes of dimension n - 3 (products of secondary polytopes). (ii) A partial triangulation is regular, if it has distance n - 3 in the Hasse diagram of the partial order of partial subdivisions from the trivial subdivision. (iii) All partial triangulations of a point set are regular iff the partial order of partial subdivisions has height n - 3. (iv) There are arbitrarily large sets P with non-regular partial triangulations and such that every proper subset has only regular triangulations, i.e., there are no small certificates for the existence of non-regular triangulations., Discrete & Computational Geometry, 68 (4), ISSN:0179-5376, ISSN:1432-0444