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 editor

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

Jakub Byszewski, Jakub Konieczny, Elżbieta Krawczyk
Substitutive systems and a finitary version of Cobham's theorem

David Conlon, Oliver Janzer, Joonkyung Lee
More on the extremal number of subdivisions

Dana Bartosova, Jordi Lopez-Abad, Martino Lupini, Brice Mbombo
The Ramsey properties for Grassmannians over R, C

Gabriel Currier
New results on simplex-clusters in set systems

Shaofei Du, Klavdija Kutnar, Dragan Marusic
Resolving the Hamiltonian problem for vertex-transitive graphs of order a product of two primes

Venkatesan Guruswami, Nicolas Resch, Chaoping Xing
Lossless Dimension Expanders via Linearized Polynomials and Subspace Designs

Bence Csajbók, Zsuzsa Weiner
Generalizing Korchmáros-Mazzocca arcs

Tomasz Schoen
A Diophantine Ramsey theorem

Daniel Kráľ, Jonathan A. Noel, Sergey Norin, Jan Volec, Fan Wei
Non-bipartite k-common graphs

Jie Ma, Tianchi Yang
Counting critical subgraphs in k-critical graphs

Primož Potočnik, Pablo Spiga
On the number of fixed points of automorphisms of vertex-transitive graphs

Daniel Di Benedetto, József Solymosi, Ethan White
On the directions determined by a Cartesian product in an affine Galois plane

Noga Alon
Explicit expanders of every degree and size

Tao Feng, Weicong Li
On transitive ovoids of finite Hermitian polar spaces

Péter Vrana
Probabilistic refinement of the asymptotic spectrum of graphs

Luke Postle, Evelyne Smith-Roberge
On The Density of C_7-Critical Graphs

Jan Grebik, Israel Rocha
Fractional isomorphism of graphons

Gary Greaves, Jeven Syatriadi, Pavlo Yatsyna
Equiangular lines in low dimensional Euclidean spaces

François Hennecart, Gyan Prakash, E. Pramod
On thin sum-product bases

Tomasz Łuczak, Joanna Polcyn, Christian Reiher
On the Ramsey-Turán density of triangles

Antonio Girao, Kamil Popielarz, Richard Snyder
(2k+1)-connected tournaments with large minimum out-degree are k-linked

Sergey Norin, Zi-Xia Song
A new upper bound on the chromatic number of graphs with no odd K_t minor

Jacob Fox, János Pach, Andrew Suk
Bounded VC-dimension implies the Schur-Erdős conjecture

Dávid Matolcsi, Imre Ruzsa, George Shakan, Dmitrii Zhelezov
An Analytic Approach to the Cardinalities of Sumsets

Tai Do Duc
New Constructions of Group-Invariant Butson Hadamard Matrices

David Conlon, Jacob Fox, Yuval Wigderson
Ramsey numbers of books and quasirandomness

Zhicong Lin, Dongsu Kim
A combinatorial bijection on k-noncrossing partition

Alexandr Polyanskii
A cap covering theorem

Dhruv Mubayi, Xizhi Liu
A hypergraph Turán problem with no stability

Brandon Hanson, Oliver Roche-Newton, Misha Rudnev
Higher convexity and iterated sum sets

Vida Dujmović, David Eppstein, Robert Hickingbotham, Pat Morin, David R. Wood
Stack-Number is not Bounded by Queue-Number

Tony Huynh, Gwenaël Joret, Piotr Micek, Michał Seweryn, Paul Joseph Wollan
Excluding a ladder

Sergey Avvakumov, Karim Alexander Adiprasito, Roman Karasev
A subexponential size triangulation of RP^n

Arnold Neumaier, Safet Penjić
On bounding the diameter of a distance-regular graph

Pavel Pudlak, Vojtěch Rödl
Extractors for small zero-fixing sources

Jana Cslovjecsek, Romanos Diogenes Malikiosis, Márton Naszódi, Matthias Schymura
Computing the covering radius of a polytope with an application to lonely runners

Felix Joos, Stefan Ehard
A short proof of the blow-up lemma for approximate decompositions

Sean Eberhard
The characteristic polynomial of a random matrix

Martin Balko, David Chodounský, Jan Hubička, Matěj Konečný, Lluís Vena
Big Ramsey degrees of 3-uniform hypergraphs are finite

Drago Bokal, Zdenek Dvorak, Petr Hlineny, Jesus Leanos, Bojan Mohar, Tilo Wiedera
Bounded degree conjecture holds precisely for c-crossing-critical graphs with c<=12

Maxime Fortier Bourque, Bram Petri
Kissing numbers of regular graphs

Bodo Lass
Calculating the Euler characteristic of the moduli space of curves

Tsz Ho Chan, Jared Lichtman, Carl Pomerance
On the critical exponent for k-primitive sets

Gábor Kun
On Gardner's conjecture

Daniele Bartoli, Giacomo Micheli
Algebraic constructions of complete m-arcs

Jeff Kahn, Jinyoung Park
The number of maximal independent sets in the Hamming cube

Yoichi Iwata, Yutaro Yamaguchi
Finding a Shortest Non-zero Path in Group-Labeled Graphs

Volume 41, Issue 3, 2021

Nicolas Bousquet, Wouter Cames Van Batenburg, Louis Esperet, Gwenaël Joret, William Lochet, Carole Muller, François Pirot
Packing and Covering Balls in Graphs Excluding a Minor
Pages 299-318  |  DOI:10.1007/s00493-020-4423-3

Matija Bucić, Dániel Korándi, Benny Sudakov
Covering Graphs by Monochromatic Trees and Helly-Type Results for Hypergraphs
Pages 319-352  |  DOI:10.1007/s00493-020-4292-9

Michael Capalbo
An Explicit Infinite Family of M-Vertex Graphs with Maximum Degree K and Diameter [1+o(1)]logK−1M for Each K − 1 a Prime Power
Pages 353-378  |  DOI:10.1007/s00493-020-3989-0

Maria Chudnovsky, Alex Scott, Paul Seymour, Sophie Spirkl
Pure Pairs. II. Excluding All Subdivisions of A Graph
Pages 379-405  |  DOI:10.1007/s00493-020-4024-1

Vincent Froese, Malte Renken
Persistent Graphs and Cyclic Polytope Triangulations
Pages 407-423  |  DOI:10.1007/s00493-020-4369-5

Dragan Mašulović, Branislav Šobot
Countable Ordinals and Big Ramsey Degrees
Pages 425-446  |  DOI:10.1007/s00493-020-4192-z

Volume 41, Issue 2, 2021

Henning Bruhn, Matthias Heinlein, Felix Joos
The Edge-Erdős-Pósa Property
Pages 147-173  |  DOI:10.1007/s00493-020-4071-7

Matija Bucić, Eoin Long, Asaf Shapira, Benny Sudakov
Tournament Quasirandomness from Local Counting
Pages 175-208  |  DOI:10.1007/s00493-020-4371-y

Karthik Chandrasekha, Richard Ehrenborg
Bounds on the Number of Compatible k-Simplices Matching the Orientation of the (k−1)-Skeleton of a Simplex
Pages 209-236  |  DOI:10.1007/s00493-020-4220-z

Bence Csajbók, Giuseppe Marino, Olga Polverino, Ferdinando Zullo
Generalising the Scattered Property of Subspaces
Pages 237-262  |  DOI:10.1007/s00493-020-4347-y

Romain Tessera, Matthew C. H. Tointon
A Finitary Structure Theorem for Vertex-Transitive Graphs of Polynomial Growth
Pages 263-298  |  DOI:10.1007/s00493-020-4295-6

Volume 41, Issue 1, 2021

Maria Chudnovsky, Alex Scott, Paul Seymour
Detecting a Long Odd Hole
Pages 1-30  |  DOI:10.1007/s00493-020-4301-z

Joshua Erde, J. Pascal Gollin, Attila Joó, Paul Knappe, Max Pitz
Base Partition for Mixed Families of Finitary and Cofinitary Matroids
Pages 31-52  |  DOI:10.1007/s00493-020-4422-4

Limor Friedman, Michael Krivelevich
Cycle Lengths in Expanding Graphs
Pages 53-74  |  DOI:10.1007/s00493-020-4434-0

Yael Tauman Kalai, Ilan Komargodski, Ran Raz
A Lower Bound for Adaptively-Secure Collective Coin Flipping Protocols
Pages 75-98  |  DOI:10.1007/s00493-020-4147-4

Ashwin Sah
Improving the 1/3−2/3 Conjecture for Width Two Posets
Pages 99-126  |  DOI:10.1007/s00493-020-4091-3

Lorenzo Venturello, Hailun Zheng
A New Family of Triangulations of RP^d
Pages 127-146  |  DOI:10.1007/s00493-020-4351-2

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