Search

Abstract: To meet always increasing safety requirements in car industry, design and safety assessment methods are developed in order to fit the complexity of new embedded mecatronic systems. Hybrid (discrete/continuous) and dynamic features, specific to these systems, require choosing a suitable formalism. These features should also be considered in safety studies made all through the system design. The aim of this paper is to propose a quantitative analysis method based on the construction of an aggregated Markov graph, which allows a limitation of the combinatorial expansion. This graph is directly deducted from the Petri net modelling of the system. It is composed by a set of functional modes and a set of transitions to which statistical information regarding the system dynamics has been added. [Copyright &y& Elsevier]

Solutions to most nonlinear ordinary differential equations (ODEs) rely on numerical solvers, but this gives little insight into the nature of the trajectories and is relatively expense to compute. In this paper, we derive analytic solutions to a class of nonlinear, homogeneous ODEs with linear and quadratic terms on the right-hand side. We formulate a power series expansion of each state variable, whose function depends on the eigenvalues of the linearized system, and solve for the coefficients using some linear algebra and combinatorics. Various experiments exhibit quickly decaying coefficients, such that a good approximation to the true solution consists of just a few terms. [ABSTRACT FROM AUTHOR]

Leibniz's famous proposition that God has created the best of all possible worlds holds a significant place in his philosophical system. However, the precise manner in which God determines which world is the best remains somewhat ambiguous. Leibniz suggests that a form of "Divine mathematics" is employed to construct and evaluate possible worlds. In this paper, I uncover the underlying mechanics of Divine mathematics by formally reconstructing it. I argue that Divine mathematics is a one-player combinatorial game, in which God's goal is to find the best combination among many possibilities. Drawing on the combinatorial theory, I provide new solutions to some puzzles of compossibility. [ABSTRACT FROM AUTHOR]

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]

The independent set polynomial is important in many areas of combinatorics, computer science, and statistical physics. For every integer Δ ≥ 2 , the Shearer threshold is the value λ ⁎ (Δ) = (Δ − 1) Δ − 1 / Δ Δ. It is known that for λ < − λ ⁎ (Δ) , there are graphs G with maximum degree Δ whose independent set polynomial, evaluated at λ , is at most 0. Also, there are no such graphs for any λ > − λ ⁎ (Δ). This paper is motivated by the computational problem of approximating the independent set polynomial when λ < − λ ⁎ (Δ). The key issue in complexity bounds for this problem is "implementation". Informally, an implementation of a real number λ ′ is a graph whose hard-core partition function, evaluated at λ , simulates a vertex-weight of λ ′ in the sense that λ ′ is the ratio between the contribution to the partition function from independent sets containing a certain vertex and the contribution from independent sets that do not contain that vertex. Implementations are the cornerstone of intractability results for the problem of approximately evaluating the independent set polynomial. Our main result is that, for any λ < − λ ⁎ (Δ) , it is possible to implement a set of values that is dense over the reals. The result is tight in the sense that it is not possible to implement a set of values that is dense over the reals for any λ > λ ⁎ (Δ). Our result has already been used in a paper with Bezáková (STOC 2018) to show that it is #P-hard to approximate the evaluation of the independent set polynomial on graphs of degree at most Δ at any value λ < − λ ⁎ (Δ). In the appendix, we give an additional incomparable inapproximability result (strengthening the inapproximability bound to an exponential factor, but weakening the hardness to NP-hardness). [ABSTRACT FROM AUTHOR]

Canonical decompositions, such as the Gallai–Edmonds and Dulmage–Mendelsohn decompositions, are a series of structure theorems that form the foundation of matching theory. The classical Kotzig–Lovász decomposition is a canonical decomposition applicable to a special class of graphs with perfect matchings, called factor-connected graphs, and is famous for its contribution to the studies of perfect matching polytopes and lattices. Recently, this decomposition has been generalized for general graphs with perfect matchings; this generalized decomposition is called the general Kotzig–Lovász decomposition. In fact, this generalized decomposition can be presented as a component of a more composite canonical decomposition called the Basilica decomposition. As such, the general Kotzig–Lovász decomposition has contributed to the derivation of various new results in matching theory, such as an alternative proof of the tight cut lemma and a characterization of maximal barriers in general graphs. Joins in grafts, also known as T -joins in graphs, is a classical concept in combinatorics and is a generalization of perfect matchings in terms of parity. More precisely, minimum joins and grafts are generalizations of perfect matchings and graphs with perfect matchings, respectively. Under the analogy between matchings and joins, analogues of the canonical decompositions for grafts are expected to be strong and fundamental tools for studying joins. In this paper, we provide a generalization of the general Kotzig–Lovász decomposition for arbitrary grafts. Our result also contains Sebö's generalization of the classical Kotzig–Lovász decomposition for factor-connected grafts. From our results in this paper, a generalization of the Dulmage–Mendelsohn decomposition, which is originally a classical canonical decomposition for bipartite graphs, has been obtained for bipartite grafts. This paper is the first of a series of papers that establish a generalization of the Basilica decomposition for grafts. [ABSTRACT FROM AUTHOR]

This paper considers combinatorial optimization problems with an objective of type bottleneck, so the objective is to minimize the maximum cost among all elements in a feasible solution. For these problems, the sensitivity of an optimal solution to changes in parameters has received much less attention in existing studies than the computation of an optimal solution. This paper introduces methods for computing upper and lower tolerances which measure the amount of cost change needed in an element inside and outside an optimal solution, respectively, before that solution becomes non-optimal. Our main contribution is the development of efficient computation methods for bottleneck versions of the Linear Assignment Problem and the Minimum Spanning Tree Problem. • We study sensitivity of combinatorial problems with bottleneck objective (CBPs). • We investigate the range of element costs that keep current solutions optimal. • We derive algorithms for two CBPs in particular. • We determine the elements belonging to optimal solutions of CBPs efficiently. [ABSTRACT FROM AUTHOR]

In this paper, we are interested in digital convexity. This notion is applied in several domains like image processing and discrete tomography. We choose to study the inflation and deflation of digital convex sets while maintaining the convexity property. Knowing that any digital convex set can be read and identified by its boundary word, we use combinatorics on words perspective instead of a purely geometric approach. In this context, we characterize the points that can be added or removed over the digital convex sets without losing their convexity. Some algorithms are given at the end of each section with examples of each process. [ABSTRACT FROM AUTHOR]

Let A and B be two families of sets. A is t -intersecting if | A 1 ∩ A 2 | ≥ t for all A 1 , A 2 ∈ A. A and B are cross-intersecting if A ∩ B ≠ 0̸ for all A ∈ A and B ∈ B. Let n , k , t ≥ 1 be non-negative integers with n ≥ 2 k + t − 1. Let A ⊆ [ n ] k + t − 1 and B ⊆ [ n ] k . Frankl proved that if A is t -intersecting and | A | ≥ 1 , then | A | + | B | ≤ n k − n − k − t + 1 k + 1. In this paper, we sharpen Frankl's inequality when | A | ≥ 2 , that is, if A is t -intersecting and | A | ≥ 2 , then | A | + | B | ≤ n k − n − k − t + 1 k − n − k − t k − 1 + 2 for k ≥ 3. Furthermore, we also characterize all extremal families achieving the extremal bounds. [ABSTRACT FROM AUTHOR]

This paper introduces Riordan-Krylov matrices. These matrices naturally generalize Riordan matrices by using Krylov matrices and a more general class of algebras in place of formal power series. Fundamental properties of Riordan-Krylov matrices that are analogous to those of Riordan matrices are developed. These results and techniques are used to study incidence algebras of a poset as well as the chain and zeta-multichain polynomials of the poset. Throughout the paper applications to enumeration problems in combinatorics and number theory are provided. [ABSTRACT FROM AUTHOR]

In this paper, we analyze the Bollobás and Riordan polynomial R for ribbon graphs with half-ribbons introduced in [Combinatorics, Probability and Computing 31, 507–549, 2022]. We prove the universality property of a multivariate version of R whereas R itself turns out to be universal for a subclass of ribbon graphs with half-ribbons. We also show that R can be defined on some equivalence classes of ribbon graphs involving half-ribbons moves and that the new polynomial is universal on these classes. [ABSTRACT FROM AUTHOR]

In this paper we apply Young diagrams, a well-known object appearing in Combinatorics and Group Representation Theory, to study some properties of the polytope of 2-symmetric fuzzy measures with respect to a given partition, a subpolytope of the set of fuzzy measures. The main result in the paper allows to build a simple and fast algorithm for generating points on this polytope in a random fashion. Besides, we also study some other properties of this polytope, as for example its volume. In the last section, we give an application of this result to the problem of identification of general fuzzy measures. [ABSTRACT FROM AUTHOR]

In the papers (Benoumhani 1996;1997), Benoumhani defined two polynomials F m , n , 1 (x) and F m , n , 2 (x). Then, he defined A m (n , k) and B m (n , k) to be the polynomials satisfying F m , n , 1 (x) = ∑ k = 0 n A m (n , k) x n − k (x + 1) k and F m , n , 1 (x) = ∑ k = 0 n B m (n , k) x n − k (x + 1) k. In this paper, we give a combinatorial interpretation of the coefficients of A m + 1 (n , k) and prove a symmetry of the coefficients, i.e., [ m s ] A m + 1 (n , k) = [ m n − s ] A m + 1 (n , n − k). We give a combinatorial interpretation of B m + 1 (n , k) and prove that B m + 1 (n , n − 1) is a polynomial in m with non-negative integer coefficients. We also prove that if n ≥ 6 then all coefficients of B m + 1 (n , n − 2) except the coefficient of m n − 1 are non-negative integers. For all n , the coefficient of m n − 1 in B m + 1 (n , n − 2) is − (n − 1) , and when n ≤ 5 some other coefficients of B m + 1 (n , n − 2) are also negative. [ABSTRACT FROM AUTHOR]

We continue the study of a class of signed graphs called finite connected loop-free edge-bipartite graphs Δ (bigraphs, for short), started in Simson (2013) [33] and continued in Gąsiorek et al. (2016) [14] and Simson-Zając (2017) [38]. In this paper we present an algorithmic approach to the study of non-negative bigraphs Δ with n + r ≥ 2 vertices of corank r ≥ 1 , that is, bigraphs with the symmetric Gram matrix G Δ : = 1 2 ( G ˇ Δ + G ˇ Δ t r) ∈ M n + r (1 2 Z) positive semi-definite of rank n ≥ 1 , where G ˇ Δ ∈ M n + r (Z) is the non-symmetric Gram matrix of Δ. One of the main results of this paper are Theorems 2.1 and 2.17 asserting that every such a bigraph Δ with n + r ≥ 2 vertices can be obtained from a corank zero (i.e. positive) connected loop-free bigraph Δ ′ with n ≥ 1 vertices by an r -point extension procedure (Δ ′ , u (1) , ... , u (r)) ↦ Δ : = Δ ′ [ [ u (1) , ... , u (r) ] ] along the r ≥ 1 roots u (1) , ... , u (r) ∈ Z n of the positive definite Gram form q Δ ′ : Z n → Z , v ↦ v G ˇ Δ ′ v t r. It is also shown that the extension procedure yields a combinatorial algorithm allowing us to obtain inductively all connected loop-free non-negative corank r ≥ 1 bigraphs with n + r ≥ 2 vertices, from the corank-zero bigraphs Δ ′ with n ≥ 1 vertices. [ABSTRACT FROM AUTHOR]

Let F q be a finite field of order q and E be a set in F q d. The distance set of E is defined by Δ (E) : = { ‖ x − y ‖ : x , y ∈ E } , where ‖ α ‖ = α 1 2 + ... + α d 2. Iosevich, Koh and Parshall (2018) proved that if d ≥ 2 is even and | E | ≥ 9 q d / 2 , then F q = Δ (E) Δ (E) = { a b : a ∈ Δ (E) , b ∈ Δ (E) ∖ { 0 } }. In other words, for each r ∈ F q ⁎ there exist (x , y) ∈ E 2 and (x ′ , y ′) ∈ E 2 such that ‖ x − y ‖ ≠ 0 and ‖ x ′ − y ′ ‖ = r ‖ x − y ‖. Geometrically, this means that if the size of E is large, then for any given r ∈ F q ⁎ we can find a pair of edges in the complete graph K | E | with vertex set E such that one of them is dilated by r ∈ F q ⁎ with respect to the other. A natural question arises whether it is possible to generalize this result to arbitrary subgraphs of K | E | with vertex set E and this is the goal of this paper. In this paper, we solve this problem for k -paths (k ≥ 2) , simplexes and 4-cycles. We are using a mix of tools from different areas such as enumerative combinatorics, group actions and Turán type theorems. [ABSTRACT FROM AUTHOR]

Rainbow coloring problems, of noteworthy applications in Information Security, have been receiving much attention in the last years in Combinatorics. In particular, the rainbow connection number of a connected graph G , denoted r c (G) , is the least k for which G admits a (not necessarily proper) k -edge-coloring such that between any pair of vertices there is a path whose edge colors are all distinct. When G is disconnected, we define r c (G) = ∞. A graph G is rainbow critical if the deletion of any edge of G increases r c (G). In this paper we determine the rainbow connection number for the shadow graphs of paths, some circulant graphs, and some Cartesian products involving cycles and paths. We also determine conditions for the rainbow criticality and non-criticality of wheels, fans, and some Cartesian products involving cycles, paths, pans, and complete graphs. [ABSTRACT FROM AUTHOR]

One way to study the combinatorics of finite metric spaces is to study the betweenness relation associated with the metric space. In the hypergraph metrization problem, one has to find and characterize metric betweennesses with collinear triples (or alternatively, non-degenerate triangles) that coincide with the edges of a given 3-uniform hypergraph. Metrizability of different kinds of hypergraphs was investigated in the last decades. Chen showed that Steiner triple systems are not metric, while Richmond and Richmond characterized linear betweennesses, i.e. metric betweennesses that realize the complete 3-uniform hypergraph. The latter result was also generalized to pseudometric (almost-metric) betweennesses by Beaudou et al. In this paper, we further extend this theory by characterizing the largest non-linear almost-metric betweennesses that satisfy certain hereditary properties, as well as the ones that contain a small linear number of non-degenerate triangles. [ABSTRACT FROM AUTHOR]

A string w is called a minimal absent word (MAW) for another string T if w does not occur in T but the proper substrings of w occur in T. For example, let Σ = { a , b , c } be the alphabet. Then, the set of MAWs for string w = abaab is { aaa , aaba , bab , bb , c }. In this paper, we study combinatorial properties of MAWs in the sliding window model, namely, how the set of MAWs changes when a sliding window of fixed length d is shifted over the input string T of length n , where 1 ≤ d < n. We present tight upper and lower bounds on the maximum number of changes in the set of MAWs for a sliding window over T , both in the cases of general alphabets and binary alphabets. Our bounds improve on the previously known best bounds [Crochemore et al., 2020]. [ABSTRACT FROM AUTHOR]

Abstract Shape grammars are a generative formalism in which dynamic changes to shape structure plays a vital role. Such changes support ambiguity and emergence, and as a result shape grammars are often used as the basis for proposed developments in supporting shape exploration in computer-aided design. However, the general implementation of shape grammars remains an unsolved problem, and a common solution is to adopt a fixed structure. This paper explores the consequences of assuming a fixed shape structure, via analysis of a simple shape grammar, often used as a benchmark problem to illustrate advances in shape grammar implementation. With reference to the combinatorics of words, it is proved that adopting a finite fixed structure limits the capability of a shape grammar. The paper concludes with a discussion exploring the implications of this result for shape grammar implementation and for design descriptions in CAD. Highlights • A series of simple shape grammars are analysed according to fixed part strucutres. • It is shown that symmetric embedded lines result in periodic palindromic structures. • It is shown that these structures can limit the application of shape rules. • Implications for shape grammar implementation, and CAD in general, are discussed. [ABSTRACT FROM AUTHOR]

Highlights • The paper focuses on a single machine Jobs-Maintenance scheduling problem. • We enhanced the MHS by Zammori et al. (2014). • We also design a Cuckoo Search (CS) metaheuristics based on a new Lévy Flight. • Performance of the MHS improved, but this metaheuristic remains sub-optimal. • The newly developed CS is, instead, highly effective and robust. A bstract This paper presents and compares new metaheuristics to solve an integrated jobs-maintenance scheduling problem, on a single machine subjected to aging and failures. The problem, introduced by Zammori et al. (2014), was originally solved using the Modified Harmony Search (MHS) metaheuristic. However, an extensive numerical analysis brought to light some structural limits of the MHS, as the analysis revealed that the MHS is outperformed by the simpler Simulated Annealing by Ishibuchi et al. (1995). Aiming to solve the problem in a more effective way, we integrated the MHS with local minima escaping procedures and we also developed a new Cuckoo Search metaheuristic, based on an innovative Lévy Flight. A thorough comparison confirmed the superiority of the newly developed Cuckoo Search, which is capable to find better solutions in a smaller amount of time. This an important result, both for academics and practitioners, since the integrated job-maintenance scheduling problem has a high operational relevance, but it is known to be extremely hard to be solved, especially in a reasonable amount of time. Also, the developed Cuckoo Search has been designed in an extremely flexible way and it can be easily readapted and applied to a wide range of combinatorial problems. [ABSTRACT FROM AUTHOR]

Abstract We introduce a family of sequence transformations, defined via partial Bell polynomials, that may be used for a systematic study of a wide variety of problems in enumerative combinatorics. This family includes some of the transformations listed in the paper by Bernstein & Sloane, now seen as transformations under the umbrella of partial Bell polynomials. Our goal is to describe these transformations from the algebraic and combinatorial points of view. We provide functional equations satisfied by the generating functions, derive inverse relations, and give a convolution formula. While the full range of applications remains unexplored, in this paper we show a glimpse of the versatility of Bell transformations by discussing the enumeration of several combinatorial configurations, including rational Dyck paths, rooted planar maps, and certain classes of permutations. [ABSTRACT FROM AUTHOR]

A graph G = (V , E) is word-representable if and only if there exists a word w over the alphabet V such that letters x and y , x ≠ y , alternate in w if and only if x y ∈ E. A split graph is a graph in which the vertices can be partitioned into a clique and an independent set. There is a long line of research on word-representable graphs in the literature, and recently, word-representability of split graphs has attracted interest. In this paper, we first give a characterization of word-representable split graphs in terms of permutations of columns of the adjacency matrices. Then, we focus on the study of word-representability of split graphs obtained by iterations of a morphism, the notion coming from combinatorics on words. We prove a number of general theorems and provide a complete classification in the case of morphisms defined by 2 × 2 matrices. [ABSTRACT FROM AUTHOR]

This study develops a combinatorial approach for nonparametric short-term queue length estimation in terms of cycle-by-cycle partially observed queues from probe vehicles (PV). The method does not assume random arrivals and does not assume any primary parameters or estimation of any parameters but uses simple algebraic expressions that only depend on signal timing. For an approach lane at a traffic intersection, the conditional queue lengths given probe vehicle location, count, time, and analysis interval (e.g., at the end of the red signal phase) are represented by a Negative Hypergeometric distribution. The simple analytical estimators obtained are compared with parametric methods from literature and highway capacity manual methods using field test data and simulation data involving probe vehicles. The analysis indicates that the nonparametric models presented in this paper match the accuracy of the parametric ones used in the field test and simulated data for estimating queue lengths. • Two new models are derived for short-term queue length estimation. • The models are based on combinatorics and nonparametric. • The models are closed-form input–output formulas. • New probability mass functions for traffic queues are derived. • The models can be used in connected traffic signals. [ABSTRACT FROM AUTHOR]

Perhaps the most famous combinatorial game is nim , which was completely analyzed by C.L. Bouton in 1902. Since then, countless variants of nim have been the subject of many research papers. In Guy and Nowakowski’s Unsolved Problems in Combinatorial Games , the following entry is found: “David Gale would like to see an analysis of nim played with the option of a single pass by either of the players, which may be made at any time up to the penultimate move. It may not be made at the end of the game. Once a player has passed, the game is as in ordinary nim . The game ends when all heaps have vanished.” In this paper, we determine all of the P-positions (second-player wins) in this particular variant of nim played on heap sizes of at most four. [ABSTRACT FROM AUTHOR]

This paper is devoted to studies of I wQN-spaces and some of their cardinal characteristics. Recently, Šupina in [32] proved that I is not a weak P-ideal if and only if any topological space is an I QN-space. Moreover, under p = c he constructed a maximal ideal I (which is not a weak P-ideal) for which the notions of I QN-space and QN-space do not coincide. In this paper we show that, consistently, there is an ideal I (which is not a weak P-ideal) for which the notions of I wQN-space and wQN-space do not coincide. This is a partial solution to [6, Problem 3.7] . We also prove that for this ideal the ideal version of Scheepers Conjecture does not hold (this is the first known example of such weak P-ideal). We obtain a strictly combinatorial characterization of non ( I wQN-space ) similar to the one given in [32] by Šupina in the case of non ( I QN-space ) . We calculate non ( I QN-space ) and non ( I wQN-space ) for some weak P-ideals. Namely, we show that b ≤ non ( I QN-space ) ≤ non ( I wQN-space ) ≤ d for every weak P-ideal I and that non ( I QN-space ) = non ( I wQN-space ) = b for every F σ ideal I as well as for every analytic P-ideal I generated by an unbounded submeasure (this establishes some new bounds for b ( I , I , Fin ) introduced in [31] ). As a consequence, we obtain some bounds for add ( I QN-space ) . In particular, we get add ( I QN-space ) = b for analytic P-ideals I generated by unbounded submeasures. By a result of Bukovský, Das and Šupina from [6] it is known that in the case of tall ideals I the notions of I QN-space ( I wQN-space) and QN-space (wQN-space) cannot be distinguished. Answering [6, Problem 3.2] , we prove that if I is a tall ideal and X is a topological space of cardinality less than co v ⁎ ( I ) , then X is an I wQN-space if and only if it is a wQN-space. [ABSTRACT FROM AUTHOR]

Given a finite relational language L , a hereditary L -property is a class of finite L -structures which is closed under isomorphism and model theoretic substructure. This notion encompasses many objects of study in extremal combinatorics, including (but not limited to) hereditary properties of graphs, hypergraphs, and oriented graphs. In this paper, we generalize certain definitions, tools, and results form the study of hereditary properties in combinatorics to the setting of hereditary L -properties, where L is any finite relational language with maximum arity at least two. In particular, the goal of this paper is to generalize how extremal results and stability theorems can be combined with well-known techniques and tools to yield approximate enumeration and structure theorems. We accomplish this by generalizing the notions of extremal graphs, asymptotic density, and graph stability theorems using structures in an auxiliary language associated to a hereditary L -property. Given a hereditary L -property H , we prove an approximate asymptotic enumeration theorem for H in terms of its generalized asymptotic density. Further we prove an approximate structure theorem for H , under the assumption of that H has a stability theorem. The tools we use include a new application of the hypergraph containers theorem (Balogh–Morris–Samotij [16] , Saxton–Thomason [38] ) to the setting of L -structures, a general supersaturation theorem for hereditary L -properties (also new), and a general graph removal lemma for L -structures proved by Aroskar and Cummings in [5] . Similar results in the setting of multicolored graphs and hypergraphs were recently proved independently by Falgas-Ravry, O'Connel, Strömberg, and Uzzell [21] . [ABSTRACT FROM AUTHOR]

Partitioning a set into similar, if not, identical, parts is a fundamental research topic in combinatorics. The question of partitioning the integers in various ways has been considered throughout history. Given a set { x 1 , … , x n } of integers where x 1 < ⋯ < x n , let the gap sequence of this set be the unordered multiset { d 1 , … , d n − 1 } = { x i + 1 − x i : i ∈ { 1 , … , n − 1 } } . This paper addresses the following question, which was explicitly asked by Nakamigawa: can the set of integers be partitioned into sets with the same gap sequence? The question is known to be true for any set where the gap sequence has length at most two. This paper provides evidence that the question is true when the gap sequence has length three. Namely, we prove that given positive integers p and q , there is a positive integer r 0 such that for all r ≥ r 0 , the set of integers can be partitioned into 4-sets with gap sequence p , q , r . [ABSTRACT FROM AUTHOR]

The Catalan numbers occur in various counting problems in combinatorics. This paper reveals a connection between the Catalan numbers and list colouring of graphs. Assume G is a graph and f : V ( G ) → N is a mapping. For a nonnegative integer m , let f ( m ) be the extension of f to the graph G K m ¯ for which f ( m ) ( v ) = | V ( G ) | for each vertex v of K m ¯ . Let m c ( G , f ) be the minimum m such that G K m ¯ is not f ( m ) -choosable and m p ( G , f ) be the minimum m such that G K m ¯ is not f ( m ) -paintable. We study the parameter m c ( K n , f ) and m p ( K n , f ) for arbitrary mappings f . For x → = ( x 1 , x 2 , … , x n ) , an x → -dominated path ending at ( a , b ) is a monotonic path P of the a × b grid from ( 0 , 0 ) to ( a , b ) such that each vertex ( i , j ) on P satisfies i ≤ x j + 1 . Let ψ ( x → ) be the number of x → -dominated paths ending at ( x n , n ) . By this definition, the Catalan number C n equals ψ ( ( 0 , 1 , … , n − 1 ) ) . This paper proves that if G = K n has vertices v 1 , v 2 , … , v n and f ( v 1 ) ≤ f ( v 2 ) ≤ … ≤ f ( v n ) , then m c ( G , f ) = m p ( G , f ) = ψ ( x → ( f ) ) , where x → ( f ) = ( x 1 , x 2 , … , x n ) and x i = f ( v i ) − i for i = 1 , 2 , … , n . Therefore, if f ( v i ) = n , then m c ( K n , f ) = m p ( K n , f ) equals the Catalan number C n . We also show that if G = G 1 ∪ G 2 ∪ ⋯ ∪ G p is the disjoint union of graphs G 1 , G 2 , … , G p and f = f 1 ∪ f 2 ∪ ⋯ ∪ f p , then m c ( G , f ) = ∏ i = 1 p m c ( G i , f i ) and m p ( G , f ) = ∏ i = 1 p m p ( G i , f i ) . This generalizes a result in Carraher et al. (2014), where the case each G i is a copy of K 1 is considered. [ABSTRACT FROM AUTHOR]

This paper provides new insights into coding invariance for linear models with qualitative factors, including a coding invariant way of denoting the model coefficients. On this basis, “interaction contributions” (ICs) are proposed for decomposing generalized word counts for factorial designs into contributions that neither depend on level allocation nor on the coding of factors. Combinatorially equivalent designs yield the same ICs, so that ICs are suitable for classifying factorial designs with qualitative factors. ICs are based on singular value decomposition and have an interpretation in terms of bias contributions of an interaction on the estimation of the overall mean. The paper introduces ICs and their tabulations in interaction contribution frequency tables and illustrates their behavior in various examples. ICs are compared to several other tools for assessing combinatorial equivalence of general factorial designs, and they are found to provide a useful complement to existing methods. [ABSTRACT FROM AUTHOR]

We study a combinatorial problem arising from the microarray synthesis. The objective of the Border Minimization Problem (BMP) is to place a set of sequences in the array and to find an embedding of these sequences into a common supersequence such that the sum of the “border length” is minimized. A variant of the problem, called P-BMP, is that the placement is given and the concern is simply to find the embedding. An exponential time algorithm has been proposed for the problem but it is unknown whether the problem is NP-hard or not. In this paper, we give a comprehensive study of different variations of BMP by presenting NP-hardness proofs and approximation algorithms. We show that BMP, P-BMP, and 1D-BMP are all NP-hard and 1D-BMP is polynomial time solvable. The interesting implications include (i) the BMP is NP-hard regardless of the dimension (1D or 2D) of the array; (ii) the array dimension differentiates the complexity of the P-BMP; and (iii) for 1D array, whether placement is given differentiates the complexity of the BMP. Another contribution of the paper is devising approximation algorithms, and in particular, we present a randomized approximation algorithm for BMP with approximation ratio O ( n 1 ∕ 4 log 2 n ) , where n is the total number of sequences. [ABSTRACT FROM AUTHOR]

In 2017, Davis, Nelson, Petersen, and Tenner (Davis et al. (2018) [1]) initiated the combinatorics of pinnacles in permutations. We provide a simple and efficient recursion to compute p n (S) , the number of permutations in S n with pinnacle set S , and a conjectural closed formula for the related numbers q n (S). This conjecture was proved between the first draft of this paper and its final version by Fang (2022) [4] and later by Minnich [7]. We also determine the lexicographically minimal elements of the orbits of the modified Foata-Strehl action, prove that these elements form a lower ideal of the left weak order and characterize and count the maximal elements of this ideal. [ABSTRACT FROM AUTHOR]

As environmental awareness grows, sustainable scheduling is attracting increasing attention. The purposes of this paper are obtain the lower bound of energy-efficient flexible job shops with machine selection, job sequencing, and machine on-off decision making via a new mathematical model and to discover more energy-efficient rules with easy implementation in real practice via an efficient Gene Expression Programming (eGEP) algorithm. This paper first formulates a novel mixed-integer linear mathematical model to achieve effective machine selection, job sequencing, and machine off-on decision making. Then for the purpose of avoiding the empirical combination, five attributes exerting direct influence on the total energy consumption are extracted and consequently involved in the evolutionary process of eGEP. Furthermore, diversified rule mining operations with multi-gene representation and self-study are designed to enhance the search space and solutions quality. And, unsupervised learning is utilized in which global best and current worst are set to guide evolution direction since the learning progress has no prior knowledge. Experimental results show that machine off-on decisions efficiently reduce the total energy consumption; and, the discovered rules reach the lower bound calculated by GAMS/CPLEX in small problems and have significant superiority over other dispatching rules in energy saving. [ABSTRACT FROM AUTHOR]

Recent investigations in computational biology have focused on a family of 2-colored digraphs, called 2-colored best match graphs (briefly 2-BMGs), which naturally arise from rooted phylogenetic trees. Actually the defining properties of a 2-BMG are unusual apart from bi-transitivity, and a natural question is whether 2-BMGs also have properties which well fit in structural graph theory. In this paper we show some of such properties. A major result is that if a 2-BMG has no equivalent vertices then each of its orientation is acyclic. We also point out that the arising topological ordering can efficiently be used for enumeration and reconstruction of 2-BMGs from smaller 2-BMGs and almost 2-BMGs. [ABSTRACT FROM AUTHOR]

Given a bipartite graph G = (V 1 , V 2 , E) , a biclique of G is a complete bipartite subgraph of G , and a biclique partitioning of G is a set A ⊆ E such that the bipartite graph G ′ = (V 1 , V 2 , A) is a vertex-disjoint union of bicliques. The biclique partitioning problem (BPP) consists of, given a complete bipartite graph G = (V 1 , V 2 , E) with edge weights w e ∈ R for all e ∈ E (thus, negative weights are allowed), finding a biclique partitioning A ⊆ E of minimum weight. The bicluster editing problem (BEP) is a variant of the BPP and consists of editing a minimum number of edges of an input bipartite graph G in order to transform its edge set into a biclique partitioning. Editing an edge consists of either adding it to the graph or deleting it from the graph. In addition to the BPP and the BEP, other problems in the literature aim at finding biclique partitionings, and this motivates the study of the biclique partitioning polytope P n m of the complete bipartite graph K n m (i.e., P n m is the convex hull of the incidence vectors of the biclique partitionings of K n m). In this paper we develop such a polyhedral study and show that ladder , bellows , and grid inequalities induce facets of P n m. Our computational results show that these inequalities are very effective in solving the BEP. In particular, they are able to improve the value of the relaxed solution by up to 20%. [ABSTRACT FROM AUTHOR]

In this paper, we are interested in the separation problem for the so-called rounded capacity inequalities which are valid for the CVRP (Capacitated Vehicle Routing Problem) polytope. Rounded capacity inequalities, as well as the associated separation problem, are of particular interest for solving the CVRP, especially when dealing with the two-index formulation of the CVRP and Branch-and-Cut algorithms based on this formulation. To the best of our knowledge, it is not known in the literature whether this separation problem is NP-hard or polynomial (see for instance Augerat et al. (1998) and Letchford and Salazar (2015)), and it has been conjectured that the problem is NP-hard. In this paper, we prove this conjecture. We also show that the separation problem for rounded capacity inequalities is strongly NP-hard when the considered solution belongs to a particular relaxation of the problem and the clients have all the same demand. [ABSTRACT FROM AUTHOR]

This paper is an enlarged, revised and improved version of a poster presented by the second author at the 2013 Brazilian Conference on General Topology and Set Theory (STW 2013, Maresias, Brazil, 2013). Our main goal is to investigate – within the realm of Isbell–Mrówka spaces – some relative versions of covering properties of κ -paracompactness type, inspired by a comprehensive list of strengthenings of countable paracompactness introduced by M.E. Rudin in [18] . For any property P among the ones presented, we will say that an almost disjoint family A satisfies P if it satisfies a relative version of P in the corresponding Isbell–Mrówka space. We present combinatorial characterizations of the a.d. families with some of these new relative topological properties and prove several related results; for instance, it is shown that maximal almost disjoint families are not countably paracompact. The paper finishes with a number of questions and open problems. [ABSTRACT FROM AUTHOR]

In this paper, we consider infinite words that arise as fixed points of primitive substitutions on a finite alphabet and finite colorings of their factors. Any such infinite word exhibits a “hierarchal structure” that will allow us to define, under the additional condition of strong recognizability , certain remarkable finite colorings of its factors. In particular we generalize two combinatorial results by Justin and Pirillo concerning arbitrarily large monochromatic k -powers occurring in infinite words; in view of a recent paper by de Luca, Pribavkina and Zamboni, we will give new examples of classes of infinite words u and finite colorings that do not allow infinite monochromatic factorizations u = u 1 u 2 u 3 … . [ABSTRACT FROM AUTHOR]

Analogous to MacMahon’s definition of compositions, the second author, 2000, defined n -color compositions as n -color ordered partitions. Several combinatorial properties of n -color compositions were subsequently found by him, 2003, G. Narang and A.K. Agarwal, 2006, 2008, and C. Shapcott, 2012. Recently, Y. Guo 2012, 2013, studied three restricted n -color composition functions and found generating functions, explicit formulas and recurrence relations for them. In this paper, we introduce nine new restricted n -color composition functions. It is then shown that three of them are equal to three other functions. Eventually, here we study six integer sequences from the combinatorial point of view. In addition to generating functions, explicit formulas and recurrence relations for each of them, we also obtain six combinatorial identities involving different n -color composition functions. The main results of this paper are contained in Section 3. [ABSTRACT FROM AUTHOR]

In this paper, by using Riordan arrays and a particular model of lattice paths, we are able to generalize in several ways an identity proposed by Lou Shapiro by giving both an algebraic and a combinatorial proof. The identities studied in this paper allow us to move from an arithmetic progression, and other C-finite sequences, to a geometric progression in terms of Riordan array transformations and vice versa, via the Riordan array inverse. [ABSTRACT FROM AUTHOR]

In two previous papers [33,37] , we exposed a combinatorial approach to the program of Geometry of Interaction, a program initiated by Jean-Yves Girard [16] . The strength of our approach lies in the fact that we interpret proofs by simpler structures – graphs – than Girard's constructions, while generalising the latter since they can be recovered as special cases of our setting. This third paper extends this approach by considering a generalisation of graphs named graphings , which is in some way a geometric realisation of a graph on a measured space. This very general framework leads to a number of new models of multiplicative-additive linear logic which generalise Girard's geometry of interaction models and opens several new lines of research. As an example, we exhibit a family of such models which account for second-order quantification without suffering the same limitations as Girard's models. [ABSTRACT FROM AUTHOR]

This paper proposes an understanding of agrammatism from the perspective of a recent usage-based theory of grammatical status, the ProGram theory (Boye and Harder, 2012). According to this theory, grammatical elements have two central properties: they are by convention discursively secondary (i.e. attentional background) and dependent on combination with a host item. The paper first surveys studies of agrammatic speech which, based on or reconsidered in relation to the above-mentioned criteria, show that the usage-based theory makes correct predictions about the behaviour of linguistic elements in agrammatic speech. Subsequently, the paper outlines and discusses two hypotheses about the mechanism behind agrammatism that can be derived from each of the two central properties of grammatical items. According to the prominence hypothesis, agrammatism is due to insufficient overall processing resources; this leads to a prioritization of lexical over grammatical expressions because the latter, being discursively secondary, can be dispensed with for communicative purposes. According to the dependence hypothesis, agrammatism results from an impaired capacity for combining or unifying simple elements into complex wholes: This impairment affects grammatical elements in particular, because these are dependent on (combination with) host items. • Recent studies of agrammatism support a usage-based theory of grammatical status: The Program Theory. •Grammatical elements are discursively secondary (background) and depend on a host item. •The ProGram theory entails two hypotheses about the causes of agrammatism. •Agrammatism is a deprioritization of secondary elements in response to resource reduction. •It is also due to an impaired capacity for combining simple elements into complex ones. [ABSTRACT FROM AUTHOR]

In a fundamental paper in polyhedral combinatorics, Queyranne describes the complete facial structure of a classical object in combinatorial optimization, the single machine scheduling polytope. In the same paper, he answers essentially all relevant algorithmic questions with respect to optimization and separation. In the present paper, motivated by recent applications in the design of optimal incentive compatible mechanisms, we address an algorithmic question that was apparently not addressed before. Namely, we turn Carathéodory’s theorem into an algorithm, and ask to write an arbitrary point in the scheduling polytope as a convex combination of the vertices of the polytope. We give a combinatorial O ( n 2 ) time algorithm, which is linear in the naive encoding of the output size. We obtain this result by exploiting the fact that the scheduling polytope is a zonotope, and by the observation that its barycentric subdivision has a simple, linear description. The actual decomposition algorithm is an implementation of a method proposed by Grötschel, Lovász and Schrijver, applied to one of the subpolytopes of the barycentric subdivision. We thereby also shed new light on an algorithm recently proposed for a special case, namely the permutahedron. [ABSTRACT FROM AUTHOR]

This paper is devoted to dualization of dimension-theoretical results from the small scale to the large scale. So far there are two approaches for such dualization: one consisting of creating analogs of small scale concepts using covers and the other amounting to the covering dimension of the Higson corona ν ( X ) of X . The first approach was used by M. Gromov when defining the asymptotic dimension asdim ( X ) of metric spaces X . The second approach was implicitly contained in the paper [6] by Dranishnikov on asymptotic topology. It is not known if the two approaches yield the same concept. However, Dranishnikov–Keesling–Uspenskiy proved dim ( ν ( X ) ) ≤ asdim ( X ) and Dranishnikov established that dim ( ν ( X ) ) = asdim ( X ) provided asdim ( X ) < ∞ . We characterize asymptotic dimension (for spaces of finite asymptotic dimension) in terms of extensions of slowly oscillating functions to spheres. Our approach is specifically designed to relate asymptotic dimension to the covering dimension of the Higson corona ν ( X ) in case of proper metric spaces X . As an application, we recover the results of Dranishnikov–Keesling–Uspenskiy and Dranishnikov. [ABSTRACT FROM AUTHOR]

This paper presents some partial answers to the following question. Question If a normal space X is the union of an increasing sequence of open sets U 1 ⊂ U 2 ⊂ U 3 ⊂ … such that each U n contracts to a point in X , must X be contractible? The main results of the paper are: Theorem 1 If a normal space X is the union of a sequence of open subsets { U n } such that c l ( U n ) ⊂ U n + 1 and U n contracts to a point in U n + 1 for each n ≥ 1 , then X is contractible. Corollary 2 If a locally compact σ-compact normal space X is the union of an increasing sequence of open sets U 1 ⊂ U 2 ⊂ U 3 ⊂ … such that each U n contracts to a point in X, then X is contractible. [ABSTRACT FROM AUTHOR]

In this paper we describe the Hopf algebra approach to the center problem for the differential equation d v d x = ∑ i = 1 ∞ a i ( x ) v i + 1 , x ∈ [ 0 , T ] , and study some combinatorial properties of the first return map of this equation. The paper summarizes and extends previously developed approaches to the center problem due to Devlin and the author. [ABSTRACT FROM AUTHOR]

In this paper, we classify all maximal peak-pit Condorcet domains of maximal width for n ≤ 5 alternatives. To achieve this, we bring together ideas from several branches of combinatorics. The main tool used in the classification is the ideal of a domain. In contrast to the size of maximal peak-pit Condorcet domains of maximal width themselves, the size of their associated ideal is constant. • Unifies and generalizes methods and tools from the literature in order to classify Condorcet domains. • Provides a complete classification of all maximal peak-pit Condorcet domains with maximal width for up to five alternatives. • Proves that the ideal of a maximal peak-pit Condorcet domain with maximal width has a constant cardinality. [ABSTRACT FROM AUTHOR]

For a bilinear map ⁎ : R d × R d → R d with nonnegative coefficients and a vector s ∈ R d of positive entries, among an exponential number of ways combining n instances of s using n − 1 applications of ⁎ for a given n , we are interested in the largest entry over all the resulting vectors. An asymptotic behavior is that the n -th root of this largest entry converges to a growth rate λ when n tends to infinity. In this paper, we prove the existence of this limit by a special structure called linear pattern. We also pose a question on the possibility of a relation between the structure and whether λ is algebraic. [ABSTRACT FROM AUTHOR]

V -order is a total order on strings that determines an instance of Unique Maximal Factorization Families (UMFFs), a generalization of Lyndon words. The fundamental V -comparison of strings can be done in linear time and constant space. V -order has been proposed as an alternative to lexicographic order (lexorder) in the computation of suffix arrays and in the suffix-sorting induced by the Burrows-Wheeler transform (BWT). In line with the recent interest in the connection between suffix arrays and Lyndon factorization, in this paper we obtain similar results for the V -order factorization. Indeed, we show that the results describing the connection between suffix arrays and Lyndon factorization are matched by analogous V -order processing. We also describe a methodology for efficiently computing the FM-Index in V -order, as well as V -order substring pattern matching using backward search. [ABSTRACT FROM AUTHOR]