×

Combinatorics. Abstracts from the workshop held January 1–7, 2023. (English) Zbl 1525.00023

Summary: Combinatorics is an area of mathematics primarily concerned with counting and studying properties of discrete objects such as graphs, set systems, partial orders, polyhedra, etc. Combinatorial problems naturally arise in many areas of mathematics, such as algebra, geometry, probability theory, and topology, and in theoretical computer science. Historically, such questions were often studied using ad hoc arguments. However, over the last few decades, the development of general and powerful methods have elevated combinatorics to a thriving branch of mathematics with many connections to other subjects. The workshop brought together the established leading experts and the brightest young talents from different parts of this very broad area in order to discuss the most exciting recent developments, current themes and trends, and the most promising new directions for future research.

MSC:

00B05 Collections of abstracts of lectures
00B25 Proceedings of conferences of miscellaneous specific interest
05-06 Proceedings, conferences, collections, etc. pertaining to combinatorics
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] P. D. Seymour and R. Thomas. Call routing and the ratcatcher, Combinatorica 14 (1994): 217-241. · Zbl 0799.05057
[2] M. Gromov, Singularities, expanders and topology of maps. Part 2: From combinatorics to topology via algebraic isoperimetry, Geometric and Functional Analysis 20.2 (2010): 416-526. · Zbl 1251.05039
[3] D. Eppstein, L. Merker, S Norin, M. T. Seweryn, D. R. Wood. Three-dimensional graph products with unbounded stack-number, Discrete and Computational Geometry, to appear. (2022) arXiv preprint arXiv:2202.05327.
[4] S. A. Burr and V. Rosta: On the Ramsey multiplicities of graphs-problems and recent results, J. Graph Theory 4 (1980), 347-361. · Zbl 0455.05046
[5] D. Conlon, J. Fox and B. Sudakov: Recent developments in graph Ramsey theory, in: Sur-veys in combinatorics 2015, London Math. Soc. Lecture Note Ser., volume 424 (2015), 49-118. · Zbl 1352.05123
[6] P. Erdős: On the number of complete subgraphs contained in certain graphs, Magyar Tud. Akad. Mat. Kutató Int. Közl. 7 (1962), 459-464. · Zbl 0116.01202
[7] P. Erdős and M. Simonovits: Supersaturated graphs and hypergraphs, Combinatorica 3 (1983), 181-192. · Zbl 0529.05027
[8] A. W. Goodman: On sets of acquaintances and strangers at any party, Amer. Math. Monthly 66 (1959), 778-783. · Zbl 0092.01305
[9] A. Grzesik, J. Lee, B. Lidický and J. Volec: On tripartite common graphs, to appear in Combin. Probab. Comput. · Zbl 1510.05140
[10] H. Hatami, J. Hladký, D. Kráľ, S. Norine and A. Razborov: Non-three-colourable common graphs exist, Combin. Probab. Comput. 21 (2012), 734-742. · Zbl 1248.05090
[11] C. Jagger, P.Šťovíček and A. Thomason: Multiplicities of subgraphs, Combinatorica 16 (1996), 123-141. · Zbl 0846.05061
[12] S. Ko and J. Lee: Common graphs with arbitrary connectivity and chromatic number, preprint arXiv:2207.09427. · Zbl 1519.05081
[13] F. P. Ramsey: On a problem of formal logic, Proceedings of the London Mathematical Society 2 (1930), 264-286. · JFM 55.0032.04
[14] A. Sidorenko: A correlation inequality for bipartite graphs, Graphs Combin. 9 (1993), 201-204. · Zbl 0777.05096
[15] A. F. Sidorenko: Extremal problems in graph theory and functional-analytic inequalities, Proceedings of the All-Union seminar on discrete mathematics and its applications (Russian) (1986), 99-105.
[16] A. F. Sidorenko: Cycles in graphs and functional inequalities, Mat. Zametki 46 (1989), 72-79, 104. · Zbl 0694.05041
[17] A. Thomason: A disproof of a conjecture of Erdős in Ramsey theory, J. London Math. Soc. (2) 39 (1989), 246-255. · Zbl 0638.05037
[18] L. Grabowski, A. Máthé, and O. Pikhurko. Measurable circle squaring. Annals of Math. (2), 185:671-710, 2017. · Zbl 1376.52023
[19] L. Grabowski, A. Máthé, and O. Pikhurko. Measurable equidecompositions for group actions with an expansion property. J. Europ. Math. Soc, 24:4277-4326, 2022. · Zbl 07619418
[20] J. Grebík and V. Rozhoň. Local problems on grids from the perspective of distributed algorithms, finitary factors, and descriptive combinatorics. E-print arxiv:2103.08394, 2021. · Zbl 07741091
[21] A. S. Kechris. Classical descriptive set theory, volume 156 of Graduate Texts in Mathematics. Springer-Verlag, New York, 1995. · Zbl 0819.04002
[22] M. Laczkovich. Equidecomposability and discrepancy; a solution of Tarski’s circle-squaring problem. J. Reine Angew. Math., 404:77-117, 1990. · Zbl 0748.51017
[23] M. Laczkovich. Decomposition of sets with small boundary. J. Lond. Math. Soc., 46:58-64, 1992. · Zbl 0776.11041
[24] M. Laczkovich. Uniformly spread discrete sets in R d . J. Lond. Math. Soc., 46:39-57, 1992. · Zbl 0774.11038
[25] M. Laczkovich. The story of squaring the circle, July 2017. Workshop “Geometric mea-sure theory”, Warwick, 10-14 July 2017. Talk slides: http://homepages.warwick.ac.uk/ masfay/workshop_2017/Slides/Laczkovich.pdf.
[26] A. S. Marks and S. Unger. Borel circle squaring. Annals of Math. (2), 186:581-605, 2017. · Zbl 1400.03064
[27] A. Máthé. Measurable equidecompositions. In Proceedings of the International Congress of Mathematicians. Volume 2, pages 1709-1728. World Scientific, 2018. · Zbl 1454.28007
[28] A. Máthé, J. A. Noel, and O. Pikhurko. Circle squaring with pieces of small boundary and low borel complexity. E-print arxiv:2202.01412, 2022.
[29] A. Tarski. Problème 38. Fund. Math., 7:381, 1925.
[30] S. Wagon. Circle-squaring in the twentieth century. Math. Intelligencer, 3:176-181, 1980/81. References · Zbl 0479.01009
[31] Noga Alon, Michael Krivelevich, and Benny Sudakov, Induced subgraphs of prescribed size, J. Graph Theory 43 (2003), 239-251. · Zbl 1025.05043
[32] Boaz Barak, Anup Rao, Ronen Shaltiel, and Avi Wigderson, 2-source dispersers for n op1q entropy, and Ramsey graphs beating the Frankl-Wilson construction, Ann. of Math. (2) 176 (2012), 1483-1543. · Zbl 1256.05146
[33] Boris Bukh and Benny Sudakov, Induced subgraphs of Ramsey graphs with many distinct degrees, J. Combin. Theory Ser. B 97 (2007), 612-619. · Zbl 1120.05057
[34] Neil Calkin, Alan Frieze, and Brendan D. McKay, On subgraph sizes in random graphs, Combin. Probab. Comput. 1 (1992), 123-134. · Zbl 0793.05105
[35] F. R. K. Chung, Open problems of Paul Erdős in graph theory, J. Graph Theory 25 (1997), 3-36. · Zbl 0872.05052
[36] Fan Chung and Ron Graham, Erdős on graphs, A K Peters, Ltd., Wellesley, MA, 1998, His legacy of unsolved problems. · Zbl 0890.05049
[37] P. Erdős, Some remarks on the theory of graphs, Bull. Amer. Math. Soc. 53 (1947), 292-294. · Zbl 0032.19203
[38] P. Erdős and G. Szekeres, A combinatorial problem in geometry, Compositio Math. 2 (1935), 463-470. · JFM 61.0651.04
[39] P. Erdős and A. Szemerédi, On a Ramsey type theorem, Period. Math. Hungar. 2 (1972), 295-299. · Zbl 0242.05122
[40] Paul Erdős, Some of my favourite problems in various branches of combinatorics. Combi-natorics 92 (Catania, 1992), Matematiche (Catania) 47 (1992), 231-240 (1993). · Zbl 0797.05001
[41] Paul Erdős, Some of my favourite problems in number theory, combinatorics, and geometry, Resenhas 2 (1995), 165-186, Combinatorics Week (Portuguese) (São Paulo, 1994). · Zbl 0871.11002
[42] Paul Erdős, Some recent problems and results in graph theory. The Second Krakow Confer-ence on Graph Theory (Zgorzelisko, 1994), Discrete Math. 164 (1997), 81-85. · Zbl 0871.05054
[43] Matthew Jenssen, Peter Keevash, Eoin Long, and Liana Yepremyan, Distinct degrees in induced subgraphs, Proc. Amer. Math. Soc. 148 (2020), 3835-3846. · Zbl 1444.05140
[44] Matthew Kwan and Benny Sudakov, Proof of a conjecture on induced subgraphs of Ramsey graphs, Trans. Amer. Math. Soc. 372 (2019), 5571-5594. · Zbl 1423.05106
[45] Matthew Kwan and Benny Sudakov, Ramsey graphs induce subgraphs of quadratically many sizes, Int. Math. Res. Not. IMRN (2020), 1621-1638. · Zbl 1440.05151
[46] Xin Li, Non-malleable extractors and non-malleable codes: partially optimal constructions, 34th Computational Complexity Conference, LIPIcs. Leibniz Int. Proc. Inform., vol. 137, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2019, pp. Art. No. 28, 49. · Zbl 07564428
[47] Eoin Long and Laurent , iu Ploscaru, A bipartite version of the Erdős-McKay conjecture, arXiv:2207.12874.
[48] Elchanan Mossel, Ryan O’Donnell, and Krzysztof Oleszkiewicz, Noise stability of functions with low influences: invariance and optimality, Ann. of Math. (2) 171 (2010), 295-341. · Zbl 1201.60031
[49] Bhargav Narayanan, Julian Sahasrabudhe, and István Tomon, Ramsey graphs induce sub-graphs of many different sizes, Combinatorica 39 (2019), 215-237. · Zbl 1438.05237
[50] Hans Jürgen Prömel and Vojtěech Rödl, Non-Ramsey graphs are c log n-universal, J. Com-bin. Theory Ser. A 88 (1999), 379-384. · Zbl 0934.05090
[51] Saharon Shelah, Erdős and Rényi conjecture, J. Combin. Theory Ser. A 82 (1998), 179-185. · Zbl 0906.05048
[52] Roman Vershynin, Invertibility of symmetric random matrices, Random Structures Algo-rithms 44 (2014), 135-182. · Zbl 1291.15088
[53] L. Babai, V. Sós, Sidon sets in groups and induced subgraphs of Cayley graphs, European J. Combin. 6 (1985), 101-114. · Zbl 0573.05032
[54] William Beckner. Inequalities in Fourier analysis. Annals of Mathematics, pages 159-182, 1975 · Zbl 0338.42017
[55] Aline Bonami.Étude des coefficients de Fourier des fonctions de L p pGq. In Annales de l’institut Fourier, volume 20(2), pages 335-402, 1970. · Zbl 0195.42501
[56] Sean Eberhard. Product mixing in the alternating group. Discrete Analysis, 2:18pp, 2016. References · Zbl 1454.20020
[57] Bose, P., Lubiw, A., Pathak, V., and Verdonschot, S. Flipping edge-labelled triangulations. Comput. Geom. 68 (2018), 309-326. · Zbl 1380.05173
[58] De Loera, J. A., Rambau, J., and Santos, F. Triangulations: Structures for Algorithms and Applications. Springer, 2010. · Zbl 1207.52002
[59] Hurtado, F., Noy, M., and Urrutia, J. Flipping edges in triangulations. Discrete Comput. Geom. 22 (1999), no. 3, 333-346. · Zbl 0939.68135
[60] Lawson, C. L. Transforming triangulations. Discrete Math. 3 (1972), no. 4, 365-372. · Zbl 0253.05116
[61] Lubiw, A., Masárová, Z., and Wagner, U. A proof of the orbit conjecture for flipping edge-labelled triangulations. Discrete Comput. Geom. 61 (2019), no. 4, 880-898. · Zbl 1411.05234
[62] Orden, D., and Santos, F. The polytope of non-crossing graphs on a planar point set. Discrete Comput. Geom. 33 (2005), no. 2, 275-305. · Zbl 1063.68077
[63] Wagner, U. and Welzl, E. Connectivity of triangulation flip graphs in the plane. Discrete Comput. Geom. 68 (2022), no. 4, 1227-1284 · Zbl 1507.05027
[64] J. Akiyama and V. Chvátal, A short proof of the linear arboricity for cubic graphs, Bull. Liber. Arts Sci. NMS 2 (1981), 1-3.
[65] J. Akiyama, G. Exoo, and F. Harary, Covering and packing in graphs. III: Cyclic and acyclic invariants, Mathematica Slovaca 30 (1980), no. 4, 405-417. · Zbl 0458.05050
[66] R. E. L. Aldred and N. C. Wormald, More on the linear k-arboricity of regular graphs, Australas. J. Combin. 18 (1998), 97-104. · Zbl 0930.05075
[67] N. Alon, The linear arboricity of graphs, Israel J. Math. 62 (1988), no. 3, 311-325. · Zbl 0673.05019
[68] J.-C. Bermond, J.-L. Fouquet, M. Habib, and B. Peroche, On linear k-arboricity, Discr. Math. 52 (1984), no. 2-3, 123-132. · Zbl 0556.05054
[69] A. Ferber, J. Fox, and V. Jain, Towards the linear arboricity conjecture, J. Combin. Theory Ser. B 142 (2020), 56-79. · Zbl 1436.05047
[70] B. Jackson and N. C. Wormald, On the linear k-arboricity of cubic graphs, Discr. Math. 162 (1996), no. 1-3, 293-297. · Zbl 0870.05036
[71] G. Kronenberg, S. Letzter, A. Pokrovskiy, and L. Yepremyan, Decomposing cubic graphs into isomorphic linear forests, arXiv:2210.11458 (2022).
[72] R. Lang and L. Postle, An improved bound for the linear arboricity conjecture, arXiv:2008.04251 (2020).
[73] N. Alon and J. Bourgain. Additive patterns in multiplicative subgroups. Geometric and Functional Analysis, 24(3):721-739, 2014. · Zbl 1377.11013
[74] N. Alon and Y. Roichman. Random Cayley graphs and expander. Random Structures Al-gorithms, 5(2):271-284, 1994. · Zbl 0798.05048
[75] S. Akbari, O. Etesami, H. Mahini and M. Mahmoody. On rainbow cycles in edge colored complete graphs. Australasian Journal of Combinatorics, 37:33-42, 2007. · Zbl 1130.05024
[76] L. Babai. Long cycles in vertex-transitive graphs. Journal of Graph Theory, 3(3):301-304, 1979. · Zbl 0414.05032
[77] B. Bollobás. The evolution of sparse graphs. Graph Theory and Combinatorics, Academic Press, London 35-57, 1984. · Zbl 0552.05047
[78] D. Christofides and K. Markstrom. Random Latin square graphs. Random Structures Algo-rithms, 41(1):47-65, 2012. · Zbl 1247.05216
[79] D. Christofides, J. Hladký and A. Máthé. Hamilton cycles in dense vertex-transitive graphs. Journal of Combinatorial Theory, Series B, 109:34-72, 2014. · Zbl 1301.05204
[80] V. Chvátal and P. Erdős. A note on Hamiltonian circuits. Discrete Mathematics, 2(2):111-113, 1972. · Zbl 0233.05123
[81] C. Cooper, A. Frieze and B. Reed. Random regular graphs of non-constant degree: connec-tivity and Hamiltonicity. Combinatorics, Probability and Computing, 11(3):249-261, 2002. · Zbl 1005.05039
[82] S. Curran and J. Gallian. Hamiltonian cycles and paths in Cayley graphs and digraphs -a survey. Discrete Mathematics, 156(1-3):1-18, 1996. · Zbl 0857.05067
[83] G. A. Dirac. Some theorems on abstract graphs. Proceedings of the London Mathematical Society, 3(1):69-81, 1952. · Zbl 0047.17001
[84] J. Komlós and E. Szemerédi. Limit distribution for the existence of Hamiltonian cycles in a random graph. Discrete Mathematics, 43(1):55-63, 1983. · Zbl 0521.05055
[85] A. Korshunov. Solution of a problem of Erdős and Rényi on Hamilton cycles in non-oriented graphs. Soviet Math. Dokl, 17:760-764, 1976. · Zbl 0353.05039
[86] M. Krivelevich, B. Sudakov, V. Vu and N. Wormald. Random regular graphs of high degree. Random Structures Algorithms, 18(4):346-363, 2001. · Zbl 0996.05106
[87] M. Krivelevich and B. Sudakov. Sparse pseudo-random graphs are Hamiltonian. Journal of Graph Theory, 42(1):17-33, 2003. · Zbl 1028.05059
[88] M. Krivelevich and B. Sudakov. Pseudo-random graphs. More sets, graphs and numbers, Springer, 199-262, 2006. · Zbl 1098.05075
[89] L.Lovász. Combinatorial structures and their applications. Proc. Calgary Internat. Conf., Calgary, Alberta, 1970:243-246, 1969. · Zbl 0257.05122
[90] J. Meng and H. Qiongxiang. Almost all Cayley graphs are Hamiltonian. Acta Mathematica Sinica, 12(2):151-155, 1996. · Zbl 0858.05068
[91] I. Pak and ,R. Radoičić. Hamiltonian paths in Cayley graphs. Discrete Mathematics, 309(17):5501-5508, 2009. · Zbl 1229.05184
[92] L. Pósa. Hamiltonian circuits in random graphs. Discrete Mathematics, 14(4):359-364, 1976. · Zbl 0322.05127
[93] E. Rapaport-Strasser. Cayley color groups and Hamilton lines. Scripta Mathematica, 24:51-58, 1959. · Zbl 0084.25401
[94] Louigi Addario-Berry and Laura Eslava, Hitting time theorems for random matrices, Com-bin. Probab. Comput. 23 (2014), 635-669. · Zbl 1310.15068
[95] R. C. Alamino and D. Saad, Typical kernel size and number of sparse random matrices over Galois fields: a statistical physics approach, Phys. Rev. E (3) 77 (2008), 061123, 12.
[96] Anirban Basak and Mark Rudelson, Sharp transition of the invertibility of the adjacency matrices of sparse random graphs, arXiv:1809.08454. · Zbl 1468.05275
[97] M. Bauer and O. Golinelli, Core percolation in random graphs: a critical phenomena anal-ysis, The European Physical Journal B 24 (2001), 339-352.
[98] M. Bauer and O. Golinelli, Exactly solvable model with two conductor-insulator transitions driven by impurities, Physical Review Letters 86 (2001), 2621-2624.
[99] Charles Bordenave, Marc Lelarge, and Justin Salez, The rank of diluted random graphs, Ann. Probab. 39 (2011), 1097-1121. · Zbl 1298.05283
[100] Amin Coja-Oghlan, Oliver Cooley, Mihyun Kang, Joon Lee, and Jean Bernoulli Ravelo-manana, The sparse parity matrix, arXiv:2107.06123.
[101] Amin Coja-Oghlan, Alperen A. Ergür, Pu Gao, Samuel Hetterich, and Maurice Rolvien, The rank of sparse random matrices, Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, PA, 2020, pp. 579-591. · Zbl 07304058
[102] Kevin P. Costello, Terence Tao, and Van Vu, Random symmetric matrices are almost surely nonsingular, Duke Math. J. 135 (2006), 395-413. · Zbl 1110.15020
[103] Kevin P. Costello and Van Vu, On the rank of random sparse matrices, Combin. Probab. Comput. 19 (2010), 321-342. · Zbl 1204.15042
[104] Kevin P. Costello and Van H. Vu, The rank of random graphs, Random Structures Algo-rithms 33 (2008), 269-285. · Zbl 1194.05083
[105] Amir Dembo and Andrea Montanari, Finite size scaling for the core of large random hy-pergraphs, Ann. Appl. Probab. 18 (2008), 1993-2040. · Zbl 1152.05051
[106] Patrick DeMichele, Margalit Glasgow, and Alexander Moreira, On the rank, kernel, and core of sparse random graphs, arXiv:2105.11718.
[107] Asaf Ferber, Matthew Kwan, and Lisa Sauermann, Singularity of sparse random matrices: simple proofs, arXiv:2011.01291. · Zbl 1511.15029
[108] R. M. Karp and M. Sipser, Maximum matching in sparse random graphs, 22nd Annual Symposium on Foundations of Computer Science (sfcs 1981), IEEE, October 1981.
[109] J. Komlós, On the determinant of p0, 1q matrices, Studia Sci. Math. Hungar. 2 (1967), 7-21. · Zbl 0153.05002
[110] J. Komlós, On the determinant of random matrices, Studia Sci. Math. Hungar. 3 (1968), 387-399. · Zbl 0226.60048
[111] M. Mézard, F. Ricci-Tersenghi, and R. Zecchina, Two solutions to diluted p-spin models and XORSAT problems, J. Statist. Phys. 111 (2003), 505-533. · Zbl 1049.82073
[112] Konstantin Tikhomirov, Singularity of random Bernoulli matrices, Ann. of Math. (2) 191 (2020), 593-634. · Zbl 1458.15023
[113] Van Vu, Some recent results on random matrices, lecture at a workshop on Probabilistic Techniques and Applications, hosted by the Institute for Pure & Applied Mathematics (IPAM), http://www.ipam.ucla.edu/abstract/?tid=8303&pcode=CMAWS1, 2009. References
[114] J. Nešetřil, V. Rödl, Partitions of vertices, Commentationes Mathematicae Universitatis Carolinae, 17 (1976) 85-95. · Zbl 0344.05150
[115] N. Alon, J. Pach and J. Solymosi, “Ramsey-type theorems with forbidden subgraphs”, Combinatorica 21 (2001), 155-170. · Zbl 0989.05124
[116] M. Chudnovsky, “The Erdős-Hajnal conjecture-a survey”, Journal of Graph Theory 75, no. 2, (2014), 178-190. · Zbl 1280.05086
[117] M. Chudnovsky, J. Fox, A. Scott, P. Seymour and S. Spirkl, “Towards Erdős-Hajnal for graphs with no 5-hole”, Combinatorica 39 (2019), 983-991. · Zbl 1449.05148
[118] M. Chudnovsky, A. Scott, P. Seymour, and S. Spirkl, Erdős-Hajnal for graphs with no 5-hole, Proceedings of the London Mathematical Society, to appear. · Zbl 1521.05078
[119] D. Conlon, J. Fox and B. Sudakov, “Recent developments in graph Ramsey theory”, in: Surveys in Combinatorics 2015, Cambridge University Press, 2015, 49-118. · Zbl 1352.05123
[120] P. Erdős and A. Hajnal, “On spanned subgraphs of graphs”, Graphentheorie und Ihre An-wendungen (Oberhof, 1977). · Zbl 0405.05031
[121] P. Erdős and A. Hajnal, “Ramsey-type theorems”, Discrete Applied Mathematics 25 (1989), 37-52. · Zbl 0715.05052
[122] J. Fox and B. Sudakov, “Induced Ramsey-type theorems”, Advances in Mathematics 219 (2008), 1771-1800. · Zbl 1152.05054
[123] A. Gyárfás, “Reflections on a problem of Erdős and Hajnal”, in: The Mathematics of Paul Erdős, (R. L. Graham and J. Nešetřil, eds.), Algorithms and Combinatorics 14, Vol. II, Springer-Verlag, Heidelberg, (1997), 93-98. · Zbl 0863.05047
[124] V. Nikiforov, “Edge distribution of graphs with few copies of a given graph”, Combin. Probab. Comput. 15 (2006), 895-902. · Zbl 1120.05072
[125] V. Rödl, “On universality of graphs with uniformly distributed edges”, Discrete Math. 59 (1986), 125-134. · Zbl 0619.05035
[126] N. Alon, Z. Füredi, Covering the cube with by affine hyperplanes, European J. Combin. 14 (2) (1993), 79-83. · Zbl 0773.52011
[127] N. Alon, N. Linial, and R. Meshulam, Additive bases of vector spaces over prime fields, J. Combin. Theory Ser. A 57 (1991), 203-210. · Zbl 0739.11003
[128] N. Alon, and M. Tarsi, A nowhere-zero point in linear mappings, Combinatorica 9 (4) (1989), 393-395. · Zbl 0717.05021
[129] F. Jaeger, Nowhere-zero flow problems, in “Selected Topics in Graph Theory” (L. Beineke and R. Wilson, Eds.), Vol. 3, pp. 91-95, Academic Press, London/New York, 1988. · Zbl 0648.00003
[130] J. Nagy, and P. P. Pach, The Alon-Jaeger-Tarsi conjecture via group ring identities, preprint (2021), arXiv:2107.03956.
[131] J. Nagy, P. P. Pach, and I. Tomon, Additive bases, coset covers, and non-vanishing linear maps, preprint (2021), arXiv:2111.13658.
[132] L. Pyber, How abelian is a finite group? in: The Mathematics of Paul Erdős, vol. I, Springer-Verlag, Heidelberg, (1996), 372-384. · Zbl 0869.20010
[133] B. Szegedy, Coverings of abelian groups and vector spaces, J. Combin. Theory Ser. A 114 (1) (2007), 20-34. · Zbl 1105.20045
[134] M.J. Tomkinson, Groups covered by finitely many cosets or subgroups, Comm. Algebra 15 (4) (1987), 845-859. · Zbl 0613.20025
[135] Peter Allen, Almost every 2-SAT function is unate, Israel J. Math. 161 (2007), 311-346. · Zbl 1141.68033
[136] József Balogh, Dingding Dong, Bernard Lidický, Nitya Mani, Yufei Zhao Nearly all k-SAT functions are unate, arXiv:2209.04894.
[137] Béla Bollobás and Graham R. Brightwell, The number of k-SAT functions, Random Struc-tures Algorithms 22 (2003), 227-247. · Zbl 1026.68063
[138] Béla Bollobás, Graham R. Brightwell, and Imre Leader, The number of 2-SAT functions, Israel J. Math. 133 (2003), 45-60. · Zbl 1024.68044
[139] Dingding Dong, Nitya Mani, and Yufei Zhao, Enumerating k-SAT functions, ACM-SIAM Symposium on Discrete Algorithms (SODA’22), arXiv:2107.09233.
[140] L. Ilinca and J. Kahn, The number of 3-SAT functions, Israel J. Math. 192 (2012), 869-919. References · Zbl 1258.68104
[141] O. Borodin and A. Kostochka, On an upper bound of a graph’s chromatic number depending on the graph’s degree and density, J. Combin. Theory Ser. B, 23, (1977), 247-250. · Zbl 0336.05104
[142] R. Brooks, On Colouring the Nodes of a Network, Math. Proc. Cambridge Phil. Soc., 37 (1941), 194-197. · Zbl 0027.26403
[143] P. Catlin, Embedding subgraphs and coloring graphs under extremal degree conditions, Ph. D thesis, (1976), The Ohio State University.
[144] P. Catlin, Another bound on the chromatic number of a graph, Discrete Mathematics, 24, (1978), 1-6. · Zbl 0384.05043
[145] M. Chudnovsky, A. King, M. Plumettaz, and P. Seymour, A local strengthening of Reed’s ω, ∆, χ conjecture for quasi-line graphs, SIAM Journal on Discrete Mathematics, 27(1), (2013), 95-108. · Zbl 1267.05116
[146] D. Cranston and L. Rabern, Coloring claw-free graphs with ∆´1 colors, SIAM Journal on Discrete Mathematics, 27(1), (2013), 534-549. · Zbl 1268.05069
[147] D. Cranston and L. Rabern. Graphs with χ ” ∆ have big cliques, SIAM Journal on Discrete Mathematics, 29(4), (2015), 1792-1814. · Zbl 1321.05080
[148] B. Farzad, M. Molloy and B. Reed, p∆´kq-critical graphs, Journal of Combinatorial Theory, Series B, 93, (2005), 173-185. · Zbl 1062.05056
[149] U. Gupta and D. Pradhan, Borodin-Kostochka’s Conjecture on pP 5 , C 4 q-free graphs, Journal of Applied Mathematics and Computing, 65, (2020), 1-8.
[150] P. Haxell, A note on vertex list-colouring, Combinatorics, Probability and Computing, 10, (2001), 345-347. · Zbl 0986.05042
[151] T. Kelly and L. Postle, A local epsilon version of Reed’s conjecture. Journal of Combinatorial Theory, Series B, 141, (2020), 181-222. · Zbl 1430.05038
[152] A. King, Hitting all maximum cliques with a stable set using lopsided independent transver-sals, Journal of Graph Theory, 67(4), (2011), 300-305. · Zbl 1231.05205
[153] A. King and B. Reed, Bounding χ in terms of ω and ∆ for quasi-line graphs, Journal of Graph Theory, 59(3), (2008), 215-228. · Zbl 1184.05045
[154] A. King and B. Reed, A short proof that χ can be bounded ǫ away from ∆‘1 toward ω, Journal of Graph Theory, 81(1), (2016), 30-34. · Zbl 1330.05070
[155] A. Kohl and I. Schiermeyer. Some results on Reed’s conjecture about ω, ∆, and χ with respect to α, Discrete Mathematics, 310(9), (2010), 1429-1438. · Zbl 1221.05147
[156] A. Kostochka. Degree, density and chromatic number of graphs. Metody Diskret. Analiz., 35, (1980), 45-70. · Zbl 0459.05038
[157] C. MacDonald, On finding large cliques when χ is near ∆, MMath Thesis, University of Waterloo, (2021).
[158] N. Mozhan. Chromatic number of graphs with a density that does not exceed two-thirds of the maximal degree, Metody Diskretn. Anal, 39, (1983), 52-65. · Zbl 0536.05023
[159] L. Rabern, A note on Reed’s conjecture, SIAM Journal on Discrete Mathematics, 22(2), (2008), 820-827. · Zbl 1191.05042
[160] B. Reed, A Strengthening of Brooks Theorem, J. Combin. Theory Ser. B, 76, (1999), 136-149. · Zbl 0935.05045
[161] B. Reed, ω, ∆ and χ, Journal of Graph Theory, 27(4), (1998), 177-212. · Zbl 0980.05026
[162] I. Schiermeyer, Chromatic number of P 5 -free graphs: Reed’s Conjecture, Discrete Mathe-matics, 339(7), (2016), 1940-1943. · Zbl 1334.05045
[163] D. Best and I. M. Wanless. What did Ryser conjecture? arXiv preprint arXiv:1801.02893, 2018.
[164] A. E. Brouwer, A. de Vries, and R. Wieringa. A lower bound for the length of partial transversals in a Latin square. Nieuw Archief Voor Wiskunde, 26(2):330-332, 1978. · Zbl 0395.05012
[165] R. A. Brualdi and H. J. Ryser. Combinatorial matrix theory. Cambridge University Press, 1991. · Zbl 0746.05002
[166] D. A. Drake. Maximal sets of latin squares and partial transversals. Journal of Statistical Planning and Inference, 1(2):143-149, 1977. · Zbl 0392.05014
[167] L. Euler. Recherches sur un nouvelle espéce de quarrés magiques. Verhandelingen uitgegeven door het zeeuwsch Genootschap der Wetenschappen te Vlissingen, pages 85-239, 1782.
[168] P. Hatami and P. W. Shor. A lower bound for the length of a partial transversal in a latin square. Journal of Combinatorial Theory, Series A, 115(7):1103-1113, 2008. · Zbl 1159.05303
[169] P. Keevash, A. Pokrovskiy, B. Sudakov, and L. Yepremyan. New bounds for Ryser’s conjec-ture and related problems. arXiv preprint arXiv:2005.00526, 2020.
[170] K. K. Koksma. A lower bound for the order of a partial transversal in a Latin square. Journal of Combinatorial Theory, 7(1):94-95, 1969. · Zbl 0172.01504
[171] R. Montgomery, A. Pokrovskiy, and B. Sudakov. Decompositions into spanning rainbow structures. Proceedings of the London Mathematical Society, 119(4):899-959, 2019. · Zbl 1429.05024
[172] V. Rödl, A. Ruciński, and E. Szemerédi. A Dirac-type theorem for 3-uniform hypergraphs. Combinatorics, Probability and Computing, 15(1-2):229-251, 2006. · Zbl 1082.05057
[173] H. Ryser. Neuere probleme der kombinatorik. Vorträgeüber Kombinatorik, Oberwolfach, pages 69-91, 1967.
[174] P. W. Shor. A lower bound for the length of a partial transversal in a Latin square. Journal of Combinatorial Theory, Series A, 33(1):1-8, 1982. · Zbl 0489.05012
[175] S. K. Stein. Transversals of Latin squares and their generalizations. Pacific J. Math., 59:567-575, 1975. · Zbl 0302.05015
[176] D. E. Woolbright. An nˆn Latin square has a transversal with at least n´?n distinct symbols. Journal of Combinatorial Theory, Series A, 24(2):235-237, 1978. References · Zbl 0368.05012
[177] R. Aharoni and E. Berger, Rainbow matchings in r-partite r-graphs, Electron. J. Combin. 16(1) (2009), R119. · Zbl 1186.05118
[178] R. Aharoni, E. Berger, M. Chudnovsky, D. Howard, and P. Seymour: Large rainbow match-ings in general graphs, European J. Combin. 79 (2019), 222-227. · Zbl 1414.05235
[179] R. Aharoni, R. Holzman, and Z. Jiang, Rainbow fractional matchings, Combinatorica 39 (2019), pp. 1191-1202. · Zbl 1463.05532
[180] N. Alon, Multicolored matchings in hypergraphs, Mosc. J. Comb. Number Theory 1 (2011), 3-10. · Zbl 1255.05144
[181] R. Alweiss, L. Shachar, K. Wu, and J. Zhang, Improved bounds for the sunflower lemma, Ann. of Math. (2) 194 (2021), no. 3, 795-815. · Zbl 1479.05343
[182] D. Chakraborti, and P.-S. Loh, Rainbow matchings in edge-colored simple graphs, preprint: arXiv:2011.04650.
[183] D. Munhá Correia, B. Sudakov, and I. Tomon, Flattening rank and its combinatorial appli-cations, Linear Algebra Appl. 625 (2021), 113-125. · Zbl 1465.05183
[184] A. Drisko, Transversals in row-latin rectangles, J. Combin. Theory Ser. A 84 (1998), 181-195. · Zbl 0915.05025
[185] K. Frankston, J. Kahn, B. Narayanan, and J. Park, Thresholds versus fractional expectation-thresholds, Ann. of Math. (2) 194 (2021), no. 2, 475-495. · Zbl 1472.05132
[186] R. Glebov, B. Sudakov, and T. Szabó, How many colors guarantee a rainbow matching?, Electron. J. Combin. 21(1) (2014), P1.27. · Zbl 1300.05097
[187] P. Keevash, A. Pokrovskiy, B. Sudakov, and L. Yepremyan, New bounds for Ryser’s conjec-ture and related problems, Trans. Amer. Math. Soc. Ser. B 9 (2022), 288-321. · Zbl 1490.05269
[188] S. Lovett, N. Solomon, and J. Zhang. From DNF compression to sunflower theorems via regularity. 34th Computational Complexity Conference (CCC 2019) , Leibniz International Proceedings in Informatics 137 (2019), 5:1-5:14. · Zbl 07564405
[189] Alavi, Y., Boals, A. J., Chartrand, G., Erdos, P., & Oellermann, O. R. (1987). The ascending subgraph decomposition problem. Congressus Numerantium, 58(7), 14. · Zbl 0641.05046
[190] Ali, A., Chartrand, G., & Zhang, P. (2021). Irregularity in Graphs. New York: Springer. · Zbl 1472.05001
[191] Katsamaktsis, K, Letzter, S, Pokrovskiy, A, & Sudakov, B. In preparation.
[192] Ma, K., Zhou, H., & Zhou, J. (1994). On the ascending star subgraph decomposition of star forests. Combinatorica, 14(3), 307-320. · Zbl 0819.05049
[193] Freya Behrens, Gabriel Arpino, Yaroslav Kivva, and Lenka Zdeborová, (dis) assor-tative partitions on random regular graphs, arXiv preprint arXiv:2202.10379 (2022). · Zbl 1516.05199
[194] Wei-Kuo Chen, David Gamarnik, Dmitry Panchenko, and Mustazee Rahman, Subop-timality of local algorithms for a class of max-cut problems, The Annals of Probability 47 (2019), no. 3, 1587-1618. · Zbl 1466.60200
[195] Amir Dembo, Andrea Montanari, and Subhabrata Sen, Extremal cuts of sparse ran-dom graphs, The Annals of Probability 45 (2017), no. 2, 1190-1217. · Zbl 1372.05196
[196] Asaf Ferber, Matthew Kwan, Bhargav Narayanan, Ashwin Sah, and Mehtaab Sawh-ney, Friendly bisections of random graphs, arXiv preprint arXiv:2105.13337 (2021). · Zbl 1522.05424
[197] Z. Füredy, Personal communication.
[198] David Gamarnik, The overlap gap property: A topological barrier to optimizing over random structures, Proceedings of the National Academy of Sciences 118 (2021), no. 41.
[199] David Gamarnik and Quan Li, On the max-cut over sparse random graph, Random Structures and Algorithms 52 (2018), no. 2, 219-262. · Zbl 1388.05167
[200] Ben Green, 100 open problems, Manuscript 1.
[201] Dmitry Panchenko, On the k-sat model with large number of clauses, Random Struc-tures & Algorithms 52 (2018), no. 3, 536-542. · Zbl 1391.60023
[202] Subhabrata Sen, Optimization on sparse random hypergraphs and spin glasses, Ran-dom Structures & Algorithms 53 (2018), no. 3, 504-536. · Zbl 1397.05121
[203] Ajtai, Miklós; Komlós, János; Szemerédi, Endre A note on Ramsey numbers. J. Combin. Theory Ser. A 29 (1980), no. 3, 354-360. · Zbl 0455.05045
[204] Alon, Noga Explicit Ramsey graphs and orthonormal labelings. Electron. J. Combin. 1 (1994), Research Paper 12, approx. 8 pp. · Zbl 0814.05056
[205] Alon, Noga; Krivelevich, Michael(IL-TLAV) Constructive bounds for a Ramsey-type prob-lem. Graphs Combin. 13 (1997), no. 3, 217-225. · Zbl 0890.05050
[206] Alon, Noga; Rödl, Vojtěch Sharp bounds for some multicolor Ramsey numbers. (English summary) Combinatorica 25 (2005), no. 2, 125-141. · Zbl 1090.05049
[207] Bishnoi, Anurag; Ihringer, Ferdinand; Pepe, Valentina A construction for clique-free pseu-dorandom graphs https://arxiv.org/abs/1905.04677
[208] Bohman, Tom; Keevash, Peter Dynamic concentration of the triangle-free process. The Seventh European Conference on Combinatorics, Graph Theory and Applications, 489-495, CRM Series, 16, Ed. Norm., Pisa, 2013. · Zbl 1291.05183
[209] Bohman, Tom; Keevash, Peter The early evolution of the H-free process. Invent. Math. 181 (2010), no. 2, 291-336. · Zbl 1223.05270
[210] Caro, Yair; Li, Yusheng; Rousseau, Cecil C;
[211] Zhang, Yuming Asymptotic bounds for some bipartite graph: complete graph Ramsey numbers. Discrete Math. 220 (2000), no. 1-3, 51-56. · Zbl 0953.05050
[212] Conlon, David A sequence of triangle-free pseudorandom graphs. Combin. Probab. Comput. 26 (2017), no. 2, 195-200. · Zbl 1371.05259
[213] Dudek, Andrzej; Retter, Troy; Rödl, Vojtěch On generalized Ramsey numbers of Erdős and Rogers. J. Combin. Theory Ser. B 109 (2014), 213-227. · Zbl 1301.05225
[214] Erdős, P.; Szekeres, G. A combinatorial problem in geometry. Compositio Math. 2 (1935), 463-470. · JFM 61.0651.04
[215] Fiz Pontiveros, Gonzalo;
[216] Griffiths, Simon;
[217] Morris, Robert The triangle-free process and the Ramsey number Rp3, kq Mem. Amer. Math. Soc., to appear.
[218] Kostochka, Alexandr; Mubayi, Dhruv; Verstraëte, Jacques Hypergraph Ramsey numbers: triangles versus cliques. J. Combin. Theory Ser. A 120 (2013), no. 7, 1491-1507. · Zbl 1314.05125
[219] Krivelevich, Michael; Sudakov, Benny Pseudo-random graphs. More sets, graphs and num-bers, 199-262, Bolyai Soc. Math. Stud., 15, Springer, Berlin, 2006. · Zbl 1098.05075
[220] Mubayi, Dhruv; Williford, Jason On the independence number of the Erdős-Rényi and projective norm graphs and a related hypergraph. J. Graph Theory 56 (2007), no. 2, 113-127. · Zbl 1128.05040
[221] Nilli, A. On the second eigenvalue of a graph. Discrete Math. 91 (1991), no. 2, 207-210. · Zbl 0771.05064
[222] Nilli, A. Tight estimates for eigenvalues of regular graphs. Electron. J. Combin. 11 (2004), no. 1, Note 9, 4 pp. · Zbl 1053.05082
[223] Shearer, James Lower bounds for small diagonal Ramsey numbers. J. Combin. Theory Ser. A 42 (1986), no. 2, 302-304. · Zbl 0614.05037
[224] Spencer, Joel Asymptotic lower bounds for Ramsey functions. Discrete Math. 20 (1977/78), no. 1, 69-76. · Zbl 0375.05033
[225] Sudakov, Benny A note on odd cycle-complete graph Ramsey numbers. Electron. J. Combin. 9 (2002), no. 1, Note 1, 4 pp. · Zbl 0981.05098
[226] Sudakov, Benny; Szaó, Tibor; Vu, Van H. A generalization of Turán’s theorem. J. Graph Theory 49 (2005), no. 3, 187-195. · Zbl 1066.05079
[227] G. Elekes and L. Rónyai. A combinatorial problem on polynomials and rational functions. J. Combinat. Theory Ser. A. 89:1-20, 2000. · Zbl 0953.05005
[228] G. Elekes and E. Szabó. How to find groups? (and how to use them in Erdős geometry?) Combinatorica, 32(5):537-571, 2012. · Zbl 1299.05018
[229] M. Makhul, O. Roche-Newton, A. Warren and F. de Zeeuw. Constructions for the Elekes-Szabó and Elekes-Rónyai problems. Electron. J. Combin. 27(1), Paper 1.57, 2020. · Zbl 1439.52017
[230] O. E. Raz, M. Sharir, and J. Solymosi. Polynomials vanishing on grids: The Elekes-Rónyai problem revisited. Amer. J. Math., 138: 1029-1065, 2016. · Zbl 1343.05016
[231] O. E. Raz, M. Sharir, and F. de Zeeuw. Polynomials vanishing on Cartesian products: The Elekes-Szabó theorem revisited. Duke Math. J. 165(18):3517-3566, 2016. References · Zbl 1365.52023
[232] A. Barvinok, Combinatorics and Complexity of Partition Functions, Algorithms and Combinatorics, 30, Springer, Cham, 2016. · Zbl 1367.05002
[233] A. Barvinok, Approximating real-rooted and stable polynomials, with combinatorial applications, Online J. Anal. Comb. No. 14 (2019), Paper No. 8, 13 pp. · Zbl 1434.26030
[234] A. Barvinok, Computing permanents of complex diagonally dominant matrices and ten-sors, Israel J. Math. 232 (2019), no. 2, 931-945. · Zbl 07093099
[235] M. Bayati, D. Gamarnik, D. Katz, C. Nair, and P. Tetali, Simple deterministic approxi-mation algorithms for counting matchings, in STOC’07-Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 122-127, ACM, New York, 2007. · Zbl 1232.68179
[236] B. Bukh, personal communication, 2015.
[237] M. Chudnovsky and P. Seymour, The roots of the independence polynomial of a clawfree graph, J. Combin. Theory Ser. B 97 (2007), no. 3, 350-357. · Zbl 1119.05075
[238] O.J. Heilmann and E.H. Lieb, Theory of monomer-dimer systems, Comm. Math. Phys. 25 (1972), 190-232. · Zbl 0228.05131
[239] V. Patel and G. Regts, Deterministic polynomial-time approximation algorithms for partition functions and graph polynomials, SIAM J. Comput. 46 (2017), no. 6, 1893-1919. · Zbl 1383.68099
[240] Michael Braun, Tuvi Etzion, Patric R. J.Östergård, Alexander Vardy, and Alfred Wasser-mann, Existence of q-analogs of Steiner systems, Forum Math. Pi 4 (2016), e7, 14. · Zbl 1372.51003
[241] Michael Braun, Michael Kiermaier, and Alfred Wassermann, q-analogs of designs: subspace designs, Network coding and subspace designs, Signals Commun. Technol., Springer, Cham, 2018, pp. 171-211.
[242] Peter J. Cameron, Generalisation of Fisher’s inequality to fields with more than one element, Combinatorics (Proc. British Combinatorial Conf., Univ. Coll. Wales, Aberystwyth, 1973), London Math. Soc. Lecture Note Ser., No. 13, Cambridge Univ. Press, London, 1974, pp. 9-13. · Zbl 0298.05018
[243] Arman Fazeli, Shachar Lovett, and Alexander Vardy, Nontrivial t-designs over finite fields exist for all t, J. Combin. Theory Ser. A 127 (2014), 149-160. · Zbl 1297.05046
[244] J. E. Graver and W. B. Jurkat, The module structure of integral designs, J. Combinatorial Theory Ser. A 15 (1973), 75-90. · Zbl 0259.05020
[245] Venkatesan Guruswami and Chaoping Xing, List decoding Reed-Solomon, algebraic-geometric, and Gabidulin subcodes up to the Singleton bound, STOC’13-Proceedings of the 2013 ACM Symposium on Theory of Computing, ACM, New York, 2013, pp. 843-852. · Zbl 1293.94110
[246] Gil Kalai, Designs exist! [after Peter Keevash], Astérisque (2016), Exp. No. 1100, 399-422. · Zbl 1470.05002
[247] Peter Keevash, The existence of designs, arXiv:1401.3665. · Zbl 1386.05015
[248] Greg Kuperberg, Shachar Lovett, and Ron Peled, Probabilistic existence of regular combi-natorial structures, Geom. Funct. Anal. 27 (2017), 919-972. · Zbl 1369.05024
[249] Klaus Metsch, Bose-Burton type theorems for finite projective, affine and polar spaces, Surveys in combinatorics, 1999 (Canterbury), London Math. Soc. Lecture Note Ser., vol. 267, Cambridge Univ. Press, Cambridge, 1999, pp. 137-166. · Zbl 0936.51004
[250] D. K. Ray-Chaudhuri and N. M. Singhi, q-analogues of t-designs and their existence, Linear Algebra Appl. 114/115 (1989), 57-68. · Zbl 0684.05011
[251] Luc Teirlinck, Nontrivial t-designs without repeated blocks exist for all t, Discrete Math. 65 (1987), 301-311. · Zbl 0625.05005
[252] Richard M. Wilson, The necessary conditions for t-designs are sufficient for something, Utilitas Math. 4 (1973), 207-215. · Zbl 0286.05005
[253] Richard M. Wilson, An existence theory for pairwise balanced designs. III. Proof of the existence conjectures, J. Combinatorial Theory Ser. A 18 (1975), 71-79. · Zbl 0295.05002
[254] A. Arman, P. Gao and N. Wormald, Fast uniform generation of random graphs with given degree sequences, Random Structures Algorithms 59 (2021), 291-314. · Zbl 1522.68735
[255] B. Bollobás, A probabilistic proof of an asymptotic formula for the number of labelled regular graphs, European J. Combin. 1 (1980), 311-316. · Zbl 0457.05038
[256] P. Gao and N. Wormald, Uniform generation of random regular graphs, SIAM J. Comput. 46 (2017), 1395-1427. · Zbl 1368.05133
[257] B.D. McKay and N.C. Wormald, Uniform generation of random regular graphs of moderate degree, J. Algorithms 11 (1990), 52-67. · Zbl 0711.68082
[258] P. Brass, W. Moser and J. Pach, Research Problems in Discrete Geometry, Springer, New York, 2005. xii+499 pp · Zbl 1086.52001
[259] P. Erdős, On sets of distances of n points, Amer. Math. Monthly 53 (1946), 248-250. · Zbl 0060.34805
[260] P. Erdős, Problems and results in combinatorial geometry, Discrete geometry and convexity (New York, 1982), Ann. New York Acad. Sci., vol. 440, New York Acad. Sci., New York, 1985, pp. 1-11. · Zbl 0568.51011
[261] L. Guth and N. H. Katz, On the Erdős distinct distances problem in the plane, Ann. of Math. (2) 181 (2015), no. 1, 155-190. · Zbl 1310.52019
[262] J. Matoušek, The number of unit distances is almost linear for most norms, Adv. Math. 226 (2011), no. 3, 2618-2628. · Zbl 1214.52005
[263] J. Spencer, E. Szemerédi and W. Trotter, Jr., Unit distances in the Euclidean plane, Graph Theory and Combinatorics (Cambridge, 1983), Academic Press, London, 1984, pp. 293-303. · Zbl 0561.52008
[264] J. Solymosi and V. H. Vu, Near optimal bounds for the Erdős distinct distances problem in high dimensions, Combinatorica 28 (2008), no. 1, 113-125. · Zbl 1174.52009
[265] L. A. Székely, Crossing numbers and hard Erdős problems in discrete geometry, Combin. Probab. Comput. 6 (1997), no. 3, 353-358. · Zbl 0882.52007
[266] R. Diestel, R. Jacobs, P. Knappe, and J. Kurkofka. Graph decompositions. arXiv:2207.04855.
[267] P. Erdős, Problems and results in chromatic graph theory, in (F. Harary ed.) Proof Tech-niques in Graph Theory (Academic Press, 1969), 27-35. · Zbl 0194.25102
[268] V. Rödl. On the chromatic number of subgraphs of a given graph. Proc. AMS 64 (1977), 370-371. · Zbl 0408.05025
[269] Wojciech Banaszczyk, Balancing vectors and Gaussian measures of n-dimensional convex bodies, Random Structures Algorithms 12 (1998), 351-360. · Zbl 0958.52004
[270] Nikhil Bansal, Daniel Dadush, Shashwat Garg, and Shachar Lovett, The Gram-Schmidt walk: a cure for the Banaszczyk blues, STOC’18-Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, ACM, New York, 2018, pp. 587-597. · Zbl 1427.68328
[271] Yang P. Liu, Ashwin Sah, and Mehtaab Sawhney, A Gaussian fixed point random walk, 13th Innovations in Theoretical Computer Science Conference, LIPIcs. Leibniz Int. Proc. Inform., vol. 215, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2022, pp. Art. No. 101, 10. Matija Bucić Question 3. Let M n be the minimum number such that given M n transpositions in S n , one can always find a sequence of distinct elements of this set π 1 , . . . , π k such that π 1¨¨¨πk ” 1. What is M n ? This is called the additive dimension of the set of transpositions. What is known is the following upcoming result.
[272] Theorem 4 (Alon, Bucić, Sauermann, Zakharov, Zamir 2023+
[273] Peter Keevash, Dhruv Mubayi, Benny Sudakov, and Jacques Verstraëte, Rainbow Turán problems, Combin. Probab. Comput. 16 (2007), 109-126. · Zbl 1119.05058
[274] B. Bollobás, and A. Scott, Discrepancy in graphs and hypergraphs, pp 33-56 in: More Sets, Graphs and Numbers. Bolyai Society Mathematical Studies 15, Springer, 2006. · Zbl 1098.05058
[275] P. Erdős, M. Goldberg, J. Pach and J. Spencer, Cutting a graph into two dissimilar halves, Journal of Graph Theory 12, 121-131 (1988). · Zbl 0655.05059
[276] Charlotte Knierim, Maxime Larcher, Anders Martinsson, and Andreas Noever, Long cycles, heavy cycles and cycle decompositions in digraphs, J. Combin. Theory Ser. B 148 (2021), 125-148. · Zbl 1509.05149
[277] Julia Böttcher, Nóra Frankl, Domenico Mergoni Cecchelli, Olaf Parzcyk, and Jozef Skokan, Graphs with large minimum degree and no small odd cycles are 3-colorable, arXiv:2302.01875. References
[278] Ryan Alweiss, Shachar Lovett, Kewen Wu, and Jiapeng Zhang, Improved bounds for the sunflower lemma, Ann. of Math. (2) 194 (2021), 795-815. Reporter: Ashwin Sah, Mehtaab Sawhney · Zbl 1479.05343
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.