The maximum sum of the sizes of cross $ t $-intersecting separated families

Erica L. L. Liu; Erica L. L. Liu

doi:10.3934/math.20231581

AIMS Mathematics

2023, Volume 8, Issue 12: 30910-30921. doi: 10.3934/math.20231581

Previous Article Next Article

Research article

The maximum sum of the sizes of cross $ t $-intersecting separated families

Erica L. L. Liu ^,

School of Science, Tianjin University of Technology and Education, Tianjin 300222, China

Received: 14 August 2023 Revised: 04 November 2023 Accepted: 09 November 2023 Published: 17 November 2023
MSC : 05C35, 05D05

For a set $ X $ and an integer $ r\geq 0 $, let $ {X \choose \leq r} $ denote the family of subsets of $ X $ that have at most $ r $ elements. Two families $ \mathcal{A}\subset {X\choose \leq r} $ and $ \mathcal{B}\subset {X\choose \leq s} $ are cross $ t $-intersecting if $ |A\cap B|\geq t $ for all $ A\in\mathcal{A}, B\in\mathcal{B} $. In this paper, we considered the measures of cross $ t $-intersecting families $ \mathcal{A}\subset {X\choose \leq r} $, $ \mathcal{B}\subset {X\choose \leq s} $, then we used this result to obtain the maximum sum of sizes of cross $ t $-intersecting separated families.
- finite set,
- separated families,
- cross intersecting,
- generating set method,
- the shifting method
Citation: Erica L. L. Liu. The maximum sum of the sizes of cross $ t $-intersecting separated families[J]. AIMS Mathematics, 2023, 8(12): 30910-30921. doi: 10.3934/math.20231581

Related Papers:

Abstract

For a set $ X $ and an integer $ r\geq 0 $, let $ {X \choose \leq r} $ denote the family of subsets of $ X $ that have at most $ r $ elements. Two families $ \mathcal{A}\subset {X\choose \leq r} $ and $ \mathcal{B}\subset {X\choose \leq s} $ are cross $ t $-intersecting if $ |A\cap B|\geq t $ for all $ A\in\mathcal{A}, B\in\mathcal{B} $. In this paper, we considered the measures of cross $ t $-intersecting families $ \mathcal{A}\subset {X\choose \leq r} $, $ \mathcal{B}\subset {X\choose \leq s} $, then we used this result to obtain the maximum sum of sizes of cross $ t $-intersecting separated families.

References

[1]	P. Erdös, C. Ko, R. Rado, Intersection theorems for systems of finite sets, Q. J. Math., 12 (1961), 313–320. https://doi.org/10.1093/qmath/12.1.313 doi: 10.1093/qmath/12.1.313
[2]	P. Frankl, The Erdös-Ko-Rado theorem is true for $n = ckt$, Combinatorics, 1 (1978), 365–375.
[3]	R. M. Wilson, The exact bound in the Erdös-Ko-Rado theorem, Combinatorica, 4 (1984), 247–257. https://doi.org/10.1007/BF02579226 doi: 10.1007/BF02579226
[4]	A. J. W. Hilton, E. C. Milner, Some intersection theorems for systems of finite sets, Q. J. Math., 18 (1967), 369–384. https://doi.org/10.1093/qmath/18.1.369 doi: 10.1093/qmath/18.1.369
[5]	P. Frankl, N. Tokushige, Some best possible inequalities concerning cross-intersecting families, J. Comb. Theory, 61 (1992), 87–97. https://doi.org/10.1016/0097-3165(92)90054-X doi: 10.1016/0097-3165(92)90054-X
[6]	J. Wang, H. Zhang, Nontrivial independent sets of bipartite graphs and cross-intersecting families, J. Comb. Theory, 120 (2013), 129–141. https://doi.org/10.1016/j.jcta.2012.07.005 doi: 10.1016/j.jcta.2012.07.005
[7]	P. Borg, C. Feghali, The maximum sum of sizes of cross-intersecting families of subsets of a set, Discrete Math., 345 (2022), 112981. https://doi.org/10.1016/j.disc.2022.112981 doi: 10.1016/j.disc.2022.112981
[8]	I. Dinur, S. Safra, On the hardness of approximating minimum vertex cover, Ann. Math., 162 (2005), 439–485.
[9]	Y. Filmus, The weighted complete intersection theorem, J. Comb. Theory, 151 (2017), 84–101. https://doi.org/10.1016/j.jcta.2017.04.008 doi: 10.1016/j.jcta.2017.04.008
[10]	P. Gupta, Y. Mogge, S. Piga, B. Schülke, $r$-Cross $t$-intersecting families via necessary intersection points, Bull. London Math. Soc., 55 (2023), 1447–1458. https://doi.org/10.1112/blms.12803 doi: 10.1112/blms.12803
[11]	S. J. Lee, M. Siggers, N. Tokushige, AK-type stability theorems on cross $t$-intersecting families, Eur. J. Combin., 82 (2019), 102993. https://doi.org/10.1016/j.ejc.2019.07.004 doi: 10.1016/j.ejc.2019.07.004
[12]	P. Frankl, The shifting technique in extremal set theory, Surv. Comb., 123 (1987), 81–110.
[13]	R. Ahlswede, L. H. Khachatrian, The complete intersection theorem for systems of finite sets, Eur. J. Combin., 18 (1997), 125–136. https://doi.org/10.1006/eujc.1995.0092 doi: 10.1006/eujc.1995.0092
[14]	P. Frankl, E. L. L Liu, J. Wang, Z. Yang, Non-trivial $t$-intersecting separated families, Discret. Appl. Math., 342 (2024), 124–137. https://doi.org/10.1016/j.dam.2023.09.011 doi: 10.1016/j.dam.2023.09.011
[15]	P. Frankl, Z. Füredi, The Erdös-Ko-Rado theorem for integer sequences, SIAM J. Algebraic Discrete Methods, 1 (1980), 376–381. https://doi.org/10.1137/0601044 doi: 10.1137/0601044

Reader Comments

Your name:*

Email:*
© 2023 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)