论文标题
在边缘替代和变形虫家族下的图形同构
Graphs isomorphisms under edge-replacements and the family of amoebas
论文作者
论文摘要
本文对一个称为Amoebas的图表进行了系统的研究。最近，Amoebas从Ramsey-Turan理论的背景下对完整图的边缘的强制模式进行了研究，并在极端的零和最大问题中发挥了重要作用。对于以下操作，变形虫是具有独特行为的图形：让$ g $为图形，让$ e \在e（g）$中，$ e'\ in E（\ overline {g}）$。如果图$ g'= g-e+e'$是同构至$ g $，我们说$ g'$是通过执行\ emph {可行的边缘复制}从$ g $获得的。如果任何两个副本$ g_1 $，$ g_2 $ g $ $ g $ a \ emph {local amoeba}，同一顶点套装的$ g_2 $ $ g $，则可以通过一系列可行的边缘更换链将$ g_1 $转换为$ g_2 $。另一方面，如果有一个整数$ t_0 \ ge 0 $，则$ g $称为\ emph {global amoeba}，这样$ g \ cup tk_1 $是所有$ t \ ge t_0 $的本地变形虫。为了建模$ g $的可行边缘替换的动态，我们定义了一个$ {\ rm fer}（g）$满足$ g $的$ g $是本地的amoeba，并且仅当$ {\ rm fer}（g）（g）（g）\ cong s_n $，其中$ n $是$ g $的订单。通过这种代数环境，对变形虫的结构及其内在特性有了更深入的了解。此外，我们提出了不同的结构，这些结构证明了这些图形家族的丰富性，除其他外，任何连接的图形都可以是全球变形虫的连接组成部分，即全球变形虫可以非常密集，并且它们可以按照其顺序成比例，大量和大数字。此外，建造了一个具有斐波那契的结构且具有任意较大最高程度的全球变形虫树的家族。
This paper offers a systematic study of a family of graphs called amoebas. Amoebas recently emerged from the study of forced patterns in $2$-colorings of the edges of the complete graph in the context of Ramsey-Turan theory and played an important role in extremal zero-sum problems. Amoebas are graphs with a unique behavior with regards to the following operation: Let $G$ be a graph and let $e\in E(G)$ and $e'\in E(\overline{G})$. If the graph $G'=G-e+e'$ is isomorphic to $G$, we say $G'$ is obtained from $G$ by performing a \emph{feasible edge-replacement}. We call $G$ a \emph{local amoeba} if, for any two copies $G_1$, $G_2$ of $G$ on the same vertex set, $G_1$ can be transformed into $G_2$ by a chain of feasible edge-replacements. On the other hand, $G$ is called \emph{global amoeba} if there is an integer $t_0 \ge 0$ such that $G \cup tK_1$ is a local amoeba for all $t \ge t_0$. To model the dynamics of the feasible edge-replacements of $G$, we define a group ${\rm Fer}(G)$ that satisfies that $G$ is a local amoeba if and only if ${\rm Fer}(G) \cong S_n$, where $n$ is the order of $G$. Via this algebraic setting, a deeper understanding of the structure of amoebas and their intrinsic properties comes into light. Moreover, we present different constructions that prove the richness of these graph families showing, among other things, that any connected graph can be a connected component of a global amoeba, that global amoebas can be very dense and that they can have, in proportion to their order, large clique and chromatic numbers. Also, a family of global amoeba trees with a Fibonacci-like structure and with arbitrary large maximum degree is constructed.
