Papers

The Brown–Erdős–Sós problem is a fundamental problem in sparse hypergraph Turán theory. For integers $r,k\ge 2$ and $s\ge r$, the problem asks for the maximum number $f^{(r)}(n;s,k)$ of edges in an $n$-vertex $r$-uniform hypergraph containing no $k$ distinct edges spanning at most $s$ vertices. In 1971, Brown, Erdős, and Sós proved that $f^{(r)}\bigl(n;(r-t)k+t,k\bigr)=\Theta(n^t)$ for all $r>t\ge 2$ and $k\ge 2$. However, the existence and the value of the leading coefficient have remained largely open. We determine the coefficient $\pi(r,t,k):=\lim_{n\to\infty}n^{-t}f^{(r)}\bigl(n;(r-t)k+t,k\bigr)$ for every such $r,t,k$, except when $(r,t)=(3,2)$ and $k\ge 4$ is even. In particular, \[ \pi(r,t,k) = \begin{cases} \frac{2}{t!\bigl(2\binom{r}{t}-1\bigr)}, & \text{if $k$ is odd},\\ \frac{1}{t!\binom{r}{t}}, & \text{if $k$ is even and $r\ge4$}. \end{cases} \] Surprisingly, for $r\ge4$, the limit $\pi(r,t,k)$ depends on $k$ only through its parity, not its value. For the remaining case, we prove that $\pi(3,2,k)>1/6$ for all even $k\ge 4$, showing that the natural packing construction is never asymptotically optimal. As an application, we extend a connection of Bennett, Cushman, and Dudek to arbitrary uniformity to resolve several cases of the Erdős–Gyárfás–Shelah generalized Ramsey problem.

We study local systems on line arrangements for which no admissibility conditions are satisfied. In doing so we demonstrate the existence of these anti-admissible objects in both the finite and infinite setting and discuss their relation to the combinatorial data of arrangements. We also observe the connection between anti-admissibility and smooth branched coverings and how this connection is related to the branch set being minimal in one sense and maximal in another.

Unit interval graphs admit a classical Catalan encoding by area sequences, or equivalently by Dyck paths. We introduce a new statistic on these graphs, called peak-nesting, defined as the largest number of peak-cliques containing a common vertex. Through the correspondence with area sequences, peak-nesting also defines a new statistic on Dyck paths. We construct a bijection between Dyck paths and bicolored Motzkin paths which simultaneously records peak-nesting and the number of peaks. This yields a refinement of Touchard's identity, coefficient formulas involving Dyck paths of given height, and new combinatorial interpretations for several sequences recorded in the OEIS. We study the peak and peak-nesting polynomials over all unit interval graphs and over the subclasses of connected, Abelian, $2$-nested, and reduced unit interval graphs. For these families we obtain closed formulas, recurrences, and, for the symmetric cases, nonnegative expansions in the gamma-basis with explicit combinatorial interpretations. We also investigate questions regarding the location of zeros and the log-concavity of the corresponding coefficient sequences: some of the polynomial families form generalized Sturm sequences, whereas others fail to be real-rooted but appear nevertheless to have log-concave coefficients. Finally, we relate the peak-clique presentation of a unit interval graph to lattice path matroids.

Beke, Csáji, Csikvári, and Pituk showed that the Merino–Welsh quotient $\Phi(M)=T_M(1,1)^2/(T_M(2,0)T_M(0,2))$ can be arbitrarily large, so the multiplicative Merino-Welsh inequality fails for matroids in general. We show that $\Phi$ is uniformly bounded on the class of matroids whose cyclic-flat lattice avoids any fixed finite poset $P$ as an induced subposet. We further prove $\Phi(M)\leq1$ for matroids of cyclic width at most $7$, cyclic height at most $6$, and for loop- and coloop-free $4$-paving or $4$-copaving matroids.

The Erdős-Rogers function $f_{\ell,s}(n)$ is the largest order of a $K_\ell$-free induced subgraph guaranteed to exist in every $K_s$-free graph on $n$ vertices. While this function is well understood for $s=\ell+1$, the case where $s$ is much larger than $\ell$ has remained wide open. A long-standing lower bound of Sudakov states that $f_{\ell,s}(n)\geq n^{\frac{\ell}{2s}+O_\ell(s^{-2})}$, while a recent result of Bradač shows that $f_{\ell,s}(n)\leq n^{\frac{\ell-1}{s-1}+o(1)}$. In this paper, we close this gap asymptotically by proving that $f_{\ell,s}(n)= n^{\frac{\ell}{2s}+O_\ell(s^{-2})}$. More precisely, we prove that for all $2\leq \ell<s$, we have $f_{\ell,s}(n)\leq n^{\frac{\ell}{2s-\ell}+o(1)}$. Our proof builds on Bradač's recent tight construction for off-diagonal Ramsey numbers, which can be viewed as the $\ell=2$ case of our result.

An independent set of a graph G is a subset of VG, no two of which are adjacent. The cardinality of a maximum independent set in a graph G is called the independence number of G, denoted by alpha(G). The essential connectivity kappa'(G) of a graph G is denoted as the minimum number of vertices of G whose removal produces a disconnected graph with at least two non-trivial components. In this paper, we determine the n-vertex connected graphs with given independence number and essential connectivity that attain the minimum distance spectral radius, and fully characterize the corresponding extremal graphs.

We prove a sharp quadratic inequality between the largest two eigenvalues $\lambda_1 \ge \lambda_2$ of a graph with $n$ vertices. We also prove a quadratic inequality between the second and third largest eigenvalues $\lambda_2 \ge \lambda_3$. These results in particular imply the bounds $\lambda_1 + \lambda_2 \le \frac{8}{7} n - 2$, $\lambda_3 \le \frac{n}{3} - 1$ and $\lambda_2 + \lambda_3 \le \frac{2}{3} n - 2$. In fact we determine the closure of the set of possible $(\frac{\lambda_1+1}{n}, \frac{\lambda_2+1}{n}) \in \mathbb{R}^2$ and $(\frac{\lambda_2+1}{n}, \frac{\lambda_3+1}{n}) \in \mathbb{R}^2$. More generally, we prove quadratic bounds in the case of symmetric matrices in $[0,1]^{n \times n}$, and we also give a quadratic bound for two eigenvalues of a symmetric matrix in $[-1,1]^{n \times n}$. These bounds are proved by transforming the problem into extremal geometric questions in $\mathbb{R}^3$ and $\mathbb{R}^2$. We use the method of Lagrange multipliers to reduce to special cases with at most five points, and we deal with these special cases directly.

A graph is $K_3$-irregular if its vertices belong to pairwise distinct numbers of triangles. We prove that no $8$-regular $K_3$-irregular graph exists, settling the last unresolved case. Following the initial discovery of such graphs for regularities $r \in \{10,11,12\}$ (Stevanovi'c et al., 2024), our previous work (Hak et al., 2025) showed that no such graphs exist for $r \le 7$, provided the first example for $r=9$, and proved that any $8$-regular candidate must have between $17$ and $22$ vertices. We exclude these possible orders for $r=8$ by combining careful analysis of triangle degrees with integer linear programming techniques. Meanwhile, a recent construction (Zhang, 2026) established that regular $K_3$-irregular graphs do exist for all $r \ge 9$. Together with our results, this establishes that an $r$-regular $K_3$-irregular graph exists if and only if $r\geq 9$.

A majority edge-colouring of a graph $G$ is a colouring of the edges of $G$ such that, for every vertex $v$ of $G$, at most half of the edges incident with $v$ receive the same colour. This notion was introduced by Bock et al. in 2023, who proved that every graph of minimum degree at least $2$ has a majority $4$-edge-colouring. We investigate an on-line variant of majority edge-colouring in which the graph is revealed by the Presenter edge-by-edge and the Algorithm must colour each edge immediately and irrevocably. In particular. we prove that the greedy strategy, which uses at most five colours, is optimal among on-line algorithms if $\delta = O(\frac{\log n}{\log\log n})$. We further extend our results to $1/k$-majority edge-colourings.

Motivated by the work of Andrews and El Bachraoui on partitions with repeated smallest parts, Malik and Sarma recently extended this concept to overpartitions. Using generating functions and $q$-series techniques, they established several results, including four identities, and posed the problem of finding combinatorial proofs for these identities. Recently, Baruah, Li, and Mohanta provided combinatorial proofs for three of these identities. In this paper, we present a combinatorial proof of the remaining identity.

Given an $n\times n$ symmetric matrix $M$ with largest eigenvalue $\lambda_1\geq 0$, it is easy to show that the solution of the optimisation problem $\max_{v\in [-1,1]^n}v^TMv$ is at most $\lambda_1 n$. We prove the following converse: if every $n'\times n'$ principal submatrix of $M$ has maximal eigenvalue at least $\lambda$, then $\max_{v\in [-1,1]^n}v^TMv\geq \lambda(n-n'+1)$. This allows us to lift results about the second largest and the smallest eigenvalue of graphs to the (a priori more difficult) setting of positive discrepancy and MaxCut. Using this new connection, we prove that every $n$-vertex $m$-edge graph that is far from a disjoint union of cliques has a cut of size at least $m/2+n^{5/4-o(1)}$, which is sharp up to the $o(1)$-term. Moreover, we prove that every $d$-regular $n$-vertex graph has bisection width at most $dn/4-\Omega_{\varepsilon}(d^{1/3}n)$ for $d\leq (1-\varepsilon)n/2$, which is optimal for $d=\Omega(n)$. This confirms a conjecture of Räty, Sudakov and Tomon.

We show that low discrepancy is equivalent to spectral gap for directed $k$-uniform hypergraphs. For undirected hypergraphs this recovers a theorem of Lenz and Mubayi, with a considerably shorter proof. At the heart of our argument is a Frieze–Kannan type spectral regularity lemma for hypergraphs based on the variational notion of hypergraph eigenvalues by Friedman–Wigderson, which decomposes any tensor into a bounded number of rank-one tensors plus a quasi-random tensor with small top eigenvalue. This lemma may be of independent interest, and we prove it for complex-valued, not necessarily symmetric tensors. We also briefly discuss a Szemerédi-type variant and the regularization of Cayley-type hypergraphs over finite abelian groups.

We use multipoint semidefinite programming to prove the nonexistence of strongly regular graphs. A normalized eigenspace projection of a primitive strongly regular graph gives a spherical two-distance set with one point for each vertex. A bound smaller than the required number of points therefore rules out the graph. Following the formulations of de Laat et al. and Kao and Yu, we use, for each reference type, coefficient matrices indexed by the feasible inner-product labels of the selected points. In degree zero, we combine the matrix coordinates indexed by the reference points into a single coordinate. The resulting programs use configurations of up to six points, with matrix orders at most $2^m+1$ for a reference set of $m$ points. Feasible dual solutions, verified in exact rational arithmetic, exclude strongly regular graphs with parameters $(351,140,73,44)$, $(550,162,75,36)$, $(703,182,81,35)$ and $(1344,221,88,26)$.

A Latin square of order $n$ is an $n \times n$ array filled with $n$ symbols so that each symbol appears exactly once in every row and column. A partial Latin square of order $n$ is an $n \times n$ array whose cells are either empty or filled in such a way that each symbol appears at most once in every row and column, and at most $n$ distinct symbols are used. In 1983, Daykin and Häggkvist conjectured that every partial Latin square in which each row and column contains at most $n/4$ symbols, and each symbol is used at most $n/4$ times, can be completed to a Latin square. We prove that every partial Latin square in which each row and column contains at most $0.231n$ symbols, and each symbol is used at most $0.231n$ times, can be completed to a Latin square, significantly improving the previous best-known bound of $0.08n$, obtained by Fu and Weng. This problem can be seen as a partite analogue of the Nash-Williams conjecture concerning triangle decompositions of dense graphs, recently proved in the breakthrough work of Delcourt and Postle. Our proof uses a `discharging' strategy, adapting the approach of Delcourt and Postle, combined with a novel method to achieve a `balancedness' property, required for the partite setting.

The Bárány-Larman conjecture states that for any $d+1$ sets of $r$ points each in $\mathbb{R}^d$, considered as color classes, we can partition their union into $r$ rainbow $(d+1)$-tuples whose convex hulls intersect. We prove that the topological version of this conjecture holds when $r$ is a prime number. We also show that the optimal colorful Tverberg theorem of Blagojević, Matschke, and Ziegler cannot be extended to prime powers.

The interval $[1,c]_T$ between the identity element and a Coxeter element $c$ in the absolute order on a Coxeter group $W$ is a generalization of the poset of noncrossing partitions arising when $W$ is the symmetric group. When $W$ is finite, this poset is always a lattice, and it is natural to associate to every element $w\in [1,c]_T$ its moved space $\mathsf{Mov}(w)=\mathrm{Im}(w - \mathrm{Id}_V)$ in the geometric representation $V$ of $W$. It has dimension equal to the reflection length $\ell_T(w)$ of $w$, and gives a realization of $[1,c]_T$ inside the lattice of subspaces of $V$. It is an important tool in the study of $[1,c]_T$. When $W$ is infinite, the moved space of an element $w\in [1,c]_T$ no longer has dimension $\ell_T(w)$ in general, and distinct elements may have the same moved space. We propose a replacement for the moved space of an element $w\in [1,c]_T$ in an arbitrary Coxeter group, that we call absolute moved space of $w$. This subspace $\mathsf{AM}(w)$ of $V$ always contains $\mathsf{Mov}(w)$ and has dimension equal to $\ell_T(w)$, and distinct elements have distinct absolute moved spaces. This allows us to derive several properties of noncrossing partition posets that hold in full generality, and to show that the natural map from $[1,c]_T$ to reflection subgroups of $W$, which to $w\in [1,c]_T$ associates the subgroup $P(w)$ generated by reflections lying below $w$ in the absolute order, is always injective. Among others, we also derive a new proof of the lattice property of $[1,c]_T$ when $W$ has rank three, and exhibit infinitely many new examples of infinite Coxeter groups of rank four and choices of Coxeter elements for which $[1,c]_T$ fails to be a lattice.

We study the $q$-matroids associated with nondegenerate $\F_{q^m}$-linear near-MRD codes, which we call near-uniform $q$-matroids. Using the correspondence between rank-metric codes and their associated $q$-systems, we determine explicitly their rank functions and characterize their cyclic flats. We show that near-uniform $q$-matroids form a class of representable paving $q$-matroids. and prove an upper bound on the number of their cyclic flats, which is shown to be sharp for certain parameters. Finally, when $n>m$, exploiting the rank distribution of near-MRD codes, we obtain an exact count of the nontrivial cyclic flats of the associated $q$-matroids.

A majority coloring of a graph $G = (V,E)$ is a coloring of $V(G)$ such that, for each vertex $v$, the number of neighbors of $v$ with the same color as $v$ is at most $deg(v)/2$. A strong majority coloring is a coloring of $V(G)$ such that, for each vertex $v$, every monochromatic subset of $N(v)$ has size at most $deg(v)/2$. The (strong) majority coloring game is a two-player Maker-Breaker-type game, in which two players Alice and Bob color the vertices of a graph $G$ alternately, maintaining the (strong) majority condition. The least number of colors such that Alice has a winning strategy in such a game is called the (strong) majority game chromatic number of the graph $G$, denoted $\mu_g(G)$ (or $\mathrm{Maj}_g(G)$ for the strong version). For the majority coloring game, we prove that $\mu_g(G) \le 3$ under the following cases: $G$ is a $2$-caterpillar, $G$ is a rooted tree with all leaves at depth $k \le 4$, and $G$ is a subdivision of some graph. The latter resolves a problem posed by Bosek–Grytczuk–Jakóbczak in 2019, who also asked whether $\mu_g(T) \le 3$ for every tree $T$. For the latter question, we discuss various difficulties that arise when natural strategies are attempted by Alice to win the majority coloring game on trees. We include a comparison with the marking game and relaxed coloring game on trees, and with the majority coloring game on locally finite acyclic graphs $G$ with $\delta(G) > 1$. For the strong majority coloring game, we compute $\mathrm{Maj}_g(C_n)$ exactly for each cycle $C_n$, $n \ge 3$. We also initiate the study of the computational complexity of the strong majority coloring game; specifically, we prove that the decision version of the Strong Majority Game Chromatic Number problem is PSPACE-complete. We also show that the Strong Majority 2-Coloring problem is NP-complete on Eulerian graphs.

With a view toward applications in Riemannian geometry, we explore coloop splitting properties of regular matroids. Nienhaus showed by classification in rank four that a regular matroid has a cocircuit whose deletion yields two coloops unless the matroid takes a particular form. In the latter case, one can split off any element of the ground set as a coloop. We reprove this using Seymour's structure theorem for regular matroids and prove an extension to matroids of ranks five and six. As an application to Riemannian geometry, we prove that the torus symmetry assumption in a recent result of Mouillé, Nienhaus, and the second author can be relaxed from rank ten to rank nine.

Let $G$ be a connected graph, and let $\lambda_1(G) > \lambda_2(G)$ denote its two largest adjacency eigenvalues. The spectral gap of $G$ is defined as the difference $\lambda_1(G) - \lambda_2(G)$. For integers $r\geq 2$ and $s\geq 0$, the double kite $DK(r,s)$ is formed by taking two vertex-disjoint copies of the complete graph $K_r$ and joining one specified vertex of each clique to a path with $s$ internal vertices. Stanić (2013) conjectured that every connected $n$-vertex graph with minimum adjacency spectral gap is a double kite. In this paper, we confirm this conjecture for sufficiently large $n$.

We study weak and strong forbidden subposet problems in the linear lattice $L_n(q)$. We show that the $q$-analogues of the Bukh–Griggs–Lu conjecture fail for every prime power $q$. If $q\ge 3$ and $n$ and $d$ have opposite parity, then $La_q(n,L_d(q))=La_q^*(n,L_d(q))=\Sigma_q(n,d)$. We also show that $La_q(n,D_s)=La_q^*(n,D_s)=\Sigma_q(n,2)$ for $2\le s\le q$ and all $n$, and for $s=q+1$ when $n$ is odd. For $n$ even, a maximum strong $D_{q+1}$-free family can be contained from the three middle layers. The case $s=2$ settles the $q$-analog of the diamond conjecture in the affirmative.

In 1977, Erdős posed the problem of determining the maximum number $f_r(n)$ of edges in an $n$-vertex $r$-uniform hypergraph in which all disjoint pairs of edges have distinct unions. Füredi later conjectured that, for every fixed $r\ge 4$ and all sufficiently large $n$, $f_r(n)=\binom{n-1}{r-1}+\lfloor \frac{n-1}{r}\rfloor$. In this paper, we prove this conjecture and determine all extremal configurations. Our proof combines a stability theorem for such dense hypergraphs with a delicate deletion argument applied to an associated bipartite $3$-graph. The stability theorem also resolves a conjecture of Mubayi.

Linked projective spaces are quiver Grassmannians of subspaces of dimension 1 of certain quiver representations. Degenerations of linear series produce these representations, with the limit divisors parameterized by the associated linked projective spaces. It is not known whether all linked projective spaces arise this way. If they do, they are degenerations of the (small) diagonal in a product of projective spaces. In any case, we prove here that they have the (multivariate) Hilbert polynomial of the diagonal. To achieve this, we first extend a Hilbert-polynomial formula for multiplicity-free varieties to (simple) normal-crossings schemes with multiplicity-free strata in products of projective spaces. Then we prove that a linked projective space is normal-crossings, by describing it locally in terms of Mustafin varieties. Finally, we use a relation between intersections of components of the linked projective space and certain polytopes in the tiling of a simplex associated to the linked net to prove that our formula for the Hilbert polynomial applies.

In this paper, we first construct two graphs $\mathcal{F}(l,m,t,s)$ and $\mathcal{G}_4(l,m,t,s)$. Then we introduce the graph $\mathcal{F}_n(l,m,t,s)$ and the operator $E_{\mathcal{G}_4(l,m,t,s)}$, where $\mathcal{F}_n(l,m,t,s)$ is defined by identifying the vertex $c$ of $n$ copies of $\mathcal{F}(l,m,t,s)$, and $E_{\mathcal{G}_4(l,m,t,s)}$ is defined by replacing each edge of $G$ with $\mathcal{G}_4(l,m,t,s)$, for any simple finite undirected graph $G$. By using the theory of Lorentzian polynomials, we prove that the independence polynomials of the graphs $\mathcal{F}_n(l,m,t,s)$ and the image graphs of $E_{\mathcal{G}_4(l,m,t,s)}$ are log-concave, respectively. As applications, our results not only make progress on the conjecture of Alavi, Malde, Schwenk and Erdős, but also generalize the results of Bendjeddou and Hardiman.

We prove that the Ehrhart $h^*$-polynomial of a rank-two matroid with exactly three parallel classes is real-rooted whenever its smallest parallel class has size at most three. This bound is sharp: the rank-two matroids with parallel-class sizes $(4,561,600)$ and $(4,a,a+29)$, for all sufficiently large integers $a$, have $h^*$-polynomials that are not real-rooted. These counterexamples disprove Ferroni's real-rootedness conjecture. Their duals are cycle matroids of theta graphs and have the same $h^*$-polynomials. Nevertheless, every matroid of rank two or corank two has a positive $h^*$-coefficient sequence that is ultra log-concave of order equal to the polynomial's degree. In particular, the unimodality conjecture holds in both cases.

Let $s(N)$ denote the smallest side length of a square containing $N$ unit squares with arbitrary orientations and pairwise disjoint interiors. Nagamochi's Packing Unit Squares in a Rectangle (2005) states a rectangle packing bound from which he deduces two infinite families of exact values: $s(k^2-1) = k$ and $s(k^2-2) = k$ for every integer $k \geq 2$. We construct a family of counterexamples, local to a corner of the container, to the scoring assertion in Nagamochi's Lemma 1. These counterexamples show that the published proof of the rectangle bound is incomplete, but do not disprove the bound itself. We then give an independent proof of a weaker rectangle bound using a strip measure. This recovers $s(k^2-1) = k$ for every integer $k \geq 2$ and yields an explicit lower bound for $s(N)$ that improves strictly on the area bound for every nonsquare integer $N \geq 8$. Our argument does not establish Nagamochi's full rectangle bound or the identity $s(k^2-2) = k$.

We present a determinantal evaluation formula for the very-well-poised ${}_8\Phi_7$ basic hypergeometric Askey-Wilson function in terms of elementary functions. The formula in question is valid for discrete values of the four permutation-symmetric Askey-Wilson parameters; specifically, these consist of all quadruples of parameter values that are given, up to a sign, by powers $q^k$ with $k$ a positive integer or half-integer, in such a way that each of the four types (positive/negative sign, integer/half-integer power) occurs exactly once. The proof hinges on a product formula for an associated Cauchy-type determinant, which is of independent interest and is established here by elementary means using Krattenthaler's `identification of factors' method for determinant evaluations.

For graphs $H$ and $F$, let $\text{ex}(n,H,F)$ denote the maximum number of copies of $H$ in an $n$-vertex $F$-free graph. Gerbner, Győri, Methuku, and Vizer proved that $\text{ex}(n,C_{2\ell},C_{2k})=\Theta(n^\ell)$ for $k>\ell\ge2$. They determined the leading term for $\ell=2$, but for $k>\ell\ge3$ their general lower and upper bounds had different leading constants, leaving open the problem of closing this gap. We solve this problem by showing that, for every $k>\ell\ge2$, \[\text{ex}(n,C_{2\ell},C_{2k})=\left(\frac{(k-1)_\ell}{2\ell}+o(1)\right)n^\ell, \] where $(k-1)_\ell=(k-1)(k-2)\cdots(k-\ell)$.

A balanced $k$-partite $k$-graph is a $k$-uniform hypergraph whose vertex set is partitioned into $k$ classes of the same size and whose edges meet every class in exactly one vertex. Lo and Markström (2014) determined the minimum vertex-degree threshold for perfect matchings when $k=3$, and Lu, Wang and Yuan recently determined it when $k=4$. We prove the corresponding exact result for every fixed $k\ge5$ and all sufficiently large class sizes. The close case follows from the general theorem of Lu, Wang and Yuan. For the non-closed case, we extend their stability result from the 3-partite setting to arbitrary partite uniformity, using the probability-tail rigidity theorem of Cao, Liu and Zhang, thereby replacing the earlier weighted lemma.

Let $E_2$ be the extraspecial group of order $3^5$ and exponent three. We prove that $d(E_2\times C_3^r)=2r+10$ for $0\le r\le3$. The upper bounds follow from signed zero-block identities and two finite statements in the four-dimensional symplectic space over $\mathbb F_3$. The first supplies edge weights for all completable balanced triangles on any indexed list of at most sixteen nonzero vectors. The second supplies weights for the direction families that can occur in a critical list with no central terms. We give complete coverage arguments, exact certificate files, and separately implemented checking programs. A compression argument removes any need for an induction through smaller list lengths in the sixteen-term potential theorem. The formula for $r\ge4$ remains open.