Papers

In an asymmetric shelf shuffle, a deck of $n$ cards is dealt sequentially from the bottom and assigned one of the $m$ shelves uniformly at random. The card is placed at the top of the assigned shelf with probability $p$, and at the bottom of the assigned shelf with probability $(1-p)$. Analysis of the shelf shuffle has gained much attention recently, and the case $p=1/2$ was first treated by Diaconis–Fulman–Holmes [Ann. Appl. Prob. 23 (2013), no. 4, 1692–1720]. In this paper, we extend the analysis of the shelf shuffle to general $p\in (0, 1)$. In particular, we study the distribution of cycles, cycle lengths, number of descents, number of valleys, number of inversions, and the RSK shape of a permutation obtained from an asymmetric shelf shuffle. Our results extend the analysis of Diaconis–Fulman–Holmes to arbitrary $p$. Furthermore, our analysis of the distribution of descents and inversions is new even for $p=1/2$.

A mechanical shuffler consists of $m$ shelves. A deck of $n$ cards, arranged in increasing order, is dealt from the bottom sequentially. Each card is assigned a shelf uniformly at random and placed on the top (bottom) of the existing pile with probability $p$ ($1-p$) independently. We refer to this as asymmetric shelf-shuffle. We find the law $\nu_{n, m}^{(p)}$ of the permutation induced by the asymmetric shelf-shuffle and show that the pair consisting of the number of descents and the number of valleys is a sufficient statistic. This generalizes a result of Diaconis, Fulman, and Holmes (Ann. Appl. Prob., 2013) corresponding to the case $p=1/2$. For $p=1/2$, Chen and Ottolini (ECP, 2025) established the cutoff in the total variation distance near $\lfloor n^{5/4}\rfloor$. We establish the cutoff for the asymmetric shelf shuffle. Let $\nu_n$ be the uniform measure on the set of all permutations $S_n$ of $\{1, \ldots, n\}$. For a fixed $p\neq 1/2$ and $c>0$, we show that \[\TV\left(\nu_{n, \lfloor cn^{3/2}\rfloor }^{(p)}, \nu_n\right)=1-2\Phi\left(-\frac{|2p-1|}{4\sqrt{3}c}\right)+O_{c, p}(n^{-1/2})\;.\] We also establish the cutoff in the separation distance near $m\approx n^{2}$ and in the relative entropy near $m=n^{3/2}$. In both cases, we also obtain the cutoff profile explicitly.

We determine the precise asymptotic number of unlabelled cubic planar graphs with $n$ vertices. Our approach blends generating series methods with computational bounds and probabilistic local large deviation theorems.

The inversion of a set $X$ of vertices in an oriented graph reverses every arc with both endpoints in $X$. The inversion graph $I(G)$ of a graph $G$ has the labelled orientations of $G$ as its vertices, two orientations being adjacent when a single inversion transforms one into the other, and the inversion diameter $\diam(I(G))$ is its diameter. Answering a question of Havet, Hörsch and Rambaud, we prove the bound in terms of edge number $\diam(I(G)) \le 2\sqrt{|E(G)|}$, and we complement it with a lower bound $\diam(I(G)) \ge \frac{|E(G)|}{|V(G)|}$ obtained by viewing $I(G)$ as a Cayley graph on $\F_2^{E(G)}$. We further refine the upper bound for bipartite graphs $G$ by showing $ \diam(I(G))\le \max\left\{\rho, \left\lceil\log_2\bigl(2+\sigma(2^{\rho-1}-1)\bigr)\right\rceil\right\}$ where the two parts of $G$ have maximum degrees $\sigma$ and $\rho$, respectively.

For $n\ge 2$, let $M(n)$ be the supremum of $\sum_{a\in A}1/(n-a)$ over pairwise coprime sets $A\subset[1,n)$. Erdős asked whether $M(n)\le \sum_{p<n}1/p+O(1)$ uniformly in $n$. We prove the quantitative average-order formula $\sum_{n\le N}M(n)=e^{-\gamma}N\log\log N+O(N)$. The proof combines the self-rough lower construction $\{n-d:P^{-}(n-d)>d\}$ with a bounded-cost dual certificate and Buchstab–de Bruijn estimates. We also show $M(n)=(e^{-\gamma}+o(1))\log\log n$ for almost all $n$, with a quantitative exceptional-set bound, so Erdős's inequality holds for almost all $n$. The argument combines a long-interval two-dimensional beta sieve for two moving forbidden residue classes with an exact finite singular-series cancellation. The remaining obstacles to a full variance estimate are a shifted-prime second moment for $d>\sqrt{2N}$ and finite-$u$ rough correlations in the intermediate tail, yielding a precise conditional criterion. For every $\varepsilon>0$ we also prove the uniform pointwise bound $M(n)\le(2+\varepsilon)\log\log n+O_{\varepsilon}(1)$ and explain the linear-sieve barrier at the constant $2$. The results of this paper have been formally verified in Lean.

We study the asymptotic enumeration of labelled connected multitype graphs in the sparse regime, where both the number of vertices and edges grow linearly and the excess is proportional to the size of the graph. Extending the classical theory of connected graph enumeration to the multitype setting, we consider graphs with prescribed numbers of vertices of each type and prescribed edge counts between each pair of types. Our approach is probabilistic and relies on the theory of inhomogeneous random graphs. In particular, we exploit large-deviation principles and asymptotic estimates for connectedness probabilities to relate the counting problem to the emergence of giant components in suitably tuned supercritical random graphs. From large deviation asymptotics of connected components of inhomogeneous random graphs, we recognize that a connected graph with a given edge statistics corresponds to the (unique) giant component of larger inhomogeneous random graph with a suitably chosen connection kernel. This correspondence allows us to derive the leading exponential asymptotics for the number of connected multitype graphs with fixed type profile and edge matrix. The resulting formula generalizes the asymptotic enumeration results of Bender, Canfield, and McKay for connected sparse graphs to the multitype framework. More broadly, the paper illustrates how probabilistic techniques can provide transparent and effective tools for addressing new combinatorial enumeration problems.

For a graph $G$ put $h_r(G)=\max{\chi(H):H\subseteq G,\operatorname{girth}(H)\ge r}.$ Erdős and Hajnal asked whether $h_r(G)\to\infty$ as $\chi(G)\to\infty$, for every fixed $r\ge4$. We prove this in every fixed polynomial edge-density regime: for all $r\ge4$, $k\ge2$, $P,C>0$, there is $M=M_{r,k}(P,C)$ such that $\chi(G)\ge M,\ e(G)\le C\chi(G)^P\Longrightarrow h_r(G)\ge k.$ Quantitatively, after replacing $P$ by $P\vee2$ and $C$ by $C\vee2$, $M_{r,k}(P,C)\le \exp!\left(O_{r,k}\bigl((P+2+\log(C\vee2))^2\bigr)\right),$ and consequently the same conclusion holds throughout the quasi-polynomial range $e(G)\le \exp\bigl(C_0(\log\chi(G))^a\bigr),\ 1 < a < 3/2,$ for all sufficiently large $\chi(G)$. In each fixed polynomial-density regime we also obtain $f_{P,C}(k,r)\le k^{O_{r,P,C}(1)}.$ The proof combines a chromatic-defect random extraction lemma, compact and near-quadratic sparse-core bases, and a peeling/thinning bootstrap increasing the admissible edge exponent by $1/(r-1)$. We also prove structural saturation results for possible counterexamples, including Moore-strength exact-cycle packings and quadratic saturation in projected colour-pair space. Finally, writing $h_r^{\mathrm f}(G)=\max{\chi_{\mathrm f}(H):H\subseteq G,\operatorname{girth}(H)\ge r},$ we develop a fractional random-extraction framework based on Mohar-Wu preservation. We prove sufficient cheap-cycle-killing criteria and verify them for several structured families, including clique-organised families, line graphs of incidence graphs of equal-order generalized quadrangles and generalized hexagons, and the Bohman-Keevash tracking-time triangle-free-process graph. We also isolate a density-free obstruction that any proof using this fractional surgery route must overcome.

Let us consider a random infinite lower triangular matrix, where the entries on and below the diagonal are i.i.d. uniform random elements of a fixed finite field. We investigate the evolution of the span of the first $n$ rows of this matrix as $n$ grows. Many properties of this evolving subspace can be captured with the help of the verbose persistence diagram, which is a standard tool in stochastic topology and topological data analysis. We give an explicit formula for the distribution of the persistence diagram. We prove a law of large numbers for the distribution of lifetimes. We also describe the fluctuations of the persistent Betti numbers.

Wegner conjectured in 1965 that every finite family $\mathcal R$ of axis-parallel rectangles satisfies $\tau(\mathcal R)\le 2\nu(\mathcal R)-1$, where $\tau(\mathcal R)$ is the minimum number of piercing points and $\nu(\mathcal R)$ is the maximum size of a pairwise-disjoint subfamily. We disprove the conjecture by an explicit triangle-free family of $64$ rectangles with $\nu=16$ and $\tau\ge 32$. More generally, for every $\varepsilon>0$, we construct triangle-free rectangle families for which the standard clique-LP relaxation for maximum independent set of rectangles has integrality gap at least $5/2-\varepsilon$. The same families satisfy $\tau(\mathcal R)\ge (5/2-\varepsilon)\nu(\mathcal R)$. We also prove that, on triangle-free rectangle families, this LP has gap at most $3$. Our approach gives an example with axis-parallel segments instead of rectangles with integrality gap tending to $2$. We also give a relatively small $4092$-rectangle triangle-free family with chromatic number $6$ improving the construction of Asplund and Grünbaum (On a coloring problem, Mathematica Scandinavica, 1960) that required more than $10^8$ rectangles.

Let $G$ be a graph with vertex set $\{v_1,\dots,v_n\}$. The Seidel matrix of $G$ is an $ n\times n$ matrix whose diagonal entries are zero, $ij$-th entry is $-1$ if $v_i$ and $v_j$ are adjacent, and otherwise is $1$. The $p$-Seidel energy of the graph $G$ is defined as the sum of the absolute values of the $p$-th powers of all eigenvalues of the Seidel matrix of $G$ and introduced in [European Journal of Combinatorics, (86) (2020), 103078]. In this article, we characterize the graph that minimizes the $p$-Seidel energy among all graphs with fixed order $n$, for $p>2$. We also characterize the graph that maximizes the $p$-Seidel energy among all graphs with fixed order $n$, for $0<p<2$. In addition, for every $p>2$, we characterize the graph that minimizes the $p$-Seidel energy among all $r$-regular graphs with fixed order $n$, where $n$ is a prime power with $n\equiv 1\pmod 4$, $r=\frac{n-1}{2}$. For every $p>2$, we also characterize the graph that maximizes the $p$-Seidel energy among all $r$-regular graphs with fixed order $n=2r$. Finally, we pose several open problems concerning the $p$-Seidel energy for different values of $p$.

The shifted Jack Littlewood-Richardson coefficients generalize the ordinary Jack coefficients and are Laurent polynomials in the Jack parameter $\alpha$. We prove a previously conjectured congruence: coefficients indexed by triples differing by a single box move are congruent modulo the shared $\alpha$-hook at the pivot. We also prove a shifted Macdonald analogue, with a power-of-$t$ twist, and establish that the normalized shifted Macdonald coefficients are Laurent polynomials in $q$ and $t$. The proofs combine coincidences of shifted coordinates with Laurent-preserving shift transforms, and the Macdonald input uses Knop's inversion formula and the integrality of the Bergeron-Garsia-Haiman-Tesler operators. Finally, we realize the Jack and Macdonald congruences as necessary edge conditions on Hilbert schemes of points, in equivariant cohomology and equivariant $K$-theory, respectively. In the Macdonald case a tautological determinant twist accounts for the power-of-$t$ normalization

The Seidel energy is defined as the sum of the absolute values of the eigenvalues of the Seidel matrix of a hypergraph. We first characterize the k-uniform hypergraphs of fixed order n with minimum and maximum Frobenius norms of Seidel matrices and then derive bounds for the Seidel energy. Building on these results, we obtain a negative answer to the hypergraph analogue of Haemers Conjecture by showing that the complete k-uniform hypergraph does not, in general, minimize Seidel energy. Motivated by the theory of hypoenergetic and non-hypoenergetic graphs, we define Seidel hypoenergetic and Seidel non-hypoenergetic hypergraphs and prove that almost all k-uniform hypergraphs are Seidel non-hypoenergetic.

Hypergraph polytopes (or nestohedra) form a broad class of polytopes obtained by truncating faces of a simplex according to a hypergraph. In earlier work, the authors constructed q-tridendriform algebras on the set of faces of certain families of hypergraph polytopes, including associahedra and permutohedra. The well-definedness of these structures relied on a connectedness property on the hypergraphs involved, called strictness. Nevertheless, notable examples of hypergraph polytopes such as cyclohedra fell outside this setting. We introduce a new connectedness condition, called anti-strictness, which goes opposite to strictness and captures a different class of hypergraph polytopes, including associahedra, permutohedra and cyclohedra. Our main result produces natural (-1)-tridendriform algebras in the anti-strict framework, which match previously introduced tridendriform algebras in the overlap of the two frameworks, thereby extending the range of hypergraph polytopes admitting such algebraic structures.

We study duality for monoids in an infinite-dimensional setting that are invariant under the action of the infinite symmetric group Sym. Our main result is an equivariant Minkowski–Weyl theorem for monoids. More precisely, we analyze the evolution of dual monoids along stabilizing Sym-invariant chains and describe the eventual behavior of their equivariant Hilbert bases. In addition, we develop a systematic study of structural properties of dual symmetric monoids, including a characterization of the duals of positive and non-positive monoids.

We study monoids in an infinite-dimensional setting that are invariant under the action of the infinite symmetric group Sym. Our main result establishes a local–global principle characterizing equivariant finite generation for arbitrary Sym-invariant monoids, extending earlier results that required additional assumptions. We further analyze local–global phenomena for other fundamental properties, including positivity, normality, seminormality, and simplicity. In addition, we obtain structural results for symmetric monoids, including characterizations of positivity and non-positivity, a description of their groups of units, and explicit formulas for the ranks of local symmetric monoids and stabilizing Sym-invariant chains.

We study the counting problem for non-uniform intersecting families in extremal set theory. Let $J(n,k)$ denote the number of intersecting families $\mathcal{F}\subset 2^{[n]}$ such that every member of $\mathcal{F}$ has size at most $k$. Extending recent counting results for uniform intersecting families, we prove that for $n\ge 2k+2+2\sqrt{k \log k}$ and $k \rightarrow +\infty$, \[ J(n,k) =(n+o(1)) 2^{\sum_{i=1}^{k} \binom{n-1}{i-1}}. \] This result reveals that typical non-uniform intersecting families of bounded size are trivial, i.e., almost all such families share a common fixed element.

Motivated by the recent constructions of Golay Complementary Array (GCA), we extend the "Three-stage construction" proposed by Fiedler and Jedwab to a more general form. All the known 2-phase Golay Complementary Sequences (GCSs) of length $2^a10^b26^c,a,b,c\ge 0$ and 4-phase GCSs of length $2^{a+u}3^b5^c11^d13^e$ where $a,b,c,d,e,u\ge0,b+c+d+e\le a+2u+1,u\le c+e$ can be constructed in a uniform method from five 2-phase seeds of length 2,10,10,20,26 and five 4-phase seeds of length 3,5,8,11,13. Furthermore, additional 2-phase and 4-phase GCSs of many lengths are produced and a closed form for numbers of 2-phase and 4-phase GCSs is given.

Menger's theorem is one of the most fundamental results in graph theory. It states that if a graph $G$ does not contain $k$ disjoint paths between two given sets $X$ and $Y$ of vertices in $G$, then there is a set of at most $k-1$ vertices that intersects every path between $X$ and $Y$. Nguyen, Scott, and Seymour gave a counterexample to the conjectured natural coarse variant in which the paths are required to be pairwise at distance at least $d$, and, conversely, there is a set of at most $k-1$ bounded-radius balls intersecting every path between $X$ and $Y$. In other words, the coarse Menger property does not hold in general. We prove that graphs whose cycles space is generated by cycles of bounded length do have the coarse Menger property. As a corollary, we show that many natural graphs and geodesic metric spaces have the coarse Menger property. These include hyperbolic graphs, Cayley graphs of finitely presented groups, planar graphs with bounded face size, and complete Riemannian planes.

An upper homogeneous (upho) poset is a poset whose every principal filter is isomorphic to the whole poset. Fu–Peng–Zhang conjectured that every finitary upho poset admits a compatible left-cancellative, invertible-free monoid structure whose left-divisibility order coincides with the given order. We disprove this conjecture. For every vertex-transitive graph $G$, we construct a finitary upho poset $P(G,v_0)$ from walks starting at a fixed vertex $v_0$. Applying this construction to the Petersen graph, we show that multiplicability of $P(G,v_0)$ would force the automorphism group of $G$ to contain a regular subgroup. This would imply that $G$ is a Cayley graph, contradicting the fact that the Petersen graph is not Cayley. Hence $P(G,v_0)$ is a non-multiplicable finitary upho poset. We also show that the analogous poset associated with the line graph of the Petersen graph is multiplicable, demonstrating that non-Cayleyness of the underlying graph alone does not determine multiplicability.

The Fomin local rules for Schensted column insertion can be seen as a two-lane box-ball system, in which a carrier moves particles forward or laterally. Running such two-lane dynamics in parallel on a periodic lattice gives rise to a two-dimensional generalization of the box-ball system, which we call the skew column RSK dynamics. Equivalently, this is a deterministic dynamics on pairs of skew semistandard Young tableaux $(P_t,Q_t)_{t \in \mathbb{Z}}$. We prove that this dynamics exhibits solitonic behavior and construct an explicit bijection $(P,Q) \leftrightarrow (H_1,H_2,\kappa,\nu)$ that linearizes the time evolution. The resulting coordinates consist of two horizontally weak tableaux $H_1,H_2$ recording the asymptotic soliton data, integer riggings $\kappa$, and a weakly decreasing sequence of integers $\nu$. A key feature of the construction is an explicit projection from the skew column RSK dynamics to the classical box-ball system; under this projection, the rigging $\kappa$ is precisely the Kerov–Kirillov–Reshetikhin rigging of the associated box-ball configuration. Our proof uses two commuting affine crystal structures on pairs of skew tableaux and a novel connectivity theorem for distinguished subgraphs of tensor products of Kirillov–Reshetikhin crystals. We also derive Greene-type formulas for the soliton lengths in terms of last-passage percolation on the associated cylindrical environment. Finally, by taking generating functions in the linearizing coordinates, we obtain bijective proofs of Cauchy and Kawanaka–Littlewood-type identities for transformed Hall–Littlewood polynomials.

We develop a new combinatorial large sieve method for sets with bounded algebraic multiplicities. The method exploits algebraic splitting modulo many small primes: local congruence branching produces many modular collisions, while global bounded-multiplicity hypotheses force these collisions to be rare. As a first application, we prove that every Sidon subset $A\subset\{1^2,\ldots,N^2\}$ satisfies \[ |A| \le N\exp\left( -c\frac{\log N}{\log\log N} \right) \] for some absolute constant $c>0$. This gives the first super-polylogarithmic saving for a classical problem of Alon and Erdős. As a second application, we establish new upper bounds for two grid-distance problems. We show that the largest subset of $[N]^2$ with no repeated distance has size at most $N\exp\left(-c\log N/\log\log N\right)$, giving the first progress in over thirty years on a problem of Erdős and Guy. The same method also gives a similar saving for subsets of $[N]^2$ with no isosceles triangles, a problem recently popularized by Ellenberg and by the PatternBoost work of Charton, Ellenberg, Wagner, and Williamson. We then develop an entropic version of the method. This gives bounds for $B_2[g]$-sets in the squares and for analogous bounded-multiplicity problems associated with norm forms over arbitrary number fields. More importantly, this new method also allows us to establish the first nontrivial bounds for $B_3[g]$-sets in the cubes and $B_4[g]$-sets in the fourth powers.

In recent work of Dombos, the set of integer partitions of $n$ wherein the parts are either divisible by 4 or congruent to $\pm 1 \pmod{6}$ arose in a natural way. In this work, we will denote the function which counts the number of such partitions of $n$ by $dp(n)$. Using elementary generating function manipulations and classical $q$–series results, we prove several congruences satisfied by $dp(n)$. As an example, we prove that, for all $\alpha \geq 1$ and all $n \geq 0$, \begin{equation*} dp \left( 3^{2\alpha + 1}n + \frac{7 \cdot 9^\alpha + 1}{4} \right) \equiv 0 \pmod{3}. \end{equation*}

We use perfect matchings and labelled Fano planes to construct and study the $2025$ orthogonal bases of positive roots in the $E_8$ root system. The set of these bases forms a highly structured, Bruhat-like graded poset $(\Omega, \leq_Q)$ whose rank function can be computed from the cardinalities of so-called generalized Rothe diagrams. We give combinatorial characterizations of these diagrams in terms of matchings and Fano planes, and we explain how to compute the ranks of the elements of $\Omega$ using suitable combinatorial statistics such as the weights of perfect matchings. We establish simple formulas for the rank generating functions of $\Omega$ and of its 50 congruence classes under a natural order congruence relation. Our derivation of the generating functions contains some intermediate results on general perfect matchings and labelled Fano planes that can be stated without mentioning root systems and may be of independent interest.

Let $G$ be a connected graph, and let $b\geq2$ be an even integer. The distance spectral radius of $G$ is denoted by $\mu(G)$. An $H_b$-factor of $G$ is a spanning subgraph $F$ of $G$ with $d_F(v)\in\{1,3,5,\ldots,b-1,b\}$ for any $v\in V(G)$, where $d_F(v)$ is the degree of $v$ in $F$. Lu and Wang provided a sufficient condition with respect to the number of odd components in $G-S$ for a connected graph $G$ of even order to contain an $H_b$-factor, where $S$ is a vertex subset of $G$ [H. Lu, D. Wang, On Cui-Kano's characterization problem on graph factors, J. Graph Theory 74 (2013) 335–343]. In this paper, motivated by Lu and Wang's above result, we establish an upper bound on the distance spectral radius $\mu(G)$ of a connected graph $G$ to guarantee that $G$ contains an $H_b$-factor.

We study the space of splines $\mathcal{S}^{\mathbf{r}}(\Sigma^\mathscr{A})$ where ${\mathbf{r}}$ denotes a smoothness distribution and $\Sigma^\mathscr{A}$ is the fan of a central hyperplane arrangement $\mathscr{A}$ in $\mathbb{R}^3$. This is the first step in the analysis of splines on three-dimensional cross-cut partitions, which naturally generalize planar cross-cut partitions. We show that the Hilbert function of $\mathcal{S}^{\mathbf{r}}(\Sigma^\mathscr{A})$ is bounded by an expression that involves the dimensions of specific Koszul homology modules constructed from the defining equations of the hyperplane arrangement $\mathscr{A}$ and the smoothness distribution function. By exploiting this connection with Koszul homology, we are able to: 1) compute the dimension of the spline space in high degrees, 2) compute all values of the dimension of the spline space if $\mathscr{A}$ is generic with five or fewer hyperplanes, and 3) compute the Hilbert function of the spline space if $\mathscr{A}$ is a generic arrangement with sufficiently many hyperplanes and ${\mathbf{r}}$ is a constant distribution. As an application of our methods, we compute $\dim \mathcal{S}^0_d(\Sigma^\mathscr{A})$ and $\dim \mathcal{S}^1_d(\Sigma^\mathscr{A})$ for all values of $d$ when $\mathscr{A}$ is a generic arrangement.

A general framework is developed for deriving sharp inequalities on simple graphs from majorization and Schur-convexity. After establishing majorization relations between the spectrum of an arbitrary graph and the spectra of the complete, complete bipartite, and matching graphs, it is shown that every positive Schur-convex spectral functional yields several sharp inequalities relating $\lambda_1$, $|\lambda_n|$, and $\|G\|_\ast$. This reduces the problem of proving graph inequalities to the choice of a suitable Schur-convex function. This optimization problem is then studied within the family of random vector norms, whose moment and cumulant expansions connect the framework to the numbers of closed walks. This yields new sharp results, recovers classical inequalities from a unified viewpoint, and produces further bounds in settings such as triangle-free and square-free graphs.

Motivated by the optimization of bounded binary black-box functions, we study the problem of learning polynomial surrogates over the Boolean hypercube. To ensure that optimizing the surrogate yields good solutions for the underlying objective, we require uniform $L_\infty$-error guarantees rather than the usual $L_2$-type guarantees. We characterize the minimax sample complexity of uniform estimation under subgaussian noise for two classes of bounded polynomials. First, for polynomials of degree at most $d$ on $n$ variables, the sample complexity scales as $n^{d+1}$. Second, for $s$-sparse Fourier-Walsh polynomials with $s \leq n$, it scales as $ns^2$. These rates differ structurally from the noiseless setting, where uniform exact recovery scales as $n^d$ and $ns$, respectively. Our lower bounds hold even for arbitrary adaptive learners, showing that the additional factors are intrinsic to the noisy cases. Standard Fourier-analysis tools for the $L_2$-norm do not naturally extend to the $L_\infty$-setting in a way that yields uniform guarantees. Our proofs overcome this difficulty by relying on suitably chosen auxiliary norms that serve as proxies for controlling the $L_\infty$-error. Together, our results provide a tight characterization of the sample complexity of learning optimization-safe polynomial surrogates.

In this paper we study the class of graphs without cycles of size 4 and independent sets of size 4 as induced subgraphs: $\mathop{Free}\{C_4, 4K_1\}$. This is one of the three minimal minimal open cases for the complexity of the colouring problem when restricted to classes defined by excluding induced subgraphs of order 4. We investigate the clique width of some subclasses of $\mathop{Free}\{C_4, 4K_1\}$. We introduce a new framework: the $(k,l,m)$-decomposition and prove that if all the graphs of a class $\cal G$ are $(k,l,m)$-decomposable, then graphs in $\cal G$ have bounded clique width. We give a few examples of such class, found with the help of a program we designed. We also show, for any graph $G \in \mathop{Free}\{C_4, 4K_1\}$ that is 3 cliques coverable, an infinite family in $\mathop{Free}\{C_4, 4K_1\}$ of supergraphs of $G$ which have unbounded clique width.

For a finite poset $\mathcal{P}$, its height $h(\mathcal{P})$ is the number of cover relations in its longest chain. When $\mathcal{P}$ is a lattice $\mathcal{L}$, we label its elements $x$ with $h(x_\downarrow) = h([\hat{0},x])$ and its cover relations $x \lessdot y$ with $h(y_\downarrow) - h(x_\downarrow)$. When a lattice $\mathcal{L}'$ extends $\mathcal{L}$, $h(x_\downarrow)_\mathcal{L} \leq h(x_\downarrow)_{\mathcal{L}'}$. We study lattices $\mathcal{L}$ and $\mathcal{L}'$ such that $h(x_\downarrow)_\mathcal{L} = h(x_\downarrow)_{\mathcal{L}'}$. Cover relations labeled $1$ in $\mathcal{L}$ induce a poset that we call the (long) skeletal poset $\mathrm{SK}(\mathcal{L})$. Its Hasse diagram is the largest spanning subgraph that the Hasse diagrams of $\mathcal{L}$ and $\mathcal{L}'$ have in common. An example of lattices $\mathcal{L}$ and $\mathcal{L}'$ is the alt-Tamari lattices introduced by Chenevière, where every alt-Tamari lattice $\mathrm{alt}\text{-}\mathrm{Tam}_n$ extends the Tamari lattice $\mathrm{Tam}_n$/refines the Dyck lattice $\mathrm{Dyck}_n$ such that $h(x_\downarrow)_{\mathrm{Tam}_n} = h(x_\downarrow)_{\mathrm{alt}\text{-}\mathrm{Tam}_n}$. We study $\mathrm{SK}(\mathrm{Tam}_n)$ with another poset we introduce. We enumerate intervals in these posets. For a well-chosen distributive lattice, we introduce its altitude lattices, which generalize the alt-Tamari lattices $\mathrm{alt}\text{-}\mathrm{Tam}_n$. Altitude lattices within a family have the same number of linear intervals. They are related to each other via extensions, refinements, and embeddings of some skeletal posets. For a poset $\mathcal{P}$ with $\hat{0}$, we define its Kneser graphs $KG(k) := (V(k),E)$, where $V(k) := \{x: h(x_\downarrow) = k, 1 \leq k \leq h(\mathcal{P})\}$ and $E := \{(x,y): x_\downarrow \cap y_\downarrow =\hat{0}\}$. We give some observations about them in a reconstruction setting.

The end space of an infinite graph arises naturally in many contexts as an important invariant and an interesting construction. It compactifies a locally finite graph and Diestel shows how to extend the end space to a larger space, called the tangle space, which is able to compactify any infinite graph. In both ends and tangles, it is the vertex-connectivity structure of the graph that is being studied. If we switch our attention to edge-connectivity, we can analogously define edge-ends. There is a space known as the edge-direction space which turns out to play an analogous role as the tangle space in its relationship with the end space: the edge-direction space provides a larger compact space in which the not necessarily compact space of edge-ends lives in. In this paper, we make this analogy precise, providing a natural edge analogue definition of tangles and proving they result in exactly the edge-directions. We also describe a combinatorial construction of certain Boolean algebras which give rise, via Stone duality, to the tangle and the edge-direction spaces. Finally, we pursue functorial definitions of the combinatorial constructions used in the paper, inspired by the famously functorial nature of Stone duality and by previous work by one of the authors and colleagues on trying to functorialize the end space construction. We hope our work will provide foundation and inspiration for further work on infinite graph theory that makes ample use of category theory and powerful algebraic constructions such as Boolean algebras and Stone duality.