bluuebunny/crossref_metadata_2025 huggingface dataset:
Graph weights arising from Mayer and Ree-Hoover theories of virial expansions
Authors: Kaouche Amel , Leroux Pierre
Published: August 2021

We study graph weights (i.e., graph invariants) which arise naturally in Mayer's theory and Ree-Hoover's theory of virial expansions in the context of a non-ideal gas. We give special attention to the Second Mayer weight $w_M(c)$ and the Ree-Hoover weight $w_{RH}(c)$ of a $2$-connected graph $c$ which arise from the hard-core continuum gas in one dimension. These weights are computed using signed volumes of convex polytopes naturally associated with the graph $c$. Among our results are the values of Mayer's weight and Ree-Hoover's weight for all $2$-connected graphs $b$ of size at most $8$, and explicit formulas for certain infinite families.

Nous étudions les poids de graphes (c'est-à-dire, les invariants de graphes) qui apparaissent naturellement dans la théorie de Mayer et la théorie de Ree-Hoover pour le développement du viriel dans le contexte d'un gaz imparfait. Nous donnons une attention particulière au deuxième poids $w_M(c)$ de Mayer et au poids $w_{RH}(c)$ de Ree-Hoover d'un graphe $2$-connexe $c$ dans le cas d'un gaz à noyaux durs et à positions continues en une dimension. Ces poids sont calculés à partir de volumes signés de polytopes convexes associés naturellement au graphe $c$. Parmi nos résultats sont les valeurs du poids de Mayer et du poids de Ree-Hoover pour tous les graphes $2$-connexes $b$ de taille au plus $8$, et des formules explicites pour certaines familles infinies.
A bijection between shrubs and series-parallel posets
Authors: Chapoton Frédéric
Published: August 2021

Motivated by the theory of operads, we introduce new combinatorial objects, called shrubs, that generalize forests of rooted trees. We show that the species of shrubs is isomorphic to the species of series-parallel posets.

Motivé par des considérations sur les opérades, on introduit de nouveaux objets combinatoires, appelés arbustes, qui généralisent les forêts d'arbres enracinés. On montre que l'espèce des arbustes est isomorphe à l'espèce des posets Série-Parallèle.
New bounds and algorithms for on-line scheduling: two identical processors, known sum and upper bound on the tasks
Authors: Angelelli Enrico , Speranza Maria Grazia , Tuza Zsolt
Published: August 2021

In this paper we study a semi on-line version of the classical multiprocessor scheduling problem on two identical processors. We assume that the sum of the tasks and an upper bound gamma on the size of each task are known. Each task has to be assigned upon arrival and the assignment cannot be changed later. The objective is the minimization of the maximum completion time on the processors. In this paper we propose new algorithms and improve known lower and upper bounds on the competitive ratio. Algorithms and bounds depend on the value of gamma. An optimal algorithm is obtained for gamma in the interval [ 1/n,2(n+1)/n(2n+1) ] and gamma = (2n-1)/2n(n-1), where n is any integer value larger or equal 2.
Complexity results on graphs with few cliques
Authors: Rosgen Bill , Stewart Lorna
Published: August 2021

Graphs and Algorithms

A graph class has few cliques if there is a polynomial bound on the number of maximal cliques contained in any member of the class. This restriction is equivalent to the requirement that any graph in the class has a polynomial sized intersection representation that satisfies the Helly property. On any such class of graphs, some problems that are NP-complete on general graphs, such as the maximum clique problem and the maximum weighted clique problem, admit polynomial time algorithms. Other problems, such as the vertex clique cover and edge clique cover problems remain NP-complete on these classes. Several classes of graphs which have few cliques are discussed, and the complexity of some partitioning and covering problems are determined for the class of all graphs which have fewer cliques than a given polynomial bound.
Robot's hand and expansions in non-integer bases
Authors: Loreti Paola , Lai Anna Chiara
Published: August 2021

Combinatorics

We study a robot hand model in the framework of the theory of expansions in non-integer bases. We investigate the reachable workspace and we study some configurations enjoying form closure properties. Keywords: Robot hand, discrete control, expansions in non-integer bases, expansions in complex bases
Probe split graphs
Authors: Le Van Bang , Ridder H. N.
Published: August 2021

Graphs and Algorithms

An undirected graph G=(V,E) is a probe split graph if its vertex set can be partitioned into two sets, N (non-probes) and P (probes) where N is independent and there exists E' ⊆ N× N such that G'=(V,E∪ E') is a split graph. Recently Chang et al. gave an O(V4(V+E)) time recognition algorithm for probe split graphs. In this article we give O(V2+VE) time recognition algorithms and characterisations by forbidden induced subgraphs both for the case when the partition into probes and non-probes is given, and when it is not given.
Tiling a Pyramidal Polycube with Dominoes
Authors: Bodini Olivier , Jamet Damien
Published: August 2021

The notion of pyramidal polycubes, namely the piling-up of bricks of a non-increasing size, generalizes in R^n the concept of trapezoidal polyominoes. In the present paper, we prove that n-dimensional dominoes can tile a pyramidal polycube if and only if the latter is balanced, that is, if the number of white cubes is equal to the number of black ones for a chessboard-like coloration, generalizing the result of [BC92] when n=2.
An optimal permutation routing algorithm on full-duplex hexagonal networks
Authors: Sau Ignasi , Žerovnik Janez
Published: August 2021

Distributed Computing and Networking

In the permutation routing problem, each processor is the origin of at most one packet and the destination of no more than one packet. The goal is to minimize the number of time steps required to route all packets to their respective destinations, under the constraint that each link can be crossed simultaneously by no more than one packet. We study this problem in a hexagonal network, i.e. a finite subgraph of a triangular grid, which is a widely used network in practical applications. We present an optimal distributed permutation routing algorithm on full-duplex hexagonal networks, using the addressing scheme described by F.G. Nocetti, I. Stojmenovic and J. Zhang (IEEE TPDS 13(9): 962-971, 2002). Furthermore, we prove that this algorithm is oblivious and translation invariant.
Centerpoint theorems for wedges
Authors: Erickson Jeff , Hurtado Ferran , Morin Pat
Published: August 2021

General

The Centerpoint Theorem states that, for any set S of n points in R(d), there exists a point p in R(d) such that every closed halfspace containing p contains at least [n/(d + 1)] points of S. We consider generalizations of the Centerpoint Theorem in which halfspaces are replaced with wedges (cones) of angle alpha. In R(2), we give bounds that are tight for all values of ff and give an O(n) time algorithm to find a point satisfying these bounds. We also give partial results for R(3) and, more generally, R(d).
q-Enumeration of words by their total variation
Authors: Cristea Ligia Loreta , Prodinger Helmut
Published: August 2021

Combinatorics

In recent work, Mansour [Discrete Math. Theoret. Computer Science 11, 2009, 173--186] considers the problem of enumerating all words of length n over {1,2,...,k} (where k is a given integer), that have the total variation equal to a given integer m. In the present paper we study various types of random words over the infinite alphabet ℕ, where the letters have geometric probabilities. We are interested in the probabilities of words of given type to have a given total variation.
Generating involutions, derangements, and relatives by ECO
Authors: Vajnovszki Vincent
Published: August 2021

Combinatorics

We show how the ECO method can be applied to exhaustively generate some classes of permutations. A previous work initiating this technique and motivating our research was published in Ac ta Informatica, 2004, by S. Bacchelli, E. Barcucci, E. Grazzini and E. Pergola.
On edge-intersection graphs of k-bend paths in grids
Authors: Biedl Therese , Stern Michal
Published: August 2021

Edge-intersection graphs of paths in grids are graphs that can be represented such that vertices are paths in a grid and edges between vertices of the graph exist whenever two grid paths share a grid edge. This type of graphs is motivated by applications in conflict resolution of paths in grid networks. In this paper, we continue the study of edge-intersection graphs of paths in a grid, which was initiated by Golumbic, Lipshteyn and Stern. We show that for any k, if the number of bends in each path is restricted to be at most k, then not all graphs can be represented. Then we study some graph classes that can be represented with k-bend paths, for small k. We show that every planar graph has a representation with 5-bend paths, every outerplanar graph has a representation with 3-bend paths, and every planar bipartite graph has a representation with 2-bend paths. We also study line graphs, graphs of bounded pathwidth, and graphs with -regular edge orientations.
Cubefree words with many squares
Authors: Currie James , Rampersad Narad
Published: August 2021

Automata, Logic and Semantics

We construct infinite cubefree binary words containing exponentially many distinct squares of length n. We also show that for every positive integer n, there is a cubefree binary square of length 2n.
An improved bound on the largest induced forests for triangle-free planar graphs
Authors: Kowalik Lukasz , Luzar Borut , Skrekovski Riste
Published: August 2021

We proved that every planar triangle-free graph of order n has a subset of vertices that induces a forest of size at least (71n + 72)/128. This improves the earlier work of Salavatipour (2006). We also pose some questions regarding planar graphs of higher girth.
Coloring Geographical Threshold Graphs
Authors: Bradonjic Milan , Mueller Tobias , Percus Allon G.
Published: August 2021

Graphs and Algorithms

We propose a coloring algorithm for sparse random graphs generated by the geographical threshold graph (GTG) model, a generalization of random geometric graphs (RGG). In a GTG, nodes are distributed in a Euclidean space, and edges are assigned according to a threshold function involving the distance between nodes as well as randomly chosen node weights. The motivation for analyzing this model is that many real networks (e. g., wireless networks, the Internet, etc.) need to be studied by using a ''richer'' stochastic model (which in this case includes both a distance between nodes and weights on the nodes). Here, we analyze the GTG coloring algorithm together with the graph's clique number, showing formally that in spite of the differences in structure between GTG and RGG, the asymptotic behavior of the chromatic number is identical: chi = ln n/ln ln n(1 +o(1)). Finally, we consider the leading corrections to this expression, again using the coloring algorithm and clique number to provide bounds on the chromatic number. We show that the gap between the lower and upper bound is within C ln n/(ln ln n)(2), and specify the constant C.
On a Class of Optimal Stopping Problems with Mixed Constraints
Authors: Bruss F. Thomas
Published: August 2021

Let X(1),X(2),...,X(n) be independent, identically distributed uniform random variables on [0, 1]. We can observe the outcomes sequentially and must select online at least r of them, and, moreover, in expectation at least mu >= r. Here mu need not be integer. We see X(k) as the cost of selecting item k and want to minimize the expected total cost under the described combined (r, mu)-constraint. We will see that an optimal selection strategy exists on the set S(n) of all selection strategies for which the decision at instant k may depend on the value X(k), on the number N(k) of selections up to time k and of the number n - k of forthcoming observations. Let sigma(r,mu)(n) be the corresponding S(n)-optimal selection strategy and v(r,mu)(n) its value. The main goal of this paper is to determine these and to understand the limiting behavior of v(r,mu)(n). After discussion of the specific character of this combination of two types of constraints we conclude that the S(n)-problem has a recursive structure and solve it in terms of a double recursion. Our interest will then focus on the limiting behavior of nv(r,mu)(n) as n -> infinity. This sequence converges and its limit allows for the interpretation of a normalized limiting cost L (r, mu) of the (r, mu)-constraint. Our main result is that L(r, mu) = g(r) ((mu - r)(2)/(2)) where g(r) is the r(th) iterate of the function g(x) = 1 + x + root 1 + 2x. Our motivation to study mixed-constraints problems is indicated by several examples of possible applications. We also shortly discuss the intricacy of the expectational part of the constraint if we try to extend the class of strategies S n to the set of full-history-dependent and/or randomized strategies.
On certain non-unique solutions of the Stieltjes moment problem
Authors: Penson K. A. , Blasiak Pawel , Duchamp Gérard , Horzela A. , Solomon A. I.
Published: August 2021

We construct explicit solutions of a number of Stieltjes moment problems based on moments of the form ${\rho}_{1}^{(r)}(n)=(2rn)!$ and ${\rho}_{2}^{(r)}(n)=[(rn)!]^{2}$, $r=1,2,\dots$, $n=0,1,2,\dots$, \textit{i.e.} we find functions $W^{(r)}_{1,2}(x)>0$ satisfying $\int_{0}^{\infty}x^{n}W^{(r)}_{1,2}(x)dx = {\rho}_{1,2}^{(r)}(n)$. It is shown using criteria for uniqueness and non-uniqueness (Carleman, Krein, Berg, Pakes, Stoyanov) that for $r>1$ both ${\rho}_{1,2}^{(r)}(n)$ give rise to non-unique solutions. Examples of such solutions are constructed using the technique of the inverse Mellin transform supplemented by a Mellin convolution. We outline a general method of generating non-unique solutions for moment problems generalizing ${\rho}_{1,2}^{(r)}(n)$, such as the product ${\rho}_{1}^{(r)}(n)\cdot{\rho}_{2}^{(r)}(n)$ and $[(rn)!]^{p}$, $p=3,4,\dots$.
Distributional Analysis of the Parking Problem and Robin Hood Linear Probing Hashing with Buckets
Authors: Viola Alfredo
Published: August 2021

This paper presents the first distributional analysis of both, a parking problem and a linear probing hashing scheme with buckets of size b. The exact distribution of the cost of successful searches for a b alpha-full table is obtained, and moments and asymptotic results are derived. With the use of the Poisson transform distributional results are also obtained for tables of size m and n elements. A key element in the analysis is the use of a new family of numbers, called Tuba Numbers, that satisfies a recurrence resembling that of the Bernoulli numbers. These numbers may prove helpful in studying recurrences involving truncated generating functions, as well as in other problems related with buckets.
On the residual solvability of generalized free products of solvable groups
Authors: Kahrobaei Delaram , Majewicz Stephen
Published: August 2021

special issue in honor of Laci Babai's 60th birthday: Combinatorics, Groups, Algorithms, and Complexity

In this paper, we study the residual solvability of the generalized free product of solvable groups.
Separating the k-party communication complexity hierarchy: an application of the Zarankiewicz problem
Authors: Hayes Thomas P.
Published: August 2021

special issue in honor of Laci Babai's 60th birthday: Combinatorics, Groups, Algorithms, and Complexity

For every positive integer k, we construct an explicit family of functions f : \0, 1\(n) -\textgreater \0, 1\ which has (k + 1) - party communication complexity O(k) under every partition of the input bits into k + 1 parts of equal size, and k-party communication complexity Omega (n/k(4)2(k)) under every partition of the input bits into k parts. This improves an earlier hierarchy theorem due to V. Grolmusz. Our construction relies on known explicit constructions for a famous open problem of K. Zarankiewicz, namely, to find the maximum number of edges in a graph on n vertices that does not contain K-s,K-t as a subgraph.
On the number of factors in codings of three interval exchange
Authors: Ambrož Petr , Frid Anna , Masáková Zuzana , Pelantová Edita
Published: August 2021

Graph Theory

We consider exchange of three intervals with permutation (3, 2, 1). The aim of this paper is to count the cardinality of the set 3iet (N) of all words of length N which appear as factors in infinite words coding such transformations. We use the strong relation of 3iet words and words coding exchange of two intervals, i.e., Sturmian words. The known asymptotic formula #2iet(N)/N-3 similar to 1/pi(2) for the number of Sturmian factors allows us to find bounds 1/3 pi(2) +o(1) \textless= #3iet(N)N-4 \textless= 2 pi(2) + o(1)
8-star-choosability of a graph with maximum average degree less than 3
Authors: Chen Min , Raspaud André , Wang Weifan
Published: August 2021

Graphs and Algorithms

A proper vertex coloring of a graphGis called a star-coloring if there is no path on four vertices assigned to two colors. The graph G is L-star-colorable if for a given list assignment L there is a star-coloring c such that c(v) epsilon L(v). If G is L-star-colorable for any list assignment L with vertical bar L(v)vertical bar \textgreater= k for all v epsilon V(G), then G is called k-star-choosable. The star list chromatic number of G, denoted by X-s(l)(G), is the smallest integer k such that G is k-star-choosable. In this article, we prove that every graph G with maximum average degree less than 3 is 8-star-choosable. This extends a result that planar graphs of girth at least 6 are 8-star-choosable [A. Kundgen, C. Timmons, Star coloring planar graphs from small lists, J. Graph Theory, 63(4): 324-337, 2010].
On the algebraic numbers computable by some generalized Ehrenfest urns
Authors: Albenque Marie , Gerin Lucas
Published: August 2021

This article deals with some stochastic population protocols, motivated by theoretical aspects of distributed computing. We modelize the problem by a large urn of black and white balls from which at every time unit a fixed number of balls are drawn and their colors are changed according to the number of black balls among them. When the time and the number of balls both tend to infinity the proportion of black balls converges to an algebraic number. We prove that, surprisingly enough, not every algebraic number can be ''computed'' this way.
Optimal Computer Crash Performance Precaution
Authors: Laksman Efraim , Lennerstad Hakan , Lundberg Lars
Published: August 2021

Distributed Computing and Networking

For a parallel computer system with m identical computers, we study optimal performance precaution for one possible computer crash. We want to calculate the cost of crash precaution in the case of no crash. We thus define a tolerance level r meaning that we only tolerate that the completion time of a parallel program after a crash is at most a factor r + 1 larger than if we use optimal allocation on m - 1 computers. This is an r-dependent restriction of the set of allocations of a program. Then, what is the worst-case ratio of the optimal r-dependent completion time in the case of no crash and the unrestricted optimal completion time of the same parallel program? We denote the maximal ratio of completion times f(r, m) - i.e., the ratio for worst-case programs. In the paper we establish upper and lower bounds of the worst-case cost function f (r, m) and characterize worst-case programs.
Unary profile of lambda terms with restricted De Bruijn indices
Authors: Grygiel Katarzyna , Larcher Isabella
Published: August 2021

In this paper we present an average-case analysis of closed lambda terms with restricted values of De Bruijn indices in the model where each occurrence of a variable contributes one to the size. Given a fixed integer k, a lambda term in which all De Bruijn indices are bounded by k has the following shape: It starts with k De Bruijn levels, forming the so-called hat of the term, to which some number of k-colored Motzkin trees are attached. By means of analytic combinatorics, we show that the size of this hat is constant on average and that the average number of De Bruijn levels of k-colored Motzkin trees of size n is asymptotically Θ(√ n). Combining these two facts, we conclude that the maximal non-empty De Bruijn level in a lambda term with restrictions on De Bruijn indices and of size n is, on average, also of order √ n. On this basis, we provide the average unary profile of such lambda terms.
On-line ranking of split graphs
Authors: Borowiecki Piotr , Dereniowski Dariusz
Published: August 2021

Graphs and Algorithms

A vertex ranking of a graph G is an assignment of positive integers (colors) to the vertices of G such that each path connecting two vertices of the same color contains a vertex of a higher color. Our main goal is to find a vertex ranking using as few colors as possible. Considering on-line algorithms for vertex ranking of split graphs, we prove that the worst case ratio of the number of colors used by any on-line ranking algorithm and the number of colors used in an optimal off-line solution may be arbitrarily large. This negative result motivates us to investigate semi on-line algorithms, where a split graph is presented on-line but its clique number is given in advance. We prove that there does not exist a (2-ɛ)-competitive semi on-line algorithm of this type. Finally, a 2-competitive semi on-line algorithm is given.
A note on contracting claw-free graphs
Authors: Fiala Jiří , Kamiński Marcin , Paulusma Daniël
Published: August 2021

Discrete Algorithms

A graph containment problem is to decide whether one graph called the host graph can be modified into some other graph called the target graph by using a number of specified graph operations. We consider edge deletions, edge contractions, vertex deletions and vertex dissolutions as possible graph operations permitted. By allowing any combination of these four operations we capture the following problems: testing on (induced) minors, (induced) topological minors, (induced) subgraphs, (induced) spanning subgraphs, dissolutions and contractions. We show that these problems stay NP-complete even when the host and target belong to the class of line graphs, which form a subclass of the class of claw-free graphs, i.e., graphs with no induced 4-vertex star. A natural question is to study the computational complexity of these problems if the target graph is assumed to be fixed. We show that these problems may become computationally easier when the host graphs are restricted to be claw-free. In particular we consider the problems that are to test whether a given host graph contains a fixed target graph as a contraction.
Coupon collecting and transversals of hypergraphs
Authors: Wild Marcel , Janson Svante , Wagner Stephan , Laurie Dirk
Published: August 2021

Analysis of Algorithms

The classic Coupon-Collector Problem (CCP) is generalized. Only basic probability theory is used. Centerpiece rather is an algorithm that efficiently counts all k-element transversals of a set system.
A type B analog of the Lie representation
Authors: Berget Andrew
Published: August 2021

We describe a type B analog of the much studied Lie representation of the symmetric group. The nth Lie representation of Sn restricts to the regular representation of Sn−1, and our generalization mimics this property. Specifically, we construct a representation of the type B Weyl group Bn that restricts to the regular representation of Bn−1. We view both of these representations as coming from the internal zonotopal algebra of the Gale dual of the corresponding reflection arrangements.
Factorial Characters and Tokuyama's Identity for Classical Groups
Authors: Hamel Angèle M. , King Ronald C.
Published: August 2021

In this paper we introduce factorial characters for the classical groups and derive a number of central results. Classically, the factorial Schur function plays a fundamental role in traditional symmetric function theory and also in Schubert polynomial theory. Here we develop a parallel theory for the classical groups, offering combinatorial definitions of the factorial characters for the symplectic and orthogonal groups, and further establish flagged factorial Jacobi-Trudi identities and factorial Tokuyama identities, providing proofs in the symplectic case. These identities are established by manipulating determinants through the use of certain recurrence relations and by using lattice paths.
The colored symmetric and exterior algebras
Authors: Gonzalez D'Leon Rafael S.
Published: August 2021

In this extended abstract we present colored generalizations of the symmetric algebra and its Koszul dual, the exterior algebra. The symmetric group Sn acts on the multilinear components of these algebras. While Sn acts trivially on the multilinear components of the colored symmetric algebra, we use poset topology techniques to describe the representation on its Koszul dual. We introduce an Sn-poset of weighted subsets that we call the weighted boolean algebra and we prove that the multilinear components of the colored exterior algebra are Sn- isomorphic to the top cohomology modules of its maximal intervals. We show that the two colored Koszul dual algebras are Koszul in the sense of Priddy et al.
Weak Separation, Pure Domains and Cluster Distance
Authors: Farber Miriam , Galashin Pavel
Published: August 2021

Following the proof of the purity conjecture for weakly separated sets, recent years have revealed a variety of wider classes of pure domains in different settings. In this paper we show the purity for domains consisting of sets that are weakly separated from a pair of “generic” sets I and J. Our proof also gives a simple formula for the rank of these domains in terms of I and J. This is a new instance of the purity phenomenon which essentially differs from all previously known pure domains. We apply our result to calculate the cluster distance and to give lower bounds on the mutation distance between cluster variables in the cluster algebra structure on the coordinate ring of the Grassmannian. Using a linear projection that relates weak separation to the octahedron recurrence, we also find the exact mutation distances and cluster distances for a family of cluster variables.
Parabolic double cosets in Coxeter groups
Authors: Billey Sara , Konvalinka Matjaz , Petersen T. Kyle , Slofstra William , Tenner Bridget
Published: August 2021

Parabolic subgroups WI of Coxeter systems (W,S) and their ordinary and double cosets W/WI and WI\W/WJ appear in many contexts in combinatorics and Lie theory, including the geometry and topology of generalized flag varieties and the symmetry groups of regular polytopes. The set of ordinary cosets wWI , for I ⊆ S, forms the Coxeter complex of W , and is well-studied. In this extended abstract, we look at a less studied object: the set of all double cosets WIwWJ for I,J ⊆ S. Each double coset can be presented by many different triples (I, w, J). We describe what we call the lex-minimal presentation and prove that there exists a unique such choice for each double coset. Lex-minimal presentations can be enumerated via a finite automaton depending on the Coxeter graph for (W, S). In particular, we present a formula for the number of parabolic double cosets with a fixed minimal element when W is the symmetric group Sn. In that case, parabolic subgroups are also known as Young subgroups. Our formula is almost always linear time computable in n, and the formula can be generalized to any Coxeter group.
Rational Shi tableaux and the skew length statistic
Authors: Sulzgruber Robin
Published: August 2021

We define two refinements of the skew length statistic on simultaneous core partitions. The first one relies on hook lengths and is used to prove a refined version of the theorem stating that the skew length is invariant under conjugation of the core. The second one is equivalent to a generalisation of Shi tableaux to the rational level of Catalan combinatorics. We prove that the rational Shi tableau is injective. Moreover we present a uniform definition of the rational Shi tableau for Weyl groups and conjecture injectivity in the general case.
Cataland: Why the Fuss?
Authors: Stump Christian , Thomas Hugh , Williams Nathan
Published: August 2021

The main objects of noncrossing Catalan combinatorics associated to a finite Coxeter system are noncross- ing partitions, sortable elements, and cluster complexes. The first and the third of these have known Fuss–Catalan generalizations. We provide new viewpoints for these, introduce a corresponding generalization of sortable elements as elements in the positive Artin monoid, and show how this perspective ties together all three generalizations.
A two-sided analogue of the Coxeter complex
Authors: Petersen T. Kyle
Published: August 2021

For any Coxeter system (W, S) of rank n, we introduce an abstract boolean complex (simplicial poset) of dimension 2n − 1 which contains the Coxeter complex as a relative subcomplex. Faces are indexed by triples (J,w,K), where J and K are subsets of the set S of simple generators, and w is a minimal length representative for the double parabolic coset WJ wWK . There is exactly one maximal face for each element of the group W . The complex is shellable and thin, which implies the complex is a sphere for the finite Coxeter groups. In this case, a natural refinement of the h-polynomial is given by the “two-sided” W -Eulerian polynomial, i.e., the generating function for the joint distribution of left and right descents in W .
Hook formulas for skew shapes
Authors: Morales Alejandro H. , Pak Igor , Panova Greta
Published: August 2021

The celebrated hook-length formula gives a product formula for the number of standard Young tableaux of a straight shape. In 2014, Naruse announced a more general formula for the number of standard Young tableaux of skew shapes as a positive sum over excited diagrams of products of hook-lengths. We give two q-analogues of Naruse's formula for the skew Schur functions and for counting reverse plane partitions of skew shapes. We also apply our results to border strip shapes and their generalizations.
Slicings of parallelogram polyominoes, or how Baxter and Schröder can be reconciled
Authors: Bouvel Mathilde , Guerrini Veronica , Rinaldi Simone
Published: August 2021

We provide a new succession rule (i.e. generating tree) associated with Schröder numbers, that interpolates between the known succession rules for Catalan and Baxter numbers. We define Schröder and Baxter generalizations of parallelogram polyominoes (called slicings) which grow according to these succession rules. We also exhibit Schröder subclasses of Baxter classes, namely a Schröder subset of triples of non-intersecting lattice paths, and a new Schröder subset of Baxter permutations.
Separation of Variables and the Computation of Fourier Transforms on Finite Groups, II
Authors: Maslan David , Rockmore Daniel N. , Wolff Sarah
Published: August 2021

We present a general diagrammatic approach to the construction of efficient algorithms for computingthe Fourier transform of a function on a finite group. By extending work which connects Bratteli diagrams to theconstruction of Fast Fourier Transform algorithms we make explicit use of the path algebra connection and work inthe setting of quivers. In this setting the complexity of an algorithm for computing a Fourier transform reduces to pathcounting in the Bratelli diagram, and we generalize Stanley's work on differential posets to provide such counts. Ourmethods give improved upper bounds for computing the Fourier transform for the general linear groups over finitefields, the classical Weyl groups, and homogeneous spaces of finite groups.
Links in the complex of weakly separated collections
Authors: Oh Suho , Speyer David
Published: August 2021

Plabic graphs are combinatorial objects used to study the totally nonnegative Grassmannian. Faces of plabic graphs are labeled by k-element sets of positive integers, and a collection of such k-element sets are the face labels of a plabic graph if that collection forms a maximal weakly separated collection. There are moves that one can apply to plabic graphs, and thus to maximal weakly separated collections, analogous to mutations of seeds in cluster algebras. In this short note, we show if two maximal weakly separated collections can be mutated from one to another, then one can do so while freezing the face labels they have in common. In particular, this provides a new, and we think simpler, proof of Postnikov's result that any two reduced plabic graphs with the same decorated permutations can be mutated to each other.
Staircase diagrams and the enumeration of smooth Schubert varieties
Authors: Richmond Edward , Slofstra William
Published: August 2021

In this extended abstract, we give a complete description and enumeration of smooth and rationally smooth Schubert varieties in finite type. In particular, we show that rationally smooth Schubert varieties are in bijection with a new combinatorial data structure called staircase diagrams.
Counting quadrant walks via Tutte's invariant method (extended abstract)
Authors: Bernardi Olivier , Bousquet-Mélou Mireille , Raschel Kilian
Published: August 2021

Extended abstract presented at the conference FPSAC 2016, Vancouver.

In the 1970s, Tutte developed a clever algebraic approach, based on certain " invariants " , to solve a functional equation that arises in the enumeration of properly colored triangulations. The enumeration of plane lattice walks confined to the first quadrant is governed by similar equations, and has led in the past decade to a rich collection of attractive results dealing with the nature (algebraic, D-finite or not) of the associated generating function, depending on the set of allowed steps. We first adapt Tutte's approach to prove (or reprove) the algebraicity of all quadrant models known or conjectured to be algebraic (with one small exception). This includes Gessel's famous model, and the first proof ever found for one model with weighted steps. To be applicable, the method requires the existence of two rational functions called invariant and decoupling function respectively. When they exist, algebraicity comes out (almost) automatically. Then, we move to an analytic viewpoint which has already proved very powerful, leading in particular to integral expressions of the generating function in the non-D-finite cases, as well as to proofs of non-D-finiteness. We develop in this context a weaker notion of invariant. Now all quadrant models have invariants, and for those that have in addition a decoupling function, we obtain integral-free expressions of the generating function, and a proof that this series is differentially algebraic (that is, satisfies a non-linear differential equation).
Matrix product and sum rule for Macdonald polynomials
Authors: Cantini Luigi , De Gier Jan , Wheeler Michael
Published: August 2021

We present a new, explicit sum formula for symmetric Macdonald polynomials Pλ and show that they can be written as a trace over a product of (infinite dimensional) matrices. These matrices satisfy the Zamolodchikov– Faddeev (ZF) algebra. We construct solutions of the ZF algebra from a rank-reduced version of the Yang–Baxter algebra. As a corollary, we find that the normalization of the stationary measure of the multi-species asymmetric exclusion process is a Macdonald polynomial with all variables set equal to one.
Successor-Invariant First-Order Logic on Classes of Bounded Degree
Authors: Grange Julien
Published: August 2021

We study the expressive power of successor-invariant first-order logic, which
is an extension of first-order logic where the usage of an additional successor
relation on the structure is allowed, as long as the validity of formulas is
independent of the choice of a particular successor on finite structures.
We show that when the degree is bounded, successor-invariant first-order
logic is no more expressive than first-order logic.
Analysis of 300 Total Laparoscopic Hysterectomy Cases Performed by The Same Surgeon
Authors: Tamburacı Esra , Mulayim Barış
Published: August 2021

Aim: This study aimed to evaluate the results of 300 cases of total laparoscopic hysterectomy (TLH) performed by the same surgeon.

Material and methods: During the study period, a total of 300 TLH operations were performed between January 2017 and December 2018. Demographic characteristics, indications of hysterectomy, uterine weights, intra-operative and post-operative complications, duration of the operation, length of hospital stay, blood loss of patients, visual analogue scores and amount of analgesics needed were retrospectively evaluated. Complications were analysed and compared with literature.

Results: Parameters analysed for 300 patients included in the study were as follows: mean age 47.82 ± 6.18 years, mean parity 3.4 ± 2.0 (0–11), BMI 27.41 ± 4.36 (kg/m²), mean uterine weight 367.67 ± 266.21 g (50–1600 g), mean operative time 89.07 ± 37.94 min (30–240 min), mean hospital stay 54.37 ± 21.95 h (24–168 h) and total complication rate 28 (9.3%). Conversion to open surgery was required in 29 (9.7%) patients. The level of technical difficulty and existence of prior abdominal surgery were associated with a higher risk of complications and conversions to laparotomy.

Conclusion: Total laparoscopic hysterectomy is a well-designed surgical procedure for the management of benign gynaecological conditions, and after adequate training, it seems to be a safe and effective procedure for patients.
DEVELOPMENT OF A METHODOLOGY FOR ASSESSING THE FINANCIAL SECURITY OF SPECIALIZED DEVELOPERS
Authors:   Bryansk State University of Engineering and Technology, Kosyanova V.N.
Published: August 2021

One of the key tasks in the housing construction market is to ensure the reliability of the developer. The transition to the project financing mechanism requires specialized developers to comply with financial stability within the established standards. In modern economic conditions, to disclose the financial position of a company in the construction industry, a more comprehensive analysis is needed, including not only indicators of financial stability. The author adapted the financial security assessment model based on the indicator approach for specialized developers. The information base was the data of the portal of the Unified Register of developers, taking into account a specific territory (Bryansk region). The formulated and tested model made it possible to assess the financial security of the largest enterprises of the construction industry in the region, draw appropriate conclusions and offer management solutions within the framework of issues of various indicators
THE ROLE OF FINANCIAL RISK IN MANAGING THE CAPITAL STRUCTURE AND PERFORMANCE OF RUSSIAN COMPANIES
Authors:   Pitirim Sorokin Syktyvkar State University, Nekrasova G.A.
Published: August 2021

Issues related to the formation and optimization of the capital structure are an important component of the company's financial management system. The effectiveness of decisions depends on external and internal factors that affect the financial activities of the company, including financial risk. The article reveals the concept of financial risk and assesses its role in the analysis of the relationship between the capital structure and profitability indicators. It is established that the negative impact of the level of debt in the capital structure on the return on assets weakens as the financial risk increases, measured in terms of current liquidity coefficients and interest coverage. An increase in the debt burden leads to an increase in the return on equity when the company has enough funds to service the debt and the revenue variation is at an average level.
STATE SUPPORT OF ORGANIZATIONS IN THE CONTEXT OF OVERCOMING THE CONSEQUENCES OF THE 2020 PANDEMIC IN RUSSIA
Authors:   Samara State University of Economics, Khvostenko O.A.
Published: August 2021

The purpose of the study is to justify the need for state financial support of organizations affected by the COVID-19 coronavirus pandemic in Russia, to disclose its content, to assess the timeliness and sufficiency of the measures taken, to determine the directions for further improvement of these measures in order to overcome the negative consequences and have a positive impact on the economy.
EVALUATION OF USER PREFERENCES WHEN CHOOSING CLOUD SOFTWARE PRODUCTS
Authors:   Saint-Petersburg State University of Economics., Andreyevsky I.L. , Sokolov R.V. ,   Saint-Petersburg State University of Economics.
Published: August 2021

The article analyzes the assessment of user preferences when choosing cloud software products (CSP). The peculiarity of the choice of OPP is not only the choice of an enterprise - supplier of CSP of the necessary functionality, but also the choice of enterprises-intermediaries of cloud digitalization, which include an enterprise for designing a cloud information system (CIS) based on the selected CSP and a cloud data processing center during the operation of the CIS. A multidimensional characteristic of cloud digitalization enterprises used in the selection process is given. Since the criteria for choosing an CSP are vague, fuzzy numbers, an apparatus of fuzzy sets is proposed for evaluating user preferences.
SUSTAINABLE DEVELOPMENT OF INTERACTION OF INDUSTRIAL AND TRADE POLICY IN SOCIALLY SIGNIFICANT INDUSTRIES
Authors:   Omsk F.M. Dostoevsky State University, Roslyakova E.A.
Published: August 2021

The development of socially oriented industries is a fundamental component of the socio-economic development of the country. The co-dependence of industries and the state of industry in it gives the research topic relevance, since consumer satisfaction can be achieved both with the help of their own industrial development and with cooperation with foreign industrial companies. The problem of the issue is precisely that most branches of the domestic processing industry, including socially significant ones, are import-dependent, and the level at which the interaction of industrial and trade policy (hereinafter referred to as the IITP) in them determines the future of their further development. The purpose of the study is to determine the essence of the IITP, the sustainability (and) development in socially oriented industries by considering the development both within the interaction itself (setting priorities and distributing roles among the main participants in the interaction of industrial and trade policy), and within its phased implementation as a single organism. The achievement of the author's goal was facilitated by strategic, system and process approaches using general scientific research methods: comparative comparison, abstraction, logic, analysis, synthesis, etc. As a result of the conducted research, the scheme of interaction between the spheres of material and non-material production is presented; the definitions of the IITP are formulated; a cycle-model of the development of the IITP in socially oriented sectors of the national economy is developed; a comprehensive analysis of the set of certain indicators is recommended to assess the sustainability of the IITP development; the definition of the sustainable IITP development from the position of system formation and economic activity is presented.
ECONOMIC EFFICIENCY ASSESSMENT OF GEOLOGICAL EXPLORATION WORKS IN THE PROCESS OF GEOLOGICAL EXPLORATION OF SUBSURFACE RESOURCES
Authors:   Bryansk State Technical University, Dadykin V.S. , Dadykina O.V. ,   Bryansk State Technical University
Published: August 2021

The relevance of the economic assessment of the effectiveness of geological exploration works in the process of geological exploration of the subsurface resources consists not only in the need to ensure the stages of the geological exploration process, but also in the need to increase the reliability of the economic assessment of the effectiveness of geological exploration works in the process of geological exploration of the subsurface resources. As practice shows, it is the geological study of the subsurface that is the most expensive and high-risk process, the effectiveness of which largely depends on the ability to estimate the costs of increasing reserves with the greatest accuracy, especially in terms of industrial categories. Therefore, it is necessary to develop a methodology for evaluating the effectiveness of geological exploration, the use of which would allow estimating costs and results at the planning stage. The quality of geological exploration works at the object is determined by the increment of the initial geological and economic information. The greatest risks when performing geological exploration works arise when interacting between the state customer of geological exploration works at the early stages of geological exploration and geological organizations performing works under state contracts. As a result, a method of economic evaluation of the efficiency of geological exploration works in the process of geological exploration of the subsurface was proposed, which was tested on solid minerals, using the example of the Central Federal District.
ORGANIZATION OF PROTECTION AGAINST ACQUISITIONS AS FORMS OF CORPORATE CONFLICT IN FOREIGN AND RUSSIAN PRACTICE
Authors:   Financial University under the Government of the Russian Federation, Belyaeva I.Yu. , Danilova O.V. ,   Financial University under the Government of the Russian Federation, Uskov K.V. ,   Financial University under the Government of the Russian Federation
Published: August 2021

The article discusses the features of the organization of protection against acquisitions in foreign and Russian practice. The specifics of the manifestation of corporate conflicts, methods of acquisitions are analyzed, conclusions are formulated about the effect of the use of protective mechanisms and the peculiarities of the perception of these processes in Russia and abroad. Different companies apply different degrees of protection, and the question of why this happens remains open. No standard theoretical model has yet determined what explains the observed differences in the degree of protection of companies from acquisitions and how companies choose the degree of protection necessary for them.
Surgical treatment of bilateral fracture of the femoral diaphysis in a dog using intramedullary pins and cerclage – case report
Authors: da Luz Ferro Sayonara , Cardoso Ewerton , Jönck Fernanda , Thomas Heckler Marta Cristina , Warmling Bruna
Published: August 2021

Fractures are interruptions in bone continuity of frequent occurrence in small animal clinics. Causes vary widely and diagnosis is usually obtained during clinical examination and by means of radiography, which provide fundamental information regarding the type and complexity of the fracture. Long bones fractures are generally treated by open reduction and internal fixation; secondary methods may be associated in case of instability. The present study reports the case of a 5-month-old male mongrel dog with bilateral fracture of the femoral diaphysis caused by a car accident. The animal was attended at a private veterinary clinic in the city of Criciúma, SC, where it underwent surgery. Femoral osteosynthesis was obtained by means of multiple intramedullary pins associated with cerclage as a stabilization method, which was needed due to the characteristics of the fracture. The technique proved efficient to stabilize the fracture, without postoperative complications.