Return to Colloquia & Seminar listing
Balanced Coloring of Graphs, Groups, and the Amoeba Construction
Algebra & Discrete MathematicsSpeaker: | Denae Ventura, UC Davis |
Location: | 2112 MSB |
Start time: | Tue, Oct 24 2023, 4:10PM |
Amoeba graphs were born as examples of balanceable graphs, which are graphs that appear in any edge coloring of a large enough $K_n$ using $2$ colors such that there is a sufficient amount of edges in each color. In 2019, Caro, Hansberg and Montejano defined amoeba graphs in a purely combinatorial setting. They discovered important properties but could not prove them formally using only combinatorics, so they provided an equivalent definition that employed group theory, facilitating their proofs greatly and allowing them to use algebraic techniques.
We label the vertices in our graphs.
An edge-replacement in $G$ means to take away an edge and place it in an available spot. If the resulting graph is isomorphic to the original graph, we say that the edge-replacement is feasible. Notice that every feasible edge-replacement yields a set of permutations of the labels in $G$. The set of all permutations associated with all feasible edge-replacements in $G$ generates the group Fer$(G)$. A graph $G$ of order $n$ is a local amoeba if Fer$(G) \cong S_n$ and a global amoeba if Fer$(G\cup tK_1)\cong S_{n+t}$, for a large enough $t$. An interesting problem is to find local and/or global amoebas. One might think they are hard to find, and they generally are. However, in this talk we will go over a recursive construction of infinite families of local amoebas that answers an open problem posed by Caro, Hansberg and Montejano.