Open Access. Powered by Scholars. Published by Universities.®

Discrete Mathematics and Combinatorics Commons

Open Access. Powered by Scholars. Published by Universities.®

949 Full-Text Articles 1,167 Authors 104,022 Downloads 95 Institutions

All Articles in Discrete Mathematics and Combinatorics

Faceted Search

949 full-text articles. Page 4 of 35.

Resolution Of Conjectures Related To Lights Out! And Cartesian Products, Bryan A. Curtis, Jonathan Earl, David Livingston, Bryan L. Shader 2019 University of Wyoming

Resolution Of Conjectures Related To Lights Out! And Cartesian Products, Bryan A. Curtis, Jonathan Earl, David Livingston, Bryan L. Shader

Electronic Journal of Linear Algebra

Lights Out!\ is a game played on a $5 \times 5$ grid of lights, or more generally on a graph. Pressing lights on the grid allows the player to turn off neighboring lights. The goal of the game is to start with a given initial configuration of lit lights and reach a state where all lights are out. Two conjectures posed in a recently published paper about Lights Out!\ on Cartesian products of graphs are resolved.


Lattice Simplices: Sufficiently Complicated, Brian Davis 2019 University of Kentucky

Lattice Simplices: Sufficiently Complicated, Brian Davis

Theses and Dissertations--Mathematics

Simplices are the "simplest" examples of polytopes, and yet they exhibit much of the rich and subtle combinatorics and commutative algebra of their more general cousins. In this way they are sufficiently complicated --- insights gained from their study can inform broader research in Ehrhart theory and associated fields.

In this dissertation we consider two previously unstudied properties of lattice simplices; one algebraic and one combinatorial. The first is the Poincar\'e series of the associated semigroup algebra, which is substantially more complicated than the Hilbert series of that same algebra. The second is the partial ordering of the elements of ...


Bounding The Number Of Compatible Simplices In Higher Dimensional Tournaments, Karthik Chandrasekhar 2019 University of Kentucky

Bounding The Number Of Compatible Simplices In Higher Dimensional Tournaments, Karthik Chandrasekhar

Theses and Dissertations--Mathematics

A tournament graph G is a vertex set V of size n, together with a directed edge set EV × V such that (i, j) ∈ E if and only if (j, i) ∉ E for all distinct i, jV and (i, i) ∉ E for all iV. We explore the following generalization: For a fixed k we orient every k-subset of V by assigning it an orientation. That is, every facet of the (k − 1)-skeleton of the (n − 1)-dimensional simplex on V is given an orientation. In this dissertation we bound the number of compatible k-simplices ...


Induction Of Nontrivial Supercharacter Theories For Finite Groups, Jesse Franklin 2019 University of Colorado, Boulder

Induction Of Nontrivial Supercharacter Theories For Finite Groups, Jesse Franklin

Undergraduate Honors Theses

This study focuses on the partitions of a group that arise from: action by conjugation, a two sided multiplicative generalization of conjugation, and inclusion of a subgroup into the group. Since conjugacy classes correspond to irreducible characters, studying the partitions in a group compatible with conjugacy classes in the subgroup, and by analogy, studying the partition of a group compatible with superclasses in a subgroup, invariances in the group can be derived from the subgroup's simpler structure. The fusion of conjugacy classes, and superclasses, has some effects on the calculation of an induced and superinduced function. However, these effects ...


Visualizing Random Walks On Supercharacter Theories For Uppertriangular Unipotent Matrices, Justin Willson 2019 University of Colorado, Boulder

Visualizing Random Walks On Supercharacter Theories For Uppertriangular Unipotent Matrices, Justin Willson

Undergraduate Honors Theses

The conjugacy classes of some finite groups are provably wild in the sense that there is no general solution to finding their conjugacy classes other than brute force. One solution to this problem is to create a supercharacter theory for a group which has the effect of gluing together conjugacy classes into more manageable chunks. In this paper we apply these methods to the group of uppertriangular unipotent matrices and analyze the combinatorics of this added structure.


Induction Of Nontrivial Supercharacter Theories For Finite Groups, Jesse Franklin 2019 University of Colorado, Boulder

Induction Of Nontrivial Supercharacter Theories For Finite Groups, Jesse Franklin

Undergraduate Honors Theses

This study focuses on the partitions of a group that arise from: action by conjugation, a two sided multiplicative generalization of conjugation, and inclusion of a subgroup into the group. Since conjugacy classes correspond to irreducible characters, studying the partitions in a group compatible with conjugacy classes in the subgroup, and by analogy, studying the partition of a group compatible with superclasses in a subgroup, invariances in the group can be derived from the subgroup's simpler structure. The fusion of conjugacy classes, and superclasses, has some effects on the calculation of an induced and superinduced function. However, these effects ...


Sharp Bounds For Decomposing Graphs Into Edges And Triangles, Adam Blumenthal, Bernard Lidicky, Oleg Pikhurko, Yanitsa Pehova, Florian Pfender, Jan Volec 2019 Iowa State University

Sharp Bounds For Decomposing Graphs Into Edges And Triangles, Adam Blumenthal, Bernard Lidicky, Oleg Pikhurko, Yanitsa Pehova, Florian Pfender, Jan Volec

Mathematics Conference Papers, Posters and Presentations

Let pi3(G) be the minimum of twice the number of edges plus three times the number of triangles over all edge-decompositions of G into copies of K2 and K3. We are interested in the value of pi3(n), the maximum of pi3(G) over graphs G with n vertices. This specific extremal function was first studied by Gyori and Tuza [Decompositions of graphs into complete subgraphs of given order, Studia Sci. Math. Hungar. 22 (1987), 315--320], who showed that pi3(n)<9n2/16.
In a recent advance on this problem, Kral, Lidicky, Martins and Pehova [arXiv:1710:08486] proved via flag ...


Closing In On Hill's Conjecture, József Balogh, Bernard Lidický, Gelasio Salazar 2019 University of Illinois at Urbana-Champaign

Closing In On Hill's Conjecture, JóZsef Balogh, Bernard Lidický, Gelasio Salazar

Mathematics Publications

Borrowing Laszlo Szekely's lively expression, we show that Hill's conjecture is ``asymptotically at least 98.5% true." This long-standing conjecture states that the crossing number cr(Kn) of the complete graph Kn is H(n) := 1 4 \lfloor n 2 \rfloor \lfloor n 1 2 \rfloor \lfloor n 2 2 \rfloor \lfloor n 3 2 \rfloor for all n \geq 3. This has been verified only for n \leq 12. Using the flag algebra framework, Norin and Zwols obtained the best known asymptotic lower bound for the crossing number of complete bipartite graphs, from which it follows that ...


Gergonne's Pile Problem, Kelly Chizek 2019 Iowa State University

Gergonne's Pile Problem, Kelly Chizek

Creative Components

My Creative Component topic will investigate Magic Tricks, Card Tricks, and Logic Puzzles with mathematical proofs to use to intrigue students so they want to learn mathematical concepts. After nearly five years of teaching in high schools, I have learned that students need to be interested in a topic in order to engage in learning the concepts well. During my teaching experience, I have introduced students to topics through application problems, reviewing fundamental steps, and games. Each method has proven to be helpful in its own way. I believe tricks and puzzles may be an alternate way to engage students ...


Enumerating Tilings With Thin Rectangles By Use Of Independent Sets In Graphs, Scarlitte Ponce 2019 Iowa State University

Enumerating Tilings With Thin Rectangles By Use Of Independent Sets In Graphs, Scarlitte Ponce

Creative Components

No abstract provided.


Probability Recurrences On Simple Graphs In A Forest Building Process, Joseph S. Alameda 2019 Iowa State University

Probability Recurrences On Simple Graphs In A Forest Building Process, Joseph S. Alameda

Creative Components

Consider the following process on a simple graph with no isolated vertices: Randomly order the edges and remove an edge if and only if the edge is incident to two vertices already incident to some preceding edge. This process results in a spanning forest of the graph.

Recurrences are given for the process for multiple families of graphs, and the probability of obtaining $k$ components in the above process is given by a new method for the Fan graph $F_{n-2,2}$. An approach to proving a previously published conjecture is also discussed.


Positivity Among P-Partition Generating Functions Of Partially Ordered Sets, Nate Lesnevich 2019 Bucknell University

Positivity Among P-Partition Generating Functions Of Partially Ordered Sets, Nate Lesnevich

Honors Theses

We find necessary and separate sufficient conditions for the difference between two labeled partially ordered set's (poset) partition generating functions to be positive in the fundamental basis. We define the notion of a jump sequence for a poset and show how different conditions on the jump sequences of two posets are necessary for those posets to have an order relation in the fundamental basis. Our sufficient conditions are of two types. First, we show how manipulating a poset's Hasse diagram produces a poset that is greater according to the fundamental basis. Secondly, we also provide tools to explain ...


Cop Throttling Number: Bounds, Values, And Variants, Anthony Bonato, Jane Breen, Boris Brimkov, Joshua Carlson, Sean English, Jesse Geneson, Leslie Hogben, K. E. Perry, Carolyn Reinhart 2019 Ryerson University

Cop Throttling Number: Bounds, Values, And Variants, Anthony Bonato, Jane Breen, Boris Brimkov, Joshua Carlson, Sean English, Jesse Geneson, Leslie Hogben, K. E. Perry, Carolyn Reinhart

Mathematics Publications

The cop throttling number thc(G) of a graph G for the game of Cops and Robbers is the minimum of k+captk(G), where k is the number of cops and captk(G) is the minimum number of rounds needed for k cops to capture the robber on G over all possible games in which both players play optimally. In this paper, we answer in the negative a question from [Breen et al., Throttling for the game of Cops and Robbers on graphs, {\em Discrete Math.}, 341 (2018) 2418--2430.] about whether the cop throttling number of any graph is ...


Polychromatic Colorings On The Integers, Maria Axenovich, John Goldwasser, Bernard Lidicky, Ryan R. Martin, David Offner, John Talbot, Michael Young 2019 Karlsruhe Institute of Technology

Polychromatic Colorings On The Integers, Maria Axenovich, John Goldwasser, Bernard Lidicky, Ryan R. Martin, David Offner, John Talbot, Michael Young

Mathematics Publications

We show that for any set S ⊆ Z, |S| = 4 there exists a 3-coloring of Z in which every translate of S receives all three colors. This implies that S has a codensity of at most 1/3, proving a conjecture of Newman. We also consider related questions in Zd, d ≥ 2.


Gallai-Ramsey Number For Classes Of Brooms, Benjamin J. Hamlin 2019 Georgia Southern University

Gallai-Ramsey Number For Classes Of Brooms, Benjamin J. Hamlin

Electronic Theses and Dissertations

Given a graph $G$, we consider the problem of finding the minimum number $n$ such that any $k$ edge colored complete graph on $n$ vertices contains either a rainbow colored triangle or a monochromatic copy of the graph $G$, denoted $gr_k(K_{3}:G)$. More precisely we consider $G=B_{m,\ell}$ where $B_{m,\ell}$ is a broom graph with $m$ representing the number of vertices on the handle and $\ell$ representing the number of bristle vertices. We develop a technique to reduce the difficulty of finding $gr_{k}(K_{3}:B_{m,\ell})$, and use the technique to ...


Conflict Free Connectivity And The Conflict-Free-Connection Number Of Graphs, Travis D. Wehmeier 2019 Georgia Southern University

Conflict Free Connectivity And The Conflict-Free-Connection Number Of Graphs, Travis D. Wehmeier

Electronic Theses and Dissertations

We explore a relatively new concept in edge-colored graphs called conflict-free connectivity. A conflict-free path is a (edge-) colored path that has an edge with a color that appears only once. Conflict-free connectivity is the maximal number of internally disjoint conflict-free paths between all pairs of vertices in a graph. We also define the c-conflict-free-connection of a graph G. This is the maximum conflict-free connectivity of G over all c-colorings of the edges of G. In this paper we will briefly survey the works related to conflict-free connectivity. In addition, we will use the probabilistic method to achieve a bound ...


Taking A Canon To The Adjunction Formula, Paul M. Harrelson 2019 Georgia Southern University

Taking A Canon To The Adjunction Formula, Paul M. Harrelson

Electronic Theses and Dissertations

In this paper, we show how the canonical divisor of a graph is related to the canonical divisor of its subgraph. The use of chip firing and the adjunction formula for graphs ex- plains said relation and even completes it. We go on to show the difference between the formula for full subgraphs and that of non-full subgraphs. Examples are used to simplify these results and to see the adjunction formula in action. Finally, we show that though the adjunction formula seems simple at first glance, it is somewhat complex and rather useful.


Edge Colorings Of Graphs On Surfaces And Star Edge Colorings Of Sparse Graphs, Katherine M. Horacek 2019 West Virginia University

Edge Colorings Of Graphs On Surfaces And Star Edge Colorings Of Sparse Graphs, Katherine M. Horacek

Graduate Theses, Dissertations, and Problem Reports

In my dissertation, I present results on two types of edge coloring problems for graphs.

For each surface Σ, we define ∆(Σ) = max{∆(G)| G is a class two graph with maximum degree ∆(G) that can be embedded in Σ}. Hence Vizing’s Planar Graph Conjecture can be restated as ∆(Σ) = 5 if Σ is a sphere. For a surface Σ with characteristic χ(Σ) ≤ 0, it is known ∆(Σ) ≥ H(χ(Σ))−1, where H(χ(Σ)) is the Heawood number of the surface, and if the Euler char- acteristic χ(Σ) ∈ {−7, −6, . . . , −1, 0}, ∆(Σ) is already ...


Infinite Matroids And Transfinite Sequences, Martin Andrew Storm 2019 West Virginia University

Infinite Matroids And Transfinite Sequences, Martin Andrew Storm

Graduate Theses, Dissertations, and Problem Reports

A matroid is a pair M = (E,I) where E is a set and I is a set of subsets of E that are called independent, echoing the notion of linear independence. One of the leading open problems in infinite matroid theory is the Matroid Intersection Conjecture by Nash-Williams which is a generalization of Hall’s Theorem. In [31] Jerzy Wojciechowski introduced µ- admissibility for pairs of matroids on the same ground set and showed that it is a necessary condition for the existence of a matching. A pair of matroids (M,W) with common ground set E is µ-admissible ...


Ordering Cacti With Signless Laplacian Spread, Zhen Lin, Shu-Guang Guo 2018 China University of Mining and Technology

Ordering Cacti With Signless Laplacian Spread, Zhen Lin, Shu-Guang Guo

Electronic Journal of Linear Algebra

A cactus is a connected graph in which any two cycles have at most one vertex in common. The signless Laplacian spread of a graph is defined as the difference between the largest eigenvalue and the smallest eigenvalue of the associated signless Laplacian matrix. In this paper, all cacti of order n with signless Laplacian spread greater than or equal to n − 1/2 are determined.


Digital Commons powered by bepress