Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Balanced Coloring of Graphs, Groups, and the Amoeba Construction

Algebra & Discrete Mathematics

Speaker: 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.