Marielle Jurist, DIMACS REU 2016


General Information

Student: Marielle Jurist
Office: Core 450
School: Rutgers University
E-mail: me
Project: Bilu-Linial Conjecture and Ramanujan Graphs
Mentor: Ameera Chowdhury, Mathematics Department

Project Description

This summer I will be working on proving the Bilu-Linial conjecture for all d-regular graphs.


Weekly Log

Week 1:
I spent the first week continuing the work I started over the summer with my mentor, Ameera Chowdhury. We met several times prior to the start of the REU. I finished an assignment on finding the spectra of various graphs with the help of SageMath software. Ameera and I met several times this week as well she explained what specific research question I will be tackling this summer. I also prepared a presentation on my research project for Monday.
Week 2:
This week I read some notes on Spectral Graoh theory by Dan Spielman. I worked on an assignmnet where I proved some major theorems discussed in Spielman's lecture notes. Some of the topics I covered this week included the Raleigh quotient of a vector and theorem 1.6.2 from Speilman's lecture 1 notes. I also learned more about the corresponding eignenvalues of d-regular and bipartite graphs.
Week 3:
I finished the second half of the assignment that went along with Dan Spielman's lecture notes. Some of the exercises completed included showing how the largest eigenvalue of a graph G captures information about the average degree and maximum degree of G, proving the second smallest eigenvalue of LG captures information about how well-connected G is. I also did some exercises involving the Laplacian Matrix.
Week 4:
I read over the paper by Marcus, Spielman, and Srivastava (2014), making sure I fully understand the thesis of the paper, as my research question expands on their findings. Ameera and I reiterated the main points of my thesis during one of our meetings. I finished the last two proofs on spectral graph theory I needed as preliminary work before starting my original research. The last couple days of this week I started working on writing a program in Sage math to generate every possible signing on a regular graph on four vertices.
Week 5:
I conintued working on writing my sage math program. The goal is to have a generating program that will iterate through all the possible signed regualr graphs on any number of vertices without having separate lines of code for each plotted graph.
Week 6:
This week I finished my graph generator program. It successfully assigns all posisble signings to all the d-regular graphs of a speciifed number of vertices. I ran my program on graphs up to 6 vertices then had to stop. I was surprised at the high number of graphs outputted by the program. Computation time quickly became an issue. I spent the later part of the week trying to cut the number of outputs made by my program.
Week 6:
I changed my program so that for each type of d-regular graph the program only outputs the signings that produce corresponding signed adjacency values with eignevalues within the desired range. However, outputs still exceeded the hundreds of thousands. I was able to incresase the max output messages allowed by the server so my program does not crash but I have to rethink my research strategy. I ran the program up to ten vertices, but quantifying the data and recognizing patterns in the signings will be a difficult challenge with a data set this large. I did learn this week however that the amount of singings that satisfy the conditions in the Bilu-Linial conjecture is much larger than I expected.