fairfolio
Saved Projects

Cycle Spaces of Friends-and-Strangers Graphs

CSEF · 2023 Mathematical Sciences First Award

Wei Michelle · 11

Overview

Flip graphs are graphs of combinatorial objects, where 2 adjacent objects are related through a local change, or a flip. In my work, I studied friends-and-strangers (FS) graphs, an abstract class of flip graphs first introduced in 2020. They are defined as follows. Given graphs X and Y, the friends-and-strangers graph of X and Y, denoted FS(X, Y), is a graph whose vertices are the bijections from the vertices of X to the vertices of Y, in which two bijections are adjacent in FS(X, Y) if and only if they differ by exactly one swap of elements that are adjacent in X and map to adjacent elements in Y. Defined as such, FS graphs provide a generalization for many different kinds of graphs, such as Cayley graphs and Bruhat graphs, allowing us to study these graphs under a unified framework. Acyclic orientations of FS(Path_n, Y), where Path_n is the path graph on n vertices, have wide applications in scheduling, data processing, and bioinformatics. Previous work in FS graphs focus overwhelmingly on connectivity, and other properties of FS graphs have been explored very little. In my work, I analyzed the cycle spaces of FS graphs, an approach that reveals the structure of FS graphs. I proved that when Y is any graph on n vertices with a domination number of at least 3, the cycle space of FS (Cycle_n, Y) is spanned by cycles of size 4 and 6, where Cycle_n is the cycle graph on n vertices. Related to the problem of cycle spaces are shortest paths. To determine whether a cycle is chordless, I developed a novel approach investigating shortest paths in FS graphs by analyzing the sequence of swaps of elements that takes place in the path. In addition to using this approach to show that the cycle space of FS(Cycle_n, Y) is spanned by 4-cycles and 6-cycles when Y is any graph on with a domination number of at least 3, I also used this approach to identify the conditions for which larger chordless cycles exist and to construct such cycles. This new method can be also applied to study shortest paths and cycle spaces of other graphs as well. My research is a pioneering study of the structure of FS graphs. Providing valuable insight into the structure and behavior of complex systems, my findings can be applied to implement graph-based algorithms with greater efficiency than was previously possible, with applications in many areas, such as task scheduling, data processing, and energy management.

Source coverage

This record comes from a published award list, not a complete project archive. Its abstract comes from CSEF's public project showcase as archived by the Internet Archive before judging (https://web.archive.org/web/20230401224130/https://ca-csef.zfairs.com/showcase/ShowcaseInfo?f=838e60b7-ea75-46e8-865c-fde4864244b3); the version presented may differ.

Awards (2)

Competition history

  • CSEF 2023 Mathematical Sciences · Entry S1409

Resources

Related projects

Closest projects by meaning, across every fair and year in the corpus.

Browse more like this

Source: California Science & Engineering Fair public projects

Save projects to your library

Sign in with Google to keep track of projects you find interesting, organized into folders. An account also raises your daily allowance for “Has this been done?”, and lets you create a key for the MCP server with a much higher limit than anonymous use. Browsing stays public.

Continue with Google