Investigating graphs with odd cycles via commutative algebra (08rit124)
Organizers
Christopher Francisco (Oklahoma State University)
Tai Ha (Tulane University)
Adam Van Tuyl (McMaster University)
Description
Informally, a graph is a set of points, called vertices, along with lines between the vertices, called edges. Graph theory has been extremely important in modeling optimization problems in industry, such as finding the best ways to deliver telephone or Internet service to homes and businesses. In our work, we study properties of graphs by associating an algebraic object to the graph. By investigating the structure of this
algebraic object, we learn information about the graph.
This indirect approach has been particularly useful in studying cycles of odd length. A cycle is a path in the graph in which one moves along edges from one vertex to a new vertex, eventually returning to the initial vertex; a cycle of odd length contains an odd number of edges. We have recently found a strong connection between the cycles of odd length in a graph and a specific algebraic property which we hope to exploit, thereby expanding the connections between graph theory and algebra. Our interest in studying graphs with odd cycles is partialy inspired by their connection to the celebrated Strong Perfect Graph Theorem. This theorem characterizes perfect graphs, a family of graphs with applications to diverse fields such as communications and integer-programming.
algebraic object, we learn information about the graph.
This indirect approach has been particularly useful in studying cycles of odd length. A cycle is a path in the graph in which one moves along edges from one vertex to a new vertex, eventually returning to the initial vertex; a cycle of odd length contains an odd number of edges. We have recently found a strong connection between the cycles of odd length in a graph and a specific algebraic property which we hope to exploit, thereby expanding the connections between graph theory and algebra. Our interest in studying graphs with odd cycles is partialy inspired by their connection to the celebrated Strong Perfect Graph Theorem. This theorem characterizes perfect graphs, a family of graphs with applications to diverse fields such as communications and integer-programming.
The Banff International Research Station for Mathematical Innovation and Discovery (BIRS) is a collaborative Canada-US-Mexico venture that provides an environment for creative interaction as well as the exchange of ideas, knowledge, and methods within the Mathematical Sciences, with related disciplines and with industry. The research station is located at The Banff Centre in Alberta and is supported by Canada's Natural Science and Engineering Research Council (NSERC), the US National Science Foundation (NSF), Alberta's Advanced Education and Technology, and Mexico's Consejo Nacional de Ciencia y Tecnología (CONACYT).
