Current Research
Current Research
复制标题
DOI：
10.5596/c05-028
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
S. Hoory
中科院分区：
文献类型：
--
作者：
S. Hoory
(a)也许在极值图论中最重要的课题是确定图H的Turán个数。这是一个大小为n的图，在没有同H同构的子图的情况下，所能拥有的最大边数。当H是非二部的，这个函数的渐近性由著名的Erdös-Stone定理决定，直到1 + 0(1)个因子。然而，对于二部图的Turán个数，特别是偶长循环C2k，找到好的估计是一个长期存在的问题。在我过去的工作[1,3,4]中，我开发了一种利用熵参数获得图极值性质下界的技术。最近，我在与Jacques a . Verstraete和Felix Lazebnik的联合工作中发现了该技术的另一个应用，涉及Sidorenko 1991的一个猜想：对于任何l < k，当C2l的自由图是C2l的Turán图时，长度为2k的循环数在C2l中最大。我们在证明l = k−1和l = k−2情况下的猜想方面取得了重大进展。我们的主要工具是对我的工作b[1]的概括。这一工作给出了在给定边缘密度的图中，长度为k的路径的局部1对1嵌入次数的下界。我们最近的推广是在嵌入树而不是路径时证明类似的结果。
(a) Perhaps the most important topic in extremal graph theory, is to determine the Turán number of a graph H . This is the maximal number of edges a graph of size n can have, without having a subgraph isomorphic to H . When H is non-bipartite, the asymptotics of this function is determined by the celebrated Erdös-Stone theorem, up to an 1 + o(1) factor. However, it is a longstanding problem to find good estimates on the Turán number of bipartite graphs, and in particular of even length cycles, C2k. In my past work in [1, 3, 4], I developed a technique for obtaining lower bounds on extremal properties of graphs, using entropy arguments. Recently I found one more application for this technique, in a joint work with Jacques A. Verstraete, and Felix Lazebnik, concerning a conjecture of Sidorenko 1991: For any l < k, the number of length 2k cycles is maximized in a C2l free graph, when the graph is a Turán graph for C2l. We have made significant progress in proving the conjecture for the cases l = k − 1, and l = k − 2. Our main tool is a generalization of my work [1]. That work gives a lower bound on the number of locally one to one embeddings of the length k path into a graph of a specified edge density. Our recent generalization, is to prove a similar result when embedding trees instead of paths.