In this paper, we study the existence of unavoidable 2-edge-colored patterns in edge-colorings of the complete graph. We are interested in how these patterns change as the densities of the color classes change. A graph is called balanceable if it can be found, with half its edges in one color and half of them in the other, in any 2-edge-coloring of Kn with sufficiently many edges in each color class and n large enough. The balancing number bal(n,G) of a balanceable graph G is the maximum number m of edges such that there is a coloring of Kn with m edges in one color class without having a balanced copy of G. Equivalently, any 2-edge-coloring of Kn with more than bal(n,G) edges in each color contains a balanced copy of G. Graphs with constant (not depending on n) balancing number have been previously characterized. We give a new proof of such characterization that allows us not only to understand in a deeper way the structure of the graphs with constant balancing number but also to show that bal(n,G) is quadratic on the number of edges of G, a bound that differs substantially from the previous known that was exponential.

We investigate the Sidon set problem in the modular case and its corresponding version in Ramsey theory. Specifically, we study the function ̅F(n) that maximizes the size of a Sidon set in Zn, as well as the minimum n such that Zn admits no Sidon r-partition (a partition whose parts are all Sidon sets), denoted by ̅SR(r), for a fixed positive integer r. We use known results and the pigeonhole principle to establish an upper bound of ̅SR(r), which allows us to find the exact values of ̅SR(r) for r ϵ {2, 3, 4, 7}. We also present a criterion for determining the non-existence of almost difference sets (ADS) in Zn. By exploiting such criterion and the connection between ADS sets and the existence of Sidon sets in Zn, we derive nontrivial upper bounds of ̅F(n) for infinitely many values of n, and we refine the upper bound on ̅SR(r) in multiple cases, determining also the exact value for r ϵ {5, 6}. Our findings shed new light on the behavior of Sidon sets in cyclic groups. In particular, we find infinitely many values for which ̅F(n) > ̅F(n + 1).

Let G be a graph of order n, and let e ϵ E(G) and e' ϵ (V(G)/2) \ E(G). If the graph G' = G - e + e' is isomorphic to G, we say that e → e' is a feasible edge-replacement. We call G a local amoeba if, for any two copies G1 and G2 of G on V(G), G2 can be reach from G1 by performing a sequence of edge replacements. A graph G is a global amoeba if it can be made into a local amoeba by adding some isolated vertices. Our work includes a proof that almost every graph is not an amoeba, and the identification of a special type of edge-replacement called weird-edge-replacements. Additionally, we provide an infinite family of trees that are both weird local and global amoebas. Our contributions extend to the development and implementation of several algorithms for detecting local and global amoebas, which are made available in a public repository along with multiple examples.

Global amoebas are a wide and rich family of graphs that emerged from the study of certain Ramsey-Turán problems in 2-colorings of the edges of the complete graph Kn that deal with the appearance of unavoidable patterns once a certain amount of edges in each color is guaranteed. Indeed, it turns out that, as soon as such coloring constraints are satisfied and if n is sufficiently large, then every global amoeba can be found embedded in Kn such that it has half its edges in each color. Even more surprising, every bipartite global amoeba G is unavoidable in every tonal-variation, meaning that, for any pair of integers r, b such that r + b is the number of edges of G, there is a subgraph of Kn isomorphic to G with r edges in the first color and b edges in the second. The feature that makes global amoebas work are one-by-one edge replacements that leave the structure of the graph invariant. By means of a group theoretical approach, the dynamics of this feature can be modeled. As a counterpart to the global amoebas that “live” inside a possibly large complete graph Kn, we also consider local amoebas which are spanning subgraphs of Kn with the same feature. In an effort to highlight their richness and versatility, we present here three different recursive constructions of amoebas, two of them yielding interesting families per se and one of them offering a wide range of possibilities.