Search

Abstract: We define a quiver to be rigid if all the associated truncated quiver algebras are rigid. The rigidity of quivers is then determined by the combinatorics of the set of pairs of parallel paths of the underlying quiver as follows from Cibils'' criteria for the rigidity of truncated quiver algebras. In this paper we characterize rigid quivers Δ and relate this characterization with the condensed quiver and the quiver of beads of Δ, two much simpler quivers associated to Δ. The first one is a well-known object and the second one is introduced by us to this end. [Copyright &y& Elsevier]

Abstract: Determining the location of the maximum of Stirling numbers is a well-developed area. In this paper we give the same results for the so-called r-Stirling numbers which are natural generalizations of Stirling numbers. [Copyright &y& Elsevier]

Abstract: Permutominoes are polyominoes defined by suitable pairs of permutations. In this paper we provide a formula to count the number of convex permutominoes of given perimeter. To this aim we define the transform of a generic pair of permutations, we characterize the transform of any pair defining a convex permutomino, and we solve the counting problem in the transformed space. [Copyright &y& Elsevier]

Abstract: A graph is said to be half-arc-transitive if its automorphism group acts transitively on the set of its vertices and edges but not on the set of its arcs. With each half-arc-transitive graph of valency 4 a collection of the so-called alternating cycles is associated, all of which have the same even length. Half of this length is called the radius of the graph in question. Moreover, any two adjacent alternating cycles have the same number of common vertices. If this number, the so-called attachment number, coincides with the radius, we say that the graph is tightly attached. In [D. Marušič, Half-transitive group actions on finite graphs of valency 4, J. Combin. Theory Ser. B 73 (1998) 41–76], Marušič gave a classification of tightly attached half-arc-transitive graphs of valency 4 with odd radius. In this paper the even radius tightly attached graphs of valency 4 are classified, thus completing the classification of all tightly attached half-arc-transitive graphs of valency 4. [Copyright &y& Elsevier]

Abstract: A language is called a relatively regular language if its syntactic monoid has finite ideals. In this paper, we show that there are close relationships between the relatively regular languages and some other classes of languages such as (generalized) disjunctive languages, fd-domains and 2-codes. In particular, we prove that every relatively regular 2-code is thin. Thus, the well known result of Bestel and Perrin in 1985 becomes an easy corollary of our result. [Copyright &y& Elsevier]

Abstract: In this paper, we consider a relation between the Hall–Janko graph and the Witt system . We will reconstruct the Hall–Janko graph from the group and the hexacode. [Copyright &y& Elsevier]

Abstract: Let G be a finite abelian group of order n and let be non-empty. Generalizing a well-known constant, we define the Davenport constant of G with weight A, denoted by , to be the least natural number k such that for any sequence with , there exists a non-empty subsequence and such that . Similarly, for any such set A, is defined to be the least such that for all sequences with , there exist indices , and with . In the present paper, we establish a relation between the constants and under certain conditions. Our definitions are compatible with the previous generalizations for the particular group and the relation we establish had been conjectured in that particular case. [Copyright &y& Elsevier]

Abstract: Separating hash families are useful combinatorial structures which are studied in a general form in this paper. Necessary and sufficient conditions for the existence of certain types of generalized hash functions are considered. [Copyright &y& Elsevier]

Abstract: Consider a polar space weakly embedded in a projective space . A secant of is the intersection of the point set of with a line of spanned by two non-collinear points of . The geometry consisting of the points of and as lines the secants is a so-called Delta space. In this paper we give a characterization of this and some related geometries. [Copyright &y& Elsevier]

Abstract: In this paper, we show that the stabilizer subgroup of for a without multiple roots can be derived from the stabilizer of . As an application, we construct a family of 3-designs such as , where is a prime power such that and . [Copyright &y& Elsevier]

Abstract: A graph is called circular super-critical if for every vertex of . In this paper, analogous to a result of Dirac on chromatic critical graphs, a sharp lower bound on the vertex degree of circular super-critical graphs is proved. This lower bound provides a partial answer to a question of X. Zhu [The circular chromatic number of induced subgraphs, J. Combin. Theory Ser. B 92 (2004) 177–181]. Some other structural properties of circular super-critical graphs are also presented. [Copyright &y& Elsevier]

Abstract: Many approaches to deciding the satisfiability of quantifier-free formulae with respect to a background theory T—also known as Satisfiability Modulo Theory, or SMT(T)—rely on the integration between an enumerator of truth assignments and a decision procedure for conjunction of literals in T. When the background theory T is the combination of two simpler theories, the approach is typically instantiated by means of a theory combination schema (e.g. Nelson–Oppen, Shostak). In this paper we propose a new approach to SMT, where the enumerator of truth assignments is integrated with two decision procedures, one for T 1 and one for T 2, acting independently from each other. The key idea is to search for a truth assignment not only to the atoms occurring in the formula, but also to all the equalities between variables which are shared between the theories. This approach is simple and expressive: for instance, no modification is required to handle non-convex theories (as opposed to traditional Nelson-Oppen combinations which require a mechanism for splitting). Furthermore, it can be made practical by leveraging on state-of-the-art boolean and SMT search techniques, and on theory layering (i.e., cheaper reasoning first, and more often). We provide thorough experimental evidence to support our claims: we instantiate the framework with two decision procedures for the combinations of Equality and Uninterpreted Functions () and Linear Arithmetic (), both for (the convex case of) reals and for (the non-convex case of) integers; we analyze the impact of the different optimizations on a variety of test cases; and we compare the approach with state-of-the-art competitor tools, showing that our implemented tool compares positively with them, sometimes with dramatic gains in performance. [Copyright &y& Elsevier]

Abstract: In this paper we study the finite generation of Ext-algebras of a class of algebras called δ-resolution determined algebras. We characterize the δ-resolution determined algebras which are monomial algebras. If Λ is a graded algebra such that the associated monomial algebra is δ-resolution determined, we classify when the Ext-algebra of Λ is finitely generated. [Copyright &y& Elsevier]

Abstract: Let be a regular uncountable cardinal and . The principle of Stationary Reflection in has been successful in settling problems of infinitary combinatorics in the case . For the principle is known to fail if is large enough. In this paper the principle is shown to fail for every . [Copyright &y& Elsevier]

Abstract: Let be the group of monomial matrices, i.e., the group generated by all permutation matrices and diagonal matrices in . The group acts on the set of all subspaces of . The number of orbits of this action, denoted by , is the number of non-equivalent linear codes in . It was conjectured by Lax that as . We confirm this conjecture in this paper. [Copyright &y& Elsevier]

Abstract: The method of graphical condensation for enumerating perfect matchings was found by Propp (Theoret. Comput. Sci. 303 (2003) 267), and was generalized by Kuo (Theoret. Comput. Sci. 319 (2004) 29). In this paper, we obtain some more general results on graphical condensation than Kuo''s. Our method is also different from Kuo''s. As applications of our results, we obtain a new proof of Stanley''s multivariate version of the Aztec diamond theorem and we enumerate perfect matchings of a type of molecular graph. Finally, a combinatorial identity on the number of plane partitions is also given. [Copyright &y& Elsevier]

Abstract: Let G be a group that is a set-theoretic union of finitely many proper subgroups. Cohn defined to be the least integer m such that G is the union of m proper subgroups. Tomkinson showed that can never be 7, and that it is always of the form (q a prime power) for solvable groups G. In this paper we give exact or asymptotic formulas for . In particular, we show that , while for alternating groups we find unless or 9. An application of this result is also given. [Copyright &y& Elsevier]