论文标题
有限图的演变
Evolutions of finite graphs
论文作者
论文摘要
每个可计数的图形都可以通过适当的无限过程从有限图构建，要么随机添加新的顶点，要么在新边缘施加一些规则。另一方面，构建了一个拓扑图作为带有图型的有限图的反极限。 我们建议同时研究这两个结构。我们认为可以通过使用嵌入和投影来从有限的图中构建的可计数图，这可能在每个步骤中添加一个顶点。我们证明可以通过这种方式构建Rado图，而Henson的通用三角形无图形则不能。 我们还研究了相应的涂鸦图。最后，我们提出了一个投影通用图形图的具体模型，即有限图的投射fraisse极限，特别表明它具有密集的隔离顶点。
Every countable graph can be built from finite graphs by a suitable infinite process, either adding new vertices randomly or imposing some rules on the new edges. On the other hand, a profinite topological graph is built as the inverse limit of finite graphs with graph epimorphisms. We propose to look at both constructions simultaneously. We consider countable graphs that can be built from finite ones by using both embeddings and projections, possibly adding a single vertex at each step. We show that the Rado graph can be built this way, while Henson's universal triangle-free graph cannot. We also study the corresponding profinite graphs. Finally, we present a concrete model of the projectively universal profinite graph, the projective Fraisse limit of finite graphs, showing in particular that it has a dense subset of isolated vertices.
