Contributions to Discrete Mathematics (E-Journal, University of Calgary)
Not a member yet
406 research outputs found
Sort by
On the number of partitions into odd parts or congruent to
No full textLet denote the number of partitions of into parts that are odd or congruent to . In 2007, Andrews considered partitions with some negative parts and provided a second combinatorial interpretation for . In this paper, we give a collection of linear recurrence relations for the partition function . As a corollary, we obtain a simple criterion for deciding whether is odd or even. Some identities involving overpartitions and partitions into distinct parts are derived in this context
A characterization of well-founced algebraic lattices
Get PDFWe characterize well-founded algebraic lattices by means of forbidden subsemilattices of the join-semilattice made of their compact elements. More specifically, we show that an algebraic lattice L is well-founded if and only if K(L), the join semi-lattice of compact elements of L, is well founded and contains neither [\omega]^\omega, nor \underscore(\Omega)(\omega*) as a join semilattice. As an immediate corollary, we get that an algebraic modular lattice L is well-founded if and only if K(L) is well founded and contains no infinite independent set. If K(L) is a join-subsemilattice of I_{<\omega}(Q), the set of finitely generated initial segments of a well founded poset Q, then L is well-founded if and only if K(L) is well-quasi-ordered
Bounds for the boxicity of Mycielski graphs
Get PDFA box in Euclidean k-space is the Cartesian product of k closed intervals on the real line. The boxicity of a graph G, denoted by box(G), is the minimum nonnegative integer k such that G can be isomorphic to the intersection graph of a family of boxes in Euclidean k-space.Mycielski introduced an interesting graph operation that extends a graph G to a new graph M(G), called the Mycielski graph of G. In this paper we observe the behavior of boxicity of Mycielski graphs. We see that box(M(G)) is at least box(G) for a graph G, and hence we are interested in whether the boxicity of Mycielski graph of G is more than that of G or not. Here we give bounds for the boxicity of Mycielski graphs in terms of the number of universal vertices of G and the edge clique cover number of the complement of G. Further observations determine the boxicity of the Mycielski graph M(G) if G has no universal vertices or odd universal vertices and box(G) is equal to the edge clique cover number of the complement of G.We also present relations between the Mycielski graph M(G) and its generalizations M3(G) and Mr(G) in the context of boxicity, which will encourage us to calculate the boxicity of M(G) and M3(G)
Uniformly resolvable -designs of order v and
No full textIn this paper we consider the uniformly resolvable decompositions of the complete graph into subgraphs where each resolution class contains only blocks isomorphic to the same graph. We consider the cases in which all the resolution classes are either or . We prove that this type of system does not exist for odd and determine completely the spectrum for
The Complexity of Power Graphs Associated With Finite Groups
Get PDFThe power graph P(G) of a finite group G is the graph whose vertex set isG, with two elements in G being adjacent if one of them is a power of theother. The purpose of this paper is twofold: (1) to find the complexity ofa clique-replaced graph and study some applications; (2) to derive someexplicit formulas concerning the complexity \kappa(P(G)) for various groupsG such as the cyclic group of order n, the simple groups L_2(q), the extra-special p-groups of order p^3, the Frobenius groups, etc
Density dichotomy in random words
Get PDFWord is said to encounter word provided there is a homomorphism mapping letters to nonempty words so that is a substring of . For example, taking such that and , we see that ``science\u27\u27 encounters ``huh\u27\u27 since . The density of in , , is the proportion of substrings of that are homomorphic images of . So the density of ``huh\u27\u27 in ``science\u27\u27 is . A word is doubled if every letter that appears in the word appears at least twice.The dichotomy: Let be a word over any alphabet, a finite alphabet with at least 2 letters, and chosen uniformly at random. Word is doubled if and only if as .We further explore convergence for nondoubled words and concentration of the limit distribution for doubled words around its mean
Regularity in Weighted Graphs a Symmetric Function Approach
Get PDFThis work describes how the class of k-regular multigraphs with edge multiplicities from a finite set can be expressed using symmetric species results of Mendez. Consequently, the generating functions can be computed systematically using the scalar product of symmetric functions. This gives conditions on when the classes are D-finite using criteria of Gessel, and a potential route to asymptotic enumeration formulas
Arrangements of Homothets of a Convex Body II
Get PDFA family of homothets of an o-symmetric convex body K in d-dimensional Euclidean space is called a Minkowski arrangement if no homothet contains the center of any other homothet in its interior.We show that any pairwise intersecting Minkowski arrangement of a d-dimensional convex body has at most 2*3^d members.This improves a result of Polyanskii (Discrete Mathematics 340 (2017), 1950--1956).Using similar ideas, we also give a proof the following result of Polyanskii: Let K_1,....,K_n be a sequence of homothets of the o-symmetric convex body K, such that for any i<j, the center of K_j lies on the boundary of K_i. Then n<= O(3^d d)
Small on-line Ramsey numbers---a new approach
Get PDFIn this note, we revisit the problem of calculating small on-line Ramsey numbers R(G,H). A new approach is proposed that reduces the running time of the algorithm determining that R(K_3,K_4)=17 by a factor of at least 2*10^6 comparing to the previously used approach. Using high performance computing networks, we determined that R(K_4,K_4) <= 26, R(K_3,K_5) < 25, and that R(K_3,K_3,K_3) <= 20 for a natural generalization to three colours. All graphs on 3 or 4 vertices are investigated as well, including non-symmetric cases
Some inequalities for orderings of acyclic digraphs
Get PDFLet be an acyclic digraph. For define to be the difference of the indegree and the outdegree of . An acyclic ordering of the vertices of is a one-to-one map that has the property that for all if , then g(x) < g(y).We prove that for every acyclic ordering of the following inequality holds:The class of acyclic digraphs for which equality holds is determined as the class of comparability digraphs of posets of order dimension two