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.

**Imre Bárány**, Rényi Institute of Mathematics, Budapest

**József Solymosi**, University of British Columbia

**László Babai**, University of Chicago

**László Lovász**, ELTE Eötvös University, Budapest

**Lilla Tóthmérész**, ELTE Eötvös University, Budapest

**Viktor Harangi**, Rényi Institute of Mathematics, Budapest

**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

**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

Papers can be submitted to COMBINATORICA
via EditFlow.

Please **read the instructions below** before submission.

*Submission.*Manuscripts should be submitted via the editorial system EditFlow. Please use the following link: https://ef.msp.org/submit/combinatorica*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.*Notes.*Short notes are welcome and processed in an expedited fashion.*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).*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.*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).

*Reprints.*50 Reprints are provided free of charge upon request. Additional reprints may be ordered.

The papers below are accepted for publication in COMBINATORICA and will appear in upcoming issues. Some have already been published electronically and can be accessed on the Springer website: Online First articles.

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**

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

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

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

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

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

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

If you have any question, please do not hesitate to contact us at

Note that papers can **no longer** be submitted via e-mail:

submission information.

Postal address:

*COMBINATORICA
Rényi Institute of Mathematics
Reáltanoda u. 13-15.
H-1053, Budapest, Hungary*

For information on journal subscription,

please visit
the Springer website.

For orders within Hungary, please contact the

Bolyai Mathematical Society.