Square network on a word
Square network on a word
复制标题
方网就一句话
DOI：
10.1016/j.tcs.2021.08.004
复制
发表时间：
2021
影响因子：
1.1
通讯作者：
Seki Shinnosuke
中科院分区：
文献类型：
--
作者：
Fazekas Szilard Zsolt;Seki Shinnosuke
最后出现的左对齐的正方形（双正方形）为长度为n的词ω上可以包含多少个不同的正方形的问题提供了深刻的见解，并带来了最著名的上界11 n/6。其他类型的对齐（如中心对齐）以及长距离关系（如出现相同的正方形）将ω上的正方形合并到正方形和位置{1，2，.，n}的二分图中，我们称之为正方形网络。在有限的空间中填充越来越多的正方形，一旦正方形密度超过一个阈值，肯定会导致特定类型的子图，如果已知其中一个子图是禁止的，则阈值提供了不同正方形数量的上限。在本文中，我们指定一个特定的位置的双重广场为P1，并获得某些诱导子图，以及禁止的P1对齐的双重广场的存在下保证的，特别感兴趣的诱导子图表示的全球唯一性的平方。
Left-aligned last occurrences of squares (double-square) have provided profound insights into the question of how many distinct squares can be packed on a word ω of length n and brought the best known upper bound 11 n/6. Other types of alignments such as being center-aligned as well as long distance relations such as being the occurrences of the same square incorporate the squares on ω into a bipartite graph of the squares and positions {1, 2,…, n}, which we call the square network. Packing more and more squares in a limited space certainly induces specific kinds of subgraphs once the square density exceeds a threshold, and if one of the subgraphs is known to be forbidden, the threshold provides an upper bound on the number of distinct squares. In this paper, we designate a specific position of double-squares as P 1 and obtain certain induced subgraphs as well as forbidden ones guaranteed by the presence of P 1-aligned double squares; an induced subgraph of particular interest expresses the global uniqueness of squares involved.