A path Turán problem for infinite graphs

详细信息    查看全文

• 作者：Xing Peng^a ; ^{x2peng@tju.edu.cn} ; Craig Timmons^b ; ^{craig.timmons@csus.edu}
• 关键词：Path Turá ; n ; Infinite graphs
• 刊名：Discrete Mathematics
• 出版年：2017
• 出版时间：6 February 2017
• 年：2017
• 卷：340
• 期：2
• 页码：181-191
• 全文大小：452 K
• 卷排序：340

文摘

Let GG be an infinite graph whose vertex set is the set of positive integers, and let GnGn be the subgraph of GG induced by the vertices {1,2,…,n}{1,2,…,n}. An increasing path of length kk in GG, denoted IkIk, is a sequence of k+1k+1 vertices 1≤i1<i2<⋯<ik+11≤i1<i2<⋯<ik+1 such that i1,i2,…,ik+1i1,i2,…,ik+1 is a path in GG. For k≥2k≥2, let p(k)p(k) be the supremum of lim infn→∞e(Gn)n2 over all IkIk-free graphs GG. In 1962, Czipszer, Erdős, and Hajnal proved that p(k)=14(1−1k) for k∈{2,3}k∈{2,3}. Erdős conjectured that this holds for all k≥4k≥4. This was disproved for certain values of kk by Dudek and Rödl who showed that p(16)>14(1−116) and p(k)>14+1200 for all k≥162k≥162. Given that the conjecture of Erdős is true for k∈{2,3}k∈{2,3} but false for large kk, it is natural to ask for the smallest value of kk for which p(k)>14(1−1k). In particular, the question of whether or not p(4)=14(1−14) was mentioned by Dudek and Rödl as an open problem. We solve this problem by proving that p(4)≥14(1−14)+1584064 and p(k)>14(1−1k) for 4≤k≤154≤k≤15. We also show that p(4)≤14 which improves upon the previously best known upper bound on p(4)p(4). Therefore, p(4)p(4) must lie somewhere between 316+1584064 and 14.