Contributions to Discrete Mathematics (E-Journal, University of Calgary)
Not a member yet
406 research outputs found
Sort by
Asymptotic estimate on the distance energy of lattices
Full text linkSince the well-known breakthrough of L. Guth and N. Katz on the Erdős distinct distances problem in the plane, it aroused mainstream interest by their method and the Elekes–Sharir framework. In short, they study the second moment in the framework. One may wonder if higher moments would be more efficient. In this paper, using number-theoretic methods, we show that any higher moment fails the expectation. We also show that the second moment gives an optimal estimate in higher dimensions. Moreover, we prove the mean second moment attains the maximum for the hexagonal lattice in , which is a parallel result on the distinct distances problem for lattices
About the second neighborhood conjecture for tournaments missing two stars or disjoint paths
Full text linkSeymour\u27s Second Neighborhood Conjecture (SSNC) asserts that every oriented finite simple graph (without digons) has a vertex whose second out-neighborhood is at least as large as its first out-neighborhood. Such a vertex is said to have the second neighborhood property (SNP). In this paper, we prove SSNC for tournaments missing two stars. We also study SSNC for tournaments missing disjoint paths and, particularly, in the case of missing paths of length 2. In some cases, we exhibit at least two vertices with the SNP
An Ehrhart theoretic approach to generalized Golomb rulers
Full text linkA Golomb ruler is a sequence of integers whose pairwise differences, or equivalently pairwise sums, are all distinct. This definition has been generalized in various ways to allow for sums of h integers, or to allow up to g repetitions of a given sum or difference. Beck, Bogart, and Pham applied the theory of inside-out polytopes of Beck and Zaslavsky to prove structural results about the counting functions of Golomb rulers. We extend their approach to the various types of generalized Golomb rulers
The asymmetric index of a graph
Full text linkA graph is asymmetric if its automorphism group is trivial. Asymmetric graphs were introduced by Erdős and Rényi (1963). They suggested the problem of starting with an asymmetric graph and removing some number of edges and/or adding some number of edges so that the resulting graph is nonasymmetric. Erdős and Rényi defined the degree of asymmetry of a graph to be the minimum value of . In this paper, we define another property that measures how close a given nonasymmetric graph is to being asymmetric. We define the asymmetric index of a graph , denoted , to be the minimum of so that the resulting graph is asymmetric.
We investigate the asymmetric index of both connected and disconnected graphs. We prove that for any nonnegative integer , there exists a graph where . We show that the asymmetric index of a cycle with at least six vertices is two, and provide a complete characterization of all possible pairs of edges that can be added to a cycle to create an asymmetric graph. In addition we determine the asymmetric index of paths, certain circulant graphs, Cartesian products involving paths and cycles, and bounds for complete graphs, and complete bipartite graphs
Combinatorics of certain classes of plane partitions
Full text linkIn this paper, we study new restricted plane partitions and connect them with associated lattice paths by using -color partitions. We also obtain generating functions and recurrence relations for certain classes of plane partitions
Congruences modulo powers of 3 for 6-colored generalized Frobenius partitions
No full textIn his 1984 AMS Memoir, Andrews introduced the family of functions , which denotes the number of -colored generalized Frobenius partitions of . In this paper, we prove three congruences and three internal congruences modulo powers of 3 for by utilizing the generating function of due to Hirschhorn. Finally, we conjecture two families of congruences and two families of internal congruences modulo arbitrary powers of 3 for , which strengthen a conjecture due to Gu, Wang and Xia in 2016
Congruence properties modulo powers of 2 for partition pairs into distinct parts
Full text linkLet denote the number of partitions of into distinct parts. In 1997, Gordon and Ono proved that almost all values of are divisible by with any fixed positive integer . Let denote the number of partition pairs of into distinct parts. A result derived by Ray and Barman reveals that almost all values of are also divisible by with any fixed positive integer . Quite recently, the author derived several internal congruences and congruences modulo powers of satisfied by . In this paper, we prove some internal congruences and congruences modulo powers of 2 for . Moreover, we prove an infinite family of congruence relations modulo and dozens of congruence relations modulo powers of enjoyed by . Finally, we pose two conjectures on congruence properties modulo powers of for
On the permanent of an even-dimensional non-negative polystochastic tensor of order n
Full text linkIn this paper, we present an algorithm that allows us to compute the permanent of a tensor by using Laplace expansion. We prove that the permanent of a -dimensional polystochastic -tensor of order constructed using a special row-Latin rectangle with no transversals is positive. Also, we show that the permanent of an even-dimensional polystochastic -tensor of order constructed using the row-Latin rectangle is positive. The result obtained here proves that each odd-dimensional Latin hypercube of order has a transversal (Wanless\u27 conjecture for odd-dimensional Latin hypercubes of order ). We prove that the number of perfect matchings of the bipartite hypergraph associated to an even-dimensional polystochastic -tensor of order is positive. Furthermore, we extend some results concerning polystochastic -tensors to nonnegative polystochastic tensors. Moreover, we prove that the permanent of a -dimensional nonnegative polystochastic tensor of order constructed using the row-Latin rectangle is positive. More generally, we show that the permanent of an even-dimensional nonnegative polystochastic tensor of order constructed using the row-Latin rectangle is positive. The result obtained here proves that the permanent of an even-dimensional nonnegative polystochastic tensor of order is positive
Two families of strongly walk regular graphs from three-weight codes over
No full textA necessary condition for a -code to be a three-weight code for the Lee weight is given. Two special constructions of three-weight codes over are derived. The coset graphs of their duals are shown to be strongly 3-walk-regular, a generalization of strongly regular graphs
On the Directed Hamilton-Waterloo Problem with Two Cycle Sizes
Full text linkThe Directed Hamilton-Waterloo Problem asks for a directed -factorization of the complete symmetric digraph where there are two non-isomorphic -factors. In the uniform version of the problem, factors consist of either directed -cycles or -cycles. In this paper, necessary conditions for a solution to this problem are given, and the problem is completely solved for the factors with . Furthermore, the problem is solved for when is odd with a few possible exceptions