Mathematics Commons^™

Doubly Chorded Cycles In Graphs, Maia Wichman

Student Scholars Day Oral Presentations

In 1963, Corradi and Hajnal proved that for any positive integer k if a graph contains at least 3k vertices and has minimum degree at least 2k, then it contains k disjoint cycles. This result is sharp, meaning there are graphs on at least 3k vertices with a minimum degree of 2k-1 that do not contain k disjoint cycles. Their work is the motivation behind finding sharp conditions that guarantee the existence of specific structures, e.g. cycles, chorded cycles, theta graphs, etc. In this talk, we will explore minimum degree conditions which guarantee a specific number of doubly chorded cycles, …

On The Classification Of Vertex-Transitive Structures, John Clemens, Samuel Coskey, Stephanie Potter

Mathematics Faculty Publications and Presentations

We consider the classification problem for several classes of countable structures which are “vertex-transitive”, meaning that the automorphism group acts transitively on the elements. (This is sometimes called homogeneous.) We show that the classification of countable vertex-transitive digraphs and partial orders are Borel complete. We identify the complexity of the classification of countable vertex-transitive linear orders. Finally we show that the classification of vertex-transitive countable tournaments is properly above E₀ in complexity.

Conventions, Habits, And U.S. Teachers’ Meanings For Graphs, Kevin C. Moore, Jason Silverman, Teo Paoletti, Dave Liss, Stacy Musgrave

Department of Mathematics Facuty Scholarship and Creative Works

In this paper, we use relevant literature and data to motivate a more detailed look into relationships between what we perceive to be conventions common to United States (U.S.) school mathematics and individuals’ meanings for graphs and related topics. Specifically, we draw on data from pre-service (PST) and in-service (IST) teachers to characterize such relationships. We use PSTs’ responses during clinical interviews to illustrate three themes: (a) some PSTs’ responses implied practices we perceive to be conventions of U.S. school mathematics were instead inherent aspects of PSTs’ meanings; (b) some PSTs’ responses implied they understood certain practices in U.S. school …

Comparing Powers Of Edge Ideals, Mike Janssen, Thomas Kamp, Jason Vander Woude

Faculty Work Comprehensive List

Given a nontrivial homogeneous ideal I ⊆ k[x1, x2, . . . ,xd], a problem of great recent interest has been the comparison of the rth ordinary power of I and the mth symbolic power I(m). This comparison has been undertaken directly via an exploration of which exponents m and r guarantee the subset containment I(m) ⊆ Ir and asymptotically via a computation of the resurgence ρ(I), a number for which any m/r > ρ(I) guarantees I(m) ⊆ Ir. Recently, a third quantity, the symbolic defect, was introduced; as It ⊆ I(t), the symbolic defect is the minimal number of generators …

On Robust Colorings Of Hamming-Distance Graphs, Isaiah Harney, Heide Gluesing-Luerssen

Mathematics Faculty Publications

H_q(n, d) is defined as the graph with vertex set Zⁿ_q and where two vertices are adjacent if their Hamming distance is at least d. The chromatic number of these graphs is presented for various sets of parameters (q, n, d). For the 4-colorings of the graphs H₂(n, n − 1) a notion of robustness is introduced. It is based on the tolerance of swapping colors along an edge without destroying properness of the coloring. An explicit description of the maximally robust 4-colorings of …

Persistence Equivalence Of Discrete Morse Functions On Trees, Yuqing Liu

Mathematics Summer Fellows

We introduce a new notion of equivalence of discrete Morse functions on graphs called persistence equivalence. Two functions are considered persistence equivalent if and only if they induce the same persistence diagram. We compare this notion of equivalence to other notions of equivalent discrete Morse functions. We then compute an upper bound for the number of persistence equivalent discrete Morse functions on a fixed graph and show that this upper bound is sharp in the case where our graph is a tree. We conclude with an example illustrating our construction.

Ideas & Graphs, Martin Zwick

Systems Science Faculty Publications and Presentations

A graph can specify the skeletal structure of an idea, onto which meaning can be added by interpreting the structure.

This paper considers graphs (but not hypergraphs) consisting of four nodes, and suggests meanings that can be associated with several different directed and undirected graphs.

Drawing on Bennett's "systematics," specifically on the Tetrad that systematics offers as a model of 'activity,' the analysis here shows that the Tetrad is versatile model of problem-solving, regulation and control, and other processes.

Arithmagons And Geometrically Invariant Multiplicative Integer Partitions, J. A. Franco, J. Champion, J. W. Lyons

Mathematics Faculty Publications and Presentations

In this article, we introduce a formal definition for integral arithmagons. Informally, an arithmagon is a polygonal figure with integer labeled vertices and edges in which, under a binary operation, adjacent vertices equal the included edge. By considering the group of automorphisms for the associated graph, we count the number of integral arithmagons whose exterior sum or product equals a fixed number.

Intensity-Based Skeletonization Of Cryoem Gray-Scale Images Using A True Segmentation-Free Algorithm, Kamal Al Nasr, Chunmei Liu, Mugizi Rwebangira, Legand Burge, Jing He

Computer Science Faculty Publications

Cryo-electron microscopy is an experimental technique that is able to produce 3D gray-scale images of protein molecules. In contrast to other experimental techniques, cryo-electron microscopy is capable of visualizing large molecular complexes such as viruses and ribosomes. At medium resolution, the positions of the atoms are not visible and the process cannot proceed. The medium-resolution images produced by cryo-electron microscopy are used to derive the atomic structure of the proteins in de novo modeling. The skeletons of the 3D gray-scale images are used to interpret important information that is helpful in de novo modeling. Unfortunately, not all features of the …

A Method Based On Total Variation For Network Modularity Optimization Using The Mbo Scheme, Huiyi Hu, Thomas Laurent, Mason A. Porter, Andrea L. Bertozzi

Mathematics Faculty Works

The study of network structure is pervasive in sociology, biology, computer science, and many other disciplines. One of the most important areas of network science is the algorithmic detection of cohesive groups of nodes called “communities.” One popular approach to finding communities is to maximize a quality function known as modularity to achieve some sort of optimal clustering of nodes. In this paper, we interpret the modularity function from a novel perspective: we reformulate modularity optimization as a minimization problem of an energy functional that consists of a total variation term and an $\ell_2$ balance term. By employing numerical techniques …

Cyclic Matching Sequencibility Of Graphs, Richard A. Brualdi, Kathleen P. Kiernan, Seth A. Meyer, Michael W. Schroeder

Mathematics Faculty Research

We define the cyclic matching sequencibility of a graph to be the largest integer d such that there exists a cyclic ordering of its edges so that every d consecutive edges in the cyclic ordering form a matching. We show that the cyclic matching sequencibility of K_2m and K_2m+1 equals m − 1.

The Erdős-Lovász Tihany Conjecture For Quasi-Line Graphs, J. Balogh, A. V. Kostochka, N. Prince, M. Stiebitz

Faculty Publications & Research

Erdős and Lovász conjectured in 1968 that for every graph G with χ(G) > ω(G) and any two integers s, t ≥ 2 with s + t = χ(G) + 1, there is a partition (S,T) of the vertex set V(G) such that χ(G[S]) ≥ s and χ(G[T]) ≥ t . Except for a few cases, this conjecture is still unsolved. In this note we prove the conjecture for quasi-line graphs and for graphs with independence number 2.

Extremal Problems For Roman Domination, E. W. Chambers, W. Kinnersley, N. Prince, D. B. West

Faculty Publications & Research

A Roman dominating function of a graph G is a labeling f: V(G) →{0,1,2} such that every vertex with a label 0 has a neighbor with label 2. The Roman domination number γ_R(G) of G is the minimum of ∑_ʋϵV(G)f(v) over such functions. Let G be a connected n-vertex graph. We prove that γ_R(G) ≤ 4n/5, and we characterize the graphs achieving equality. We obtain sharp upper and lower bounds for γ_R(G) + …

Review: Set-Theoretic Solutions Of The Yang-Baxter Equation, Graphs And Computations, Gizem Karaali

Pomona Faculty Publications and Research

No abstract provided.

Groups As Graphs, Florentin Smarandache, W.B. Vasantha Kandasamy

Branch Mathematics and Statistics Faculty and Staff Publications

Through this book, for the first time we represent every finite group in the form of a graph. The authors choose to call these graphs as identity graph, since the main role in obtaining the graph is played by the identity element of the group. This study is innovative because through this description one can immediately look at the graph and say the number of elements in the group G which are self-inversed. Also study of different properties like the subgroups of a group, normal subgroups of a group, p-sylow subgroups of a group and conjugate elements of a group …

On KS,T-Minors In Graphs With Given Average Degree, A. V. Kostochka, N. Prince

Faculty Publications & Research

Let D(H) be the minimum d such that every graph G with average degree d has an H-minor. Myers and Thomason found good bounds on D(H) for almost all graphs H and proved that for 'balanced' H random graphs provide extremal examples and determine the extremal function. Examples of 'unbalanced graphs' are complete bipartite graphs K_s,t for a fixed s and large t. Myers proved upper bounds on D(K_s,t ) and made a conjecture on the order of magnitude of D(K_s,t ) for a fixed s and …

Highly Connected Multicoloured Subgraphs Of Multicoloured Graphs, H. Liu, R. Morris, N. Prince

Faculty Publications & Research

Suppose the edges of the complete graph on n vertices, E(Kn), are coloured using r colours; how large a k-connected subgraph are we guaranteed to find, which uses only at most s of the colours? This question is due to Bollobás, and the case s=1 was considered in Liu et al. [Highly connected monochromatic subgraphs of multicoloured graphs, J. Graph Theory, to appear]. Here we shall consider the case s is greater than or equal to 2, proving in particular that when s=2 and r+1 is a power of 2 then the answer lies between 4n/(r+1)-17kr(r+2k+1) and 4n/(r+1)+4 and that …

Intrinsic Linking And Knotting Of Graphs In Arbitrary 3–Manifolds, Erica Flapan, Hugh Howards, Don Lawrence, Blake Mellor

Pomona Faculty Publications and Research

We prove that a graph is intrinsically linked in an arbitrary 3–manifold M if and only if it is intrinsically linked in S³. Also, assuming the Poincaré Conjecture, we prove that a graph is intrinsically knotted in M if and only if it is intrinsically knotted in S³.

Maps Which Preserve Graphs, Van C. Nall

Department of Math & Statistics Faculty Publications

In 1976 Eberhart, Fúgate, and Gordh proved that the weakly confluent image of a graph is a graph. A much weaker condition on the map is introduced called partial confluence, and it is shown that the image of a graph is a graph if and only if the map is partially confluent.

In addition, it is shown that certain properties of one-dimensional continua are preserved by partially confluent maps, generalizing theorems of Cook and Lelek, Tymchatyn and Lelek, and Grace and Vought. Also, some continua in addition to graphs are shown to be the images of partially confluent maps only.

Graphs With 1-Factors, David Sumner

Faculty Publications

In this paper it is shown that if G is a connected graph of order 2n (n > 1) not containing a 1-factor, then for each k, 1