Discrete Mathematics and Combinatorics Commons^™

The Hafnian And A Commutative Analogue Of The Grassmann Algebra, Dmitry Efimov

Electronic Journal of Linear Algebra

A close relationship between the determinant, the pfaffian, and the Grassmann algebra is well-known. In this paper, a similar relation between the permanent, the hafnian, and a commutative analogue of the Grassmann algebra is described. Using the latter, some new properties of the hafnian are proved.

On Facial Unique-Maximum (Edge-)Coloring, Vesna Andova, Bernard Lidicky, Borut Luzar, Riste Skrekovski

Mathematics Publications

A facial unique-maximum coloring of a plane graph is a vertex coloring where on each face α the maximal color appears exactly once on the vertices of α. If the coloring is required to be proper, then the upper bound for the minimal number of colors required for such a coloring is set to 5. Fabrici and Göring [5] even con- jectured that 4 colors always suffice. Confi the conjecture would hence give a considerable strengthening of the Four Color Theorem. In this paper, we prove that the conjecture holds for subcubic plane graphs, outerplane graphs and plane quadrangulations. Additionally ...

A Counterexample To A Conjecture On Facial Unique-Maximal Colorings, Bernard Lidicky, Kacy Messerschmidt, Riste Skrekovski

Mathematics Publications

A facial unique-maximum coloring of a plane graph is a proper vertex coloring by natural numbers where on each face α the maximal color appears exactly once on the vertices of α. Fabrici and Göring [4] proved that six colors are enough for any plane graph and conjectured that four colors suffice. This conjecture is a strengthening of the Four Color theorem. Wendland [6] later decreased the upper bound from six to five. In this note, we disprove the conjecture by giving an infinite family of counterexamples. s we conclude that facial unique-maximum chromatic number of the sphere is five.

Policy-Preferred Paths In As-Level Internet Topology Graphs, Mehmet Engin Tozal

Theory and Applications of Graphs

Using Autonomous System (AS) level Internet topology maps to determine accurate AS-level paths is essential for network diagnostics, performance optimization, security enforcement, business policy management and topology-aware application development. One significant drawback that we have observed in many studies is simplifying the AS-level topology map of the Internet to an undirected graph, and then using the hop distance as a means to find the shortest paths between the ASes. A less significant drawback is restricting the shortest paths to only valley-free paths. Both approaches usually inflate the number of paths between ASes; introduce erroneous paths that do not conform to ...

Minimizing The Number Of 5-Cycles In Graphs With Given Edge-Density, Patrick Bennett, Andrzej Dudek, Bernard Lidicky

Mathematics Publications

Motivated by the work of Razborov about the minimal density of triangles in graphs we study the minimal density of cycles C5. We show that every graph of order n and size (1−1k)(n2), where k≥3 is an integer, contains at least (110−12k+1k2−1k3+25k4)n5+o(n5)

copies of C5. This bound is optimal, since a matching upper bound is given by the balanced complete k-partite graph. The proof is based on the flag algebras framework. We also provide a stability result for 2≤k≤73.

Design And Analysis Of Graph-Based Codes Using Algebraic Lifts And Decoding Networks, Allison Beemer

Dissertations, Theses, and Student Research Papers in Mathematics

Error-correcting codes seek to address the problem of transmitting information efficiently and reliably across noisy channels. Among the most competitive codes developed in the last 70 years are low-density parity-check (LDPC) codes, a class of codes whose structure may be represented by sparse bipartite graphs. In addition to having the potential to be capacity-approaching, LDPC codes offer the significant practical advantage of low-complexity graph-based decoding algorithms. Graphical substructures called trapping sets, absorbing sets, and stopping sets characterize failure of these algorithms at high signal-to-noise ratios. This dissertation focuses on code design for and analysis of iterative graph-based message-passing decoders. The ...

Weak Dynamic Coloring Of Planar Graphs, Caroline Accurso, Vitaliy Chernyshov, Leaha Hand, Sogol Jahanbekam, Paul Wenger

Faculty Publications

The k-weak-dynamic number of a graph G is the smallest number of colors we need to color the vertices of G in such a way that each vertex v of degree d(v) sees at least min{k, d(v)} colors on its neighborhood. We use reducible configurations and list coloring of graphs to prove that all planar graphs have 3-weak-dynamic number at most 6.

Families Of Graphs With Maximum Nullity Equal To Zero Forcing Number, Joseph S. Alameda, Emelie Curl, Armando Grez, Leslie Hogben, O'Neill Kingston, Alex Schulte, Derek Young, Michael Young

Mathematics Publications

The maximum nullity of a simple graph G, denoted M(G), is the largest possible nullity over all symmetric real matrices whose ijth entry is nonzero exactly when fi, jg is an edge in G for i =6 j, and the iith entry is any real number. The zero forcing number of a simple graph G, denoted Z(G), is the minimum number of blue vertices needed to force all vertices of the graph blue by applying the color change rule. This research is motivated by the longstanding question of characterizing graphs G for which M(G) = Z(G). The ...

An Update On A Few Permanent Conjectures, Fuzhen Zhang

Fuzhen Zhang

We review and update on a few conjectures concerning matrix permanent that are easily stated, understood, and accessible to general math audience. They are: Soules permanent-on-top conjecture†, Lieb permanent dominance conjecture, Bapat and Sunder conjecture† on Hadamard product and diagonal entries, Chollet conjecture on Hadamard product, Marcus conjecture on permanent of permanents, and several other conjectures. Some of these conjectures are recently settled; some are still open.We also raise a few new questions for future study. (†conjectures have been recently settled negatively.)

Educational Magic Tricks Based On Error-Detection Schemes, Ronald I. Greenberg

Ronald Greenberg

Magic tricks based on computer science concepts help grab student attention and can motivate them to delve more deeply. Error detection ideas long used by computer scientists provide a rich basis for working magic; probably the most well known trick of this type is one included in the CS Unplugged activities. This paper shows that much more powerful variations of the trick can be performed, some in an unplugged environment and some with computer assistance. Some of the tricks also show off additional concepts in computer science and discrete mathematics.

An Investigation Of Montmort's "Probleme De Recontres" And Generalizations, Ronald I. Greenberg

Ronald Greenberg

I have investigated a problem which may be phrased in many ways, such as finding the probability of answering a given number of questions correctly on a randomly-completed matching test which may have a number of extra "dud" answers. I have determined such probabilities, the average number of correct answers, and other allied results. I have also investigated a related problem involving the number of ways of choosing a different element from each of a certain collection of sets.

On The Inverse Of A Class Of Weighted Graphs, Swarup Kumar Panda, Sukanta Pati

Electronic Journal of Linear Algebra

In this article, only connected bipartite graphs $G$ with a unique perfect matching $\c{M}$ are considered. Let $G_\w$ denote the weighted graph obtained from $G$ by giving weights to its edges using the positive weight function $\w:E(G)\ar (0,\ity)$ such that $\w(e)=1$ for each $e\in\c{M}$. An unweighted graph $G$ may be viewed as a weighted graph with the weight function $\w\equiv\1$ (all ones vector). A weighted graph $G_\w$ is nonsingular if its adjacency matrix $A(G_\w)$ is nonsingular. The {\em inverse} of a nonsingular weighted graph ...

On The Second Least Distance Eigenvalue Of A Graph, Xueyi Huang, Qiongxiang Huang, Lu Lu

Electronic Journal of Linear Algebra

Let $G$ be a connected graph on $n$ vertices, and let $D(G)$ be the distance matrix of $G$. Let $\partial_1(G)\ge\partial_2(G)\ge\cdots\ge\partial_n(G)$ denote the eigenvalues of $D(G)$. In this paper, the connected graphs with @n􀀀1(G) at least the smallest root of $x^3=3x^2-11x-6 = 0$ are determined. Additionally, some non-isomorphic distance cospectral graphs are given.

Traveling In Networks With Blinking Nodes, Braxton Carrigan, James Hammer

Theory and Applications of Graphs

We say that a blinking node system modulo $n$ is an ordered pair $(G,L)$ where $G$ is a graph and $L$ is an on-labelling which indicates when vertices can be visited. An On-Hamiltonian walk is a sequence of all the vertices of $G$ such that the position of each vertex modulo $n$ is an integer of the label of that vertex. This paper will primarily investigate finding the shortest On-Hamiltonian walks in a blinking node system on complete graphs and complete bipartite graphs but also establishes the terminology and initial observations for working with blinking node systems on other ...

The Graphs And Matroids Whose Only Odd Circuits Are Small, Kristen Nicole Wetzler

LSU Doctoral Dissertations

This thesis is motivated by a graph-theoretical result of Maffray, which states that a 2-connected graph with no odd cycles exceeding length 3 is bipartite, is isomorphic to K_4, or is a collection of triangles glued together along a common edge. We first prove that a connected simple binary matroid M has no odd circuits other than triangles if and only if M is affine, M is M(K_4) or F_7, or M is the cycle matroid of a graph consisting of a collection of triangles glued together along a common edge. This result implies that a 2-connected loopless graph ...

On The Density Of The Odd Values Of The Partition Function, Samuel Judge

Dissertations, Master's Theses and Master's Reports

The purpose of this dissertation is to introduce a new approach to the study of one of the most basic and seemingly intractable problems in partition theory, namely the conjecture that the partition function $p(n)$ is equidistributed modulo $2$. We provide a doubly-indexed, infinite family of conjectural identities in the ring of series $\Z_2[[q]]$, which relate $p(n)$ with suitable $t$-multipartition functions, and show how to, in principle, prove each such identity. We will exhibit explicit proofs for $32$ of our identities. However, the conjecture remains open in full generality. A striking consequence of these conjectural identities ...

Distributive Lattice Models Of The Type C One-Rowed Weyl Group Symmetric Functions, William Atkins

Murray State Theses and Dissertations

We present two families of diamond-colored distributive lattices – one known and one new – that we can show are models of the type C one-rowed Weyl symmetric functions. These lattices are constructed using certain sequences of positive integers that are visualized as filling the boxes of one-rowed partition diagrams. We show how natural orderings of these one-rowed tableaux produce our distributive lattices as sublattices of a more general object, and how a natural coloring of the edges of the associated order diagrams yields a certain diamond-coloring property. We show that each edge-colored lattice possesses a certain structure that is associated with ...

On The Domination Chain Of M By N Chess Graphs, Kathleen Johnson

Murray State Theses and Dissertations

A survey of the six domination chain parameters for both square and rectangular chess boards are discussed.

On Saturation Numbers Of Ramsey-Minimal Graphs, Hunter M. Davenport

Honors Undergraduate Theses

Dating back to the 1930's, Ramsey theory still intrigues many who study combinatorics. Roughly put, it makes the profound assertion that complete disorder is impossible. One view of this problem is in edge-colorings of complete graphs. For forbidden graphs H1,...,Hk and a graph G, we write G "arrows" (H₁,...,H_k) if every k-edge-coloring of G contains a monochromatic copy of H_i in color i for some i=1,2,...,k. If c is a (red, blue)-edge-coloring of G, we say c is a bad coloring if G contains no red K₃or ...

A Combinatorial Miscellany: Antipodes, Parking Cars, And Descent Set Powers, Alexander Thomas Happ

Theses and Dissertations--Mathematics

In this dissertation we first introduce an extension of the notion of parking functions to cars of different sizes. We prove a product formula for the number of such sequences and provide a refinement using a multi-parameter extension of the Abel--Rothe polynomial. Next, we study the incidence Hopf algebra on the noncrossing partition lattice. We demonstrate a bijection between the terms in the canceled chain decomposition of its antipode and noncrossing hypertrees. Thirdly, we analyze the sum of the 𝑟th powers of the descent set statistic on permutations and how many small prime factors occur in these numbers. These results ...