Advances in Applied Mathematics
Vol.
09
No.
03
(
2020
), Article ID:
34783
,
7
pages
10.12677/AAM.2020.93054
Dependent Random Choice and Generalized Turán Numbers of Even Wheels
Yujun Cui, Xiuzhuan Duan, Weihua Yang*
School of Mathematics, Taiyuan University of Technology, Jinzhong Shanxi
Received: Mar. 4th, 2020; accepted: Mar. 20th, 2020; published: Mar. 27th, 2020
ABSTRACT
Let G be a graph on n vertices, and be a triangle in graph G. We denoted by a graph with s vertices in the center, a 2l long even circle in the periphery, and 2l edges on the even circle are connected with s vertices in the center; and represents a graph in which the center has s vertices, the periphery is an l-long road, and ledges of the road are connected with s vertices of the center. In this paper, we mainly proved that the following generalized Turán number by using the technique of dependent random choice: 1) . 2) .
Keywords:Generalized Turán Number, Triangles, Dependent Random Choice
依赖随机选择与偶轮的广义Turán数
崔玉君,段秀转,杨卫华*
太原理工大学数学学院,山西 晋中
收稿日期:2020年3月4日;录用日期:2020年3月20日;发布日期:2020年3月27日
摘 要
令G表示n个顶点的图, 表示图G中的三角形。 表示中心有s个顶点,外围是一个2l长的偶圈,且偶圈上的2l条边都与中心的s个点相连的一个图; 表示中心有s个顶点,外围是一条l长的路,且路上的l条边都与中心的s个点相连的一个图。在本文中,我们主要利用依赖随机选择技术证明了下述广义Turán数: 1) 。 2) 。
关键词 :广义Turán数,三角形,依赖随机选择
Copyright © 2020 by author(s) and Hans Publishers Inc.
This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).
http://creativecommons.org/licenses/by/4.0/
1. 引言
令 表示一些图组成的集族,如果对于任意的 ,图G都不包含F作为子图,那么称图G是不包含族 的。Turán数 定义为在n个顶点且不包含 的图G的最大边数。如果集族 仅包含一个简单图F,我们可以用 代替 。令 表示l长的路,在1959年,Erdös和Gallai [1] 计算了图G中有关 的Turán数。
定理1.1:(Erdős, Gallai [1] )令G是一个n个顶点的图, 表示l长的路,那么 。
随后在1965年,Erdős [2] 又计算了有关偶圈的Turán数,Bondy和Simonovits [3] 对此进行了证明。
定理1.2:(Erdös [2] )令G是一个n个顶点的图, 表示2l长的偶圈,且 ,那么存在正整数C,使得 。
现在,关于Turán数已经有大量的研究,详见综述文献 [4] [5]。
令T表示一个简单图,广义Turán数 定义为n个顶点的不包含 的图G中T复制的最大个数。如果 ,那么广义Turán数 就是经典的Turán数 。同样的,对于一个简单图F,我们通常用 代替 。最近,广义Turán数问题的研究也受到了广泛的关注,详见文献 [6] [7] [8] [9]。
表示t个顶点的完全图。在1962年,Erdős [10] 首先计算了完全图的广义Turán数:
与Erdös-Stone定理相类似,Alon-Shikhelman [6] 证明了:对任意的图H,如果图H的色数 ,并且当 时,那么 ;当 时,那么 。Bollobás和Győri [7] 证明了在n个顶点的图G中不包含 时, 的个数为: 。Győri和Li [11] 证明了在n个顶点的图G中不包含 时, 的个数为: 。Alon-Shikhelman [6] 又对上述两个结果的上界进行了改进,得到:1) ; 2) 。
依赖随机选择是图论中一种简单而且有用的方法。早期,这种技术是被Rödl,Gowers,Kostochka以及Sudakovd等人 [12] [13] [14] 证明而且应用推广的。这个基本方法,也是一个著名的概率办法,详见文献 [15]。现在,依赖随机选择技术已经被应用到更多方面,比如:极值图论、拉姆齐理论、可加组合数学、组合几何等。
引理1.3:(依赖随机选择引理)令a,m,r,n都是正整数,d是一个正实数。G表示n个顶点的图,其平均密度为d。如果存在正实数t,使得
那么图G中存在一个大小至少是a的子集U,使得U中任意r个顶点在图G中至少有m个公共邻点。
并且利用依赖随机选择技术,可以计算出有关二部图H的Turán数。
定理1.4:(Alon et al. [16] )令s是一个正整数, 是一个二部图,且B中顶点的度 。那么存在一个常数 ,使得
在n个顶点的图G中,令表示中心有s个顶点,外围是一个2l长的偶圈,且偶圈上的2l条边都与中心的s个顶点相连接的一个图;表示中心有s个顶点,外围是一条l长的路,且路上的l条边都与中心的s个顶点相连接的一个图。本文中,我们主要利用依赖随机选择技术得到下述两个结果:
定理1.5:假设,,且C和c是两个正数。令G是n个顶点的图,且边数为e,那么
定理1.6:假设,。令G是n个顶点的图,且边数为e,那么存在正数C,使得
本文主要内容安排如下:第二节主要利用依赖随机选择技术证明一个相关引理;第三节证明主要定理。
2. 引理的证明
我们先利用依赖随机选择技术证明下述引理。
引理2.1:令a,m,r,n都是正整数。G是一个n个顶点的图,且图G中的边数为e,将图G中三角形的个数记为k,如果存在正整数t,使得
那么图G中存在一个大小至少是a的子集U,使得集合U中任意r个顶点在图G中至少含有m条公共邻边。
证明:令是一个n个顶点,边数为e的简单图,且图G中有k个三角形。我们将图G的顶点集记为:,边集记为:。首先,我们将从图G的边集中依均匀分布的可重复的选择t条边组成集合,记为。令X表示这t条边的所有公共邻点的集合,个数记为。
我们做如下标记:
,
那么,的期望值为:
又因为
其中,表示包含点的所有三角形的个数。
所以,
令R表示集合X中由r个顶点构成的r元-子集。如果R在图G中的公共邻边小于m条,就称R是“坏”的r元-子集。令Y表示集合X中所有“坏”的r元-子集,个数记为。令Z表示图G中的所有“坏”的r元-子集。
同样地,我们也做如下标记:
那么,可以得到的期望值为:
又因为R是Y中的r元-子集,且R在图G中的公共邻边小于m条,那么
所以,
我们利用期望的线性,就可以得到的期望值为:
那么根据引理的条件得到:。
所以在图G中必定存在一种边集的选择,使得成立。那么令U是从X中的每个“坏”的r元-子集中删除一个顶点得到的集合,那么,并且U中任意r个点在图G中至少有 条公共邻边。
3. 主要定理的证明
引理3.1:假设,。令G是n个顶点的图,且边数为e,那么存在足够大的正数C,使得
证明:假设图G中三角形的个数,那么根据引理2.1,令,,,并且存在足够大的正整数,使得。又因为的色数为3,根据Erdős-Stone定理,所以图G的边数。通过计算,我们可以得到:
(1)
(1)式的推导过程详见附录。所以在图G中存在一个大小至少是s的子集U,使得U中任意s个点在
图G中至少含有条公共邻边。又根据定理1.2,那么在U的一个s集的公共邻边中一定存在一个2l
长的偶圈,并且这2l条边都与这s个顶点相连。所以在图G中就可以找到一个的复制,与图G中不包含矛盾。
引理3.2:假设,。令G是n个顶点的图,那么存在正数c,使得
证明:从图G中按概率p随机地选择一条边,其中。用X表示图G中的所有三角形构成的集合,个数记为。那么的期望值为:
令Y表示图G中所有构成的集合,个数记为,同样的,的期望值为:
接下来,从图G中的一个中删除一条边,至多删除个三角形,那么将图G中所有的都删除一条边,至多就删除个三角形,所以,
(2)
(2)式中不等式成立是因为,即:
所以存在一个n个顶点的图G,使得图G中没有的复制,但三角形的个数为。
我们利用引理3.1和引理3.2就完成了定理1.5的证明。
引理3.3:假设,。令G是n个顶点的图,且边数为e,那么存在足够大的正数C,使得
证明:与定理3.1的证明类似,假设图G中三角形的个数,根据引理2.1,令,,,。同样的,因为的色数为3,所以图G的边数。通过验证,可以得到:
(3)
(3)式的推导过程详见附录。所以在图G中可以找见一个大小至少是s的子集U,使得U中任意s个
点在图G中至少含有条公共邻边。又根据定理1.1,那么在U的一个s集的公共邻边中一定存在
着一条l长的路,使得上的边都与这s个点相连。所以在图G中一定可以找到一个的复制,与图G中不包含矛盾。
引理3.4:假设,。令G是n个顶点的图,那么存在正数c,使得
证明:从图G中按概率p随机地选择一条边,其中,用X表示图G中的所有三角形构成的集合,个数记为。那么的期望值为:
令Y表示图G中所有构成的集合,个数记为,同理,的期望值为:
同样地,从图G中的一个中删除一条边,至多删除个三角形,那么将图G中所有的都删除一条边,至多删除个三角形,所以,
(4)
(4)式中不等式成立是因为,即:
所以可以找到一个n个顶点的图G,使得图G中没有的复制,但三角形的个数为。
同样的,利用引理3.3和引理3.4完成定理1.6的证明。
基金项目
本文得到了中国自然科学基金(11671296)和山西省优青青年学术带头人项目支持。
文章引用
崔玉君,段秀转,杨卫华. 依赖随机选择与偶轮的广义Turán数
Dependent Random Choice and Generalized Turán Numbers of Even Wheels[J]. 应用数学进展, 2020, 09(03): 444-450. https://doi.org/10.12677/AAM.2020.93054
参考文献
- 1. Erd?s, P. and Gallai, P, (1959) On Maximal Paths and Circuits of Graphs. Acta Mathematica Academiae Scientiarum Hungaricae, 10, 337-356. https://doi.org/10.1007/BF02024498
- 2. Erd?s, P. (1965) Extremal Problems in Graph Theory. In: Fiedler, M., Ed., Theory of Graphs and Its Applications, Academic Press, New York, 29-36. https://doi.org/10.1007/BF02760037
- 3. Bondy, A. and Simonovits, M. (1974) Cycles of Even Length in Graphs. Journal of Combinatorial Theory, Series B, 16, 87-105. https://doi.org/10.1016/0095-8956(74)90052-5
- 4. Keevash, P. (2011) Hypergraph Turán Problems. Surveys in Combinatorics, 392, 83-140.https://doi.org/10.1017/CBO9781139004114.004
- 5. Sidorenko, A. (1995) What We Know and What We Do Not Know about Turán Numbers. Graphs and Combinatorics, 11, 179-199. https://doi.org/10.1007/BF01929486
- 6. Alon, N. and Shikhelman, C. (2016) Many T-Copies in H-Free Graphs. Journal of Combinatorial Theory, Series B, 121, 146-172. https://doi.org/10.1016/j.jctb.2016.03.004
- 7. Bollobas, B. and Gy?ri, E. (2008) Pentagons vs. Triangles. Discrete Mathematics, 308, 4332-4336.https://doi.org/10.1016/j.disc.2007.08.016
- 8. Furedi, Z., Kostochka, A. and Luo, R. (2018) Extensions of a Theorem of Erd?s on Nonhamiltonian Graphs. Journal of Graph Theory, 89, 176-193. https://doi.org/10.1002/jgt.22246
- 9. Luo, R. (2017) The Maximum Number of Cliques in Graphs without Long Cycles. Journal of Combinatorial Theory, Series B, 128, 219-226. https://doi.org/10.1016/j.jctb.2017.08.005
- 10. Erd?s, P. (1962) On the Number of Complete Subgraphs Contained in Certain Graphs. Magyar Tudományos Akadémia Matematikai Kutató Intézetének K?zleményei, 7, 459-474.
- 11. Gy?ri, E. and Li, H. (2012) The Maximum Number of Triangles in -Free Graph. Journal of Combinatorial Theory, Series B, 102, 1061-1066. https://doi.org/10.1016/j.jctb.2012.04.001
- 12. Kostochka, A. and Rodl, V. (2001) On Graphs with Small Ramsey Numbers. Journal of Graph Theory, 37, 198-204.https://doi.org/10.1002/jgt.1014
- 13. Gowers, T. (1998) A New Proof of Szemeredi’s Theorem for Arithmetic Progressions of Length Four. Geometric and Functional Analysis, 8, 529-551. https://doi.org/10.1007/s000390050065
- 14. Sudakov, B. (2003) A Few Remarks on the Ramsey-Turan-Type Problems. Journal of Combinatorial Theory, Series B, 88, 99-106. https://doi.org/10.1016/S0095-8956(02)00038-2
- 15. Alon, N. and Spencer, J. (2008) The Probabilistic Method. 3rd Edition, Wiley, New York.https://doi.org/10.1002/9780470277331
- 16. Alon, N., Krivelevich, M. and Sudakov, B, (2003) Turan Numbers of Bipartite Graphs and Related Ramsey-Type Questions. Combinatorics, Probability and Computing, 12, 477-494. https://doi.org/10.1017/S0963548303005741