Project Overview
Reconstructibility of Graphs, Matrices and Monomial Orders
Department(s)
Mathematics
Abstract
Students would work on one of the following two subprojects.
Subproject 1: A MORMORE is a Monomial Order Represented by a Matrix of Only Rational Entries. Former research conducted at Colgate by Nayda Farnsworth, PJ Horoszewski, Aranya Pal and Marisa Zarcone, under the direction of Professor Sosa Castillo characterized the MORMOREs that are reconstructible from is labeled induced subMORMOREs. Now, the question is whether a reconstructible MORMORE can be reconstructed from its unlabeled induced subMORMOREs. Alternatively, students working in this subproject could explore ways new ways to define submatrices from an n by n matrix via reductions and under what circumstances is a matrix reconstructible from its unlabeled induced submatrices.
Subproject 2: Determine a bijective function F that associates a MORMORE in n variables to a graph with n vertices in such a way that induced subMORMORES correspond to the vertex deletions of the graph. Alternatively, students working in this subproject could explore new ways to associate n by n matrices to graphs with n vertices in such a way that certain algebraic properties of the submatrices are preserved via vertex deletion of the graph.
Together the results from both subprojects would help in the proof of the Kelly/Ulam conjecture. The Kelly/Ulam conjecture is an open problem in Graph Theory (formulated in the 60s) concerning the reconstructibility of a graph from its vertex deletions.
One way to formulate the Kelly/Ulam conjecture involves defining a deck as a collection of n cards, each card featuring one graph with n-1. If G and G’ are two graphs with n vertices each, such that there is a one to one correspondence between the vertex deletions of G and the graphs featured in the cards of a deck and a one to one correspondence between the vertex deletions of G’ and the graphs featured in the cards of the same deck, then G and G’ are isomorphic graphs.
The Kelly/Ulam conjecture has been proven for specific families of graphs (regular graphs, trees, maximal planar graphs, separable graphs without end vertices, graphs with less than fourteen vertices) but a proof for the general case has not been found. Advances on either of the subprojects could help prove the Kelly/Ulam conjecture for new classes of graphs.
Student Qualifications
Required:
- Knowledge of graph theory, particularly properties of bipartite graphs, trees, chromatic graph theory, and types of matrices associated to graphs (degree matrix, distance matrix, adjacency matrix, incidence matrix, graph laplacian).
- Knowledge of linear algebra, particularly reductions of matrices, determinants, eigenvalues and eigenvectors, kernel of a matrix.
- Ability to read and write proofs, in particular mathematical induction, direct proof and proof by contrapositive.
Preferred:
- Familiarity in writing programs in Python, Julia, Matlab or Mathematica, specifically programs involving operations with matrices and reductions of matrices.
Project Length
8 or 9 weeks
APPLY