AI 速览：作者报告构造出经典色数任意大而量子色数恒为3的图，首次改进了自 Brassard–Cleve–Tapp 以来的量子色数间隙。
We confirm a conjecture of the first author [SODA'26] on a strong form of pseudo-telepathy for Khot's $d$-to-$1$ games: for every $d\geq 4$, every $ε>0$, and every $k\in\mathbb N$, there is a $d$-to-$1$ label-cover game of classical value less than $ε$ that admits a perfect quantum strategy using finite-dimensional shared entanglement with measurement contexts of radius at least $k$. As a consequence, there exist graphs whose quantum chromatic number $χ_q$ is $3$ and whose classical chromatic number $χ$ is arbitrarily large. This is the first improvement on the quantum chromatic gap since the work of Brassard, Cleve, and Tapp [Phys. Rev. Lett.'99], which produced graphs for which $χ$ grows exponentially in $χ_q$. To prove the conjecture, we proceed as follows. We start with a ``stretched'' version of the Mermin--Peres magic square, obtained by spacing out its equations and linking them with additional long equation wires. This operation increases the radius of the initial measurement contexts of a perfect quantum strategy for the game, while preserving classical unsatisfiability. We then apply parallel repetition to make the classical value small, and we turn the system into a pseudo-telepathic multi-layered Kneser hypergraph via a PCP construction of Dinur, Guruswami, Khot, and Regev [STOC'03]. Finally, we feed the resulting hypergraph into the reduction of Fei, Minzer, and Wang from hypergraph colouring to $4$-to-$1$ games, we establish quantum completeness of this reduction, and we show that it preserves context radius.
Ziad Ismaili Alaoui, Oded Lachish, Nikhil S. Mande
AI 速览：作者在割查询模型下证明，确定性寻找锦标赛中“国王”的查询复杂度为 Θ(n)。
A king in a tournament is a vertex from which every other vertex is reachable by a directed path of length at most two. We study the deterministic query complexity of finding a king when a query specifies a set of vertices and returns the number of edges directed from that set to its complement. We prove that this complexity is $Θ(n)$ for $n$-vertex tournaments. To show this, we first show that every correct deterministic algorithm in this model must output a maximum-outdegree vertex, even though a king need not have maximum outdegree. We then give an adversary whose answers, after too few queries, remain consistent with a tournament in which the algorithm's output does not have maximum outdegree.
Average pairwise Hamming distance of a subset in a hypercube
Yijia Fang, Hao Huang
AI 速览：作者证明密度为1/8的{0,1}^n子集的平均成对汉明距离至少为(n-3)/2，且等号仅由(n-3)维子立方体达到。
In this note, we prove that for a subset $\mathcal{F}$ of $\{0,1\}^n$ of density $\frac{1}{8}$, its average pairwise Hamming distance is at least $\frac{n-3}{2}$, with equality attained only by $(n-3)$-dimensional subcubes. This answers a question of Lei Yu, and solves an important open case of a more general question posed by Ahlswede and Katona in 1977.
Half-Optimal Induced Matchings in Random Graphs: Online and Low-Degree Algorithms
Abhishek Dhawan, Eren C. Kızıldağ, Neeladri Maitra, Cheng Mao, Timothy L. H. Wee
AI 速览：作者证明在 Erdős-Rényi 随机图中，寻找大诱导匹配存在尖锐的因子二间隙：简单在线贪心可达约一半最优，而在线算法与低阶多项式算法均无法突破该阈值。
For many optimization problems on random graphs, most prominently the largest independent set problem, natural algorithms reach only half the optimum, and such factor-two gaps are known to be sharp within broad algorithmic classes. We prove such a gap for finding large induced matchings in Erdős-Rényi random graphs. In the worst case, requiring a matching to be induced turns a polynomial-time solvable problem into an NP-hard one; our results reveal an average-case counterpart. In $G(n,p)$ with $C/n\le p\le 1-κ$, the largest induced matching has size $(1+o(1))L$ with high probability, where $L=\log_{1/(1-p)}(np)$. A simple online greedy algorithm finds an induced matching of size $(1/2-ε)L$, while no online algorithm, even with adaptive inspection order and unbounded computation, finds one of size $(1/2+ε)L$ except with probability $\exp(-Ω(L\log(np)))$. In the sparse regime $p=d/n$, low-degree polynomial algorithms exhibit the same sharp threshold. Our guarantees rest on a maximality principle: with high probability, every maximal induced matching is half-optimal. Greedy outputs a maximal induced matching and our low-degree algorithm a near-maximal one. We bypass the delicate coupling arguments classically used to analyze greedy since Karp. For low-degree hardness, we adapt Wein's overlap gap argument, with forbidden structures that track overlaps between endpoint sets rather than edge sets, since a new edge may join two previously used endpoints and thus encounter no fresh randomness. For online hardness, we give a new and significantly simpler argument that avoids the correlated instances of prior OGP-based proofs: at a suitable stopping time, all pairs involving uninspected vertices remain unrevealed, so a direct first-moment bound suffices.
Recently, Chudnovsky, Cook, Davies, Oum, and Tan obtained the first finite bound on the chromatic number of t-perfect graphs, showing that they are 199053-colorable. We improve this bound to 130 by refining their proof. The original proof establishes that every graph with large odd girth and large chromatic number contains a certain structure called an r-arithmetic rope, and that its existence in a certain leveling of a graph with large odd girth would imply an odd wheel as a t-minor, a known obstruction to t-perfectness. While their technique requires a lower bound on the chromatic number that is exponential in r, we show that the existence of an r-arithmetic rope can already be guaranteed under a linear bound. Using a slightly weakened notion of arithmetic ropes allows us to reduce the bound even further.
For fixed nonempty words $u,v$, the minimum insertion degree of a shuffle is the least number of inserted-source runs among its representations. We prove that, after a block exchange from a minimum mask of degree $r$, the minimum over masks with commuting source projections is exactly $r-1$; a larger decrease occurs precisely when a noncommuting mask has fewer runs. If either source is unary, every such exchange is exact. We prove an explicit repair for an infinite periodic degree-three family. Computer-assisted results establish first-mask descent through combined length seventeen over every alphabet, degree-three first-mask descent through length thirty, and a uniform repair of all degree-three failures through length thirty, including all further letter identifications. Counterexamples to arbitrary, first, and last minimum-mask choices explain the need for alternative masks. Finally, we prove that minimum iteration depths have no gaps for arbitrary languages. General block-exchange descent and Singleton No-Gap remain open.
We complete the determination of the minimum possible length of eight-dimensional binary self-orthogonal codes with given minimum distance. For dimension nine we give exact values and bounds for minimum distance at most $64$. By exploiting the geometric reformulation of linear codes as multisets of points, we fully redo the classification for dimension at most seven in a simplified and computer-free manner. As a by-product we prove the non-existence of $[93,9,44]_2$ codes and show several divisibility results for putative optimal nine-dimensional binary codes.
Kellerhals, Krebs, Nichterlein, and Schmid introduced the optimization problem Tree in Binary Tree (TBT), where, given a tree $T$, the task is to find a binary tree $S^*$ with $V(T)=V(S^*)$ that minimizes $\sum_{uv\in E(T)} \operatorname{dist}_{S^*}(u,v)$. They also introduced the variant Tree in Binary Tree With Steiner Nodes (TBT-SN), where the condition $V(T)=V(S^*)$ is relaxed to $V(T)\subseteq V(S^*)$. We give a simple linear-time $\frac{8}{3}$-approximation algorithm for TBT and a polynomial-time approximation scheme (PTAS) for TBT-SN. Our main building idea in both algorithms is to iteratively consider subtrees of the tree $T$ which contain all vertices below some vertex $v$ and construct a solution where $v$ has degree 1. For the PTAS, we cut $T$ into smaller trees, solve these instances, modify the obtained solutions, and combine them to achieve a solution for the original instance.
Let $S$ be a reachable image of a strongly connected synchronizing automaton and $\varnothing\ne A\subsetneq S$. We determine the maximum shortest avoid-or-compress length over binary and arbitrary finite alphabets for $m=n-|S|=4$ and $m=5$. The exact values are $\min(n-|A|,11)$ and $\min(n-|A|,14)$, respectively. Uniform binary constructions attain both bounds. For the upper bounds, short-pair graphs and actual-image constraints reduce all parameters to finite necessary domains. Exhaustive checks exclude the domains, apart from a single relaxation eliminated by a multipartite overlap lemma. The largest calculation covers 3,206,988 domains.
We prove that finite two-graphs have coherent EPPA and that neither graphs modulo global complementation nor two-graphs modulo global complementation have EPPA. This completes the classification of EPPA and coherent EPPA for the reducts of the random graph, answering a question and confirming a conjecture of Evans, Hubička, Konečný and Nešetřil.
Yuta Inoue, Ken-ichi Kawarabayashi, Atsuyuki Miyashita, Bojan Mohar, Carsten Thomassen, Mikkel Thorup
The famous Four Color Theorem (4CT) states that any planar graph can be colored with four colors, but how do we find a 4-coloring? In our previous paper [FOCS'26], we presented a simple combinatorial algorithm to 4-color planar graphs in $O(n\log n)$ time. We improve it here to $O(n)$ time, which is optimal. The algorithm from our previous paper is based on proving that every planar triangulation has a linear number of reducible configurations or obstructing cycles. The bottleneck for the algorithm is that we need $O(\log n)$ Kempe changes to extend a recursive 4-coloring to the reducible configurations. Each Kempe change can involve a constant fraction of the graph and takes linear time. Here we show that all $O(\log n)$ Kempe changes can be identified and implemented in $O(n)$ time. The idea is to spend $O(n)$ time to preprocess the graph so that we can identify and simulate each good Kempe change in $O(n/\log n)$ amortized time. Thus, we implement all $O(\log n)$ Kempe changes in $O(n)$ total time. Based on this, we implement the whole 4-coloring in linear time. We note that creating such a representation for fast identification and simulation of the right Kempe changes is a challenge of data structures, unlike the previous paper that builds on a new graph theoretic understanding of reducible configurations.
For an integer $h\geq2$, an edge-ordered $h$-uniform hypergraph $H^<$ is an $h$-uniform hypergraph with a linear ordering of its hyperedges. For an integer $q \geq 1$, the edge-ordered Ramsey number $R_{\mathrm{edge}}(H^<;q)$ of $H^<$ is the smallest positive integer $N$ such that there exists an edge-ordered $h$-uniform hypergraph $G^<$ on $N$ vertices such that, for every $q$-coloring of the hyperedges of $G^<$, there is a monochromatic copy of $H^<$ in $G^<$ preserving the hyperedge order. In this note, we show that, for every edge-ordered $h$-uniform hypergraph $F^<$ on $n$ vertices with $m\geq1$ hyperedges, $R_{\mathrm{edge}}(F^<;q) \leq R_h(F;q)^{Cm^2}$ where $F$ is the underlying unordered hypergraph, $R_h(F;q)$ is its standard $q$-color Ramsey number, and $C=C(h,q)>0$ is a constant. For fixed $h\geq3$ and $q\geq2$, this shows that prescribing the hyperedge order does not require an increase in the tower height of the classical upper bound. It also settles a problem posed by Fox and Li (2020), and for $h=2$ gives the bound $2^{O(n^4\log n)}$, improving their bounds for every fixed $q \geq 3$.
Triadic closure is a natural mechanism for modeling the clustering phenomenon observed in many real-world networks. Given a possibly random undirected graph $H$, we consider pairs of non-adjacent vertices that have a common neighbor. Conditional on $H$, each such pair is joined by an edge independently and simultaneously, with a probability depending on the degrees of its endpoints and on the number of their common neighbors. The resulting graph is called a triadic closure of $H$. We study the effect of this operation on local convergence. More precisely, we prove that if a sequence of potentially random finite undirected graphs of $\left( H_n \right)_{n \in \mathbb{N}}$ converges locally in probability to a rooted graph $H^*$, then the corresponding sequence of triadic closures converges locally in probability to the same triadic closure of $H^*$. As a consequence, we obtain a general limit theorem for the clustering coefficients of triadic closures. In particular, we show that the triadic closures can have a strictly positive limiting clustering coefficients even when the limiting clustering coefficients of the parent graph sequence is zero. Finally, we apply our results to several classical sparse random graph models including Erdős-Rényi, configuration, preferential attachment models and compute the limiting clustering coefficients of their triadic closures.
Expander graphs have been central objects of study for over fifty years. Ramanujan graphs attain the asymptotically optimal nontrivial adjacency-eigenvalue threshold for infinite fixed-degree families. The original arithmetic constructions by Lubotzky-Phillips-Sarnak (1988) and Margulis (1988), and the iterative $2$-lift method of Bilu-Linial (2006) provide different approaches to Ramanujan graph constructions. Motivated by work on Mealy automata, we combine both approaches to give the following new arithmetic construction. For every prime $p\equiv 1\pmod {17}$, we construct a infinite tower of $(p+1)$-regular non-bipartite Ramanujan graphs on $2^n$ vertices, with label-preserving $2$-lifts between consecutive levels. These construction is strongly explicit: for fixed $p$, a neighbor or lift sign is computable in $O_p(n^3)$ bit operations. The construction uses fixed algebraic $2$-adic transformations, specified by finite data computable in preprocessing depending only on $p$. The main number-theoretic tool is Blasius's Ramanujan-Petersson theorem for Hilbert modular forms, applied through the Jacquet-Langlands correspondence to obtain the sharp bound $|λ|\leq2\sqrt p$ for every nontrivial adjacency eigenvalue of our $(p+1)$-regular graphs. The transformations preserve $2$-adic distance, which gives the binary covers and an explicit formula for their signings.
A set $S$ of vertices of a graph $G$ is a mutual-visibility set if every pair of vertices of $S$ is joined by a shortest path whose internal vertices avoid $S$, and the mutual-visibility chromatic number $χ_μ(G)$ is the least number of mutual-visibility sets into which $V(G)$ can be partitioned. Klavžar, Kuziak, Valenzuela Tripodoro and Yero (2025) proved that $χ_μ(G)\leχ(G)$ whenever $G$ has diameter two, observed that equality holds for complete bipartite graphs, and asked whether there are any other diameter-two graphs attaining equality. We answer this question in the affirmative. We construct a graph $G_{11}$ of order 11 and diameter two with $χ_μ(G_{11})=χ(G_{11})=3$, and an infinite family of such graphs obtained from $G_{11}$ by replacing one vertex with pairwise non-adjacent copies of it.
An identifying code of a graph is a dominating set $C$ such that the sets $N[v]\cap C$ are pairwise distinct. The minimum density of an identifying code has been studied extensively for several infinite grids. It is known to be $1/4$ for the triangular grid and $7/20$ for the square grid, whereas for the hexagonal grid the problem is still open, between $5/12$ and $53/126$. These three grids are the regular members of the family of the eleven Archimedean grids. In this paper, we start a systematic study of identifying codes in this family. We determine the minimum density for five of the nine Archimedean grids for which it was not known: it is $2/3$ for the truncated hexagonal grid, $3/7$ for the truncated square grid, and $1/3$ for the trihexagonal (kagome) grid, the elongated triangular grid and the snub hexagonal grid. All lower bounds are proved by the discharging method. For the three remaining non-regular Archimedean grids, we also obtain some bounds: the minimum density lies between $3/7$ and $13/30$ for the truncated trihexagonal grid, between $1/3$ and $11/30$ for the rhombitrihexagonal grid, and between $2/7$ and $9/28$ for the snub square grid. As a by-product, we prove that every identifying code of a cubic graph with the slow growth property in which every vertex lies on exactly one triangle (resp. $4$-cycle) has density at least $2/3$ (resp. $3/7$).
Call a finite nonempty point set $S\subset\mathbb{R}^d$ all-even if for every direction $\ell \in \mathbb{P}(\mathbb{R}^d)$, the number of hyperplanes perpendicular to $\ell$ that intersect $S$ is even. In 2026, Francisco Santos presented a question of Juan Benigno Seoane-Sepúlveda on the existence of all-even sets in dimensions $3$ and higher, together with examples of such sets in dimension $2$. Call a set $S\in\mathbb{R}^d$ line-all-even if for every direction $\ell \in \mathbb{P}(\mathbb{R}^d)$ the number of lines parallel to $\ell$ that intersect $S$ is even. As Santos pointed out, every all-even set in $\mathbb{R}^3$ is line-all-even. We conjecture that there exist no line-all-even sets in $\mathbb{R}^3$ that affinely span $\mathbb{R}^3$ We show that our conjecture is equivalent to the statement that every planar all-even set satisfies a certain property, which we call height-rigidity. This property has a natural interpretation in linear algebra terms. Furthermore, we present a hierarchy of properties of planar point sets that imply height-rigidity. We construct several all-even sets in the plane, including some infinite families, and show that all the sets we constructed are height-rigid. In addition, we prove that every all-even set in the plane that can be covered by six or fewer parallel lines is height-rigid.
The balance constant is a poset parameter measuring how well random linear extensions can be split according to their relative order on two elements. We give an $\varepsilon$-improvement for the balance constant over the bound by Brightwell, Felsner and Trotter (1995), for some small $\varepsilon>0$. This is the first general result towards the $\frac{1}{3}$--$\frac{2}{3}$ conjecture in over 30 years.
Joshua Brakensiek, David Conlon, Venkatesan Guruswami, Xiaoyu He, Jiaxi Nie, Maya Sankar, Hung-Hsun Hans Yu
In the study of constraint satisfaction problems (CSPs), the non-redundancy of a relation measures the maximum number of clauses in a CSP instance which can be logically independent. In the last few years, CSP non-redundancy has found a number of applications including in query complexity, sparsification, kernelization and streaming. In this paper, we present a novel technique for upper-bounding the non-redundancy of some relations using locally decodable codes (LDCs) and locally correctable codes (LCCs). More precisely, known limitations on the structure of 2-query LDCs and LCCs can be translated into limitations on the size of certain non-redundant CSP instances. This technique builds on a technique used by Brakensiek and Guruswami [STOC 2025] to bound non-redundancy via techniques from matching vector codes. Using LDCs and LCCs, we give improved upper bounds on non-redundancy of the BCK predicate pioneered by Bessiere, Carbonnel, and Katsirelos [AAAI 2020] as well as its well-studied Boolean variant. We also give the first example of a Boolean predicate whose non-redundancy is provably not of the form $n^{k\pm o(1)}$ for some positive integer $k$.
We give the first explicit constant for crossing families of linear size by showing that every set of $n$ points in general position in the plane contains a crossing family of size approximately $\frac{n}{79}$. We further identify some conditions where there are even larger crossing families. The first such condition forbids the existence of a large different pattern, namely non-convex 4-clusters: We show that every point set contains either a large non-convex 4-cluster or a large crossing family. The second condition is the existence of many crossings: We give a bound for the size of a crossing family in terms of the number of crossings of the complete geometric graph drawn on the point set.
We investigate a simple method to compute an unbiased estimate of the number of nodes of a directed acyclic graph (DAG) by following a random directed path. This method is due to Leonard Pitt from 1987, and it generalizes a method of D. E. Knuth from the 1960s for estimating the size of a rooted tree. A slight variation makes it possible to estimate the number of source-sink paths. We extend the algorithm to use many "agents" that walk cooperatively through the graph. This extension unifies and generalizes several methods that have been proposed for approximately counting the nodes of a tree.
Let $X$ be a random vector in $\mathbb{F}_2^m$, and let $X'$ be an independent copy. We prove that, for every $\varepsilon>0$, there is a subspace $G$ with $\dim G\le 2^{320(1+\varepsilon)/\varepsilon}H(X)$ such that $H(q_GX)\le(1+\varepsilon)(H(q_GX+q_GX')-H(q_GX))$. In particular, the quotient entropy is at most $(1+\varepsilon)(H(X+X')-H(X))$. The coefficient is independent of the ambient dimension, and its exponential order in $1/\varepsilon$ is necessary. The structural result is a logarithmic rigidity estimate for finite weighted families of laws with averaged subspace entropy sparsity. A common variational quotient controls both a family and its convolution family without decreasing the original family's normalized mean entropy defect. Posterior families preserve averaged sparsity, and a fresh-index argument combines a local-to-global estimate with the entropic Marton theorem to increase the defect ratio at a fixed multiplicative sparsity cost. We also obtain two-input almost-additivity and concentration of moderate-doubling sets on subspace cosets at the same exponential scale. The constants are not optimized.
Every semi-magic square of order $n$ satisfies the axial moment identities $\sum_{i,j}s_{ij}j^m=\sum_{i,j}s_{ij}i^m=M(n)\sum_jj^m$ for all $m\ge1$, where $M(n)=n(n^2+1)/2$. For real matrices the converse requires $1\le m\le n-1$, whereas for arrangements of $\{1,\dots,n^2\}$ fewer moments suffice once $n\ge14$. We define the permutation threshold $k^*(n)$ as the least $k$ such that every arrangement satisfying these identities for $1\le m\le k$ is semi-magic. In terms of the column-sum deviations $γ_j$, the degree-$k$ conditions state that $\sum_jγ_jt^j$ is divisible by $(t-1)^{k+1}$, linking $k^*(n)$ to the Prouhet--Tarry--Escott problem. While Schur's bound on real zeros gives $k^*(n)\le\sqrt{2(n-1)\log(n^4/4)}$, we prove the converse realisability bound $k^*(n)\ge(\sqrt2-o(1))\sqrt n$ (and $k^*(n)\ge(\sqrt6-o(1))\sqrt n$ when $4\mid n$) by perturbing semi-magic squares with complementary row pairs via horizontal swaps. We also show that $k^*(n)=n-1$ for $3\le n\le13$, $k^*(n)=n-2$ for $14\le n\le17$, and $k^*(n)\le n-3$ for $n\ge18$, and determine $k^*(n)$ for $18\le n\le40$ with computer assistance. Finally, at the $k=1$ level of the hierarchy, we specialise the Mantel--Hubert quadratic assignment variance formula to obtain exact means, variances, and limit laws under a uniform random arrangement for the full line-sum energy $E_{\mathrm{full}}$, for the four-term energy $E_4$ combining the first moments and the two diagonals, and for Loly's moment of inertia, and find that $|L_4|=14{,}639{,}440$ arrangements of order $4$ satisfy $E_4=0$.
We construct three binary extremal self-dual codes of length $60$ with weight enumerators for which no binary extremal self-dual codes of length $60$ were previously known to exist. This completes the determination of the weight enumerators that occur for binary extremal self-dual codes of length $60$.
Given an arrangement of $\{1,\dots,n^2\}$ in an $n\times n$ grid, we lift each cell to $\mathbb{R}^3$ by centring its grid coordinates $(x,y)$ at the origin and taking its centred entry $z = s_{ij} - (n^2+1)/2$ as a vertical height. The convex hull of these $n^2$ points is the gem of the arrangement, whose lower and upper boundaries are the regular subdivisions of the grid induced by $\pm z$. While random arrangements and generic linear magic squares have gems whose vertex counts grow with $n$, our main theorem shows that the classical Siamese (de la Loubère) magic square of every odd order $n\ge5$ has $f$-vector $(12,26,16)$, isometry group $\{\pm\mathrm{id}\}$, and only the twelve vertices forced by the boundary of the grid. The proof shears the lift onto five horizontal terraces and reduces the hull calculation to a finite table of polynomials in $m=(n-1)/2$; the same method gives $f$-vector $(12,24,14)$ for the base-$n$ digit-exchanged square. Along any family of linear squares with fixed steps the $f$-vector is eventually periodic in $n$, whereas over all linear magic squares of prime order $n$ the maximum vertex count grows as $Θ(\ln n)$. Whenever the heights have vanishing first moments, a short principal-axes argument shows that the point set has a non-trivial isometry if and only if the arrangement is self-complementary up to dihedral symmetry. An exact census of the $880$ magic squares of order four yields $616$ congruence classes and $352$ combinatorial types of gems, and shows that while vertex and facet counts are nearly insensitive to the magic line-sum conditions, the volume and solid centroid shift systematically.
L-extendable functions on the integer lattice are functions that admit a $\frac12$UJ-convex relaxation; that is, values can be assigned to the additional half-integral points, while keeping the original values at integer points, so that the resulting function is $\frac12$UJ-convex. Various examples of L-extendable functions and their applications are known. A general characterization of L-extendability for functions on the integer lattice, however, remains open. In this paper, we study the L-extendability of functions on the integer lattice. We first obtain a necessary condition: L-extendable functions are integrally convex. We then consider a special subclass of L-extendable functions, namely, those whose local convex extensions give L-convex relaxations. This subclass has a useful optimization property: the optimal value of the original function coincides with that of the $\frac12$UJ-convex relaxation given by its local convex extension, a property not guaranteed for general $\frac12$UJ-convex relaxations. We characterize this subclass by showing that a function is L-extendable through its local convex extension if and only if it is integrally convex and its restriction to every unit hypercube is D-convex, where D-convexity is a discrete convexity associated with reflected Freudenthal simplicial divisions. This subclass strictly contains the class of D-convex functions. We also give a combinatorial characterization of D-convex subsets of the vertices of a unit hypercube: a set $X\subseteq\{0,1\}^n$ is D-convex if and only if it is majority-closed and contains a relative opposite pair.
We show that for every prime power $q$ and $ρ\in(0,1-\frac1q)$ there exists $\varepsilon_0(q, ρ) > 0$ such that for all positive $\varepsilon < \varepsilon_0(q, ρ)$, a random linear code over $\mathbb{F}_q$ of rate $1-h_q(ρ)-\varepsilon$ has list size $\lfloor h_q(ρ)/\varepsilon\rfloor$ or $\lfloor h_q(ρ)/\varepsilon\rfloor+1$ with probability $1-o(1)$. Before this work, the list size was known only up to a constant factor for $q\ge3$, and for $q=2$ it was known to be either $\lfloor h_2(ρ)/\varepsilon\rfloor-1$, $\lfloor h_2(ρ)/\varepsilon\rfloor$ or $\lfloor h_2(ρ)/\varepsilon\rfloor+1$. We also show that the same two-point concentration holds for the list size of random LDPC codes. This follows from a general theorem establishing that random LDPC codes and random linear codes have the same threshold rate for distance, list decoding, list recovery from errors and any other \emph{convex} property, which answers a question of Mosheiff, Resch, Ron-Zewi, Silas and Wootters.
We study classes of permutations that are defined by avoidance of forbidden patterns. For each fixed finite set $B$ of forbidden patterns, we study the \emph{avoider enumeration problem}: given an integer $n$, output all $B$-avoiding permutations of length $n$. Avoider enumeration is output-polynomial for every fixed $B$. However, our main notion of efficiency is polynomial delay. We use the insert-maximum tree as a search tree, in which permutations are built by repeatedly inserting a new maximum while preserving pattern avoidance. This leads to the \emph{insert-maximum extension problem}, which asks if a given permutation has an avoiding descendant at a specified depth. An algorithm for this problem can prune branches that cannot reach the target length. Hence, if this problem is in P, we obtain polynomial-delay enumeration. To investigate this problem, we introduce and study \emph{pockets}, the maximal finite subtrees of the insert-maximum tree. For fixed $B$, if there is a polynomial $p$ such that every pocket rooted at $ρ$ has at most $p(|ρ|)$ nodes, then the extension problem is solvable in polynomial time and enumeration has polynomial delay. In particular, a bound on pocket depth depending only on $B$ suffices. We prove such a bound if the class is well-quasi-ordered, has a regular insertion encoding, or if $B$ omits one of the three maximum-position types: leftmost, interior, or rightmost. We also prove that extension is in NP for every fixed $B$, even with binary-encoded target depth. On the negative side, we construct a fixed set of $55$ forbidden patterns for which extension is NP-complete. Consequently, enumerating valid extensions from a given starting permutation cannot have polynomial delay unless P=NP. This also answers a question of Hanika by showing that the forbidden permutation constraint satisfaction problem can be NP-complete for a fixed forbidden set.
We study conformal prediction under covariate shift with a known covariate density ratio, seeking prediction sets with minimum expected length under the target distribution. For every calibration sample size, we prove that the rule combining the inverse conditional-density score with randomized weighted conformal calibration minimizes this expected length among all rules valid over the full weighted-exchangeability class. We approximate the oracle using quantile and kernel histograms, including forest-weighted estimators, and select estimators and tuning parameters by resampling to estimate calibrated target length. On a bounded response domain, we bound excess length linearly in $L^1$ density error at fixed calibration size, without requiring a uniform positive lower bound on the true density. We also bound selection-pool and resampling errors. Under explicit growth conditions, the selected procedure approaches the same oracle while the calibration size remains fixed. Experiments on 36 known-density configurations and four public regression datasets compare coverage, prediction-set length, and runtime with existing methods. In targeted low-coverage and strong-shift comparisons, inverse-density selection yields shorter mean sets in most cases and lower mean runtime than the evaluated weighted baselines, with some differences in achieved coverage.