The Lovász local lemma (LLL) is a central tool in probabilistic combinatorics, providing a sufficient condition under which a finite collection of undesirable events with limited dependencies can be simultaneously avoided with positive probability. This paper offers a self-contained expository treatment of the lemma and its strengthened versions, emphasizing mathematical foundations, conceptual clarity, and applications. We begin with a pedagogically motivated proof of the LLL based entirely on unconditional probability inequalities. Particular attention is given to the symmetric form of the lemma and several subsequent strengthenings. We also discuss a variety of classical applications of both the symmetric and asymmetric forms of the LLL in combinatorics and graph theory, including bounds for the edge-disjoint paths problem, satisfiability of Boolean formulas in conjunctive normal form, lower bounds on diagonal and off-diagonal Ramsey numbers, hypergraph coloring results, structural properties of directed graphs, and acyclic graph colorings. Additional observations and refinements are provided throughout. We also introduce the algorithmic framework of Moser and Tardos, highlighting its constructive counterpart to the LLL, together with an introduction to the entropy-compression principle. The lopsided LLL, a refinement of the LLL, is presented along with an application to the Latin transversal problem. We further discuss the cluster-expansion lemma and its relation to the LLL, and present an alternative treatment of the Latin transversal problem from the cluster-expansion perspective that yields an improved result. The exposition concludes with a high-level overview of the iterated LLL, also known as the semi-random method.
Citation: Igal Sason. The Lovász local lemma: foundations and applications[J]. AIMS Mathematics, 2026, 11(7): 19659-19715. doi: 10.3934/math.2026798
The Lovász local lemma (LLL) is a central tool in probabilistic combinatorics, providing a sufficient condition under which a finite collection of undesirable events with limited dependencies can be simultaneously avoided with positive probability. This paper offers a self-contained expository treatment of the lemma and its strengthened versions, emphasizing mathematical foundations, conceptual clarity, and applications. We begin with a pedagogically motivated proof of the LLL based entirely on unconditional probability inequalities. Particular attention is given to the symmetric form of the lemma and several subsequent strengthenings. We also discuss a variety of classical applications of both the symmetric and asymmetric forms of the LLL in combinatorics and graph theory, including bounds for the edge-disjoint paths problem, satisfiability of Boolean formulas in conjunctive normal form, lower bounds on diagonal and off-diagonal Ramsey numbers, hypergraph coloring results, structural properties of directed graphs, and acyclic graph colorings. Additional observations and refinements are provided throughout. We also introduce the algorithmic framework of Moser and Tardos, highlighting its constructive counterpart to the LLL, together with an introduction to the entropy-compression principle. The lopsided LLL, a refinement of the LLL, is presented along with an application to the Latin transversal problem. We further discuss the cluster-expansion lemma and its relation to the LLL, and present an alternative treatment of the Latin transversal problem from the cluster-expansion perspective that yields an improved result. The exposition concludes with a high-level overview of the iterated LLL, also known as the semi-random method.
| [1] | P. Erdős, L. Lovász, Problems and results on $3$-chromatic hypergraphs and some related questions, Colloq. Math. Soc. János Bolyai, North-Holland, 1975, 609–627. |
| [2] | N. Alon, J. H. Spencer, The probabilistic method, 4 Eds., Wiley, 2016. |
| [3] | M. Mitzenmacher, E. Upfal, Probability and computing: randomization and probabilistic techniques in algorithms and data analysis, 2 Eds., Cambridge University Press, 2017. |
| [4] | P. Brémaud, Discrete probability models and methods: probability on graphs and trees, Markov chains and random fields, entropy and coding, Springer, 2017. https://doi.org/10.1007/978-3-319-43476-6 |
| [5] | B. Bollobás, Random graphs, 2 Eds., Cambridge University Press, 2001. https://doi.org/10.1017/CBO9780511814068 |
| [6] | M. Molloy, The probabilistic method, In: M. Habib, C. McDiarmid, J. Ramirez-Alfonsin, B. Reed, Probabilistic methods for algorithmic discrete mathematics, Springer, 1998, 1–35. https://doi.org/10.1007/978-3-662-12788-9_1 |
| [7] | M. Molloy, B. Reed, Graph colouring and the probabilistic method, Springer, 2002. https://doi.org/10.1007/978-3-642-04016-0 |
| [8] | J. H. van Lint, R. M. Wilson, A course in combinatorics, 2 Eds., Cambridge University Press, 2001. https://doi.org/10.1017/CBO9780511987045 |
| [9] | S. Jukna, Extremal combinatorics with applications in computer science, 2 Eds., Springer, 2011. https://doi.org/10.1007/978-3-642-17364-6 |
| [10] | D. E. Knuth, The art of computer programming, Volum 4B, the: combinatorial algorithms, Addison-Wesley Professional, 2022. |
| [11] | N. Alon, C. McDiarmid, M. Molloy, Edge-disjoint cycles in regular directed graphs, J. Graph Theory, 22 (1996), 231–237. |
| [12] |
A. Z. Broder, A. M. Frieze, E. Upfal, Existence and construction of edge-disjoint paths on expander graphs, SIAM J. Comput., 23 (1994), 976–989. https://doi.org/10.1137/S0097539792232021 doi: 10.1137/S0097539792232021
|
| [13] |
Y. J. Chang, Q. He, W. Li, S. Pettie, J. Uitto, Distributed edge coloring and a special case of the constructive Lovász local lemma, ACM Trans. Algorithms, 16 (2020), 8. https://doi.org/10.1145/3365004 doi: 10.1145/3365004
|
| [14] |
J. Spencer, Ramsey's theorem–a new lower bound, J. Combin. Theory Ser. A, 18 (1975), 108–115. https://doi.org/10.1016/0097-3165(75)90071-0 doi: 10.1016/0097-3165(75)90071-0
|
| [15] |
J. Spencer, Asymptotic lower bounds for Ramsey functions, Discrete Math., 20 (1977), 69–76. https://doi.org/10.1016/0012-365X(77)90044-9 doi: 10.1016/0012-365X(77)90044-9
|
| [16] | Y. Li, Q. Lin, Elementary methods of graph Ramsey theory, Springer, 2022. https://doi.org/10.1007/978-3-031-12762-5 |
| [17] |
N. Alon, N. Linial, Cycles of length $0 \pmod{k}$ in directed graphs, J. Combin. Theory Ser. B, 47 (1989), 114–119. https://doi.org/10.1016/0095-8956(89)90071-3 doi: 10.1016/0095-8956(89)90071-3
|
| [18] |
N. Alon, Independent sets in regular graphs and sum-free subsets of finite groups, Israel J. Math., 73 (1991), 247–256. https://doi.org/10.1007/BF02772952 doi: 10.1007/BF02772952
|
| [19] | N. Alon, C. McDiarmid, B. Reed, Acyclic coloring of graphs, Random Structures Algorithms, 2 (1991), 277–288. https://doi.org/10.1002/rsa.3240020303 |
| [20] |
A. Kırtışoğlu, L. Özkahya, Coloring of graphs avoiding bicolored paths of a fixed length, Graphs Combin., 40 (2024), 11. https://doi.org/10.1007/s00373-023-02739-4 doi: 10.1007/s00373-023-02739-4
|
| [21] | K. Kolipaka, M. Szegedy, Y. Xu, A sharper local lemma with improved applications, In: A. Gupta, K. Jansen, J. Rolim, R. Servedio, Approximation, randomization, and combinatorial optimization. Algorithms and techniques, Springer, 2012, 603–614, https://doi.org/10.1007/978-3-642-32512-0_51 |
| [22] |
D. Deng, D. R. Stinson, R. Wei, The Lovász local lemma and its applications to some combinatorial arrays, Des. Codes Crypt., 32 (2004), 121–134, https://doi.org/10.1023/B:DESI.0000029217.97956.26 doi: 10.1023/B:DESI.0000029217.97956.26
|
| [23] |
Z. Füredi, J. Kahn, On the dimensions of ordered sets of bounded degree, Order, 3 (1986), 15–20. https://doi.org/10.1007/BF00403406 doi: 10.1007/BF00403406
|
| [24] | W. T. Trotter, Applications of the probabilistic method to partially ordered sets, In: R. L. Graham, J. Nešetřil, S. Butler, The mathematics of Paul Erdős II, Springer, 2013, 313–329. https://doi.org/10.1007/978-1-4614-7254-4_20 |
| [25] |
J. Kratochvíl, P. Savický, Z. Tuza, One more occurrence of variables makes satisfiability jump from trivial to NP-complete, SIAM J. Comput., 22 (1993), 203–210. https://doi.org/10.1137/0222015 doi: 10.1137/0222015
|
| [26] |
H. Gebauer, Disproof of the neighborhood conjecture with implications to SAT, Combinatorica, 32 (2012), 573–587. https://doi.org/10.1007/s00493-012-2679-y doi: 10.1007/s00493-012-2679-y
|
| [27] |
H. Gebauer, T. Szabó, G. Tardos, The local lemma is asymptotically tight for SAT, J. ACM, 63 (2016), 43. https://doi.org/10.1145/2975386 doi: 10.1145/2975386
|
| [28] |
B. Haeupler, B. Saha, A. Srinivasan, New constructive aspects of the Lovász local lemma, J. ACM, 58 (2011), 28. https://doi.org/10.1145/2049697.2049702 doi: 10.1145/2049697.2049702
|
| [29] | H. Gebauer, R. A. Moser, D. Scheder, E. Welzl, The Lovász local lemma and satisfiability, In: S. Albers, H. Alt, S. Näher, Efficient algorithms, Springer, 2009, 30–54. https://doi.org/10.1007/978-3-642-03456-5_3 |
| [30] |
A. Moitra, Approximate counting, the Lovász local lemma, and inference in graphical models, J. ACM, 66 (2019), 10. https://doi.org/10.1145/3268930 doi: 10.1145/3268930
|
| [31] | J. Livieratos, Constraint satisfaction problems: probabilistic approach and applications to social choice theory, Ph.D. Thesis, Department of Mathematics, National and Kapodistrian University of Athens, 2020. |
| [32] | Z. Chen, A. Lonkar, C. Wang, K. Yang, Y. Yin, Counting random $k$-SAT near the satisfiability threshold, Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025, 867–878. https://doi.org/10.1145/3717823.3718163 |
| [33] |
A. Ambainis, J. Kempe, O. Sattath, A quantum Lovász local lemma, J. ACM, 59 (2012), 24. https://doi.org/10.1145/2371656.2371659 doi: 10.1145/2371656.2371659
|
| [34] | L. J. Schulman, Deterministic coding for interactive communication, Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993, 747–756. https://doi.org/10.1145/167088.167279 |
| [35] |
N. Alon, M. Braverman, K. Efremenko, R. Gelles, B. Haeupler, Reliable communication over highly connected noisy networks, Distributed Comput., 32 (2016), 505–515. https://doi.org/10.1007/s00446-017-0303-5 doi: 10.1007/s00446-017-0303-5
|
| [36] |
R. Gelles, Coding for interactive communication: a survey, Found. Trends Theor. Comput. Sci., 13 (2017), 1–157. https://doi.org/10.1561/0400000079 doi: 10.1561/0400000079
|
| [37] |
F. T. Leighton, B. M. Maggs, S. B. Rao, Packet routing and job-shop scheduling in $ O(\mathrm{congestion}+\mathrm{dilation}) $ steps, Combinatorica, 14 (1994), 167–186. https://doi.org/10.1007/BF01215349 doi: 10.1007/BF01215349
|
| [38] |
F. T. Leighton, B. M. Maggs, A. Richa, Fast algorithms for finding $ O(\mathrm{congestion}+\mathrm{dilation}) $ packet routing schedules, Combinatorica, 19 (1999), 375–401. https://doi.org/10.1007/s004930050061 doi: 10.1007/s004930050061
|
| [39] | K. Cheng, B. Haeupler, X. Li, A. Shahrasbi, K. Wu, Synchronization strings: highly efficient deterministic constructions over small alphabets, Proceedings of the 2019 Annual ACM-SIAM Symposium on Discrete Algorithms, 2019, 2185–2204. https://doi.org/10.1137/1.9781611975482.132 |
| [40] |
P. Keevash, C. Y. Ku, A random construction for permutation codes and the covering radius, Des. Codes Cryptography, 41 (2006), 79–86. https://doi.org/10.1007/s10623-006-0017-3 doi: 10.1007/s10623-006-0017-3
|
| [41] |
R. Con, A. Shpilka, I. Tamo, Reed Solomon codes against adversarial insertions and deletions, IEEE Trans. Inf. Theory, 69 (2023), 2991–3000. https://doi.org/10.1109/TIT.2023.3237711 doi: 10.1109/TIT.2023.3237711
|
| [42] |
R. Con, A. Shpilka, I. Tamo, Corrections to "Reed Solomon codes against adversarial insertions and deletions", IEEE Trans. Inf. Theory, 71 (2025), 3250–3251. https://doi.org/10.1109/TIT.2025.3538114 doi: 10.1109/TIT.2025.3538114
|
| [43] | L. Huang, Bounds and constructions of high-memory spatially-coupled codes, 2025 IEEE Information Theory Workshop (ITW), 2025. https://doi.org/10.1109/ITW62417.2025.11240539 |
| [44] | L. Huang, Counting and entropy bounds for structure-avoiding spatially-coupled LDPC constructions, 2026 IEEE International Symposium on Information Theory (ISIT), 2026. https://doi.org/10.48550/arXiv.2601.09674 |
| [45] | C. Aranda, M. Fernández, Improved existence bounds on IPP codes using the Clique Lovász local lemma, 2017 IEEE International Symposium on Information Theory (ISIT), 2017, 3170–3174. https://doi.org/10.1109/ISIT.2017.8007112 |
| [46] | M. Fernández, G. Kabatiansky, S. Martín, C. Tavernier, A constructive approach to multimedia codes with complete traceability resistant to $\delta$-noise, 2023 IEEE Information Theory Workshop (ITW), 2023, 254–259. https://doi.org/10.1109/ITW55543.2023.10161685 |
| [47] |
M. Fernández, J. Livieratos, S. Martín, Bounds and constructions of parent identifying schemes via the algorithmic version of the Lovász local lemma, IEEE Trans. Inf. Theory, 69 (2023), 7049–7069. https://doi.org/10.1109/TIT.2023.3282452 doi: 10.1109/TIT.2023.3282452
|
| [48] |
M. Fernández, J. Livieratos, S. Martín, Combinatorial constructions of separating codes, J. Complexity, 86 (2025), 101906. https://doi.org/10.1016/j.jco.2024.101906 doi: 10.1016/j.jco.2024.101906
|
| [49] |
M. Fernández, F. J. Martínez-Zaldívar, V. M. García-Mollá, M. A. Simarro, J. Livieratos, A. González, GPU generation of binary $2$-separating codes, J. Supercomput., 82 (2026), 149, https://doi.org/10.1007/s11227-026-08280-4 doi: 10.1007/s11227-026-08280-4
|
| [50] |
H. G. Yeh, $d$-disjunct matrices: bounds and Lovász local lemma, Discrete Math., 253 (2002), 97–107. https://doi.org/10.1016/S0012-365X(01)00452-6 doi: 10.1016/S0012-365X(01)00452-6
|
| [51] |
M. Dalai, S. D. Fiore, A. A. Rescigno, U. Vaccaro, An efficient algorithm for group testing with runlength constraints, Discrete Appl. Math., 360 (2025), 181–187. https://doi.org/10.1016/j.dam.2024.09.001 doi: 10.1016/j.dam.2024.09.001
|
| [52] |
A. A. Rescigno, U. Vaccaro, Bounds and algorithms for generalized superimposed codes, Inf. Process. Lett., 182 (2023), 106365. https://doi.org/10.1016/j.ipl.2023.106365 doi: 10.1016/j.ipl.2023.106365
|
| [53] |
A. A. Rescigno, U. Vaccaro, Improved algorithms and bounds for list union-free families, IEEE Trans. Inf. Theory, 70 (2024), 2456–2463. https://doi.org/10.1109/TIT.2023.3316435 doi: 10.1109/TIT.2023.3316435
|
| [54] |
L. Gargano, A. A. Rescigno, U. Vaccaro, Low-weight superimposed codes and related combinatorial structures: bounds and applications, Theor. Comput. Sci., 806 (2020), 655–672. https://doi.org/10.1016/j.tcs.2019.10.032 doi: 10.1016/j.tcs.2019.10.032
|
| [55] |
A. D. Scott, A. D. Sokal, The repulsive lattice gas, the independent-set polynomial, and the Lovász local lemma, J. Stat. Phys., 118 (2005), 1151–1261. https://doi.org/10.1007/s10955-004-2055-4 doi: 10.1007/s10955-004-2055-4
|
| [56] |
A. D. Scott, A. D. Sokal, On dependency graphs and the lattice gas, Combin. Probab. Comput., 15 (2006), 253–279. https://doi.org/10.1017/S0963548305007182 doi: 10.1017/S0963548305007182
|
| [57] |
R. Bissacot, R. Fernández, A. Procacci, B. Scoppola, An improvement of the Lovász local lemma via cluster expansion, Combin. Probab. Comput., 20 (2011), 709–719. https://doi.org/10.1017/S0963548311000253 doi: 10.1017/S0963548311000253
|
| [58] | M. Szegedy, The Lovász local lemma–a survey, In: A. A. Bulatov, A. M. Shur, Computer science – theory and applications, Springer, 2013. https://doi.org/10.1007/978-3-642-38536-0_1 |
| [59] |
A. Faragó, A meeting point of probability, graphs, and algorithms: the Lovász local lemma and related results–a survey, Algorithms, 14 (2021), 355. https://doi.org/10.3390/a14120355 doi: 10.3390/a14120355
|
| [60] | M. Grötschel, J. Nešetřil, The mathematics of László Lovász, In: H. Holden, R. Piene, The Abel prize 2018–2022, Springer, 2024, 535–594. https://doi.org/10.1007/978-3-031-33973-8_19 |
| [61] | J. Beck, Games, randomness, and algorithms, In: R. L. Graham, J. Nešetřil, S. Butler, The mathematics of Paul Erdős I, Springer, 2013, 311–342. https://doi.org/10.1007/978-1-4614-7258-2_21 |
| [62] | J. Kahn, On some hypergraph problems of Paul Erdős and the asymptotics of matchings, Covers and Colorings, In: R. L. Graham, J. Nešetřil, S. Butler, The mathematics of Paul Erdős I, Springer, 2013, 343–369. https://doi.org/10.1007/978-1-4614-7258-2_22 |
| [63] |
J. Beck, An algorithmic approach to the Lovász local lemma. I, Random Structures Algorithms, 2 (1991), 343–365. https://doi.org/10.1002/rsa.3240020402 doi: 10.1002/rsa.3240020402
|
| [64] |
N. Alon, A parallel algorithmic version of the local lemma, Random Structures Algorithms, 2 (1991), 367–378. https://doi.org/10.1002/rsa.3240020403 doi: 10.1002/rsa.3240020403
|
| [65] |
R. A. Moser, G. Tardos, A constructive proof of the general Lovász local lemma, J. ACM, 57 (2010), 11. https://doi.org/10.1145/1667053.1667060 doi: 10.1145/1667053.1667060
|
| [66] | R. A. Moser, A constructive proof of the Lovász local lemma, Proceedings of the forty-first annual ACM symposium on Theory of computing, 2009, 343–350. https://doi.org/10.1145/1536414.1536462 |
| [67] | K. B. R. Kolipaka, M. Szegedy, Moser and Tardos meet Lovász, Proceedings of the forty-third annual ACM symposium on Theory of computing, 2011, 235–244. https://doi.org/10.1145/1993636.1993669 |
| [68] | J. B. Shearer, On a problem of Spencer, Combinatorica, 5 (1985), 241–245. https://doi.org/10.1007/BF02579368 |
| [69] | K. He, Q. Li, X. Sun, Moser–Tardos algorithm: beyond Shearer's bound, Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2023. https://doi.org/10.1137/1.9781611977554.ch129 |
| [70] |
K. He, L. Li, X. Liu, Y. Wang, M. Xia, Variable version Lovász local lemma: a tale of two boundaries, Inf. Comput., 308 (2026), 105386. https://doi.org/10.1016/j.ic.2025.105386 doi: 10.1016/j.ic.2025.105386
|
| [71] | T. Tao, Moser's entropy compression argument, unpublished notes, 2009. Available from: https://page.math.tu-berlin.de/felsner/SemWS17-18/Tao-moser-entropy-compression.pdf. |
| [72] |
L. Esperet, A. Parreau, Acyclic edge-coloring using entropy compression, Eur. J. Combin., 34 (2013), 1019–1027. https://doi.org/10.1016/j.ejc.2013.02.007 doi: 10.1016/j.ejc.2013.02.007
|
| [73] |
V. Dujmović, G. Joret, J. Kozik, D. R. Wood, Nonrepetitive colouring via entropy compression, Combinatorica, 36 (2016), 661–686. https://doi.org/10.1007/s00493-015-3070-6 doi: 10.1007/s00493-015-3070-6
|
| [74] |
W. Pegden, An extension of the Moser–Tardos algorithmic local lemma, SIAM J. Discrete Math., 28 (2014), 911–917. https://doi.org/10.1137/110828290 doi: 10.1137/110828290
|
| [75] |
N. J. A. Harvey, J. Vondrák, An algorithmic proof of the Lovász local lemma via resampling oracles, SIAM J. Comput., 49 (2020), 394–428. https://doi.org/10.1137/18M1167176 doi: 10.1137/18M1167176
|
| [76] |
K. Chandrasekaran, N. Goyal, B. Haeupler, Deterministic algorithms for the Lovász local lemma, SIAM J. Comput., 42 (2013), 2132–2155. https://doi.org/10.1137/100799642 doi: 10.1137/100799642
|
| [77] |
D. G. Harris, Deterministic algorithms for the Lovász local lemma: simpler, more general, and more parallel, Random Structures Algorithms, 63 (2023), 716–752. https://doi.org/10.1002/rsa.21152 doi: 10.1002/rsa.21152
|
| [78] |
P. Erdős, J. Spencer, Lopsided Lovász local lemma and Latin transversals, Discrete Appl. Math., 30 (1991), 151–154. https://doi.org/10.1016/0166-218X(91)90040-4 doi: 10.1016/0166-218X(91)90040-4
|
| [79] | J. Vondrák, Math 233: nonconstructive methods in combinatorics, Stanford University, 2016. Available from: https://theory.stanford.edu/jvondrak/MATH233-2016/Math233-lec02.pdf. |
| [80] |
R. Mathon, Lower bounds for Ramsey numbers and association schemes, J. Combin. Theory Ser. B, 42 (1987), 122–127. https://doi.org/10.1016/0095-8956(87)90067-0 doi: 10.1016/0095-8956(87)90067-0
|
| [81] | S. P. Radziszowski, Small Ramsey numbers, Electron. J. Combin., 2026. https://doi.org/10.37236/21 |
| [82] | J. Ma, W. Shen, S. Xie, An exponential improvement for Ramsey lower bounds, Invent. Math., 2026. https://doi.org/10.1007/s00222-026-01421-9 |
| [83] | Z. Hunter, A. Milojević, B. Sudakov, Gaussian random graphs and Ramsey numbers, arXiv, 2025. https://doi.org/10.48550/arXiv.2512.17718 |
| [84] | Q. Lin, L. Niu, Sharper Ramsey lower bounds from refined Gaussian estimates, arXiv, 2026. https://doi.org/10.48550/arXiv.2605.25843 |
| [85] | D. Bradač, Off-diagonal Ramsey numbers, arXiv, 2026. https://doi.org/10.48550/arXiv.2605.28793 |
| [86] | R. L. Graham, D. E. Knuth, O. Patashnik, Concrete mathematics: a foundation for computer science, 2 Eds., Addison–Wesley, 1989. Available form: https://www-cs-faculty.stanford.edu/knuth/gkp.html. |
| [87] |
B. Grünbaum, Acyclic colorings of planar graphs, Israel J. Math., 14 (1973), 390–408. https://doi.org/10.1007/BF02764716 doi: 10.1007/BF02764716
|
| [88] |
O. V. Borodin, On acyclic colorings of planar graphs, Discrete Math., 25 (1979), 211–236. https://doi.org/10.1016/0012-365X(79)90077-3 doi: 10.1016/0012-365X(79)90077-3
|
| [89] | J. Nešetřil, P. O. de Mendez, Sparsity: graphs, structures, and algorithms, Springer, 2012. https://doi.org/10.1007/978-3-642-27875-4 |
| [90] | T. M. Cover, J. A. Thomas, Elements of information theory, 2 Eds., John Wiley & Sons, Inc., 2006. https://doi.org/10.1002/047174882X |
| [91] | I. M. Wanless, Transversals in Latin squares: a survey, In: R. Chapman, Surveys in combinatorics 2011, Cambridge University Press, 2011, 403–437. https://doi.org/10.1017/CBO9781139004114.010 |
| [92] |
J. Böttcher, Y. Kohayakawa, A. Procacci, Properly coloured copies and rainbow copies of large graphs with small maximum degree, Random Structures Algorithms, 40 (2012), 425–436. https://doi.org/10.1002/rsa.20383 doi: 10.1002/rsa.20383
|
| [93] |
S. Ndreca, A. Procacci, B. Scoppola, Improved bounds on coloring of graphs, Eur. J. Combin., 33 (2012), 592–609. https://doi.org/10.1016/j.ejc.2011.12.002 doi: 10.1016/j.ejc.2011.12.002
|
| [94] | D. G. Harris, A. Srinivasan, A constructive algorithm for the Lovász local lemma on permutations, Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2014), 2014, 907–925. https://doi.org/10.1137/1.9781611973402.68 |
| [95] |
V. Rödl, On a packing and covering problem, Eur. J. Combin., 6 (1985), 69–78. https://doi.org/10.1016/S0195-6698(85)80023-8 doi: 10.1016/S0195-6698(85)80023-8
|
| [96] |
M. Ajtai, J. Komlós, J. Pintz, J. Spencer, E. Szemerédi, Extremal uncrowded hypergraphs, J. Combin. Theory Ser. A, 32 (1982), 321–335. https://doi.org/10.1016/0097-3165(82)90049-8 doi: 10.1016/0097-3165(82)90049-8
|
| [97] | A. Johansson, Asymptotic choice number for triangle-free graphs, Technical Report, 1996, 91–95. |
| [98] |
M. Molloy, The list chromatic number of graphs with small clique number, J. Combin. Theory Ser. B, 134 (2019), 264–284. https://doi.org/10.1016/j.jctb.2018.06.007 doi: 10.1016/j.jctb.2018.06.007
|
| [99] | S. Boucheron, G. Lugosi, P. Massart, Concentration inequalities: a nonasymptotic theory of independence, Oxford University Press, 2013. https://doi.org/10.1093/acprof: oso/9780199535255.001.0001 |
| [100] |
M. Raginsky, I. Sason, Concentration of measure inequalities in information theory, communications, and coding, Found. Trends Commun. Inf. Theory, 10 (2013), 1–247. https://doi.org/10.1561/0100000064 doi: 10.1561/0100000064
|
| [101] |
A. Bernshteyn, Measurable versions of the Lovász local lemma and measurable graph colorings, Adv. Math., 353 (2019), 153–223. https://doi.org/10.1016/j.aim.2019.06.031 doi: 10.1016/j.aim.2019.06.031
|
Igal Sason. The Lovász local lemma: foundations and applications[J]. AIMS Mathematics, 2026, 11(7): 19659-19715. doi: 10.3934/math.2026798
DownLoad: