Skip to main content Accessibility help

We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.

Close cookie message
×
Hostname: page-component-cd9895bd7-gxg78 Total loading time: 0 Render date: 2024-12-22T20:51:26.829Z Has data issue: false hasContentIssue false

Sublinear Expanders and Their Applications

Published online by Cambridge University Press:  23 May 2024

By
Shoham Letzter
Edited by
Felix Fischer  and
Robert Johnson
Felix Fischer
Affiliation:
Queen Mary University of London
Robert Johnson
Affiliation:
Queen Mary University of London
Get access

Summary

In this survey we aim to give a comprehensive overview of results using sublinear expanders. The term sublinear expanders refers to a variety of definitions of expanders, which typically are defined to be graphs G such that every not-too-small and not-too-large set of vertices U has neighbourhood of size at least α|U|, where α is a function of n and |U|. This is in contrast with linear expanders, where α is typically a constant. We will briefly describe proof ideas of some of the results mentioned here, as well as related open problems.

Type
Chapter
Information
Surveys in Combinatorics 2024 , pp. 89 - 130
Publisher: Cambridge University Press
Print publication year: 2024

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Abu-Khzam, F. N. and M. A. Langston, Graph coloring and the immersion order, International Computing and Combinatorics Conference, Springer, 2003, pp. 394–403. 102CrossRefGoogle Scholar
Aharoni, R. and Haxell, P., Hall’s theorem for hypergraphs, J. Graph Theory 35 (2000), 83–88. 1183.0.CO;2-V>CrossRefGoogle Scholar
Allen, P., Brightwell, G., and Skokan, J., Ramsey-goodness–and otherwise, Combinatorica 33 (2013), 125–160. 123CrossRefGoogle Scholar
Alon, N., Bucić, M., Sauermann, L., Zakharov, D., and Zamir, O., Essentially tight bounds for rainbow cycles in proper edge-colourings, arXiv:2309.04460 (2023). 113, 114Google Scholar
Alon, N., Krivelevich, M., and Sudakov, B., Turań numbers of bipartite graphs and related Ramsey-type questions, Combin. Probab. Comput. 12 (2003), 477–494. 107CrossRefGoogle Scholar
Andersen, L. D., The history of latin squares, Combinatorics: Ancient & Modern (edited by Wilson, R. and Watkins, J.J.), 2013. 124CrossRefGoogle Scholar
Balogh, J., Csaba, B., Martin, R. R., and Pluhár, A., On the path separation number of graphs, Discr. Appl. Math. 213 (2016), 26–33. 119CrossRefGoogle Scholar
Balogh, J., Liu, H., and Sharifzadeh, M., Subdivisions of a large clique in C6-free graphs, J. Combin. Theory Ser. B 112 (2015), 18–35. 93CrossRefGoogle Scholar
Bassalygo, L. A. and Pinsker, M. S., The complexity of an optimal non-blocking commutation scheme without reorganization, Problemy Peredači Informacii 9 (1973), 84–87, Translated into English in Problems of Information Transmission, 9 (1974) 64-66. 89Google Scholar
Bollobás, B., Nested cycles in graphs, Problémes combinatoires et théorie des graphes Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976), Colloq. Internat. CNRS, 260, 1978, pp. 49–50. 122Google Scholar
Bollobás, B. and Thomason, A., Highly linked graphs, Combinatorica 16 (1996), 313–320. 91CrossRefGoogle Scholar
Bonamy, M., Botler, F., Dross, F., Naia, T., and Skokan, J., Separating the edges of a graph by a linear number of paths, arXiv:2301.08707 (2023). 119CrossRefGoogle Scholar
Bradač, D., Methuku, A., and Sudakov, B., The extremal number of cycles with all diagonals, arXiv:2308.16163 (2023). 115CrossRefGoogle Scholar
Brualdi, R. A. and Ryser, H. J., Combinatorial matrix theory, Cambridge University Press, 1991. 124CrossRefGoogle Scholar
Bucić, M. and Montgomery, R., Towards the Erdős-Gallai Cycle Decomposition Conjecture, arXiv:2211.07689 (2022). 116, 117, 118, 119Google Scholar
Burr, S. A., Ramsey numbers involving graphs with long suspended paths, J. London Math. Soc. 2 (1981), 405–413. 123CrossRefGoogle Scholar
Cambie, S., Gao, J., and Liu, H., Many Hamiltonian subsets in large graphs with given density, arXiv:2301.07467 (2023). 120CrossRefGoogle Scholar
Chen, G., Erdős, P., and Staton, W., Proof of a conjecture of Bollobás on nested cycles, J. Combin. Theory Ser. B 66 (1996), 38–43. 122CrossRefGoogle Scholar
Collins, K. L. and Heenehan, M. E., Constructing graphs with no immersion of large complete graphs, J. Graph Theory 77 (2014), 1–18. 102CrossRefGoogle Scholar
Conlon, D., Fox, J., and Sudakov, B., Cycle packing, Random Structures Algorithms 45 (2014), 608–626. 116, 117CrossRefGoogle Scholar
DeVos, M., Dvořák, Z., Fox, J., McDonald, J., Mohar, B., and Scheide, D., A minimum degree condition forcing complete graph immersion, Combinatorica 34 (2014), 279–298. 101, 102CrossRefGoogle Scholar
DeVos, M., Kawarabayashi, K.-I., Mohar, B., and Okamura, H., Immersing small complete graphs, Ars Math. Contemp. 3 (2010), 139–146. 102CrossRefGoogle Scholar
DeVos, M., McDonald, J., Mohar, B., and Scheide, D., Immersing complete digraphs, Europ. J. Combin. 33 (2012), 1294–1302. 103CrossRefGoogle Scholar
DeVos, M., McDonald, J., Mohar, B., and Scheide, D., A note on forbidding clique immersions, Electron. J. Combin. 20 (2013), P55. 103CrossRefGoogle Scholar
Draganić, N., Methuku, A., Munhá-Correia, D., and Sudakov, B., Cycles with many chords, arXiv:2306.09157 (2023). 111CrossRefGoogle Scholar
Dvǒrák, Z. and Yepremyan, L., Complete graph immersions and minimum degree, J. Graph Theory 88 (2018), 211–221. 101, 102CrossRefGoogle Scholar
Erdős, P., Some recent progress on extremal problems in graph theory, Congr. Numer. 14 (1975), 3–14. 104, 115, 121Google Scholar
Erdős, P., Some new and old problems on chromatic graphs, Combinatorics and applications, 1984, pp. 118–126. 104Google Scholar
Erdős, P. and Gallai, T., On maximal paths and circuits of graphs, Acta Math. Acad. Sci. Hungar. 10 (1959), 337–356. 95CrossRefGoogle Scholar
Erdős, P., Goodman, A. W., and Pósa, L., The representation of a graph by set intersections, Canad. J. Math. 18 (1966), 106–112. 116CrossRefGoogle Scholar
Erdős, P. and Hajnal, A., On chromatic number of graphs and set-systems, Acta Math. Acad. Sci. Hungar. 17 (1966), 61–99. 104CrossRefGoogle Scholar
Euler, L., Recherches sur un nouvelle espéce de quarrés magiques, Verhandelingen uitgegeven door het zeeuwsch Genootschap der Wetenschappen te Vlissingen (1782), 85–239. 124Google Scholar
Falgas-Ravry, V., Kittipassorn, T., Korándi, D., Letzter, S., and Narayanan, B., Separating path systems, J. Combin. 5 (2014), 335–354. 119Google Scholar
Fiorini, S., Joret, G., Theis, D. O., and Wood, D. R., Small minors in dense graphs, Europ. J. Combin. 33 (2012), 1226–1245. 99CrossRefGoogle Scholar
Fernańdez, I. Gil, Hyde, J., Liu, H., Pikhurko, O., and Wu, Z., Disjoint isomorphic balanced clique subdivisions, J. Combin. Theory Ser. B 161 (2023), 417–436. 107, 108CrossRefGoogle Scholar
Fernańdez, I. Gil, Kim, J., Kim, Y., and Liu, H., Nested cycles with no geometric crossings, Proc. Am. Math. Soc. Ser. B 9 (2022), 22–32. 122, 123CrossRefGoogle Scholar
Fernández, I. Gil and Liu, H., How to build a pillar: A proof of Thomasseńs conjecture, J. Combin. Theory Ser. B 162 (2023), 13–33. 122, 123CrossRefGoogle Scholar
Girão, A. and Letzter, S., Immersion of complete digraphs in Eulerian digraphs, Israel J. Math. (2023). 103CrossRefGoogle Scholar
Harary, F., Covering and packing in graphs, I., Annals of the New York Academy of Sciences 175 (1970), 198–205. 116CrossRefGoogle Scholar
Haslegrave, J., Hu, J., Kim, J., Liu, H., Luan, B., and Wang, G., Crux and long cycles in graphs, SIAM J. Discr. Math. 36 (2022), 2942–2958. 95, 96CrossRefGoogle Scholar
Haslegrave, J., Hyde, J., Kim, J., and Liu, H., Ramsey numbers of cycles versus general graphs, Forum Math. Sigma 11 (2023), e10. 123, 124CrossRefGoogle Scholar
Haslegrave, J., Kim, J., and Liu, H., Extremal density for sparse minors and subdivisions, Int. Math. Res. Not. 2022 (2022), 15505–15548. 96CrossRefGoogle Scholar
Hoory, S., Linial, N., and Wigderson, A., Expander graphs and their applications, Bull. Am. Math. Soc. 43 (2006), 439–561. 89CrossRefGoogle Scholar
Im, S., Kim, J., Kim, Y., and Liu, H., Crux, space constraints and subdivisions, arXiv:2207.06653 (2022). 95CrossRefGoogle Scholar
Janzer, B., Large hypergraphs without tight cycles, arXiv:2012.07726 (2020). 108, 110CrossRefGoogle Scholar
Janzer, O., Rainbow Turán number of even cycles, repeated patterns and blow-ups of cycles, Israel J. Math. 253 (2023), 813–840. 110, 111, 113CrossRefGoogle Scholar
Janzer, O. and Sudakov, B., On the Turán number of the hypercube, arXiv:2211.02015 (2022). 113Google Scholar
Jiang, T., Letzter, S., Methuku, A., and Yepremyan, L., Rainbow clique subdivisions, arXiv:2108.08814 (2021). 111Google Scholar
Jiang, T., Methuku, A., and Yepremyan, L., Rainbow turán number of clique subdivisions, Europ. J. Combin. 110 (2023), 103675. 110CrossRefGoogle Scholar
Keevash, P., Mubayi, D., Sudakov, B., and Verstraëte, J., Rainbow Turań problems, Combin. Probab. Comput. 16 (2007), 109–126. 110CrossRefGoogle Scholar
Kim, J., Lee, J., Liu, H., and Tran, T., Rainbow cycles in properly edge-colored graphs, (2022), arXiv:2211.03291. 113Google Scholar
Kim, J., Liu, H., Sharifzadeh, M., and Staden, K., Proof of Komlóśs conjecture on Hamiltonian subsets, Proc. London Math. Soc. 115 (2017), 974–1013. 119CrossRefGoogle Scholar
Komlós, J. and Szemerédi, E., Topological cliques in graphs, Combin. Probab. Comput. 3 (1994), 247–256. 89, 90, 91, 92, 93CrossRefGoogle Scholar
Komlós, J. and Szemerédi, E., Topological cliques in graphs II, Combin. Probab. Comput. 5 (1996), 79–90. 89, 91, 92, 93, 94, 104CrossRefGoogle Scholar
Krivelevich, M., Expanders - how to find them, and what to find in them, Surveys in Combinatorics 2019, 2019, pp. 115–142. 89CrossRefGoogle Scholar
Kühn, D. and Osthus, D., Large topological cliques in graphs without a 4-cycle, Combin. Probab. Comput. 13 (2004), 93–102. 93CrossRefGoogle Scholar
Kühn, D. and Osthus, D., Extremal connectivity for topological cliques in bipartite graphs, J. Combin. Theory Ser. B 96 (2006), 73–99. 93CrossRefGoogle Scholar
Lescure, F. and Meyniel, H., On a problem upon configurations contained in graphs with given chromatic number, Graph theory in memory of GA Dirac, Ann. Discrete Math., vol. 41, Elsevier, 1988, pp. 325–332. 102CrossRefGoogle Scholar
Letzter, S., Separating paths systems of almost linear size, arXiv:2211.07732 (2022). 118, 119Google Scholar
Letzter, S., Hypergraphs with no tight cycles, Proc. Am. Math. Soc. 151 (2023), 455–462. 109, 111, 115CrossRefGoogle Scholar
Liu, H., Robust sublinear expander, (2020), https://homepages.warwick.ac.uk/staff/H.Liu.9/sublinear-expander-note-July16.pdf. 89Google Scholar
Liu, H. and Montgomery, R., A proof of Mader’s conjecture on large clique subdivisions in C4-free graphs, J. London Math. Soc. 95 (2017), 203–222. 93, 94, 95, 97, 108CrossRefGoogle Scholar
Liu, H. and Montgomery, R., A solution to Erdős and Hajnal’s odd cycle problem, J. Am. Math. Soc. (2023). 104, 105, 107, 108, 123CrossRefGoogle Scholar
Liu, H., Wang, G., and Yang, D., Clique immersion in graphs without a fixed bipartite graph, J. Combin. Theory Ser. B 157 (2022), 346–365. 102CrossRefGoogle Scholar
Lochet, W., Immersion of transitive tournaments in digraphs with large minimum outdegree, J. Combin. Theory Ser. B 134 (2019), 350–353. 103CrossRefGoogle Scholar
Lovász, L., On covering of graphs, Theory of Graphs, Academic Press New York, 1968, pp. 231–236. 116, 118Google Scholar
Luan, B., Tang, Y., Wang, G., and Yang, D., Balanced subdivisions of cliques in graphs, Combinatorica (2023), 1–23. 107Google Scholar
Lubotzky, A., Expander graphs in pure and applied mathematics, Bull. Am. Math. Soc. 49 (2012), 113–162. 89CrossRefGoogle Scholar
Mader, W., An extremal problem for subdivisions of K5−, J. Graph Theory 30 (1999), 261–276. 933.0.CO;2-Z>CrossRefGoogle Scholar
Montgomery, R., Transversals in latin squares, Surveys in Combinatorics. 124Google Scholar
Montgomery, R., Logarithmically small minors and topological minors, J. London Math. Soc. 91 (2015), 71–88. 93, 94, 100, 101CrossRefGoogle Scholar
Montgomery, R., A proof of the Ryser-Brualdi-Stein conjecture for large even n, arXiv:2310.19779 (2023). 124Google Scholar
Moshkovitz, G. and Shapira, A., Decomposing a graph into expanding subgraphs, Random Structures Algorithms 52 (2018), 158–178. 92CrossRefGoogle Scholar
Mubayi, D., Pikhurko, O., and Sudakov, B., Hypergraph Turán problem: Some open questions, AIM workshop problem lists (2011), manuscript. 108Google Scholar
Pokrovskiy, A. and Sudakov, B., Ramsey goodness of cycles, SIAM J. Discr. Math. 34 (2020), 1884–1908. 123CrossRefGoogle Scholar
Ryser, H. J., Neuere probleme der kombinatorik, Vorträge über Kombinatorik, Oberwolfach 69 (1967), 91. 124Google Scholar
Sarnak, P. C., What is… an expander?, Not. Am. Math. Soc. 51 (2004), 762–763. 89Google Scholar
Shapira, A. and Sudakov, B., Small complete minors above the extremal edge density, Combinatorica 35 (2015), 75–94. 89, 99, 100, 108, 109CrossRefGoogle Scholar
Stein, S. K., Transversals of Latin squares and their generalizations, Pacific J. Math. 59 (1975), 567–575. 124CrossRefGoogle Scholar
Sudakov, B. and Tomon, I., The extremal number of tight cycles, Int. Math. Res. Not. 2022 (2022), 9663–9684. 108, 109, 110, 111CrossRefGoogle Scholar
Szemerédi, E., Regular partitions of graphs, Orsay, 1975. 92Google Scholar
Thomason, A., The extremal function for complete minors, J. Combin. Theory Ser. B 81 (2001), 318–338. 99CrossRefGoogle Scholar
Thomassen, C., Subdivisions of graphs with large minimum degree, J. Graph Theory 8 (1984), 23–28. 105CrossRefGoogle Scholar
Thomassen, C., Configurations in graphs of large minimum degree, connectivity, or chromatic number, Annals of the New York Academy of Sciences 555 (1989), 402–412. 122CrossRefGoogle Scholar
Tomon, I., Robust (rainbow) subdivisions and simplicial cycles, arXiv:2201.12309 (2022). 111, 112, 114, 115, 118Google Scholar
Tuza, Zs., Exponentially many distinguishable cycles in graphs, J. Combin. Infor. Sys. Sci 15 (1990), 281–285. 119Google Scholar
Tuza, Zs., Unsolved combinatorial problems, Part I, BRICS Lecture Series LS-01-1 (2001). 119Google Scholar
Tuza, Zs., Problems on cycles and colorings, Discr. Math. 313 (2013), 2007–2013. 119CrossRefGoogle Scholar
Verstraëte, J., Extremal problems for cycles in graphs, Recent trends in combinatorics, Springer, 2016, pp. 83–116. 108CrossRefGoogle Scholar
Vizing, V. G., On an estimate of the chromatic class of a p-graph, Discret. Analiz. 3 (1964), 25–30. 116Google Scholar
Wang, Y., Balanced subdivisions of a large clique in graphs with high average degree, arXiv:2107.06583 (2021). 107Google Scholar
Wang, Y., Rainbow clique subdivisions, (2022), arXiv:2204.08804. 111, 112Google Scholar
Wanless, I. M., Transversals in latin squares: A survey, (2011), 403–437. 124Google Scholar

Save book to Kindle

To save this book to your Kindle, first ensure [email protected] is added to your Approved Personal Document E-mail List under your Personal Document Settings on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part of your Kindle email address below. Find out more about saving to your Kindle.

Note you can select to save to either the @free.kindle.com or @kindle.com variations. ‘@free.kindle.com’ emails are free but can only be saved to your device when it is connected to wi-fi. ‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.

Find out more about the Kindle Personal Document Service.

Available formats
×

Save book to Dropbox

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Dropbox.

Available formats
×

Save book to Google Drive

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Google Drive.

Available formats
×