Bollobás lemma: analysis, application, algorithm

Document Type : Research Paper

Authors

1 Department of Applied Mathematics and Computer Science, University of Isfahan,

2 Linköping University, Department of Computer and Information Science

Abstract

Many of the theorems that were developed by researchers in the 1960s and 1970s in combinations and graph theory as mathematical theorems, are still used today in designing algorithms and solving new problems. The purpose of this article is to show that useful things happened in the past that we should not forget and use them with a creative eye. Bollobás Lemma \cite{bollobas}, which was proposed in the 1970s, is a well-known problem in combinatorics. In this problem, we have a family of sets $A_1, A_2,\ldots,A_m$ each with size a and another family of sets $B_1, B_2,\ldots,B_m$ each with size b. The goal is to find the maximum size m, the number of sets so that for each index i we have $A_i \cap B_i = \emptyset $ and also $A_i \cap B_j \neq \emptyset$ where $(i \neq j).$ The Bollobás lemma expresses the upper bound for the maximum number of these sets as $m\leq \binom{a+b}{b}$. In this paper, after stating the versions of the lemma and the existing proof for this lemma, we present another probability-based proof for the Bollobás Lemma, and then with a different look at this combinatorial problem, we investigate the interesting applications of this lemma in graph theory problems and parameterized algorithms.

Keywords

References

[1] B. Bollobás, On generalized graphs, Acta Math. Acad. Sci. Hungar., 16 (1965) 447–452.
[2] B. Bollobás, The art of mathematics. Coffee time in Memphis, Cambridge University Press, New York, 2006.
[3] C. Bey, Polynomial LYM inequalities, Combinatorica, 25 no. 1 (2005) 19–38.
[4] F. V. Fomin and P. Kaski, Exact exponential algorithms, Communications of the ACM, 56 no. 3 (2013) 80–88.
[5] L. Lovász, Flats in matroids and geometric graphs, Combinatorial surveys (Proc. Sixth British Combinatorial Conf., Academic Press, London-New York, (1977) 45–86.
[6] M. Naor, L. J. Schulman and A. Srinivasan, Splitters and near-optimal derandomization, InProceedings of IEEE 36th Annual Foundations of Computer Science, (1995) 182–191.
[7] M. Cygan, F. V. Fomin, L. Kowalik ,D. Lokshtanov, D. Marx, M. Pilipczuk, M. Pilipczuk and S. Saurabh, Parameterized algorithms, Springer (2015).
Mathematics and Society
Volume 9, Issue 2 - Serial Number 2
September 2024
Pages 1-18

Files

History

  • Receive Date: 22 September 2023
  • Revise Date: 06 January 2024
  • Accept Date: 23 January 2024
  • Publish Date: 22 August 2024

Share

How to cite

Statistics