Discrete Mathematics and Combinatorics Commons^™

Generalized Splines On Arbitrary Graphs, Simcha Gilbert, Julianna Tymoczko, Shira Viel

Mathematics Sciences: Faculty Publications

Let G be a graph whose edges are labeled by ideals of a commutative ring. We introduce a generalized spline, which is a vertex labeling of G by elements of the ring so that the difference between the labels of any two adjacent vertices lies in the corresponding edge ideal. Generalized splines arise naturally in combinatorics (algebraic splines of Billera and others) and in algebraic topology (certain equivariant cohomology rings, described by Goresky, Kottwitz, and MacPherson, among others). The central question of this paper asks when an arbitrary edge-labeled graph has nontrivial generalized splines. The answer is “always”, and we …

Combinatorial Descriptions Of The Crystal Structure On Certain Pbw Bases (Extended Abstract), Ben Salisbury, Adam Schultze, Peter Tingley

Mathematics and Statistics: Faculty Publications and Other Works

Lusztig's theory of PBW bases gives a way to realize the infinity crystal for any simple complex Lie algebra where the underlying set consists of Kostant partitions. In fact, there are many different such realizations, one for each reduced expression for the longest element of the Weyl group. There is an algorithm to calculate the actions of the crystal operators, but it can be quite complicated. For ADE types, we give conditions on the reduced expression which ensure that the corresponding crystal operators are given by simple combinatorial bracketing rules. We then give at least one reduced expression satisfying our …

Impartial Avoidance Games For Generating Finite Groups, Bret J. Benesh, Dana C. Ernst, Nándor Sieben

Mathematics Faculty Publications

We study an impartial avoidance game introduced by Anderson and Harary. The game is played by two players who alternately select previously unselected elements of a finite group. The first player who cannot select an element without making the set of jointly-selected elements into a generating set for the group loses the game. We develop criteria on the maximal subgroups that determine the nim-numbers of these games and use our criteria to study our game for several families of groups, including nilpotent, sporadic, and symmetric groups.

Single Valued Neutrosophic Graphs, Florentin Smarandache, Said Broumi, Assia Bakali, Mohamed Talea

Branch Mathematics and Statistics Faculty and Staff Publications

The notion of single valued neutrosophic sets is a generalization of fuzzy sets, intuitionistic fuzzy sets. We apply the concept of single valued neutrosophic sets, an instance of neutrosophic sets, to graphs. We introduce certain types of single valued neutrosophic graphs (SVNG) and investigate some of their properties with proofs and examples.

A Beautiful Proof By Induction, Lars-Daniel Öhman

Journal of Humanistic Mathematics

The purpose of this note is to present an example of a proof by induction that in the opinion of the present author has great aesthetic value. The proof in question is Thomassen's proof that planar graphs are 5-choosable. I give a self-contained presentation of this result and its proof, and a personal account of why I think this proof is beautiful.

A secondary purpose is to more widely publicize this gem, and hopefully make it part of a standard set of examples for examining characteristics of proofs by induction.

Generalized Eulerian Numbers And Multiplex Juggling Sequences, Esther M. Banaian

All College Thesis Program, 2016-2019

We consider generalizations of both juggling sequences and non-attacking rook placements. We demonstrate the important connection between these objects, and also propose a generalization of the Eulerian numbers. These generalizations give rise to several interesting counting problems, which we explore.

An Exploration Of “The Enumeration Of Heterofullerenes”, Kayla Penkava

Conspectus Borealis

No abstract provided.

Graph Cohomology, Matthew Lin

HMC Senior Theses

What is the cohomology of a graph? Cohomology is a topological invariant and encodes such information as genus and euler characteristic. Graphs are combinatorial objects which may not a priori admit a natural and isomorphism invariant cohomology ring. In this project, given any finite graph G, we constructively define a cohomology ring H*(G) of G. Our method uses graph associahedra and toric varieties. Given a graph, there is a canonically associated convex polytope, called the graph associahedron, constructed from G. In turn, a convex polytope uniquely determines a toric variety. We synthesize these results, and describe the …

Line-Of-Sight Pursuit And Evasion Games On Polytopes In R^N, John Phillpot

HMC Senior Theses

We study single-pursuer, line-of-sight Pursuit and Evasion games in polytopes in $\mathbb{R}^n$. We develop winning Pursuer strategies for simple classes of polytopes (monotone prisms) in Rⁿ, using proven algorithms for polygons as inspiration and as subroutines. More generally, we show that any Pursuer-win polytope can be extended to a new Pursuer-win polytope in more dimensions. We also show that some more general classes of polytopes (monotone products) do not admit a deterministic winning Pursuer strategy. Though we provide bounds on which polytopes are Pursuer-win, these bounds are not tight. Closing the gap between those polytopes known to be …

Fibonomial Tilings And Other Up-Down Tilings, Robert Bennett

HMC Senior Theses

The Fibonomial coefficients are a generalization of the binomial coefficients with a rather nice combinatorial interpretation. While the ordinary binomial coefficients count lattice paths in a grid, the Fibonomial coefficients count the number of ways to draw a lattice path in a grid and then Fibonacci-tile the regions above and below the path in a particular way. We may forgo a literal tiling interpretation and, instead of the Fibonacci numbers, use an arbitrary function to count the number of ways to "tile" the regions of the grid delineated by the lattice path. When the function is a combinatorial sequence such …

Adinkras And Arithmetical Graphs, Madeleine Weinstein

HMC Senior Theses

Adinkras and arithmetical graphs have divergent origins. In the spirit of Feynman diagrams, adinkras encode representations of supersymmetry algebras as graphs with additional structures. Arithmetical graphs, on the other hand, arise in algebraic geometry, and give an arithmetical structure to a graph. In this thesis, we will interpret adinkras as arithmetical graphs and see what can be learned.

Our work consists of three main strands. First, we investigate arithmetical structures on the underlying graph of an adinkra in the specific case where the underlying graph is a hypercube. We classify all such arithmetical structures and compute some of the corresponding …

The Maximum Multiplicity Of An Eigenvalue Of Symmetric Matrices With A Given Graph, Keivan Hassani Monfared, Sudipta Mallik

Mathematics Faculty Research

For a graph G, M(G) denotes the maximum multiplicity occurring of an eigenvalue of a symmetric matrix whose zero-nonzero pattern is given by edges of G. We introduce two combinatorial graph parameters T^-(G) and T^+(G) that give a lower and an upper bound for M(G) respectively, and we show that these bounds are sharp.

A Bound On The Number Of Spanning Trees In Bipartite Graphs, Cheng Wai Koo

HMC Senior Theses

Richard Ehrenborg conjectured that in a bipartite graph G with parts X and Y, the number of spanning trees is at most the product of the vertex degrees divided by |X|⋅|Y|. We make two main contributions. First, using techniques from spectral graph theory, we show that the conjecture holds for sufficiently dense graphs containing a cut vertex of degree 2. Second, using electrical network analysis, we show that the conjecture holds under the operation of removing an edge whose endpoints have sufficiently large degrees.

Our other results are combinatorial proofs that the conjecture holds for …

On Edge-Minimization Of Vertex Minimal Graphs With Dicyclic Automorphism Group, Peter E. Huston

Undergraduate Honors Thesis Projects

We find the smallest degree of a graph with automorphism group isomorphic to the dicyclic group with 4n elements, denoted α(Dic_n). We also find the fewest edges a minimum-order graph with dicyclic automorphism group and a minimal number of vertices can have. For n not a power of 2, the value of α(Dic_n) is significantly less than the best previously known upper bound, 8n. Such an edge-minimized vertex-minimal graph is constructed and shown to have automorphism group Dic_n . That the exhibited graph is minimal is verified using a combination of techniques similar to those developed previously for Abelian groups …

The Automorphism Group Of The Halved Cube, Benjamin B. Mackinnon

Theses and Dissertations

An n-dimensional halved cube is a graph whose vertices are the binary strings of length n, where two vertices are adjacent if and only if they differ in exactly two positions. It can be regarded as the graph whose vertex set is one partite set of the n-dimensional hypercube, with an edge joining vertices at hamming distance two. In this thesis we compute the automorphism groups of the halved cubes by embedding them in R n and realizing the automorphism group as a subgroup of GLn(R). As an application we show that a halved cube is a circulant graph if …

Polytopes Of Large Rank For Psl(4,Q), Peter A. Brooksbank, Dimitri Leemans

Faculty Journal Articles

This paper examines abstract regular polytopes whose automorphism group is the projective special linear group PSL(4,q). For q odd we show that polytopes of rank 4 exist by explicitly constructing PSL(4,q) as a string C-group of that rank. On the other hand, we show that no abstract regular polytope exists whose group of automorphisms is PSL(4,2^k).

An Edge-Swap Heuristic For Finding Dense Spanning Trees, Mustafa Ozen, Hua Wang, Kai Wang, Demet Yalman

Theory & Applications of Graphs

Finding spanning trees under various restrictions has been an interesting question to researchers. A "dense" tree, from a graph theoretical point of view, has small total distances between vertices and large number of substructures. In this note, the "density" of a spanning tree is conveniently measured by the weight of a tree (defined as the sum of products of adjacent vertex degrees). By utilizing established conditions and relations between trees with the minimum total distance or maximum number of sub-trees, an edge-swap heuristic for generating "dense" spanning trees is presented. Computational results are presented for randomly generated graphs and specific …

Zeon Roots, Lisa M. Dollar, G. Stacey Staples

SIUE Faculty Research, Scholarship, and Creative Activity

Zeon algebras can be thought of as commutative analogues of fermion algebras, and they can be constructed as subalgebras within Clifford algebras of appropriate signature. Their inherent combinatorial properties make them useful for applications in graph enumeration problems and evaluating functions defined on partitions. In this paper, kth roots of invertible zeon elements are considered. More specifically, conditions for existence of roots are established, numbers of existing roots are determined, and computational methods for constructing roots are developed. Recursive and closed formulas are presented, and specific low-dimensional examples are computed with Mathematica. Interestingly, Stirling numbers of the first kind appear …

Zeons, Orthozeons, And Graph Colorings, G. Stacey Staples, Tiffany Stellhorn

SIUE Faculty Research, Scholarship, and Creative Activity

No abstract provided.

New Perspectives Of Quantum Analogues, Yue Cai

Theses and Dissertations--Mathematics

In this dissertation we discuss three problems. We first show the classical q-Stirling numbers of the second kind can be expressed more compactly as a pair of statistics on a subset of restricted growth words. We extend this enumerative result via a decomposition of a new poset which we call the Stirling poset of the second kind. The Stirling poset of the second kind supports an algebraic complex and a basis for integer homology is determined. A parallel enumerative, poset theoretic and homological study for the q-Stirling numbers of the first kind is done. We also give a bijective …

Flag F-Vectors Of Polytopes With Few Vertices, Sarah A. Nelson

Theses and Dissertations--Mathematics

We may describe a polytope P as the convex hull of n points in space. Here we consider the numbers of chains of faces of P. The toric g-vector and CD-index of P are useful invariants for encoding this information. For a simplicial polytope P, Lee defined the winding number w_k in a Gale diagram corresponding to P. He showed that w_k in the Gale diagram equals g_k of the corresponding polytope. In this dissertation, we fully establish how to compute the g-vector for any polytope with few vertices from its …

Path-Factors Involving Paths Of Order Seven And Nine, Yoshimi Egawa, Michitaka Furuya

Theory & Applications of Graphs

In this paper, we show the following two theorems (here c_i(G-Χ) is the number of components C of G-Χ with |V(C)|=i): (i) If a graph G satisfies c₁(G-Χ)+⅓c₃(G-Χ)+⅓c₅(G-Χ) ≤ ⅔ |Χ| for all Χ ≤ V(G), then G has a {Ρ₂},Ρ₇}-factor. (ii)If a graph G satisfies c₁}(G-Χ)+c₃}(G-Χ)+⅔ c₅}(G-Χ)+⅓c₇}(G-Χ) ≤ ⅔|Χ| for all Χ⊆ V(G), then G has a {P₂,P₉}-factor.

Realizing The 2-Associahedron, Patrick N. Tierney

HMC Senior Theses

The associahedron has appeared in numerous contexts throughout the field of mathematics. By representing the associahedron as a poset of tubings, Michael Carr and Satyan L. Devadoss were able to create a gener- alized version of the associahedron in the graph-associahedron. We seek to create an alternative generalization of the associahedron by considering a particle-collision model. By extending this model to what we dub the 2- associahedron, we seek to further understand the space of generalizations of the associahedron.

Interval Graphs, Joyce C. Yang

HMC Senior Theses

We examine the problem of counting interval graphs. We answer the question posed by Hanlon, of whether the formal power series generating function of the number of interval graphs on n vertices has a positive radius of convergence. We have found that it is zero. We have obtained a lower bound and an upper bound on the number of interval graphs on n vertices. We also study the application of interval graphs to the dynamic storage allocation problem. Dynamic storage allocation has been shown to be NP-complete by Stockmeyer. Coloring interval graphs on-line has applications to dynamic storage allocation. The …

Classifying Coloring Graphs, Julie Beier, Janet Fierson, Ruth Haas, Heather M. Russell, Kara Shavo

Department of Math & Statistics Faculty Publications

Given a graph G, its k-coloring graph is the graph whose vertex set is the proper k-colorings of the vertices of G with two k-colorings adjacent if they differ at exactly one vertex. In this paper, we consider the question: Which graphs can be coloring graphs? In other words, given a graph H, do there exist G and k such that H is the k-coloring graph of G? We will answer this question for several classes of graphs and discuss important obstructions to being a coloring graph involving order, girth, and induced subgraphs.

Induced Subgraph Saturated Graphs, Craig M. Tennenhouse

Theory & Applications of Graphs

A graph G is said to be H-saturated if G contains no subgraph isomorphic to H but the addition of any edge between non-adjacent vertices in G creates one. While induced subgraphs are often studied in the extremal case with regard to the removal of edges, we extend saturation to induced subgraphs. We say that G is induced H-saturated if G contains no induced subgraph isomorphic to H and the addition of any edge to G results in an induced copy of H. We demonstrate constructively that there are non-trivial examples of saturated graphs for …

On Minimum Spanning Subgraphs Of Graphs With Proper Connection Number 2, Zhenming Bi, Gary Chartrand, Garry L. Johns, Ping Zhang

Theory & Applications of Graphs

An edge coloring of a connected graph G is a proper-path coloring if every two vertices of G are connected by a properly colored path. The minimum number of colors required of a proper-path coloring of G is called the proper connection number pc(G) of G. For a connected graph G with proper connection number 2, the minimum size of a connected spanning subgraph H of G with pc(H) = 2 is denoted by μ(G). It is shown that if s and t are integers such that t ≥ s + 2 ≥ 5 …

A Class Of Graphs Approaching Vizing's Conjecture, Aziz Contractor, Elliot Krop

Theory & Applications of Graphs

For any graph G=(V,E), a subset S ⊆ V dominates G if all vertices are contained in the closed neighborhood of S, that is N[S]=V. The minimum cardinality over all such S is called the domination number, written γ(G). In 1963, V.G. Vizing conjectured that γ(G □ H) ≥ γ(G)γ(H) where □ stands for the Cartesian product of graphs. In this note, we define classes of graphs Α_n, for n≥0, so that every graph belongs to some such class, and Α₀ corresponds to class A of Bartsalkin and German. We prove that …

Group-Antimagic Labelings Of Multi-Cyclic Graphs, Dan Roberts, Richard M. Low

Theory & Applications of Graphs

Let Α be a non-trivial abelian group. A connected simple graph G = (V, E) is Α-antimagic if there exists an edge labeling f: Ε(G) → A \{0} such that the induced vertex labeling f+: V(G) → Α, defined by f+(v) = Σ{f(u,v): (u, v) ∈ E(G)}, is a one-to-one map. The integer-antimagic spectrum of a graph G is the set IAM(G) = {κ: G is ℤ_k - antimagic and κ ≥ 2}. In this paper, we analyze the integer-antimagic spectra for various classes of multi-cyclic graphs.

An Extremal Problem For Finite Lattices, John Goldwasser, Brendan Nagle, Andres Saez

Theory & Applications of Graphs

For a fixed M x N integer lattice L(M,N), we consider the maximum size of a subset A of L(M,N) which contains no squares of prescribed side lengths k(1),...,k(t). We denote this size by ex(L(M,N), {k(1),...,k(t)}), and when t = 1, we abbreviate this parameter to ex(L(M,N), k), where k = k(1).

Our first result gives an exact formula for ex(L( …