bluuebunny/crossref_metadata_2025 huggingface dataset:
Some exactly solvable models of urn process theory
Authors: Flajolet Philippe , Dumas Philippe , Puyhaubert Vincent
Published: August 2021

We establish a fundamental isomorphism between discrete-time balanced urn processes and certain ordinary differential systems, which are nonlinear, autonomous, and of a simple monomial form. As a consequence, all balanced urn processes with balls of two colours are proved to be analytically solvable in finite terms. The corresponding generating functions are expressed in terms of certain Abelian integrals over curves of the Fermat type (which are also hypergeometric functions), together with their inverses. A consequence is the unification of the analyses of many classical models, including those related to the coupon collector's problem, particle transfer (the Ehrenfest model), Friedman's "adverse campaign'' and Pólya's contagion model, as well as the OK Corral model (a basic case of Lanchester's theory of conflicts). In each case, it is possible to quantify very precisely the probable composition of the urn at any discrete instant. We study here in detail "semi-sacrificial'' urns, for which the following are obtained: a Gaussian limiting distribution with speed of convergence estimates as well as a characterization of the large and extreme large deviation regimes. We also work out explicitly the case of $2$-dimensional triangular models, where local limit laws of the stable type are obtained. A few models of dimension three or greater, e.g., "autistic'' (generalized Pólya), cyclic chambers (generalized Ehrenfest), generalized coupon-collector, and triangular urns, are also shown to be exactly solvable.
On the spectral dimension of random trees
Authors: Durhuus Bergfinnur , Jonsson Thordur , Wheater John
Published: August 2021

We determine the spectral dimensions of a variety of ensembles of infinite trees. Common to the ensembles considered is that sample trees have a distinguished infinite spine at whose vertices branches can be attached according to some probability distribution. In particular, we consider a family of ensembles of $\textit{combs}$, whose branches are linear chains, with spectral dimensions varying continuously between $1$ and $3/2$. We also introduce a class of ensembles of infinite trees, called $\textit{generic random trees}$, which are obtained as limits of ensembles of finite trees conditioned to have fixed size $N$, as $N \to \infty$. Among these ensembles is the so-called uniform random tree. We show that generic random trees have spectral dimension $d_s=4/3$.
A new method for computing asymptotics of diagonal coefficients of multivariate generating functions
Authors: Raichev Alexander , Wilson Mark C.
Published: August 2021

Let $\sum_{\mathbf{n} \in \mathbb{N}^d} F_{\mathbf{n}} \mathbf{x}^{\mathbf{n}}$ be a multivariate generating function that converges in a neighborhood of the origin of $\mathbb{C}^d$. We present a new, multivariate method for computing the asymptotics of the diagonal coefficients $F_{a_1n,\ldots,a_dn}$ and show its superiority over the standard, univariate diagonal method. Several examples are given in detail.
Sorting using complete subintervals and the maximum number of runs in a randomly evolving sequence: Extended abstract.
Authors: Janson Svante
Published: August 2021

We study the space requirements of a sorting algorithm where only items that at the end will be adjacent are kept together. This is equivalent to the following combinatorial problem: Consider a string of fixed length n that starts as a string of 0's, and then evolves by changing each 0 to 1, with the n changes done in random order. What is the maximal number of runs of 1's? We give asymptotic results for the distribution and mean. It turns out that, as in many problems involving a maximum, the maximum is asymptotically normal, with fluctuations of order $n^{1/2}$, and to the first order well approximated by the number of runs at the instance when the expectation is maximized, in this case when half the elements have changed to 1; there is also a second order term of order $n^{1/3}$. We also treat some variations, including priority queues and sock-sorting.
A variant of the Recoil Growth algorithm to generate multi-polymer systems
Authors: Simatos Florian
Published: August 2021

The Recoil Growth algorithm, proposed in 1999 by Consta $\textit{et al.}$, is one of the most efficient algorithm available in the literature to sample from a multi-polymer system. Such problems are closely related to the generation of self-avoiding paths. In this paper, we study a variant of the original Recoil Growth algorithm, where we constrain the generation of a new polymer to take place on a specific class of graphs. This makes it possible to make a fine trade-off between computational cost and success rate. We moreover give a simple proof for a lower bound on the irreducibility of this new algorithm, which applies to the original algorithm as well.
A functional limit law for the profile of plane-oriented recursive trees.
Authors: Sulzbach Henning
Published: August 2021

We give a functional limit law for the normalized profile of random plane-oriented recursive trees. The proof uses martingale convergence theorems in discrete and continuous-time. This complements results of Hwang (2007).
Subcritical pattern languages for and/or trees
Authors: Kozik Jakub
Published: August 2021

Let $P_k(f)$ denote the density of and/or trees defining a boolean function $f$ within the set of and/or trees with fixed number of variables $k$. We prove that there exists constant $B_f$ such that $P_k(f) \sim B_f \cdot k^{-L(f)-1}$ when $k \to \infty$, where $L(f)$ denote the complexity of $f$ (i.e. the size of a minimal and/or tree defining $f$). This theorem has been conjectured by Danièle Gardy and Alan Woods together with its counterpart for distribution $\pi$ defined by some critical Galton-Watson process. Methods presented in this paper can be also applied to prove the analogous property for $\pi$.
On the density and the structure of the Peirce-like formulae
Authors: Genitrini Antoine , Kozik Jakub , Matecki Grzegorz
Published: August 2021

Within the language of propositional formulae built on implication and a finite number of variables $k$, we analyze the set of formulae which are classical tautologies but not intuitionistic (we call such formulae - Peirce's formulae). We construct the large family of so called simple Peirce's formulae, whose sequence of densities for different $k$ is asymptotically equivalent to the sequence $\frac{1}{ 2 k^2}$. We prove that the densities of the sets of remaining Peirce's formulae are asymptotically bounded from above by $\frac{c}{ k^3}$ for some constant $c \in \mathbb{R}$. The result justifies the statement that in the considered language almost all Peirce's formulae are simple. The result gives a partial answer to the question stated in the recent paper by H. Fournier, D. Gardy, A. Genitrini and M. Zaionc - although we have not proved the existence of the densities for Peirce's formulae, our result gives lower and upper bound for it (if it exists) and both bounds are asymptotically equivalent to $\frac{1}{ 2 k^2}$.
Staircase Macdonald polynomials and the $q$-Discriminant
Authors: Boussicault Adrien , Luque Jean-Gabriel
Published: August 2021

We prove that a $q$-deformation $\mathfrak{D}_k(\mathbb{X};q)$ of the powers of the discriminant is equal, up to a normalization, to a specialization of a Macdonald polynomial indexed by a staircase partition. We investigate the expansion of $\mathfrak{D}_k(\mathbb{X};q)$ on different bases of symmetric functions. In particular, we show that its expansion on the monomial basis can be explicitly described in terms of standard tableaux and we generalize a result of King-Toumazet-Wybourne about the expansion of the $q$-discriminant on the Schur basis.

Nous montrons qu’une $q$-déformation $\mathfrak{D}_k(\mathbb{X};q)$ des puissances du discriminant est égale, à un coefficient de normalisation près, à un polynôme de Macdonald indexé par une partition escalier pour une certaine spécialisation des paramètres. Nous examinons les développements de $\mathfrak{D}_k(\mathbb{X};q)$ dans différentes bases de fonctions symétriques. En particulier, nous montrons que son écriture dans la base des fonctions monomiales peut être explicitement décrite en terme de tableaux standard et nous généralisons un résultat de King-Toumazet-Wybourne sur le développement du $q$-discriminant dans la base de Schur.
Approximation Algorithms for Multicoloring Planar Graphs and Powers of Square and Triangular Meshes
Authors: Kchikech Mustapha , Togni Olivier
Published: August 2021

A multicoloring of a weighted graph G is an assignment of sets of colors to the vertices of G so that two adjacent vertices receive two disjoint sets of colors. A multicoloring problem on G is to find a multicoloring of G. In particular, we are interested in a minimum multicoloring that uses the least total number of colors. The main focus of this work is to obtain upper bounds on the weighted chromatic number of some classes of graphs in terms of the weighted clique number. We first propose an 11/6-approximation algorithm for multicoloring any weighted planar graph. We then study the multicoloring problem on powers of square and triangular meshes. Among other results, we show that the infinite triangular mesh is an induced subgraph of the fourth power of the infinite square mesh and we present 2-approximation algorithms for multicoloring a power square mesh and the second power of a triangular mesh, 3-approximation algorithms for multicoloring powers of semi-toroidal meshes and of triangular meshes and 4-approximation algorithm for multicoloring the power of a toroidal mesh. We also give similar algorithms for the Cartesian product of powers of paths and of cycles.
Some new optimal and suboptimal infinite families of undirected double-loop networks
Authors: Chen Bao-Xing , Meng Ji-Xiang , Xiao Wen-Jun
Published: August 2021

Let n, s be positive integers such that 2 ≤ s < n and s = n/2 . An undirected double-loop network G(n; 1, s) is an undirected graph (V,E), where V =Zn={0, 1, 2, . . . , n−1} and E={(i, i+1 (mod n)), (i, i+s (mod n)) | i ∈ Z}. It is a circulant graph with n nodes and degree 4. In this paper, the sufficient and necessary conditions for a class of undirected double-loop networks to be optimal are presented. By these conditions, 6 new optimal and 5 new suboptimal infinite families of undirected double-loop networks are given.
Infinite special branches in words associated with beta-expansions
Authors: Frougny Christiane , Masáková Zuzana , Pelantová Edita
Published: August 2021

A Parry number is a real number β > 1 such that the Rényi β-expansion of 1 is finite or infinite eventually periodic. If this expansion is finite, β is said to be a simple Parry number. Remind that any Pisot number is a Parry number. In a previous work we have determined the complexity of the fixed point uβ of the canonical substitution associated with β-expansions, when β is a simple Parry number. In this paper we consider the case where β is a non-simple Parry number. We determine the structure of infinite left special branches, which are an important tool for the computation of the complexity of uβ. These results allow in particular to obtain the following characterization: the infinite word uβ is Sturmian if and only if β is a quadratic Pisot unit.
On hereditary Helly classes of graphs
Authors: Groshaus Marina , Szwarcfiter Jayme Luiz
Published: August 2021

Graphs and Algorithms

In graph theory, the Helly property has been applied to families of sets, such as cliques, disks, bicliques, and neighbourhoods, leading to the classes of clique-Helly, disk-Helly, biclique-Helly, neighbourhood-Helly graphs, respectively. A natural question is to determine for which graphs the corresponding Helly property holds, for every induced subgraph. This leads to the corresponding classes of hereditary clique-Helly, hereditary disk-Helly, hereditary biclique-Helly and hereditary neighbourhood-Helly graphs. In this paper, we describe characterizations in terms of families of forbidden subgraphs, for the classes of hereditary biclique-Helly and hereditary neighbourhood-Helly graphs. We consider both open and closed neighbourhoods. The forbidden subgraphs are all of fixed size, implying polynomial time recognition for these classes.
Combinatorial Route to Algebra: The Art of Composition & Decomposition
Authors: Blasiak Pawel
Published: August 2021

We consider a general concept of composition and decomposition of objects, and discuss a few natural properties one may expect from a reasonable choice thereof. It will be demonstrated how this leads to multiplication and co-multiplication laws, thereby providing a generic scheme furnishing combinatorial classes with an algebraic structure. The paper is meant as a gentle introduction to the concepts of composition and decomposition with the emphasis on combinatorial origin of the ensuing algebraic constructions.
A further analysis of Cuckoo Hashing with a Stash and Random Graphs of Excess r
Authors: Kutzelnigg Reinhard
Published: August 2021

Analysis of Algorithms

Cuckoo hashing is a hash table data structure offering constant access time, even in the worst case. As a drawback, the construction fails with small, but practically significant probability. However, Kirsch et al. (2008) showed that a constant-sized additional memory, the so called stash, is sufficient to reduce the failure rate drastically. But so far, using a modified insertion procedure that demands additional running time to look for an admissible key is required. As a major contribution of this paper, we show that the same bounds on the failure probability hold even without this search process and thus, the performance increases. Second, we extend the analysis to simplified cuckoo hashing, a variant of the original algorithm offering increased performance. Further, we derive some explicit asymptotic approximations concerning the number of usual resp. bipartite graphs related to the data structures. Using these results, we obtain much more precise asymptotic expansions of the success rate. These calculations are based on a generating function approach and applying the saddle point method. Finally, we provide numerical results to support the theoretical analysis.
On the analysis of ''simple'' 2D stochastic cellular automata
Authors: Regnault Damien , Schabanel Nicolas , Thierry Eric
Published: August 2021

Cellular automata are usually associated with synchronous deterministic dynamics, and their asynchronous or stochastic versions have been far less studied although significant for modeling purposes. This paper analyzes the dynamics of a two-dimensional cellular automaton, 2D Minority, for the Moore neighborhood (eight closest neighbors of each cell) under fully asynchronous dynamics (where one single random cell updates at each time step). 2D Minority may appear as a simple rule, but It is known from the experience of Ising models and Hopfield nets that 2D models with negative feedback are hard to study. This automaton actually presents a rich variety of behaviors, even more complex that what has been observed and analyzed in a previous work on 2D Minority for the von Neumann neighborhood (four neighbors to each cell) (2007) This paper confirms the relevance of the later approach (definition of energy functions and identification of competing regions) Switching to the Moot e neighborhood however strongly complicates the description of intermediate configurations. New phenomena appear (particles, wider range of stable configurations) Nevertheless our methods allow to analyze different stages of the dynamics It suggests that predicting the behavior of this automaton although difficult is possible, opening the way to the analysis of the whole class of totalistic automata
Edge-Removal and Non-Crossing Configurations in Geometric Graphs
Authors: Aichholzer Oswin , Cabello Sergio , Fabila-Monroy Ruy , Flores-Peñaloza David , Hackl Thomas , Huemer Clemens , Hurtado Ferran , Wood David R.
Published: August 2021

Graphs and Algorithms

A geometric graph is a graph G = (V, E) drawn in the plane, such that V is a point set in general position and E is a set of straight-line segments whose endpoints belong to V. We study the following extremal problem for geometric graphs: How many arbitrary edges can be removed from a complete geometric graph with n vertices such that the remaining graph still contains a certain non-crossing subgraph. The non-crossing subgraphs that we consider are perfect matchings, subtrees of a given size, and triangulations. In each case, we obtain tight bounds on the maximum number of removable edges.
Polynomial-time normalizers
Authors: Luks Eugene M. , Miyazaki Takunari
Published: August 2021

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

For an integer constant d \textgreater 0, let Gamma(d) denote the class of finite groups all of whose nonabelian composition factors lie in S-d; in particular, Gamma(d) includes all solvable groups. Motivated by applications to graph-isomorphism testing, there has been extensive study of the complexity of computation for permutation groups in this class. In particular, the problems of finding set stabilizers, intersections and centralizers have all been shown to be polynomial-time computable. A notable open issue for the class Gamma(d) has been the question of whether normalizers can be found in polynomial time. We resolve this question in the affirmative. We prove that, given permutation groups G, H \textless= Sym(Omega) such that G is an element of Gamma(d), the normalizer of H in G can be found in polynomial time. Among other new procedures, our method includes a key subroutine to solve the problem of finding stabilizers of subspaces in linear representations of permutation groups in Gamma(d).
On the complexity of vertex-coloring edge-weightings
Authors: Dudek Andrzej , Wajc David
Published: August 2021

Graphs and Algorithms

Given a graph G = (V; E) and a weight function omega : E -\textgreater R, a coloring of vertices of G, induced by omega, is defined by chi(omega) (nu) = Sigma(e(sic)nu) omega (e) for all nu is an element of V. In this paper, we show that determining whether a particular graph has a weighting of the edges from \1, 2\ that induces a proper vertex coloring is NP-complete.
The Variance of the Profile in Digital Search Trees
Authors: Kazemi Ramin , Vahidi-Asl Mohammad Q.
Published: August 2021

Analysis of Algorithms

What today we call digital search tree (DST) is Coffman and Eve's sequence tree introduced in 1970. A digital search tree is a binary tree whose ordering of nodes is based on the values of bits in the binary representation of a node's key. In fact, a digital search tree is a digital tree in which strings (keys, words) are stored directly in internal nodes. The profile of a digital search tree is a parameter that counts the number of nodes at the same distance from the root. In this paper we concentrate on external profile, i.e., the number of external nodes at level k when n strings are sorted. By assuming that the n input strings are independent and follow a (binary) memoryless source the asymptotic behaviour of the average profile was determined by Drmota and Szpankowski (2011). The purpose of the present paper is to extend their analysis and to provide a precise analysis of variance of the profile. The main (technical) difference is that we have to deal with an inhomogeneous part in a proper functional-differential equations satisfied by the second moment and Poisson variance. However, we show that the variance is asymptotically of the same order as the expected value which implies concentration. These results are derived by methods of analytic combinatorics such as generating functions, Mellin transform, Poissonization, the saddle point method and singularity analysis.
Digraph complexity measures and applications in formal language theory
Authors: Gruber Hermann
Published: August 2021

Automata, Logic and Semantics

We investigate structural complexity measures on digraphs, in particular the cycle rank. This concept is intimately related to a classical topic in formal language theory, namely the star height of regular languages. We explore this connection, and obtain several new algorithmic insights regarding both cycle rank and star height. Among other results, we show that computing the cycle rank is NP-complete, even for sparse digraphs of maximum outdegree 2. Notwithstanding, we provide both a polynomial-time approximation algorithm and an exponential-time exact algorithm for this problem. The former algorithm yields an O((log n)^(3/2))- approximation in polynomial time, whereas the latter yields the optimum solution, and runs in time and space O*(1.9129^n) on digraphs of maximum outdegree at most two. Regarding the star height problem, we identify a subclass of the regular languages for which we can precisely determine the computational complexity of the star height problem. Namely, the star height problem for bideterministic languages is NP-complete, and this holds already for binary alphabets. Then we translate the algorithmic results concerning cycle rank to the bideterministic star height problem, thus giving a polynomial-time approximation as well as a reasonably fast exact exponential algorithm for bideterministic star height.
Random Cayley digraphs of diameter 2 and given degree
Authors: Lladser Manuel E. , Potočnik Primož , Širáň Jozef , Wilson Mark C.
Published: August 2021

Graph Theory

We consider random Cayley digraphs of order n with uniformly distributed generating sets of size k. Specifically, we are interested in the asymptotics of the probability that such a Cayley digraph has diameter two as n -> infinity and k = f(n), focusing on the functions f(n) = left perpendicularn(delta)right perpendicular and f(n) = left perpendicularcnright perpendicular. In both instances we show that this probability converges to 1 as n -> infinity for arbitrary fixed delta is an element of (1/2, 1) and c is an element of (0, 1/2), respectively, with a much larger convergence rate in the second case and with sharper results for Abelian groups.
Crisp-determinization of weighted tree automata over strong bimonoids
Authors: Fülöp Zoltán , Kószó Dávid , Vogler Heiko
Published: August 2021

We consider weighted tree automata (wta) over strong bimonoids and their
initial algebra semantics and their run semantics. There are wta for which
these semantics are different; however, for bottom-up deterministic wta and for
wta over semirings, the difference vanishes. A wta is crisp-deterministic if it
is bottom-up deterministic and each transition is weighted by one of the unit
elements of the strong bimonoid. We prove that the class of weighted tree
languages recognized by crisp-deterministic wta is the same as the class of
recognizable step mappings. Moreover, we investigate the following two
crisp-determinization problems: for a given wta ${\cal A}$, (a) does there
exist a crisp-deterministic wta which computes the initial algebra semantics of
${\cal A}$ and (b) does there exist a crisp-deterministic wta which computes
the run semantics of ${\cal A}$? We show that the finiteness of the Nerode
algebra ${\cal N}({\cal A})$ of ${\cal A}$ implies a positive answer for (a),
and that the finite order property of ${\cal A}$ implies a positive answer for
(b). We show a sufficient condition which guarantees the finiteness of ${\cal
N}({\cal A})$ and a sufficient condition which guarantees the finite order
property of ${\cal A}$. Also, we provide an algorithm for the construction of
the crisp-deterministic wta according to (a) if ${\cal N}({\cal A})$ is finite,
and similarly for (b) if ${\cal A}$ has finite order property. We prove that it
is undecidable whether an arbitrary wta ${\cal A}$ is crisp-determinizable. We
also prove that both, the finiteness of ${\cal N}({\cal A})$ and the finite
order property of ${\cal A}$ are undecidable.
Generalized Fitch Graphs III: Symmetrized Fitch maps and Sets of Symmetric Binary Relations that are explained by Unrooted Edge-labeled Trees
Authors: Hellmuth Marc , Seemann Carsten R. , Stadler Peter F.
Published: August 2021

Binary relations derived from labeled rooted trees play an import role in
mathematical biology as formal models of evolutionary relationships. The
(symmetrized) Fitch relation formalizes xenology as the pairs of genes
separated by at least one horizontal transfer event. As a natural
generalization, we consider symmetrized Fitch maps, that is, symmetric maps
$\varepsilon$ that assign a subset of colors to each pair of vertices in $X$
and that can be explained by a tree $T$ with edges that are labeled with
subsets of colors in the sense that the color $m$ appears in $\varepsilon(x,y)$
if and only if $m$ appears in a label along the unique path between $x$ and $y$
in $T$. We first give an alternative characterization of the monochromatic case
and then give a characterization of symmetrized Fitch maps in terms of
compatibility of a certain set of quartets. We show that recognition of
symmetrized Fitch maps is NP-complete. In the restricted case where
$|\varepsilon(x,y)|\leq 1$ the problem becomes polynomial, since such maps
coincide with class of monochromatic Fitch maps whose graph-representations
form precisely the class of complete multi-partite graphs.
Connectivity for line-of-sight networks in higher dimensions
Authors: Devroye Luc , Farczadi Linda
Published: August 2021

Analysis of Algorithms

Let T be a d-dimensional toroidal grid of n^d points. For a given range parameter ω, and a positive integer k ≤q d, we say that two points in T are mutually visible if they differ in at most k coordinates and are a distance at most ω apart, where distance is measured using the \ellₚ norm. We obtain a random d-dimensional line-of-sight graph G by placing a node at each point in T independently with some fixed probability p^* and connecting all pairs of mutually visible nodes. We prove an asymptotically tight connectivity result for this random graph.
The Cerný conjecture for automata respecting intervals of a directed graph
Authors: Grech Mariusz , Kisielewicz Andrzej
Published: August 2021

Automata, Logic and Semantics

The Cerný's conjecture states that for every synchronizing automaton with n states there exists a reset word of length not exceeding (n - 1)2. We prove this conjecture for a class of automata preserving certain properties of intervals of a directed graph. Our result unifies and generalizes some earlier results obtained by other authors.
Flip-sort and combinatorial aspects of pop-stack sorting
Authors: Asinowski Andrei , Banderier Cyril , Hackl Benjamin
Published: August 2021

Flip-sort is a natural sorting procedure which raises fascinating
combinatorial questions. It finds its roots in the seminal work of Knuth on
stack-based sorting algorithms and leads to many links with permutation
patterns. We present several structural, enumerative, and algorithmic results
on permutations that need few (resp. many) iterations of this procedure to be
sorted. In particular, we give the shape of the permutations after one
iteration, and characterize several families of permutations related to the
best and worst cases of flip-sort. En passant, we also give some links between
pop-stack sorting, automata, and lattice paths, and introduce several tactics
of bijective proofs which have their own interest.
Intersections of Amoebas
Authors: Juhnke-Kubitzke Martina , De Wolff Timo
Published: August 2021

Amoebas are projections of complex algebraic varieties in the algebraic torus under a Log-absolute value map, which have connections to various mathematical subjects. While amoebas of hypersurfaces have been inten- sively studied during the last years, the non-hypersurface case is barely understood so far. We investigate intersections of amoebas of n hypersurfaces in (C∗)n, which are genuine supersets of amoebas given by non-hypersurface vari- eties. Our main results are amoeba analogs of Bernstein's Theorem and Be ́zout's Theorem providing an upper bound for the number of connected components of such intersections. Moreover, we show that the order map for hypersur- face amoebas can be generalized in a natural way to intersections of amoebas. We show that, analogous to the case of amoebas of hypersurfaces, the restriction of this generalized order map to a single connected component is still 1-to-1.
Resonance in orbits of plane partitions
Authors: Dilks Kevin , Pechenik Oliver , Striker Jessica
Published: August 2021

We introduce a new concept of resonance on discrete dynamical systems. Our main result is an equivariant bijection between plane partitions in a box under rowmotion and increasing tableaux under K-promotion, using a generalization of the equivariance of promotion and rowmotion [J. Striker–N. Williams '12] to higher dimensional lattices. This theorem implies new results for K-promotion and new proofs of previous results on plane partitions.
Toric matrix Schubert varieties and root polytopes (extended abstract)
Authors: Escobar Laura , Mészáros Karola
Published: August 2021

Start with a permutation matrix π and consider all matrices that can be obtained from π by taking downward row operations and rightward column operations; the closure of this set gives the matrix Schubert variety Xπ. We characterize when the ideal defining Xπ is toric (with respect to a 2n − 1-dimensional torus) and study the associated polytope of its projectivization. We construct regular triangulations of these polytopes which we show are geometric realizations of a family of subword complexes. We also show that these complexes can be realized geometrically via regular triangulations of root polytopes. This implies that a family of β-Grothendieck polynomials are special cases of reduced forms in the subdivision algebra of root polytopes. We also write the volume and Ehrhart series of root polytopes in terms of β-Grothendieck polynomials. Subword complexes were introduced by Knutson and Miller in 2004, who showed that they are homeomorphic to balls or spheres and raised the question of their polytopal realizations.
Extending the weak order on Coxeter groups
Authors: Viard Francois
Published: August 2021

We introduce a new family of complete lattices, arising from a digraph together with a valuation on its vertices and generalizing a previous construction of the author. We then apply this to the study of two long-standing conjectures of Dyer, and we provide a description of the Tamari lattice with this theory.
On q-integrals over order polytopes (extended abstract)
Authors: Kim Jang Soo
Published: August 2021

A q-integral over an order polytope coming from a poset is interpreted as a generating function of linear extensions of the poset. As an application, theq-beta integral and aq-analog of Dirichlet’s integral are computed. A combinatorial interpretation of aq-Selberg integral is also obtained.
Wiener Index and Remoteness in Triangulations and Quadrangulations
Authors: Czabarka Éva , Dankelmann Peter , Olsen Trevor , Székely László A.
Published: August 2021

Let $G$ be a a connected graph. The Wiener index of a connected graph is the
sum of the distances between all unordered pairs of vertices. We provide
asymptotic formulae for the maximum Wiener index of simple triangulations and
quadrangulations with given connectivity, as the order increases, and make
conjectures for the extremal triangulations and quadrangulations based on
computational evidence. If $\overline{\sigma}(v)$ denotes the arithmetic mean
of the distances from $v$ to all other vertices of $G$, then the remoteness of
$G$ is defined as the largest value of $\overline{\sigma}(v)$ over all vertices
$v$ of $G$. We give sharp upper bounds on the remoteness of simple
triangulations and quadrangulations of given order and connectivity.
The game colouring number of powers of forests
Authors: Andres Stephan Dominique , Hochstättler Winfried
Published: August 2021

We prove that the game colouring number of the $m$-th power of a forest of
maximum degree $\Delta\ge3$ is bounded from above by
\[\frac{(\Delta-1)^m-1}{\Delta-2}+2^m+1,\] which improves the best known bound
by an asymptotic factor of 2.
Factoriality and the Pin-Reutenauer procedure
Authors: Almeida J. , Costa J. C. , Zeitoun M.
Published: August 2021

We consider implicit signatures over finite semigroups determined by sets of
pseudonatural numbers. We prove that, under relatively simple hypotheses on a
pseudovariety V of semigroups, the finitely generated free algebra for the
largest such signature is closed under taking factors within the free pro-V
semigroup on the same set of generators. Furthermore, we show that the natural
analogue of the Pin-Reutenauer descriptive procedure for the closure of a
rational language in the free group with respect to the profinite topology
holds for the pseudovariety of all finite semigroups. As an application, we
establish that a pseudovariety enjoys this property if and only if it is full.
Constructions of words rich in palindromes and pseudopalindromes
Authors: Pelantová Edita , Starosta Štěpán
Published: August 2021

A narrow connection between infinite binary words rich in classical
palindromes and infinite binary words rich simultaneously in palindromes and
pseudopalindromes (the so-called $H$-rich words) is demonstrated.
The correspondence between rich and $H$-rich words is based on the operation
$S$ acting over words over the alphabet $\{0,1\}$ and defined by
$S(u_0u_1u_2\ldots) = v_1v_2v_3\ldots$, where $v_i= u_{i-1} + u_i \mod 2$.
The operation $S$ enables us to construct a new class of rich words and a new
class of $H$-rich words.
Finally, the operation $S$ is considered on the multiliteral alphabet
$\mathbb{Z}_m$ as well and applied to the generalized Thue--Morse words. As a
byproduct, new binary rich and $H$-rich words are obtained by application of
$S$ on the generalized Thue--Morse words over the alphabet $\mathbb{Z}_4$.
Semipaired Domination in Some Subclasses of Chordal Graphs
Authors: Henning Michael A. , Pandey Arti , Tripathi Vikash
Published: August 2021

A dominating set $D$ of a graph $G$ without isolated vertices is called
semipaired dominating set if $D$ can be partitioned into $2$-element subsets
such that the vertices in each set are at distance at most $2$. The semipaired
domination number, denoted by $\gamma_{pr2}(G)$ is the minimum cardinality of a
semipaired dominating set of $G$. Given a graph $G$ with no isolated vertices,
the \textsc{Minimum Semipaired Domination} problem is to find a semipaired
dominating set of $G$ of cardinality $\gamma_{pr2}(G)$. The decision version of
the \textsc{Minimum Semipaired Domination} problem is already known to be
NP-complete for chordal graphs, an important graph class. In this paper, we
show that the decision version of the \textsc{Minimum Semipaired Domination}
problem remains NP-complete for split graphs, a subclass of chordal graphs. On
the positive side, we propose a linear-time algorithm to compute a minimum
cardinality semipaired dominating set of block graphs. In addition, we prove
that the \textsc{Minimum Semipaired Domination} problem is APX-complete for
graphs with maximum degree $3$.
Sonoelastographic assessment of the normal uterus and ovaries using the Shear Wave Elastography according to different menstrual phases
Authors: Turan Özgür , Ertekin Ersen , Abdullayev Oghuz , Kuh Behram
Published: August 2021

Objective: In most of the gynecological studies conducted using the Shear Wave Elastography (SWE) method in the literature, the menstrual cycle period was not taken into account. Current study, we aimed to describe the sonoelastographic features of normal myometrium and ovaries in healthy women and to define their variability during the different phases of the menstrual cycle using the SWE method.
Material and methods: All cases were selected from individuals between the ages of 24-31, with regular menstrual cycles and no systemic disease. Each case was called in, 1-5th, 12-16th, 21-24th day of their menstrual cycles and was evaluated by B-mode imaging and SWE in pelvic ultrasonography. The relationship of menstrual phases with uterine and ovarian elasticity was investigated by comparing all measurements made in different menstrual phases.
Results: No statistically significant difference was observed between the volume of right and left ovaries in terms (p> 0.05). There was no statistically significant difference in terms of elastography measurements obtained from the uterus, right and left ovaries for each menstrual phase according to Bonferroni Correction (p> 0.0163).
Conclusion: Although there was a slight decrease in myometrial SWE measurements in the follicular phase, there was no significant difference regarding the SWE measurements of uterus and ovaries in early follicular, peri-ovulatory, and luteal menstrual stages. Further studies with a large number of participants are needed to suggest whether gynecological studies planned to be carried out with the shear wave elastography method should be planned in a specific menstrual phase.
Orthotopic ureterocele in bitch (Canis familiaris) – a case report
Authors: Oliveira Valério dos Santos Iara , Justen Moreira de Souza Heloisa , Siqueira da Silva Ricardo
Published: August 2021

Ureterocele is a dilation of the final portion of the ureter, which results from an embryological failure of unknown cause. This article describes the case of a three-month-old female poodle with complaints of urinary incontinence. Imaging exams helped establish the diagnosis by disclosing an orthotopic cystic dilation. The surgical technique employed to treat the condition was resection of the ureterocele with marsupialization of the edges. Complete remission of clinical signs was achieved two months post-surgery; the dog remains continent two years after the procedure.
Efficacy of sodium cefovecin in the treatment of canine bacterial superficial folliculitis
Authors: Dinelli Lopes Jéssica , Pelegrini Carla , Lucas Ronaldo , Beviani Daniela , Morales Tatiana , Algueros Camila , Merlo Alexandre
Published: August 2021

Superficial bacterial folicullitis is a common dermatologic disease that is caused mainly by Staphylococcus pseudintermedius, a pathogen from the dog skin microbiota. We retrospectively evaluated 1,817 cases of dogs with superficial bacterial folicullitis (primary or secondary) treated with sodium cefovecin (8 mg/kg, SQ) every 14 days, according to clinical need. 68.5% of dogs required a single dose of cefovecin (1,246/1,817); 28% of the animals (507/1.817) required two doses and 3.5% (64/1.817) demanded three doses. Overall, responses were considered satisfactory in 96% (1,744/1,817) of cases. Lack of efficacy was detected in 4% (73/1,817) of cases, and side effects were not observed in any treated dog. We concluded that cefovecin is an efficacious, safe and convenient treatment for superficial bacterial folicullitis in dogs.
DUPLEX–TRIPLEX TRANSITION IN COMPLEXES OF NUCLEIC ACIDS WITH HOECHST 33258
Authors: Parsadanyan Marine A.
Published: August 2021

The study of complexes of groove binding ligand Hoechst 33258 (H33258) with Calf Thymus DNA has been carried out. The data obtained revealed that the melting curves of the complexes of H33258 with DNA are monophasic at low ligand concentrations (0 < r ≤ 0.2) and become biphasic at relatively high concentrations (0.2 < r ≤ 0.33). This effect was revealed to depend on the ionic strength of the solution, and can also occur at high concentrations of the ligand. Comparison of the obtained data with the results for poly(rA)-poly(rU) and poly(dA)-poly(dT) shows a coincidence in the case of DNA and poly(rA)-poly(rU), while in the case of poly(dA)-poly(dT) the melting curves become biphasic at low ligand concentrations and actually do not depend on the ionic strength of the solution.
LEAN SIX SIGMA E INDUSTRIA 4.0, UNA REVISIÓN DESDE LA ADMINISTRACIÓN DE OPERACIONES PARA LA MEJORA CONTINUA DE LAS ORGANIZACIONES
Authors: Ramírez Pérez José Felipe , López Torres Virginia Guadalupe , Hernández Castillo Sergio Alonso , Morejón Valdés Maylevis
Published: August 2021

La administración de operaciones es un área de estudio de la administración que se centra en la gestión estratégica de las organizaciones. En un contexto mundial marcado por la globalización, la Industria 4.0 e impactado por la pandemia Covid-19, que ha generado mayor incertidumbre y complejidad para las empresas, la adopción de metodologías, métodos y herramientas de administración de operaciones constituye una necesidad para mejorar el desempeño empresarial. El objetivo de la investigación es discutir la contribución actual que tiene la metodología Lean Six Sigma en la mejora continua de las organizaciones, el aumento de la productividad y la competitividad. Se realiza la discusión a partir del análisis de las principales aseveraciones realizadas por académicos, investigadores y empresarios de reconocido prestigio en la temática a nivel mundial. La investigación tiene un enfoque cualitativo, el alcance es exploratorio y el diseño es no experimental. El análisis documental realizado por medio de la plataforma de la Web of Sciences de Clarivate Analytics arrojó 1015 resultados, los cuales fueron procesados por medio de la implementación de la metodología PRISMA. Los resultados obtenidos permiten afirmar que la implementación de la metodología Lean Six Sigma en las organizaciones contribuye a aumentar los niveles de productividad y competitividad. Los trabajos futuros deben dirigirse a evaluar cuantitativamente el impacto real y los beneficios que aporta a las empresas su adopción en el logro de una mayor eficiencia, productividad y obtención de ventajas competitivas sostenidas.
Excessive Use of Azithromycin in Pakistan amidst the Covid Pandemic
Authors: Shaikh Hafsa
Published: August 2021

The COVID pandemic has so far taken the lives of millions of people and is now experiencing a second wave. Excessive use of Azithromycin has become very common in Pakistan during this Pandemic . This can lead to development of drug resistance in a population which already has very limited antibiotic options available. Therefore it is necessary to follow antibiotic stewardship guidelines and impose laws that prevent sales of non-prescription antibiotic .
ANALISA LAPORAN KEUANGAN DAN INDIKATOR KEBANGKRUTAN PADA PT. MAYORA INDAH TBK
Authors: Aisyah Siti , Bahri Syamsul
Published: August 2021

One way that the company can do so that the company survives, namely by analyzing the company's financial statements, which aims to find out the company's financial situation and development from year to year. The author conducted research on PT. Mayora Indah Tbk, a company engaged in the processed food industry. The purpose of this study is to compare the balances that are considered related, which can reflect the company's financial position and the company's performance. This comparison is better known as the ratio. In addition to the analysis of financial statements, an analysis of indicators of bankruptcy is also carried out on the company's financial statements. Which aims to be able to find out how the condition of a company, whether the company is experiencing financial difficulties and or the possibility of bankruptcy. The research method used in this research is a case study research method with data analysis techniques that use the financial ratio method to determine the performance and financial position of PT. Mayora Indah Tbk, and the bankruptcy method of Altman Models to determine the viability of PT. Mayora Indah Tbk. From the results of the analysis, it shows that the performance and financial position of PT. Mayora Indah Tbk in 2014 to 2018 can be said to be still quite good in the midst of unstable economic turmoil in the period concerned. Where seen from the liquidity ratio and debt management ratio, the company is able to pay off its obligations; for asset management ratios, the company is able to utilize its resources effectively and efficiently; for its profitability ratio, the company has decreased. For the analysis of bankruptcy indicators, the results obtained from 2014 to 2018, the company entered the gray area. Thus, the company is expected to be able to improve itself by knowing the existing weaknesses, and be able to immediately make improvements in order to obtain better results in the coming year.
Syntactic study of mining and metallurgical terms with a negative affix
Authors: Qayumova Munavvar Sanakulovna  , Khayriddinova Zarnigor Vahobiddinovna
Published: August 2021

The following article is devoted to identifying the main problems of translation of metallurgical texts, the peculiarities of translation of terms and terminological combinations in the metallurgical sphere.
Muqimi's Relations With His Contemporaries and The Work He Did With Them
Authors: Muhitdinova Mukhlisa Satriddinovna  , Rustamov Dostonbek Jamshid ugli
Published: August 2021

The field of textual literature and literary source studies play an important role in thedevelopment of world culture and literary-aesthetic thinking. One of the urgent tasks is to study theancient sources of different periods, which have been preserved for centuries, and to use them to raisethe morale of society. The analysis and discussion of manuscript sources is also important in terms ofidentifying the scientific truth about literary heritage.
Data Collection and Distribution in Nigerian Higher Institutions: Problems and Way Forward
Authors: Ogunode Niyi Jacob
Published: August 2021

Higher institutions in Nigeria are facing many challenges. One of such challenges is lack ofcreditable data to plan and to take decisions on development of the institutions. This paper is aim todiscuss the problems of data collection and distribution in the Nigerian higher institutions. Secondarydata were employed to discuss the various points raised in the paper. The secondary data were sourcedfrom both hard ware and software resources. The paper identified inadequate funding, inadequateworking materials, shortage of professional data experts, poor capacity development of data mangersand inadequate infrastructural facilities as the problems preventing effective data collection anddistribution in the Nigerian higher institutions. To address these problems, the paper recommended thatthe government should increase the funding of higher institutions, more professional data mangersshould be employed, adequate working tools should be provided, training and retraining programmeshould be constantly provided for data mangers and school administrators should provide allinfrastructural facilities needed by units and departments handling data management in the varioushigher institutions in the country.
Problems of Power and Administrative Governance in Higher Education of Uzbekistan and the Need for Modernization of the Governance System
Authors: Abdurasulov Abdullajon Abdukarimovich
Published: August 2021

The article examines the high responsibility of Uzbekistan to the authorities and leaders in theprocess of reforming society within the framework of a new development process, bringing it to a newstage of development.
Features of The Development of The Health Insurance System in The World
Authors: Umurzakova Mutabarkhan Nodir qizi
Published: August 2021

This article analyzes the strengths and weaknesses of the existing global health care models and proposals for health care reform in the social protection system of Uzbekistan
Ethnic Related Toponyms of The Population in Surkhandarya Region
Authors: Umarova M. H
Published: August 2021

In Surkhandarya region, toponyms related to the ethnic composition of the population, including place names in the names of people, tribes and clans, ethnonyms associated with human names, as well as place names with certain tribal names are briefly described.
Study of The Physicochemical and Commercial Properties of NPK Fertilizers
Authors: Tursunov Shahboz  , Panjiev Olimjon
Published: August 2021

Kyzylkum phosphate rock was studied with a nitric acid content of 50 and 75 and 100%, as well as in fertilizers obtained from the ratio of R2O5: K2O = 1:1. The gyroscopic points of the fertilizer size of 2-3 mm were determined at 250 ° C by the desiccator method of N.Ye. Pestov. The points of hygroscopicity of fertilizer samples with an initial moisture content of 1.0% were No. 1 - 46.5%, No. 2 - 38.0% and No. 3 - 32.4%.