Search

In 2013, while studying a relevant class of polyominoes that tile the plane by translation, i.e., double square polyominoes, Blondin Massé et al. found that their boundary words, encoded by the Freeman chain coding on a four letters alphabet, have specific interesting properties that involve notions of combinatorics on words such as palindromicity, periodicity and symmetry. Furthermore, they defined a notion of reducibility on double squares using homologous morphisms, so leading to a set of irreducible tile elements called prime double squares. The authors, by inspecting the boundary words of the smallest prime double squares, conjectured the strong property that no runs of two (or more) consecutive equal letters are present there. In this paper, we prove such a conjecture using combinatorics on words' tools, and setting the path to the definition of a fast generation algorithm and to the possibility of enumerating the elements of this class w.r.t. standard parameters, as perimeter and area. [ABSTRACT FROM AUTHOR]

To any simple graph G , the clique graph operator K assigns the graph K (G) , which is the intersection graph of the maximal complete subgraphs of G . The iterated clique graphs are defined by K 0 (G) = G and K n (G) = K (K n - 1 (G)) for n ≥ 1 . We associate topological concepts to graphs by means of the simplicial complex Cl (G) of complete subgraphs of G . Hence, we say that the graphs G 1 and G 2 are homotopic whenever Cl (G 1) and Cl (G 2) are. A graph G such that K n (G) ≃ G for all n ≥ 1 is called K -homotopy permanent. A graph is Helly if the collection of maximal complete subgraphs of G has the Helly property. Let G be a Helly graph. Escalante (1973) proved that K (G) is Helly, and Prisner (1992) proved that G ≃ K (G) , and so Helly graphs are K -homotopy permanent. We conjecture that if a graph G satisfies that K m (G) is Helly for some m ≥ 1 , then G is K -homotopy permanent. If a connected graph has maximum degree at most four and is different from the octahedral graph, we say that it is a low degree graph. It was recently proven that all low-degree graphs G satisfy that K 2 (G) is Helly. In this paper, we show that all low-degree graphs have the homotopy type of a wedge or circumferences, and that they are K -homotopy permanent. [ABSTRACT FROM AUTHOR]

Let p be a prime and let r , s be positive integers. In this paper, we prove that the Goormaghtigh equation $(x^m-1)/(x-1)=(y^n-1)/(y-1)$ , $x,y,m,n \in {\mathbb {N}}$ , $\min \{x,y\}>1$ , $\min \{m,n\}>2$ with $(x,y)=(p^r,p^s+1)$ has only one solution $(x,y,m,n)=(2,5,5,3)$. This result is related to the existence of some partial difference sets in combinatorics. [ABSTRACT FROM AUTHOR]

In this paper, we are interested in a special class of integer matrices, namely the power-product matrix, defined with two positive integers n and d. Each matrix element is computed by a power-product of two weak compositions of d into n parts. The power-product matrix has several interesting applications such as the power-sum representation of polynomials and the difference-of-convex-sums-of-squares decomposition of polynomials. We investigate some properties of this matrix including: nonsingularity, sparsity and determinant. Based on techniques in enumerative combinatorics, we prove that the power-product matrix is nonsingular and the number of nonzero entries can be computed exactly. This matrix shows sparse structure which is a good feature in numerical computation of its inverse required in some applications. Special attention is devoted to the computation of the determinant for n = 2 whose explicit formulation is obtained. [ABSTRACT FROM AUTHOR]

Feynman diagrams represent one of the most powerful and fascinating tools developed in theoretical physics in the last century. Introduced within the framework of quantum electrodynamics as a suitable method for computing the amplitude of a physical process, they rapidly became a fundamental mathematical object in quantum field theory. However, their abstract nature seems to suggest a wider usage, which actually exceeds the physical context. Indeed, as mathematical objects, they could simply be considered graphs that depict not only physical quantities but also biological or economic entities. We survey the analytical and algebraic properties of such diagrams to understand their utility in several areas of science, eventually providing some examples of recent applications. [ABSTRACT FROM AUTHOR]

The method of hypergraph containers, which was introduced several years ago by Balogh, Morris, and Samotij, and independently by Saxton and Thomason, has proved to be an extremely useful tool in the study of various monotone graph properties. In particular, a fairly straightforward application of this technique allows one to locate, for each non-bipartite graph H, the threshold at which the distribution of edges in a typical H-free graph with a given number of edges undergoes a transition from 'random-like' to 'structured'. On the other hand, for nonmonotone hereditary graph properties, the standard version of this method does not allow one to establish even the existence of such a threshold. In this paper we introduce a refinement of the container method that takes into account the asymmetry between edges and non-edges in a sparse member of a hereditary graph property. As an application, we determine the approximate structure of a typical graph with n vertices, m edges, and no induced copy of the 4-cycle, for each function m D m.n/ satisfying n4=3.log n/4 6 m n2. We show that almost all such graphs G have the following property: the vertex set of G can be partitioned into an 'almost independent' set (a set with o.m/ edges) and an 'almost-clique' (a set inducing a subgraph with density 1-a The lower bound on m is optimal up to a polylogarithmic factor, as standard arguments show that if n then almost all such graphs are 'random-like'. As a further consequence, we deduce that the random graph G.n; p/ conditioned to contain no induced 4-cycles undergoes phase transitions at p=n -2/3+o(1) p=n -2/3+o(1). [ABSTRACT FROM AUTHOR]

A family F of sets is said to be t -intersecting if for any A; B 2 F . The seminal Complete Intersection Theorem of Ahlswede and Khachatrian (1997) gives the maximal size f .n; k; t of a t -intersecting family of k-element subsets of OEn D together with a characterisation of the extremal families, solving a longstanding problem of Frankl. The forbidden intersection problem, posed by Erdos and Sós in 1971, asks for a determination of the maximal size g.n; k; t / of a family F of k-element subsets of OEn such that jA \ Bj ¤ for any A, B F. [ABSTRACT FROM AUTHOR]

Ecological networks describe the interactions between different species, informing us how they rely on one another for food, pollination, and survival. If a species in an ecosystem is under threat of extinction, it can affect other species in the system and possibly result in their secondary extinction as well. Understanding how (primary) extinctions cause secondary extinctions on ecological networks has been considered previously using computational methods. However, these methods do not provide an explanation for the properties that make ecological networks robust, and they can be computationally expensive. We develop a new analytic model for predicting secondary extinctions that requires no stochastic simulation. Our model can predict secondary extinctions when primary extinctions occur at random or due to some targeting based on the number of links per species or risk of extinction, and can be applied to an ecological network of any number of layers. Using our model, we consider how false negatives and positives in network data affect predictions for network robustness. We have also extended the model to predict scenarios in which secondary extinctions occur once species lose a certain percentage of interaction strength, and to model the loss of interactions as opposed to just species extinction. From our model, it is possible to derive new analytic results such as how ecological networks are most robust when secondary species are of equal degree. Additionally, we show that both specialization and generalization in the distribution of interaction strength can be advantageous for network robustness, depending upon the extinction scenario being considered. [ABSTRACT FROM AUTHOR]

Developing a mathematical understanding of autocatalysis in reaction networks has both theoretical and practical implications. We review definitions of autocatalytic networks and prove some properties for minimal autocatalytic subnetworks (MASs). We show that it is possible to classify MASs in equivalence classes, and develop mathematical results about their behavior. We also provide linear-programming algorithms to exhaustively enumerate them and a scheme to visualize their polyhedral geometry and combinatorics. We then define cluster chemical reaction networks, a framework for coarse-graining real chemical reactions with positive integer conservation laws. We find that the size of the list of minimal autocatalytic subnetworks in a maximally connected cluster chemical reaction network with one conservation law grows exponentially in the number of species. We end our discussion with open questions concerning an ecosystem of autocatalytic subnetworks and multidisciplinary opportunities for future investigation. [ABSTRACT FROM AUTHOR]

Network alignment aims to uncover topologically similar regions in the protein–protein interaction (PPI) networks of two or more species under the assumption that topologically similar regions tend to perform similar functions. Although there exist a plethora of both network alignment algorithms and measures of topological similarity, currently no "gold standard" exists for evaluating how well either is able to uncover functionally similar regions. Here we propose a formal, mathematically and statistically rigorous method for evaluating the statistical significance of shared GO terms in a global, 1-to-1 alignment between two PPI networks. Given an alignment in which k aligned protein pairs share a particular GO term g, we use a combinatorial argument to precisely quantify the p-value of that alignment with respect to g compared to a random alignment. The p-value of the alignment with respect to all GO terms, including their inter-relationships, is approximated using the Empirical Brown's Method. We note that, just as with BLAST's p-values, this method is not designed to guide an alignment algorithm towards a solution; instead, just as with BLAST, an alignment is guided by a scoring matrix or function; the p-values herein are computed after the fact, providing independent feedback to the user on the biological quality of the alignment that was generated by optimizing the scoring function. Importantly, we demonstrate that among all GO-based measures of network alignments, ours is the only one that correlates with the precision of GO annotation predictions, paving the way for network alignment-based protein function prediction. [ABSTRACT FROM AUTHOR]

This paper proposes explicit solutions for the algebraic Riccati matrix equation. For single‐input systems in controllable canonical form, the explicit Hermitian solutions of the non‐homogeneous Riccati equation are obtained using the entries of the system matrix, the closed‐loop system matrix, and the weighting matrix. The unknown entries of the closed‐loop system matrix are solved by scalar quadratic equations. For a homogeneous Riccati equation with a zero weighting matrix, the explicit solutions are proposed analytically in terms of the system eigenvalues. The advantages of the explicit solutions are threefold: first, if the system is controllable, the solution is directly given and the invariant subspaces of the Hamiltonian matrix are not required; second, if the system is near singularity, the explicit solution has higher numerical precision compared with the solution computed by numerical algorithms; third, for a real system in the controllable canonical form, the non‐negativity can be analysed for the explicit almost stabilizing solution. [ABSTRACT FROM AUTHOR]

Over the past two decades, the study of self-similarity and fractality in discrete structures, particularly complex networks, has gained momentum. This surge of interest is fueled by the theoretical developments within the theory of complex networks and the practical demands of real-world applications. Nonetheless, translating the principles of fractal geometry from the domain of general topology, dealing with continuous or infinite objects, to finite structures in a mathematically rigorous way poses a formidable challenge. In this paper, we overview such a theory that allows to identify and analyze fractal networks through the innate methodologies of graph theory and combinatorics. It establishes the direct graph-theoretical analogs of topological (Lebesgue) and fractal (Hausdorff) dimensions in a way that naturally links them to combinatorial parameters that have been studied within the realm of graph theory for decades. This allows to demonstrate that the self-similarity in networks is defined by the patterns of intersection among densely connected network communities. Moreover, the theory bridges discrete and continuous definitions by demonstrating how the combinatorial characterization of Lebesgue dimension via graph representation by its subsets (subgraphs/communities) extends to general topological spaces. Using this framework, we rigorously define fractal networks and connect their properties with established combinatorial concepts, such as graph colorings and descriptive complexity. The theoretical framework surveyed here sets a foundation for applications to real-life networks and future studies of fractal characteristics of complex networks using combinatorial methods and algorithms. [ABSTRACT FROM AUTHOR]

Whole-brain connectome data characterize the connections among distributed neural populations as a set of edges in a large network, and neuroscience research aims to systematically investigate associations between brain connectome and clinical or experimental conditions as covariates. A covariate is often related to a number of edges connecting multiple brain areas in an organized structure. However, in practice, neither the covariate-related edges nor the structure is known. Therefore, the understanding of underlying neural mechanisms relies on statistical methods that are capable of simultaneously identifying covariate-related connections and recognizing their network topological structures. The task can be challenging because of false-positive noise and almost infinite possibilities of edges combining into subnetworks. To address these challenges, we propose a new statistical approach to handle multivariate edge variables as outcomes and output covariate-related subnetworks. We first study the graph properties of covariate-related subnetworks from a graph and combinatorics perspective and accordingly bridge the inference for individual connectome edges and covariate-related subnetworks. Next, we develop efficient algorithms to exact covariate-related subnetworks from the whole-brain connectome data with an |$\ell_0$| norm penalty. We validate the proposed methods based on an extensive simulation study, and we benchmark our performance against existing methods. Using our proposed method, we analyze two separate resting-state functional magnetic resonance imaging data sets for schizophrenia research and obtain highly replicable disease-related subnetworks. [ABSTRACT FROM AUTHOR]

Combinatorial proofs of binomial identities involve establishing an identity by arguing that each side enumerates a certain set of outcomes. In this paper, we share results from interviews with experienced provers (mathematicians and upper-division undergraduate mathematics students) and examine one particular aspect of combinatorial proof, namely the kinds of contexts that experienced provers used to establish combinatorial proofs of binomial identities. Our findings show that overall, our participants used a variety of contexts in their work; we also demonstrate ways in which previous experiences influenced the contexts they chose, and we offer some instances in which features of a context supported their combinatorial proof production. We offer some theoretical implications of our work, and we conclude with a discussion of limitations and avenues for future work. [ABSTRACT FROM AUTHOR]

Though previously unacknowledged, a SMART (Sequential Multiple Assignment Randomized Trial) design uses both regression discontinuity (RD) and randomized controlled trial (RCT) designs. This combination structure creates a conceptual symbiosis between the two designs that enables both RCT- and previously unrecognized, RD-based inferential claims. In Phase 1, based on a quantitative cut-point, a SMART design yields successful or unsuccessful participants after the initial RCT. In Phase 2, interventions are randomly assigned to successful and unsuccessful, Phase 1 subgroups, thereby yielding both RCT and RD results. Like RCT-based inferences, many but not all newly recognized, RD-based SMART inferences are potentially unbiased. In particular, comparisons between RCT and RD outcomes are potentially problematic. Principles from the within-study comparison literature are used to inform SMART-based research, thereby introducing otherwise ignored inferential and procedural possibilities. Awareness of RD designs embedded within SMARTs encourages previously unrecognized inferential claims, though potential internal validity threats and limitations must be carefully weighed. Finally, new, SMART-like sequences of quasi-experiments and experiments can be tested and embedded logic applied. [ABSTRACT FROM AUTHOR]

We prove that for n = 2 and n = 3 there is a forcing extension with exactly n near-coherence classes of non-principal ultrafilters. We introduce localized versions of Matet forcing and we develop Ramsey spaces of names. The evaluation of some of the new forcings is based on a relative of Hindman's theorem due to Blass 1987. [ABSTRACT FROM AUTHOR]

Let G be a non-compact classical semisimple Lie group and let G / V be the adjoint orbit with respect to a fixed element in G. These manifolds can be equipped with an almost-Kähler structure and we provide explicit formulae for the existence of special almost-complex structures on G / V purely in terms of the combinatorics of the associated Vogan diagram. The formulae are given separately for Lie groups whose Lie algebras are of type A ℓ , B ℓ , C ℓ , D ℓ , where ℓ denotes the rank of the Lie algebra. [ABSTRACT FROM AUTHOR]

The issue of counting independent sets of a graph, G, represented as i (G) , is a significant challenge within combinatorial mathematics. This problem finds practical applications across various fields, including mathematics, computer science, physics, and chemistry. In chemistry, i (G) is recognized as the Merrifield–Simmons (M-S) index for molecular graphs, which is one of the most relevant topological indices related to the boiling point in chemical compounds. This article introduces an innovative algorithm designed for tallying independent sets within grid-like structures. The proposed algorithm is based on the 'branch-and-bound' technique and is applied to compute i (G m , n) for a square grid formed by m rows and n columns. The proposed approach incorporates the widely recognized vertex reduction rule as the basis for splitting the current subgraph. The methodology involves breaking down the initial grid iteratively until outerplanar graphs are achieved, serving as the 'basic cases' linked to the leaf nodes of the computation tree or when no neighborhood is incident to a minimum of five rectangular internal faces. The time complexity of the branch-and-bound algorithm speeds up the computation of i (G m , n) compared to traditional methods, like the transfer matrix method. Furthermore, the scope of the proposed algorithm is more general than the algorithms focused on grids since it could be applied to process general mesh graphs. [ABSTRACT FROM AUTHOR]

Mathematical science is the human recognition on the evolution laws of things that we can understand with the principle of logical consistency by mathematics, i.e., math-ematical reality. So, is the mathematical reality equal to the reality of thing? The answer is not because there always exists contradiction between things in the eyes of human, which is only a local or conditional conclusion. Such a situation enables us to extend the mathe-matics further by combinatorics for the reality of thing from the local reality and then, to get a combinatorial reality of thing. This is the combinatorial conjecture for mathematical science, i.e., CC conjecture that I put forward in my postdoctoral report for Chinese Acade-my of Sciences in 2005, namely any mathematical science can be reconstructed from or made by combinatorialization. After discovering its relation with Smarandache multi-spaces, it is then be applied to generalize mathematics over 1-dimensional topological graphs, namely the mathematical combinatorics that I promoted on science internationally for more than 20 years. This paper surveys how I proposed this conjecture from combinatorial topology, how to use it for characterizing the non-uniform groups or contradictory systems and furthermore, why I introduce the continuity ow GL as a mathematical element, i.e., vectors in Banach space over topological graphs with operations and then, how to apply it to generalize a few of important conclusions in functional analysis for providing the human recognition on the reality of things, including the subdivision of substance into elementary particles or quarks in theoretical physics with a mathematical supporting. [ABSTRACT FROM AUTHOR]

The Saṅgīta-ratnākara (Ocean of Music) of Śārṅgadeva (c. 1225 CE) is a 13th century text on musicology in Sanskrit. The fifth chapter of the Saṅgīta-ratnākara deals with a general analysis of all possible rhythms (tāla s) which can be obtained by combining a set of basic rhythmic components known as tālāṅga s. Here, Śārṅgadeva describes the construction of the saṃyoga-meru (Table of Combinations), a tool that tabulates the total number of possible tāla s of a given duration which are obtained by combining elements of different subsets of tālāṅga s. In this paper, we discuss the mathematical rationale employed by Śārṅgadeva in the construction of the saṃyoga-meru. [ABSTRACT FROM AUTHOR]

We establish a connection between the algebraic geometry of the type B$B$ permutohedral toric variety and the combinatorics of delta‐matroids. Using this connection, we compute the volume and lattice point counts of type B$B$ generalized permutohedra. Applying tropical Hodge theory to a new framework of "tautological classes of delta‐matroids," modeled after certain vector bundles associated to realizable delta‐matroids, we establish the log‐concavity of a Tutte‐like invariant for a broad family of delta‐matroids that includes all realizable delta‐matroids. Our results include new log‐concavity statements for all (ordinary) matroids as special cases. [ABSTRACT FROM AUTHOR]

In line with the recent development in topological graph theory, we are considering undirected graphs that are allowed to contain multiple edges, loops, and semi-edges. A graph is called simple if it contains no semi-edges, no loops, and no multiple edges. A graph covering projection, also known as a locally bijective homomorphism, is a mapping between vertices and edges of two graphs which preserves incidences and which is a local bijection on the edge-neighborhood of every vertex. This notion stems from topological graph theory, but has also found applications in combinatorics and theoretical computer science. It has been known that for every fixed simple regular graph H of valency greater than 2, deciding if an input graph covers H is NP-complete. Graphs with semi-edges have been considered in this context only recently and only partial results on the complexity of covering such graphs are known so far. In this paper we consider the list version of the problem, called List-H-Cover, where the vertices and edges of the input graph come with lists of admissible targets. Our main result reads that the List-H-Cover problem is NP-complete for every regular graph H of valency greater than 2 which contains at least one semi-simple vertex (i.e., a vertex which is incident with no loops, with no multiple edges and with at most one semi-edge). Using this result we show the NP-co/polytime dichotomy for the computational complexity of List-H-Cover for cubic graphs. [ABSTRACT FROM AUTHOR]

We study the existence of products of primes in arithmetic progressions, building on the work of Ramaré and Walker. One of our main results is that if q$q$ is a large modulus, then any invertible residue class mod q$q$ contains a product of three primes where each prime is at most q6/5+ε$q^{6/5+\epsilon }$. Our arguments use results from a wide range of areas, such as sieve theory or additive combinatorics, and one of our key ingredients, which has not been used in this setting before, is a result by Heath‐Brown on character sums over primes from his paper on Linnik's theorem. [ABSTRACT FROM AUTHOR]

The q-binomial coefficients are q-analogues of the binomial coefficients, counting the number of k-dimensional subspaces in the n-dimensional vector space F q n over F q. In this paper, we define a Euclidean analogue of q-binomial coefficients as the number of k-dimensional subspaces which have an orthonormal basis in the quadratic space (F q n , x 1 2 + x 2 2 + ⋯ + x n 2). We prove its various combinatorial properties compared with those of q-binomial coefficients. In addition, we formulate the number of subspaces of other quadratic types and study some related properties. [ABSTRACT FROM AUTHOR]

Let F (z 1 , ⋯ , z d) be the quotient of an analytic function with a product of linear functions. Working in the framework of analytic combinatorics in several variables, we compute asymptotic formulae for the Taylor coefficients of F using multivariate residues and saddle-point approximations. Because the singular set of F is the union of hyperplanes, we are able to make explicit the topological decompositions which arise in the multivariate singularity analysis. In addition to effective and explicit asymptotic results, we provide the first results on transitions between different asymptotic regimes, and provide the first software package to verify and compute asymptotics in non-smooth cases of analytic combinatorics in several variables. It is also our hope that this paper will serve as an entry to the more advanced corners of analytic combinatorics in several variables for combinatorialists. [ABSTRACT FROM AUTHOR]

In this paper, we expand on the remark by Andrews on the importance of infinite sums and products in combinatorics. Let { g d (n) } d ≥ 0 , n ≥ 1 be the double sequences σ d (n) = ∑ ℓ | n ℓ d or ψ d (n) = n d . We associate double sequences { p g d (n) } and { q g d (n) } , defined as the coefficients of ∑ n = 0 ∞ p g d (n) t n : = ∏ n = 1 ∞ (1 − t n) − ∑ ℓ | n μ (ℓ) g d (n / ℓ) n , ∑ n = 0 ∞ q g d (n) t n : = 1 1 − ∑ n = 1 ∞ g d (n) t n . These coefficients are related to the number of partitions p (n) = p σ 1 (n) , plane partitions pp (n) = p σ 2 (n) of n , and Fibonacci numbers F 2 n = q ψ 1 (n). Let n ≥ 3 and let n ≡ 0 (mod 3). Then the coefficients are log-concave at n for almost all d in the exponential (involving p g d ) and geometric cases (involving q g d ). The coefficients are not log-concave for almost all d in both cases, if n ≡ 2 (mod 3). Let n ≡ 1 (mod 3). Then the log-concave property flips for almost all  d. [ABSTRACT FROM AUTHOR]

We establish a version of the Pommerenke–Levin–Yoccoz inequality for the modulus of a polynomial-like (PL) restriction of a polynomial and give two applications. First we show that if the modulus of a PL restriction of a polynomial is bounded from below then this restricts the combinatorics of the polynomial. The second application concerns parameter slices of cubic polynomials given by the non-repelling multiplier of a fixed point. Namely, the intersection of the so-called Main Cubioid and the multiplier slice lies in the closure of the principal hyperbolic domain, with possible exception of queer components. [ABSTRACT FROM AUTHOR]

Over the last several decades, improvements in the fields of analytic combinatorics and computer algebra have made determining the asymptotic behaviour of sequences satisfying linear recurrence relations with polynomial coefficients largely a matter of routine, under assumptions that hold often in practice. The algorithms involved typically take a sequence, encoded by a recurrence relation and initial terms, and return the leading terms in an asymptotic expansion up to a big-O error term. Less studied, however, are effective techniques giving an explicit bound on asymptotic error terms. Among other things, such explicit bounds typically allow the user to automatically prove sequence positivity (an active area of enumerative and algebraic combinatorics) by exhibiting an index when positive leading asymptotic behaviour dominates any error terms. In this article, we present a practical algorithm for computing such asymptotic approximations with rigorous error bounds, under the assumption that the generating series of the sequence is a solution of a differential equation with regular (Fuchsian) dominant singularities. Our algorithm approximately follows the singularity analysis method of Flajolet and Odlyzko [SIAM J. Discrete Math. 3 (1990), pp. 216–240], except that all big-O terms involved in the derivation of the asymptotic expansion are replaced by explicit error terms. The computation of the error terms combines analytic bounds from the literature with effective techniques from rigorous numerics and computer algebra. We implement our algorithm in the SageMath computer algebra system and exhibit its use on a variety of applications (including our original motivating example, solution uniqueness in the Canham model for the shape of genus one biomembranes). [ABSTRACT FROM AUTHOR]

The design performance of real-time operating gas turbine power plants (GTPPs) deteriorates in terms of efficiency, reliability, and commercial availability due to aging, rubbing, contamination, and other similar problems. A manager minimizes operation and maintenance (O&M) expenses, consociating about the function of its basic structure (i.e., layout and design), availability (maintenance aspects), operation efficiency (trained workforce), safety and security, and other regulatory elements. Understanding plant structure improves performance, economical design, maintenance planning, etc. For a better understanding of design, a technique comprising graph theory, matrix method, and combinatorics is developed to determine the performance of GTPP. Detailed methodology for developing a system structure graph, various system structure matrices, and their permanent functions are described for the GTPP. For accessible and appropriate performance analysis, GTPP is divided into seven sub-systems. Structural interconnections between seven sub-systems of GTPP are as per real-time GTPP. The gas turbine system structure is developed in the form of a digraph. Matrix representation corresponding to digraph representation is developed, which is processed with the help of combinatorics. With the help of a computer programming tool developed in C++ for calculating the permanent of a matrix, the result comes out as a numerical value called the GTPP index. The methodology applied in the present work can be incorporated with standard computer programming tools developed for the performance assessment. In this way, it is easy to assess the dynamic behavior of the gas turbine system, as the methodology of the present work can incorporate tangible and intangible factors. Results obtained from the present methods agree with the available information in the literature. • The framework for exploring the dynamic behaviour of gas turbine systems is presented. • Graph theory, matrix method, and combinatorics are united into a single methodology. • Evaluations of efficiency, reliability, availability and maintainability are offered. • Recommendations for the ERAM evaluation of gas turbine systems are provided. [ABSTRACT FROM AUTHOR]

In problems such as variable selection and graph estimation, models are characterized by Boolean logical structure such as the presence or absence of a variable or an edge. Consequently, false-positive error or false-negative error can be specified as the number of variables/edges that are incorrectly included or excluded in an estimated model. However, there are several other problems such as ranking, clustering, and causal inference in which the associated model classes do not admit transparent notions of false-positive and false-negative errors due to the lack of an underlying Boolean logical structure. In this paper, we present a generic approach to endow a collection of models with partial order structure, which leads to a hierarchical organization of model classes as well as natural analogs of false-positive and false-negative errors. We describe model selection procedures that provide false-positive error control in our general setting, and we illustrate their utility with numerical experiments. [ABSTRACT FROM AUTHOR]

We introduce and enumerate weighted α -distanced words. We show their connection to the unified Apostol-type polynomials and provide combinatorial proofs of certain identities. [ABSTRACT FROM AUTHOR]

We investigate the uniqueness problems of meromorphic functions and their difference operators by using a new method. It is proved that if a non-constant meromorphic function f shares a non-zero constant and ∞ counting multiplicities with its difference operators Δcf(z) and Δ c 2 f (z) , then Δ c f (z) ≡ Δ c 2 f (z) . In particular, we give a difference analogue of a result of Jank–Mues–Volkmann. Our method has two distinct features: (i) It converts the relations between functions into the corresponding vectors. This makes it possible to deal with the uniqueness problem by linear algebra and combinatorics. (ii) It circumvents the obstacle of the difference logarithmic derivative lemma for meromorphic functions of infinite order, since this method does not depend on the growth of the functions. Furthermore, the idea in this paper can also be applied to the case for several variables. [ABSTRACT FROM AUTHOR]

We introduce, and partially resolve, a conjecture that brings a three-centuries-old derangements phenomenon and its much younger two-decades-old analogue under the same umbrella. Our tools blend combinatorics and analysis in a medley incorporating Inclusion-Exclusion and Tannery's theorem. [ABSTRACT FROM AUTHOR]

Let d-claw (or d-star) stand for K 1 , d , the complete bipartite graph with 1 and d ≥ 1 vertices on each part. The d-claw vertex deletion problem, d -claw-vd, asks for a given graph G and an integer k if one can delete at most k vertices from G such that the resulting graph has no d-claw as an induced subgraph. Thus, 1 -claw-vd and 2 -claw-vd are just the famous vertex cover problem and the cluster vertex deletion problem, respectively. In this paper, we strengthen a hardness result recently proved in Jena and Subramani (in: Du, Du, Wu, and Zhu (eds) Theory and applications of models of computation - 17th annual conference, TAMC 2022, Tianjin, China, September 16–18, 2022, Proceedings, 2022), by showing that cluster vertex deletion remains NP -complete even when restricted to planar bipartite graphs of maximum degree 3 and arbitrary large girth. Moreover, for every d ≥ 3 , we show that d -claw-vd is NP -complete even when restricted to planar bipartite graphs of maximum degree d. These hardness results are optimal with respect to degree constraint. By extending the hardness result in Bonomo-Braberman et al (in: Computing and combinatorics - 26th international conference, COCOON 2020, Proceedings, Lecture Notes in Computer Science, vol 12273, Springer, 2020, pp 14–26, 2020), we show that, for every d ≥ 3 , d -claw-vd is NP -complete even when restricted to split graphs without (d + 1) -claws, and split graphs of diameter 2. On the positive side, we prove that d -claw-vd is polynomially solvable on what we call d-block graphs, a class properly contains all block graphs. This result extends the polynomial-time algorithm in Cao et al (Theor Comput Sci, 2018) for 2 -claw-vd on block graphs to d -claw-vd for all d ≥ 2 and improves the polynomial-time algorithm proposed by Bonomo-Brabeman et al. for (unweighted) 3 -claw-vd on block graphs to 3-block graphs. [ABSTRACT FROM AUTHOR]

We introduce immanant varieties, associated to simple characters of a finite group. They include well-studied classes of varieties, as Segre embeddings, Grassmannians and certain other classes of Chow varieties. For a one-dimensional character χ , we define χ -matroids by a maximality property. For trivial characters, by exploring the combinatorics of incidence stratifications, we provide a set of generators for the Chow vector spaces of the corresponding immanant varieties. [ABSTRACT FROM AUTHOR]

This paper formalizes the stepping stone problem introduced Ladoucer and Rebenstock [G] to the setting of simple graphs. This paper considers the set of functions from the vertices of our graph to N, which assign a fixed number of 1's to some vertices and assign higher numbers to other vertices by adding up their neighbors' assignments. The stepping stone solution is defined as an element obtained from the argmax of the maxima of these functions, and the maxima as its growth. This work is organized into work on the bounded and unbounded degree graph cases. In the bounded case, sufficient conditions are obtained for superlinear and sublinear stepping stone solution growth. Furthermore this paper demonstrates the existence of a basis of graphs which characterizes superlinear growth. In the unbounded case, properly sublinear and superlinear stepping stone solution growth are obtained. [ABSTRACT FROM AUTHOR]

We reconsider the classical equality 0.999 . . . = 1 with the tool of circular words, that is, finite words whose last letter is assumed to be followed by the first one. Such circular words are naturally embedded with algebraic structures that enlight this problematic equality, allowing it to be considered in Q rather than in R. We comment early history of such structures, that involves English teachers and accountants of the first part of the 18th century, who appear to be the firsts to assert the equality 0.999... = 1. Their level of understanding show links with Dubinsky et al.'s apos theory in mathematics education. Eventually, we rebuilt the field Q from circular words, and provide an original proof of the fact that an algebraic integer is either an integer or an irrational number. [ABSTRACT FROM AUTHOR]

To every h + N -graded module M over an N -graded conformal vertex algebra V , we associate an increasing filtration (G p M) p ∈ Z , which is compatible with the filtrations introduced by Haisheng Li. The associated graded vector space gr G (M) is naturally a module over the vertex Poisson algebra gr G (V). We study gr G (M) for the three irreducible modules over the Ising model Vir 3 , 4 , namely Vir 3 , 4 = L (1 / 2 , 0) , L (1 / 2 , 1 / 2) and L (1 / 2 , 1 / 16). We obtain an explicit PBW basis of each of these modules and a formula for their refined characters, which are related to Nahm sums for the matrix ( 8 3 3 2 ). [ABSTRACT FROM AUTHOR]

We study the combinatorics of modular flats of oriented matroids and the topological consequences for their Salvetti complexes. We show that the natural map to the localized Salvetti complex at a modular flat of corank one is what we call a poset quasi-fibration – a notion derived from Quillen's fundamental Theorem B from algebraic K-theory. As a direct consequence, the Salvetti complex of an oriented matroid whose geometric lattice is supersolvable is a K(\pi,1)-space – a generalization of the classical result for supersolvable hyperplane arrangements due to Falk, Randell and Terao. Furthermore, the fundamental group of the Salvetti complex of a supersolvable oriented matroid is an iterated semidirect product of finitely generated free groups – analogous to the realizable case. Our main tools are discrete Morse theory, the shellability of certain subcomplexes of the covector complex of an oriented matroid, a nice combinatorial decomposition of poset fibers of the localization map, and an isomorphism of covector posets associated to modular elements. We provide a simple construction of supersolvable oriented matroids. This gives many non-realizable supersolvable oriented matroids and by our main result aspherical CW-complexes. [ABSTRACT FROM AUTHOR]

The notion of an extriangulated category gives a unification of existing theories in exact or abelian categories and in triangulated categories. In this article, we develop Auslander–Reiten theory for extriangulated categories. This unifies Auslander–Reiten theories developed in exact categories and triangulated categories independently. We give two different sets of sufficient conditions on the extriangulated category so that existence of almost split extensions becomes equivalent to that of an Auslander–Reiten–Serre duality. We also show that existence of almost split extensions is preserved under taking relative extriangulated categories, ideal quotients, and extension-closed subcategories. Moreover, we prove that the stable category \underline {\mathscr {C}} of an extriangulated category \mathscr {C} is a \tau-category (see O. Iyama [Algebr. Represent. Theory 8 (2005), pp. 297–321]) if \mathscr {C} has enough projectives, almost split extensions and source morphisms. This gives various consequences on \underline {\mathscr {C}}, including Igusa–Todorov's Radical Layers Theorem (see K. Igusa and G. Todorov [J. Algebra 89 (1984), pp. 105–147]), Auslander–Reiten Combinatorics on dimensions of Hom-spaces, and Reconstruction Theorem of the associated completely graded category of \underline {\mathscr {C}} via the complete mesh category of the Auslander–Reiten species of \underline {\mathscr {C}}. Finally we prove that any locally finite symmetrizable \tau-quiver (=valued translation quiver) is an Auslander–Reiten quiver of some extriangulated category with sink morphisms and source morphisms. [ABSTRACT FROM AUTHOR]

Recursive procedures that allow placing a vocal signal inside another of a similar kind provide a neuro-computational blueprint for syntax and phonology in spoken language and human song. There are, however, no known vocal sequences among nonhuman primates arranged in selfembedded patterns that evince vocal recursion or potential incipient or evolutionary transitional forms thereof, suggesting a neuro-cognitive transformation exclusive to humans. Here, we uncover that wild flanged male orangutan long calls feature rhythmically isochronous call sequences nested within isochronous call sequences, consistent with two hierarchical strata. Remarkably, three temporally and acoustically distinct call rhythms in the lower stratum were not related to the overarching rhythm at the higher stratum by any low multiples, which suggests that these recursive structures were neither the result of parallel non-hierarchical procedures nor anatomical artifacts of bodily constraints or resonances. Findings represent a case of temporally recursive hominid vocal combinatorics in the absence of syntax, semantics, phonology, or music. Second-order combinatorics, ‘sequences within sequences’, involving hierarchically organized and cyclically structured vocal sounds in ancient hominids may have preluded the evolution of recursion in modern language-able humans. [ABSTRACT FROM AUTHOR]

The Hilbert scheme of points |$\textrm {Hilb}^{n}(S)$| of a smooth surface |$S$| is a well-studied parameter space, lying at the interface of algebraic geometry, commutative algebra, representation theory, combinatorics, and mathematical physics. The foundational result is a classical theorem of Fogarty, stating that |$\textrm {Hilb}^{n}(S)$| is a smooth variety of dimension |$2n$|⁠. In recent years there has been growing interest in a natural generalization of |$\textrm {Hilb}^{n}(S)$|⁠ , the nested Hilbert scheme |$\textrm {Hilb}^{(n_{1}, n_{2})}(S)$|⁠ , which parametrizes nested pairs of zero-dimensional subschemes |$Z_{1} \supseteq Z_{2}$| of |$S$| with |$\deg Z_{i}=n_{i}$|⁠. In contrast to Fogarty's theorem, |$\textrm {Hilb}^{(n_{1}, n_{2})}(S)$| is almost always singular, and very little is known about its singularities. In this paper, we aim to advance the knowledge of the geometry of these nested Hilbert schemes. Work by Fogarty in the 70's shows that |$\textrm {Hilb}^{(n,1)}(S)$| is a normal Cohen–Macaulay variety, and Song more recently proved that it has rational singularities. In our main result, we prove that the nested Hilbert scheme |$\textrm {Hilb}^{(n,2)}(S)$| has rational singularities. We employ an array of tools from commutative algebra to prove this theorem. Using Gröbner bases, we establish a connection between |$\textrm {Hilb}^{(n,2)}(S)$| and a certain variety of matrices with an action of the general linear group. This variety of matrices plays a central role in our work, and we analyze it by various algebraic techniques, including the Kempf–Lascoux–Weyman technique of calculating syzygies, square-free Gröbner degenerations, and the Stanley–Reisner correspondence. Along the way, we also obtain results on classes of irreducible and reducible nested Hilbert schemes, dimension of singular loci, and |$F$| -singularities in positive characteristic. [ABSTRACT FROM AUTHOR]

We study toric degenerations arising from Gröbner degenerations or the tropicalization of partial flag varieties. We produce a new family of toric degenerations of partial flag varieties whose combinatorics are governed by matching fields and combinatorial mutations of polytopes. We provide an explicit description of the polytopes associated with the resulting toric varieties in terms of matching field polytopes. These polytopes encode the combinatorial data of monomial degenerations of Plücker forms for the Grassmannian. We give a description of matching field polytopes of flag varieties as Minkowski sums and show that all such polytopes are normal. The polytopes we obtain are examples of Newton-Okounkov bodies for particular full-rank valuations for partial flag varieties. Furthermore, we study a certain explicitly-defined large family of matching field polytopes and prove that all polytopes in this family are connected by combinatorial mutations. Finally, we apply our methods to explicitly compute toric degenerations of small Grassmannians and flag varieties and obtain new families of toric degenerations. [ABSTRACT FROM AUTHOR]

We prove that the class of 231-avoiding permutations satisfies a logical limit law, i.e. that for any first-order sentence Ψ, in the language of two total orders, the probability pn,Ψ that a uniform random 231-avoiding permutation of size n satisfies Ψ admits a limit as n is large. Moreover, we establish two further results about the behavior and value of pn,Ψ: (i) it is either bounded away from 0, or decays exponentially fast; (ii) the set of possible limits is dense in [0, 1]. Our tools come mainly from analytic combinatorics and singularity analysis. [ABSTRACT FROM AUTHOR]

We extend the notion of nonbacktracking walks from unweighted graphs to graphs whose edges have a nonnegative weight. Here the weight associated with a walk is taken to be the product over the weights along the individual edges. We give two ways to compute the associated generating function, and corresponding node centrality measures. One method works directly on the original graph and one uses a line graph construction followed by a projection. The first method is more efficient, but the second has the advantage of extending naturally to time-evolving graphs. Based on these generating functions, we define and study corresponding centrality measures. Illustrative computational results are also provided. [ABSTRACT FROM AUTHOR]

We construct explicit combinatorial Bernoulli factories for the following class of flowbased polytopes: integral 0/1-polytopes defined by a set of network flow constraints. This generalizes the results of Niazadeh et al. (who constructed an explicit factory for the specific case of bipartite perfect matchings) and provides novel exact sampling procedures for sampling paths, circulations, and k-flows. In the process, we uncover new connections to algebraic combinatorics. [ABSTRACT FROM AUTHOR]

Phylogenetic trees are used to model evolution: leaves are labeled to represent contemporary species ("taxa""), and interior vertices represent extinct ancestors. Informally, convex characters are measurements on the contemporary species in which the subset of species (both contemporary and extinct) that share a given state form a connected subtree. Kelk and Stamoulis [Adv. Appl. Math., 84 (2017), pp. 34--46] showed how to efficiently count, list, and sample certain restricted subfamilies of convex characters, and algorithmic applications were given. We continue this work in a number of directions. First, we show how combining the enumeration of convex characters with existing parameterized algorithms can be used to speed up exponential-time algorithms for the maximum agreement forest problem in phylogenetics. Second, we revisit the quantity g2(T), defined as the number of convex characters on T in which each state appears on at least 2 taxa. We use this to give an algorithm with running time Oφn poly(n)), where 1.6181 is the golden ratio and n is the number of taxa in the input trees for computation of maximum parsimony distance on two state characters. By further restricting the characters counted by g2(T) we open an interesting bridge to the literature on enumeration of matchings. By crossing this bridge we improve the running time of the aforementioned parsimony distance algorithm to O(1.5895n poly(n)) and obtain a number of new results in themselves relevant to enumeration of matchings on at most binary trees. [ABSTRACT FROM AUTHOR]