General Information
| Student: | Ruby Ortiz |
|---|---|
| Office: | 450 CoRE |
| School: | Muhlenberg College |
| E-mail: | rubyortiz@muhlenberg.edu |
| Project: | Geometry and Combinatorics of Matroids |
Project Description
This research entails the application of matroids and the relation to log-concavity. This research is focused on June Huh's paper, "Combinatorial Applications Of The Hodge-Riemann Relations". I focused on chromatic polynomial of graphs, which is the number of ways a graph, G(V,E), where V is the set of vertices and E is the set of edges, can be colored so that the adjacent vertices are different colors. This is what is known as proper q-coloring, such that no two vertices on the same edge have the same color. Chromatic polynomial is a special case that will lead to an understanding of matroids and how they work. I will be looking into proving the deletion-contraction relation, Hoggar[1974], that gives us an equation to the chromatic polynomial and essetially lead to a definition of matroids. Finally, we will eventually reach to prove the first conjecture offered in Huh's paper based on Rita's conjecture. Then we will be looking at Rota's Unimodality Conjecture and working on its proof over the summer.
Weekly Log
- Week 1:
- This week we began with an introduction to the program and the introductions of the rest REU students through DIMACS. Then, I met with my mentor to discuss my project, Geometry and The Combinatorics of Matroids, and came to a conclusion of proving the deletion-contraction relation to chromatic polynomial. I began by getting an understanding of the new terms and concepts of graph theory and started to look into chromatic polynomial examples.
- Week 2:
- This week I worked on the Deletion-Contraction Relation and getting an understanding of the proof. I looked into The Chromatic Polynomial of a graph introduced by Huh in his paper "Combinatorial Applications Of The Hodge-Riemann Relations". The relation is utilized to compute the chromatic polynomial of a graph. I looked closely into a graph with four edges and four vertices and proved how the deletion, deleting an edge, minus the contraction, contracting the vertices, equals the chromatic polynomial of the original graph. Then towards the end of the week I began to work on finding the polynomials of different types of graphs.
- Week 3:
- This week I came to generalized polynomials for graphs like cycles, trees, and paths. These equations are use to determine the chromatic polynomials and were tested with the deletion-contration relation. I use the graph method of the deletion-contraction, where we delete and contract the graph and write the equations to the chromatic polynomials for each one then compared it to the original. Towards the end of the week I began to look at more graphs like wheels to also get a general equation. Froylan explain to me his section on the symmetric matrices and their relation to being a matroid and log-concavity. I also worked on other examples of matroids and how they related to the forms of graphs and equations use to demonstrate their log-concavity.
- Week 4:
- This week I moved to section 2.6 of Huh's paper mentioned on week 2. Which is the explanation of matroids and some examples that help us get a better understanding of the definition. I began to read "Matroid Theory" by Hayley Hillman to see some definitions besides Huh. Then I also began to read the book "Matroid Theory" by James Oxley to get different explanations. There was also a trip to IBM where we learned about Research as a career. There we met Watson, the famous computer system that also happened to beat the top two Jeopardy winners in 2011. Speakers from different research projects and fields spoke about what they are doing and exposed us into what research looks like. On our tour we saw a quantum computer that is kept under hydrogen that keeps it cool.
- Week 5:
- This week I began to tackle some of the examples on Huh's 2.6 section. One example that we focused on the most was The Chow Ring and its application to graphs. We took the graphs flats and created sets out of them. Then we learned how to take the ideal of a polynomial and be able to determine the Chow Ring from the equation A(M)= S(M)/ I(x), where S(M) is the ring and I(x) is the ideal of the polynomial. The Chow Ring was then tested on the K_3 graph by making the ring a set of flats created by the K_3 graph. The ideal was then generated by the difference between the summations of the polynomials created by the flats, one for each distict flat of E, or in this case the graph. Which then gives us the sum of the sets of the Chow Rings for each dimension. We are focusing on finding the Chow Ring for multiple graphs and see where it leads us.
- Week 6:
- This week I worked a little on 3-D graphs, more specifically getting the chromatic polynomial of these graphs. It turns out that most of the bases of the 3-D graphs I have already solved a chromatic polynomial for them. The difficulty comes in seeing how the extra faces changes the amount of q color options are being taken from those graphs already known. After working with Froylan on the Chow Ring, I worked on how to find the Chromatic Polynomial of Matroids. I spend most of the week preparing for the presentations next week and createing a power point with the research I have done so far!
- Week 7:
- This week was busy in terms if concluding all I've learned and done into a powerpoint! It was presentation week, therefore I worked a lot on how to make my work presentable and concise. Dr. Tarasca helped with the wording and the formating of the presentation a little. Presentations tend to push me beyond my comfort zone, so I would like to thank all my peers and mentor who helped me practice and feel more confident with it, it was a success! Please check out my final presentation below! This week I also continued my work on finding the Chromatic Polynomial of matroids. Dr. Tarasca and I, in our meeting, managed to developed a method of finding the chromatic polynomial by using the flats and their ranks to develop an understanding of the equation referenced in "Chromatic Polynomial II", where an equation for the chromatic polynomial of a matroid is given.
- Week 8:
- This week I was finishing up what I could with my project. SO what I did was learned the complexity of applying the characteristic polynomial on matroids. Using the same discovery of last weeks, I applied it to multiple examples in Huh's article as well as Oxley's book. I did not get too far before I began writing my paper for the end of the program, where all of my work is explained in a little more detail than this website can offer. Therefore, I forcused the end of this week to outlining and organizing the structure of the paper!
- Week 9(Final Week):
- This week is a wrap up for the summer! I mainly worked on my paper all day and met with my mentor a couple times to make sure I was developing what was needed for the paper. I learned how to use TikZ to create graphs on LaTeX and make my paper more professional! It was time consuming because you have to write down all the coordinates of where you want the points and lines to make the graphs, since my project consisted of graphs it took me a while to finish! I also said goodbye to my colleagues and peers, as well as my Mentor. It was a great summer and I'm glad I was given this opportunity to experience what research is all about! Thank you DIMACS!!
Presentations
Additional Information
- My Mentors