Denae Ventura: Constructions of amoeba graphs and their balancing number

Please note this event occurred in the past.
December 05, 2025 12:00 pm - 1:00 pm ET
Discrete Math Seminar
LGRT 1569

Denae Ventura (Mount Holyoke) - Constructions of amoeba graphs and their balancing number

Abstract:  Amoeba graphs are based on iterative feasible edge-replacements, where, at each step, an edge from the graph is removed and placed in an available spot so that the resulting graph is isomorphic to the original graph.

Broadly speaking, amoebas are graphs that, by means of a chain of feasible edge-replacements, can be transformed into any other copy of itself on a given vertex set (depending on which they are defined as local or global amoebas). Global amoebas were born as examples of balanceable graphs, which appear with half of their edges in each color in any 2-edge coloring of a large enough complete graph with a sufficient amount of edges k in each color. The minimum value of k is called the balancing number of G. We provide a recursive construction to generate very diverse infinite families of local and global amoebas, which not only answers a question posed by Caro et al. but also yields an efficient algorithm that provides a chain of feasible edge-replacements that one can perform in order to move a local amoeba into an aimed copy in the same vertex set. We express the balancing number of a global amoeba G in terms of the extremal number of a class of subgraphs of G and give a general lower bound. We provide linear lower and upper bounds for the balancing number of our three case studies. Finally, we introduce the hang group, a group-theoretic invariant capturing how local amoebas embed into larger ones.

This framework provides necessary and sufficient conditions linking stem-and hang-symmetry to local and global amoebas and shows how they behave under adding leaves or isolated vertices. These results strengthen and generalize existing constructions of local and global amoebas.

These results come from two research projects which are joint work with Adriana Hansberg, Laura Eslava, Tonatiuh Matos, Ryan Pesak, Jillian Eddy, and Daniel Qin.