COMBINATORICA is an international journal of
the Bolyai Mathematical Society, Hungary,
published jointly by
the Bolyai Mathematical Society and Springer.

COMBINATORICA publishes research papers in a variety of areas of combinatorics and the theory of computing, with particular emphasis on general techniques and unifying principles.
Coverage in COMBINATORICA includes:

• combinatorial structures (graphs, matroids, hypergraphs, designs, permutation groups);
• combinatorial optimization;
• combinatorial aspects of geometry and number theory;
• algorithms in combinatorics and related fields;
• computational complexity theory;
• randomization and explicit construction in combinatorics and algorithms.

Six issues appear each year. A total of 30-40 papers are accepted for publication out of roughly 300 submissions per year.

Editors-in-Chief

Imre Bárány, Rényi Institute of Mathematics, Budapest
József Solymosi, University of British Columbia

Founding editors

László Babai, University of Chicago
László Lovász, ELTE Eötvös University, Budapest

Managing editors

Lilla Tóthmérész, ELTE Eötvös University, Budapest
Viktor Harangi, Rényi Institute of Mathematics, Budapest

Honorary editors

Gyula O.H. Katona, Rényi Institute of Mathematics, Budapest
Miklós Simonovits, Rényi Institute of Mathematics, Budapest
Vera T. Sós, Rényi Institute of Mathematics, Budapest
Endre Szemerédi, Rényi Institute of Mathematics, Budapest

Board of editors

Miklós Abért, Rényi Institute of Mathematics, Budapest
Noga Alon, Tel Aviv University & Princeton University
Anders Björner, Royal Institute of Technology (KTH), Stockholm
Aart Blokhuis, Eindhoven University of Technology
Béla Bollobás, University of Cambridge & The University of Memphis
András Frank, ELTE Eötvös University, Budapest
Peter Frankl, Rényi Institute of Mathematics, Budapest
Zoltán Füredi, Rényi Institute of Mathematics, Budapest
W. Timothy Gowers, University of Cambridge
Péter Komjáth, ELTE Eötvös University, Budapest
Daniela Kühn, University of Birmingham
Nathan Linial, The Hebrew University of Jerusalem
Dániel Marx, Max Planck Institute for Informatics
Jaroslav Nešetřil, Charles University, Prague
János Pach, Rényi Institute of Mathematics, Budapest & EPFL, Lausenne
Alexander A. Razborov, University of Chicago & Steklov Math. Inst., Moscow
Vojtěch Rödl, Emory University, Atlanta
Imre Z. Ruzsa, Rényi Institute of Mathematics, Budapest
Alexander Schrijver, CWI Amsterdam & University of Amsterdam
Paul D. Seymour, Princeton University
Benny Sudakov, ETH, Zürich
Tamás Szőnyi, ELTE Eötvös University, Budapest
Gábor Tardos, Rényi Institute of Mathematics, Budapest
Van H. Vu, Yale University
Avi Wigderson, Institute for Advanced Study, Princeton

Instructions for authors

1. Submission. Manuscripts should be submitted via the editorial system EditFlow. Please use the following link: https://ef.msp.org/submit/combinatorica
2. Length. The length of the paper should not exceed 30 pages (in 11-point LaTeX format on US letter-size paper with 1-inch margins). Authors of longer papers are advised to submit a 30-page version to COMBINATORICA with a link to a full version on arXiv.
3. Notes. Short notes are welcome and processed in an expedited fashion.
4. Form of the manuscript. The manuscript should contain a brief abstract. In a paper divided into sections, it is desirable to number theorems, lemmas, definitions, corollaries, examples, etc. consecutively using double Arabic numerals. (E.g., Section 3 may start with Definition 3.1 followed by Remark 3.2 and Theorem 3.3).
5. Style. Clarity of the presentation is paramount. The results should be made accessible to the non-specialist reader. Authors should give clear motivation, background, and exact references.
6. Final version. If the paper is accepted, the following should be submitted.
   • The final version of the paper in TeX/LaTeX format. It is best to avoid using complicated macros or non-standard packages and fonts as they tend to be in conflict with the journal format. Furthermore, it significantly simplifies the typesetting process if unused packages and definitions are deleted by the author. In general, a plain "vanilla" version is the least prone to errors when adapting it to the journal format.
   • Each figure in a separate file (in a vector graphic format that can handle embedded fonts such as EPS or vector PDF). Note that while the online version is published in color, the print version is converted to grayscale. Ensure that the figure can still be understood even when it is printed in grayscale. For example, avoid referring to colors in the text.
   • Affiliation and e-mail address for each author.
   • Abbreviated title (at most 35 characters), to be used as the running head.
   • Mathematics Subject Classification codes (primary and secondary).
7. Reprints. 50 Reprints are provided free of charge upon request. Additional reprints may be ordered.

Papers to appear in upcoming issues

Tom Kelly, Luke Postle
On the density of critical graphs with no large cliques

Simón Piga, Nicolás Sanhueza-Matamala
Cycle decompositions in 3-uniform hypergraphs

Zilin Jiang, Jonathan Tidor, Yuan Yao, Shengtong Zhang, Yufei Zhao
Spherical two-distance sets and eigenvalues of signed graphs

Daniel Glasscock, Joel Moreira, Florian Richter
A combinatorial proof of a sumset conjecture of Furstenberg

Slawomir J. Solecki
Dual Ramsey theorem for trees

Freddie Illingworth
Minimum degree stability of H-free graphs

Assaf Rinot, Jing Zhang
Strongest transformations

Jacob Fox, János Pach, Andrew Suk
Sunflowers in set systems of bounded dimension

Julien Bensmail, Hervé Hocquard, Dimitri Lajou, Éric Sopena
A proof of the Multiplicative 1-2-3 Conjecture

Sean Eberhard
Hamming sandwiches

Andries E. Brouwer, Ferdinand Ihringer, William M. Kantor
Strongly regular graphs satisfying the 4-vertex condition

Lukas Kühne
The Universality of the Resonance Arrangement and its Betti Numbers

Ilya D. Shkredov
On an application of higher energies to Sidon sets

Chaoping Xing, Chen Yuan
Beating the probabilistic lower bound on q-perfect hashing

Alex Scott, Paul Seymour, Sophie Spirkl
Polynomial bounds for chromatic number. IV. A near-polynomial bound for excluding the five-vertex path

He Guo, Kalen Patton, Lutz Warnke
Prague Dimension of Random Graphs

Evita Nestoridi, Peter Sarnak
Bounded cutoff window for the non-backtracking random walk on Ramanujan Graphs

Isabel Hubard, Elías Mochán, Antonio Montero
Voltage operations on maniplexes, polytopes and maps

Domagoj Bradac, Lior Gishboliner, Oliver Janzer, Benny Sudakov
Asymptotics of the hypergraph bipartite Turán problem

Jun Gao, Jie Ma
Tight bounds towards a conjecture of Gallai

Karthekeyan Chandrasekaran, Chandra Chekuri
Min-max Partitioning of Hypergraphs and Symmetric Submodular Functions

Matias von Bell, Rafael S. González D'León, Francisco A. Mayorga Cetina, Martha Yip
A unifying framework for the $\nu$-Tamari lattice and principal order ideals in Young's lattice

Matija Bucic, Benny Sudakov
Large independent sets from local considerations

Richard Lang, Luke Postle
An Improved Bound for the Linear Arboricity Conjecture

Alex Scott, Paul Seymour, Sophie Spirkl
Pure pairs. V. Excluding some long subdivision

Md Lutfar Rahman, Thomas Watson
6-Uniform Maker-Breaker Game Is PSPACE-Complete

Ron Rosenthal, Lior Tenenbaum
Simplicial spanning trees in random Steiner complexes

Ralph Keusch
Vertex-coloring graphs with 4-edge-weightings

Marcin Briański, Gwenaël Joret, Konrad Majewski, Piotr Micek, Michał Seweryn, Roohani Sharma
Treedepth vs circumference

Asaf Ferber, Liam Hardiman, Adva Mond
Counting Hamilton Cycles in Dirac Hypergraphs

Giovanni Longobardi, Giuseppe Marino, Rocco Trombetti, Yue Zhou
A large family of maximum scattered linear sets and MRD codes

Sergey Avvakumov, Roman Karasev, Arkadiy Skopenkov
Stronger counterexamples to the topological Tverberg conjecture

Eric Naslund
Upper Bounds For Families Without Weak Delta-Systems

Volume 42, Supplement Issue 2, 2022

Zach Hunter
Improved Lower Bounds for Van Der Waerden Numbers
Pages 1231-1252  |  DOI:10.1007/s00493-022-4925-2

Yoichi Iwata, Yutaro Yamaguchi
Finding a Shortest Non-Zero Path in Group-Labeled Graphs
Pages 1253-1282  |  DOI:10.1007/s00493-021-4736-x

Tamás Kálmán, Seunghun Lee, Lilla Tóthmérész
The Sandpile Group of a Trinity and a Canonical Definition for the Planar Bernardi Action
Pages 1283-1316  |  DOI:10.1007/s00493-021-4798-9

Vojtěch Kaluža, Martin Tancer
Even Maps, the Colin de Verdière Number and Representations of Graphs
Pages 1317-1345  |  DOI:10.1007/s00493-021-4443-7

Hemanshu Kaul, Benjamin Reiniger
A Generalization of the Graph Packing Theorems of Sauer-Spencer and Brandt
Pages 1347-1356  |  DOI:10.1007/s00493-022-4932-3

Hong Liu, Péter Pál Pach, Csaba Sándor
Polynomial Schur’s Theorem
Pages 1357-1384  |  DOI:10.1007/s00493-021-4815-z

Matei Mandache
Finding Certain Arithmetic Progressions in 2-Coloured Cyclic Groups
Pages 1385-1408  |  DOI:10.1007/s00493-022-4901-x

Tomáš Masařík, Irene Muzi, Marcin Pilipczuk, Paweł Rzążewski, Manuel Sorge
Packing Directed Cycles Quarter- and Half-Integrally
Pages 1409-1438  |  DOI:10.1007/s00493-021-4743-y

Andrew Newman
A Lower Bound on the Number of Homotopy Types of Simplicial Complexes on N Vertices
Pages 1439-1450  |  DOI:10.1007/s00493-022-4877-6

Kenta Ozeki
Kempe Equivalence Classes of Cubic Graphs Embedded on the Projective Plane
Pages 1451-1480  |  DOI:10.1007/s00493-021-4330-2

Hector Pasten
On the Chevalley-Warning Theorem When the Degree Equals the Number of Variables
Pages 1481-1486  |  DOI:10.1007/s00493-022-5043-x

Jakub Przybyło
The 1-2-3 Conjecture Holds for Graphs with Large Enough Minimum Degree
Pages 1487-1512  |  DOI:10.1007/s00493-021-4822-0

Chao Shi, Peter Frankl, Jianguo Qian
On Non-Empty Cross-Intersecting Families
Pages 1513-1525  |  DOI:10.1007/s00493-021-4839-4

Volume 42, Supplement Issue 1, 2022

Ron Aharoni, Eli Berger, Joseph Briggs, Erel Segal-Halevi, Shira Zerbib
Fractionally Balanced Hypergraphs and Rainbow KKM Theorems
Pages 913-951  |  DOI:10.1007/s00493-021-4808-y

Daniele Bartoli, Nicola Durante
On the Classification of Low-Degree Ovoids of Q(4,q)
Pages 953-969  |  DOI:10.1007/s00493-022-5005-3

Amitabh Basu, Michele Conforti, Marco Di Summa, Hongyi Jiang
Complexity of Branch-and-Bound and Cutting Planes in Mixed-Integer Optimization — II
Pages 971-996  |  DOI:10.1007/s00493-022-4884-7

Manuel Bodirsky, Florian Starke
Maximal Digraphs with Respect to Primitive Positive Constructability
Pages 997-1010  |  DOI:10.1007/s00493-022-4918-1

Swee Hong Chan, Igor Pak, Greta Panova
Log-Concavity in Planar Random Walks
Pages 1011-1026  |  DOI:10.1007/s00493-021-4860-7

Gábor Damásdi, Dömötör Pálvölgyi
Realizing an m-Uniform Four-Chromatic Hypergraph with Disks
Pages 1027-1048  |  DOI:10.1007/s00493-021-4846-5

James Davies
Vertex-Minor-Closed Classes are χ-Bounded
Pages 1049-1079  |  DOI:10.1007/s00493-021-4767-3

Zdeněk Dvořák, Luke Postle
On Decidability of Hyperbolicity
Pages 1081-1098  |  DOI:10.1007/s00493-022-4891-8

Ronen Eldan
Second-Order Bounds on Correlations Between Increasing Families
Pages 1099-1118  |  DOI:10.1007/s00493-021-4417-9

Nóra Frankl, Andrey Kupavskii
Almost Sharp Bounds on the Number of Discrete Chains in the Plane
Pages 1119-1143  |  DOI:10.1007/s00493-021-4853-6

Lior Gishboliner, Raphael Steiner, Tibor Szabó
Oriented Cycles in Digraphs of Large Outdegree
Pages 1145-1187  |  DOI:10.1007/s00493-021-4750-z

Rani Hod, Michael Krivelevich, Tobias Müller, Alon Naor, Nicholas Wormald
Component Games on Random Graphs
Pages 1189-1229  |  DOI:10.1007/s00493-022-5036-9

Volume 42, Issue 6, 2022

Stefan Ehard, Felix Joos
A Short Proof of the Blow-Up Lemma for Approximate Decompositions
Pages 771-819  |  DOI:10.1007/s00493-020-4640-9

Gábor Elek, Gábor Tardos
Convergence and Limits of Finite Trees
Pages 821-852  |  DOI:10.1007/s00493-021-4445-5

Jeff Kahn, Jinyoung Park
The Number of Maximal Independent Sets in the Hamming Cube
Pages 853-880  |  DOI:10.1007/s00493-021-4729-9

Hadi Kharaghani, Thomas Pender, Sho Suda
A Family of Balanced Generalized Weighing Matrices
Pages 881-894  |  DOI:10.1007/s00493-021-4774-4

Abhishek Methuku, István Tomon
Bipartite Turán Problems for Ordered Graphs
Pages 895-911  |  DOI:10.1007/s00493-021-4296-0

Top 20 most-cited papers (1981-1999)

Lubotzky, A.; Phillips, R.; Sarnak, P.
Ramanujan graphs
Volume 8 (1988), Issue 3, 261–277

Karmarkar, N.
A new polynomial-time algorithm for linear programming
Volume 4 (1984), Issue 4, 373–395

Grötschel, M.; Lovász, L.; Schrijver, A.
The ellipsoid method and its consequences in combinatorial optimization
Volume 1 (1981), Issue 2, 169–197

Alon, N.
Eigenvalues and expanders
Volume 6 (1986), Issue 2, 83–96

Linial, Nathan; London, Eran; Rabinovich, Yuri
The geometry of graphs and some of its algorithmic applications
Volume 15 (1995), Issue 2, 215–245

Alon, N.; Tarsi, M.
Colorings and orientations of graphs
Volume 12 (1992), Issue 2, 125–134

Chung, F. R. K.; Graham, R. L.; Wilson, R. M.
Quasi-random graphs
Volume 9 (1989), Issue 4, 345–362

Szemerédi, Endre; Trotter, William T., Jr.
Extremal problems in discrete geometry
Volume 3 (1983), Issue 3-4, 381–392

de Fraysseix, H.; Pach, J.; Pollack, R.
How to draw a planar graph on a grid
Volume 10 (1990), Issue 1, 41–51

Frankl, P.; Wilson, R. M.
Intersection theorems with geometric consequences
Volume 1 (1981), Issue 4, 357–368

Godsil, C. D.
On the full automorphism group of a graph
Volume 1 (1981), Issue 3, 243–256

Füredi, Z.; Komlós, J.
The eigenvalues of random symmetric matrices
Volume 1 (1981), Issue 3, 233–241

Frieze, Alan; Kannan, Ravi
Quick approximation to matrices and applications
Volume 19 (1999), Issue 2, 175–220

Komlós, János; Sárközy, Gábor N.; Szemerédi, Endre
Blow-up lemma
Volume 17 (1997), Issue 1, 109–123

Wilson, Richard M.
The exact bound in the Erdős-Ko-Rado theorem
Volume 4 (1984), Issue 2-3, 247–257

Pach, János; Tóth, Géza
Graphs drawn with few crossings per edge
Volume 17 (1997), Issue 3, 427–439

Babai, L.
On Lovász' lattice reduction and the nearest lattice point problem
Volume 6 (1986), Issue 1, 1–13

Mulmuley, Ketan; Vazirani, Umesh V.; Vazirani, Vijay V.
Matching is as easy as matrix inversion
Volume 7 (1987), Issue 1, 105–113

Raghavan, P.; Thompson, C. D.
Randomized rounding: a technique for provably good algorithms and algorithmic proofs
Volume 7 (1987), Issue 4, 365–374

Robertson, Neil; Seymour, Paul; Thomas, Robin
Hadwiger's conjecture for K6-free graphs
Volume 13 (1993), Issue 3, 279–361

Top 10 most-cited papers (2000-2009)

Jain, Kamal
A factor 2 approximation algorithm for the generalized Steiner network problem
Volume 21 (2001), Issue 1, 39–60

Bollobás, Béla; Riordan, Oliver
The diameter of a scale-free random graph
Volume 24 (2004), Issue 1, 5–34

Chudnovsky, Maria; Cornuéjols, Gérard; Liu, Xinming; Seymour, Paul; Vušković, Kristina
Recognizing Berge graphs
Volume 25 (2005), Issue 2, 143–186

Alon, Noga; Fischer, Eldar; Krivelevich, Michael; Szegedy, Mario
Efficient testing of large graphs
Volume 20 (2000), Issue 4, 451–476

Tao, Terence
Product set estimates for non-commutative groups
Volume 28 (2008), Issue 5, 547–594

Linial, Nathan; Meshulam, Roy
Homological connectivity of random 2-complexes
Volume 26 (2006), Issue 4, 475–487

Kim, Jeong Han; Vu, Van H.
Concentration of multivariate polynomials and its applications
Volume 20 (2000), Issue 3, 417–434

Thomassé, Stéphan; Yeo, Anders
Total domination of graphs and small transversals of hypergraphs
Volume 27 (2007), Issue 4, 473–487

Goldreich, Oded; Goldwasser, Shafi; Lehman, Eric; Ron, Dana; Samorodnitsky, Alex
Testing monotonicity
Volume 20 (2000), Issue 3, 301–337

Kühn, Daniela; Osthus, Deryk
The minimum degree threshold for perfect graph packings
Volume 29 (2009), Issue 1, 65–107

Top 10 most-cited papers (2010-2019)

Sebő, András; Vygen, Jens
Shorter tours by nicer ears: 7/5-approximation for the graph-TSP, 3/2 for the path version, and 4/3 for two-edge-connected subgraphs
Volume 34 (2014), Issue 5, 597–629

Petridis, Giorgis
New proofs of Plünnecke-type estimates for product sets in groups
Volume 32 (2012), Issue 6, 721–733

Tóth, Csaba D.
The Szemerédi-Trotter theorem in the complex plane
Volume 35 (2015), Issue 1, 95–126

Ceballos, Cesar; Santos, Francisco; Ziegler, Günter M.
Many non-equivalent realizations of the associahedron
Volume 35 (2015), Issue 5, 513–551

Dujmović, Vida; Joret, Gwenaël; Kozik, Jakub; Wood, David R.
Nonrepetitive colouring via entropy compression
Volume 36 (2016), Issue 6, 661–686

Chudnovsky, Maria; Seymour, Paul
The three-in-a-tree problem
Volume 30 (2010), Issue 4, 387–417

Füredi, Zoltán; Jiang, Tao; Seiver, Robert
Exact solution of the hypergraph Turán problem for k-uniform linear paths
Volume 34 (2014), Issue 3, 299–322

Raigorodskii, A. M.
On the chromatic numbers of spheres in Rn
Volume 32 (2012), Issue 1, 111–123

Cilleruelo, Javier
Combinatorial problems in finite fields and Sidon sets
Volume 32 (2012), Issue 5, 497–511

Devos, Matt; Dvořák, Zdeněk; Fox, Jacob; McDonald, Jessica; Mohar, Bojan; Scheide, Diego
A minimum degree condition forcing complete graph immersion
Volume 34 (2014), Issue 3, 279–298

Rudnev, Misha
On the number of incidences between points and planes in three dimensions
Volume 38 (2018), Issue 1, 219–254