Papers

The greedy Tamari poset, inspired by the well-studied Tamari lattice, was recently defined by Dermenjian in the more general setting of greedy $\nu$-Tamari posets. Bousquet-Mélou and Chapoton counted intervals of the greedy $m$-Tamari poset in 2024 by solving a functional equation, and found that they are equi-enumerous to planar $(m+1)$-constellations. In this work, we give a combinatorial proof of this fact for the case $m = 1$, which also gives the refined enumeration conjectured by Bousquet-Mélou and Chapoton. This is done by establishing a recursive decomposition of greedy Tamari intervals isomorphic to that of bipartite planar maps. We also propose a more general and refined conjecture for the case of general $m$.

Let $F(N)$ denote the largest cardinality of a Sidon subset of $\{0,1,\ldots,N-1\}$. We prove \[ F(N)\le N^{1/2}+\gamma_0N^{1/4}+O(1), \qquad \gamma_0=0.94349\ldots<0.9435. \] This improves the previously published coefficient $0.98183$. Our argument develops a vector-valued smoothing method that combines several discrete smoothing kernels, each accompanied by boundary weights that compensate for endpoint effects, so that their weighted combination satisfies the required finite covering inequalities. We also show that averaging systems that satisfy these inequalities individually cannot improve upon the best constituent. Numerical optimization is used to find an eight-component candidate system, which is then certified by exact rational arithmetic.

Very recently, using Meshulam's lemma, Blagojević proved a constrained version of the colorful Carathéodory theorem for joins of bipartite spanning trees and wedge of spheres. Our main contribution extends his result from joins of bipartite spanning trees with wedges of spheres to joins of spanning \(k\)-trees with wedges of spheres. Our proof is elementary and avoids the topological machinery. We also discuss a homological variation of spanning \(k\)-trees and some Carathéodory-type results for them.

In this paper, we investigate the combinatorial structure arising from the $(p, q)$-deformed generalized Weyl algebra generated by variables $X, Y$, and $Z_p$, satisfying the $(p, q)$-commutation relations $XY-qYX=h Y^sZ_{p}, XZ_p=pZ_pX$, and $Z_pY=pYZ_p$, where $s\in \mathbb{N}_0$. Our primary objective is to use the normal ordering process defined by these relations to develop a novel model of $(p, q)$-deformed rook theory. Specifically, we introduce a new framework of $(p, q)$-deformed $s$-rook numbers derived from this normal ordering process. Utilizing these combinatorial models, we provide explicit combinatorial interpretations for the associated $(p, q)$-generalized Stirling numbers via rook placements on staircase boards. Our results extend several classical and recent formulations in the literature to the general $p\neq 1$ setting.

The generalized honeymoon Oberwolfach problem (HOP) asks whether it is possible to seat $2n$ participants consisting of $n$ newlywed couples at a conference with $s$ tables of size $2$ and $t$ "round” tables of sizes $2m_1, 2m_2, \ldots, 2m_t$, where $n = s + \sum_{i=1}^{t} m_i $ with all $m_i \geq 2$, over several nights so that each participant sits next to their spouse every time and next to each other participant exactly once. We denote this problem by $HOP(2^{\langle s \rangle}, 2m_1, \ldots, 2m_t)$. In this paper, we provide a complete solution to the generalized HOP with one round table, showing that the obvious necessary conditions for $HOP(2^{\langle s \rangle}, 2m)$ to have a solution are also sufficient.

Vizing's conjecture, dating back to 1963, asserts that \[ \gamma(G\mathbin{\square}H) \geq \gamma(G)\gamma(H) \] for all finite graphs $G$ and $H$, where $\gamma$ denotes the domination number and $\square$ denotes the Cartesian product. In 2000, Clark and Suen proved the universal bound \[ \gamma(G\mathbin{\square}H) \geq \frac{1}{2}\gamma(G)\gamma(H). \] Recently, Steiner obtained the first constant-factor improvement of the Clark–Suen bound, proving that \[ \gamma(G\mathbin{\square}H) \geq \frac{5+\sqrt{73}}{24}\gamma(G)\gamma(H) \approx 0.5643\,\gamma(G)\gamma(H). \] In this paper, we further improve the universal constant by proving that \[ \gamma(G\mathbin{\square}H) \geq \frac{2}{3}\gamma(G)\gamma(H) \] for all finite graphs $G$ and $H$. Thus, we raise the best known universal constant in the approximate form of Vizing's conjecture from $(5+\sqrt{73})/24$ to $2/3$.

We study the supersaturation problem in its edge-spectral form. Let $\lambda(G)$ be the adjacency spectral radius of $G$. Nikiforov proved that every $K_{r+1}$-free graph $G$ with $m$ edges satisfies $\lambda (G)\le \sqrt{(1\!-\!1/r )2m}$. Recently, Li, Liu and Zhang proved the same bound for every $F$-free graph $G$, where $F$ is any color-critical graph with $\chi(F)=r+1\ge4$, with equality only for regular complete $r$-partite graphs. It is then natural to ask how many copies of $F$ are forced once $\lambda (G)$ exceeds this threshold. Fang, Lin and Zhai answered this at the threshold itself, and conjectured that for any fixed $C>0$, the condition $\lambda (G)\ge \sqrt{(1\!-\!{1}/{r})2m} +C$ forces $\Omega\!\left(m^{(f-1)/2}\right)$ copies. In this paper, we answer this question with the best possible constant. Building on the proof framework of Fang, Lin and Zhai, we prove that for every color-critical graph $F$ with $\chi(F)=r+1\ge4$, there exists $\delta_F>0$ such that if $m$ is sufficiently large, $0<q\le\delta_F\sqrt m$, and $G$ is an $m$-edge graph with $\lambda^2(G)\ge 2\left(1-\tfrac1r\right)m+q$, then \[ N_F(G)\ge\bigl(B_F-o(1)\bigr)\,q\, m^{{(f-2)}/{2}}, \quad \text{where}~~ B_F:=\tfrac{\alpha_F}{4} (\tfrac{2r}{r-1} )^{{f}/{2}}, \] and the constant $B_F$ is best possible. Our result can be viewed as an edge-spectral counterpart of Mubayi's theorem, since it converts the spectral surplus $q$ into a linear number of copies of $F$, and it solves the conjecture of Fang, Lin and Zhai in a stronger form.

In the fair allocation problem under conflict constraints, the goal is to partition the vertices of a graph among agents in a fair manner, such that no two adjacent vertices are assigned to the same agent. We study this problem for agents with common preferences through the lens of three fairness criteria: stochastic-dominance envy-freeness up to one item for preference orders (SD-EF1), envy-freeness up to one item for monotone additive valuations (EF1), and envy-freeness up to one item from each side for general additive valuations (EF[1,1]). To do so, we introduce a hierarchy of variants of the strong chromatic number, a graph quantity introduced independently by Alon and Fellows in the early nineties. Our results reveal a close connection between fair allocation under conflict constraints and the first two levels of this hierarchy, providing a unified route to both existential and algorithmic results. For SD-EF1, we fully characterize the number of agents needed to guarantee a fair allocation of a given graph for every common preference order. For EF1 and EF[1,1], we provide analogous sufficient conditions, extending a result on path graphs due to Equbal, Gurjar, Igarashi, Kumar, Manurangsi, Nath, Saxena, Vaish, and Yoneda. We also show that, unlike in the SD-EF1 setting, the sufficient conditions for EF1 and EF[1,1] are not necessary in general. Our framework yields existential and algorithmic consequences in terms of the maximum degree. We obtain that every graph with maximum degree $\Delta$ admits SD-EF1, EF1, and EF[1,1] allocations for common preferences whenever the number of agents is at least $3\Delta-1$. We further provide, for any $\varepsilon>0$, deterministic polynomial-time algorithms that find such allocations whenever the number of agents is at least $(3+\varepsilon)\Delta$. These guarantees strengthen earlier work by Barman and Viswanathan on equitable colorings.

The success of deep learning models in classification and regression is widely attributed to the low-dimensional structure that real-world data tend to exhibit, despite their high-dimensional representation. This work attempts to provide a mathematical framework for binary classification on low-dimensional data, building on Cover's (1965) function-counting theory. With our framework, we aim to address the question of how the low-dimensional structure of the data affects the classification capabilities of learning models. Cover's theory relies on a general position assumption that blinds it to the underlying data structure. We refine this assumption to account for the low-dimensionality of the data and derive dichotomy counts that reflect the data structure. We further extend Cover's separation capacity and problem of generalization to the low-dimensional setting, enabling the impact of the underlying data structure on both to be analyzed.

Bergeron, Garsia, Haiman and Tesler conjectured in 1999 that, for all partitions $\mu,\lambda\vdash n$, the polynomial $(-1)^{|\mu|-\ell(\mu)}\langle \nabla m_\mu, s_\lambda\rangle$ has nonnegative integer coefficients, where $\nabla$ is the Bergeron–Garsia nabla operator, which acts diagonally on the modified Macdonald basis, and $m_\mu$ is the monomial symmetric function. In this article, we prove this conjecture, and more generally that $(-1)^{|\mu|-\ell(\mu)}\langle\nabla^r m_\mu,s_\lambda\rangle\in\mathbb{N}[q,t]$ for all $r\geq 1$. We establish a recursion showing that $(-1)^{|\mu|-\ell(\mu)}m_\mu$ has an expansion with coefficients in $\mathbb{Q}_{\geq 0}[q]$ in the symmetric functions $C_\alpha(1)$, where $C_a$ denotes the operator introduced by Haglund, Morse and Zabrocki. Combining this expansion with the compositional shuffle theorems of Carlsson–Mellit and Mellit, and with the Schur positivity of LLT polynomials, completes the proof. The same method, using the $e$-positivity of column LLT polynomials after the substitution $q\mapsto q+1$, also gives an $e$-positive analogue.

We resolve (for all sufficiently large $n$) a conjecture of Pilz on the symmetric difference $A\Delta (2A)\Delta \cdots\Delta (nA)$ for finite sets $A\subseteq \mathbb{N}$ of positive integers. We show that this set always has cardinality at least $n$ for large $n$.

Order polytopes for generalized snake posets were recently studied by von Bell et al. (2022), and are known to be unimodularly equivalent to strength-one flow polytopes for acyclic directed graphs strongly dual to generalized snake posets. Lee, Vindas-Meléndez, and Wang (2026) conjectured that the Ehrhart $h^*$-polynomials of these order polytopes are real-rooted. We prove this conjecture using a connection between these $h^*$-polynomials and non-nesting rook polynomials, which were recently introduced by Alexandersson and Jal (2024+) in connection with $P$-Eulerian polynomials for width two posets.

Let $G$ be a graph and $I(G)$ its edge ideal. The $p$-th squarefree power $I(G)^{[p]}$ is the monomial ideal generated by squarefree monomials corresponding to the matchings of size $p$ of $G$. In this paper, we provide a combinatorial characterization of when $I(G)^{[p]}$ is linearly related, i.e., when its first syzygy module is generated by linear forms. Moreover, for a $1$-dimensional flag simplicial complex $\Delta$ and its Stanley-Reisner ideal $I_{\Delta}$, which arises as the edge ideal of the complement graph of $\Delta$, we describe the shape of the Betti table of $I_{\Delta}^{[p]}$ and we give a combinatorial characterization of when $I_{\Delta}^{[p]}$ has a linear resolution.

We determine the minimal absolute value of a non-vanishing sum of $n$ fifth roots of unity chosen with repetition, and characterize the corresponding sums. As a function of $n$, the minimal absolute value is monotone non-increasing over congruence classes of $n$ modulo $5$ and its only jumps occur when $n=5F_m$, $n=L_m$, or $n=2L_m$, where $F_m$ and $L_m$ denote the $m$-th Fibonacci and Lucas numbers respectively. To prove our results we reduce the problem to a series of inequalities involving rational approximations of the golden ratio $\varphi=(1+\sqrt{5})/2$, the solutions of which can be characterized using the theory of continued fractions.

We introduce the lower and upper Wythoff-Fibonacci sequences, obtained from the classical Wythoff sequences by a Fibonacci correction. Specifically, if we put $$\epsilon(j)=\begin{cases}(-1)^k, & \text{if }j=F_k\text{ for some }k\\ 0, & \text{in other case}\end{cases},$$ where $F_k$ is the $k$-th Fibonacci number, then we define the general terms of the lower and upper Wythoff-Fibonacci sequences by $$LWF(n)=\begin{cases} 1, & \text{if }n=1,\\ 3, & \text{if }n=2,\\ a(n)+\epsilon(n), & \text{if }n\geq 3.\end{cases}$$ and $$UWF(n)=\begin{cases} 2, & \text{if }n=1,\\ b(n)+\epsilon(n), & \text{if }n\geq 2,\end{cases}$$ respectively. We show that these sequences partition the set of natural numbers and use them to give an explicit formula for a sequence $q^{\star}_j$, defined from a greedy construction studied by the first author and his coauthors in a previous paper, but with the additional condition that $q^{\star}_1=3$, instead of being defined by the greedy rule. This sequence is a permutation of the set of non-negative integers and has the property that every integer appears exactly once in the sequence of differences $q^{\star}_j-j$. We prove that $q^{\star}_{q^{\star}_j}=j\ \forall j\geq 5$, so that $q^{\star}_j$ is an almost-involution. We also give another greedy algorithm generating $q^{\star}_j$.

Let $\boldsymbol{a}=(a_i)_{i=1}^\infty$ be an infinite sequence of points on a circle. The first $n$ of these points cuts the circle into $n$ pieces. For any given $r$, let $\mu^r_n(\boldsymbol{a})$ be the ratio between the maximum and minimum sizes of $r$ consecutive pieces. Addressing a question of De Bruijn and Erdős, we define a family of sequences for which the asymptotic least upper bound of this ratio, \[ \mu_r(\boldsymbol{a}) \;=\; \limsup_{n\to\infty}\mu^r_n(\boldsymbol{a}) , \] can easily be calculated. Hence, for small $r$, we present upper bounds on $\inf\mu_r(\boldsymbol{a})$.

A graph $G$ is called $k$-edge-hamiltonian if every linear forest (i.e., a disjoint union of paths) with at most $k$ edges is contained in a Hamilton cycle of $G$. In 2018, Füredi, Kostochka and Luo determined the maximum number of $t$-stars in nonhamiltonian graphs, thereby extending an earlier result of Erdős. Recently, Berikkyzy, Hogenson, Kirsch and McDonald extended this line of research by determining the maximum number of $t$-stars in graphs that are not $k$-edge-hamiltonian, as well as in graphs failing to satisfy related properties such as traceability, hamiltonian-connectedness and $k$-hamiltonicity. For sufficiently large $t$, they also characterized the extremal graphs, while for smaller values of $t$, they proposed a conjecture. In this paper, we investigate this conjecture. We show that the conjecture fails at the critical value and further establish a threshold-type result describing the behavior of the extremal graphs when $t$ is close to this critical value.

Let \(F\) and \(G\) be \(r\)-uniform hypergraphs, and let \(f_{F,G}(n)\) be the largest integer \(m\) such that every \(n\)-vertex \(G\)-free \(r\)-graph contains an induced \(F\)-free subgraph on \(m\) vertices. We prove that, for \(r\ge3\) and \(2\le k\le r-1\), if \(F\) is nonempty, \(G\) is \(k\)-tightly connected, and there is no homomorphism from \(G\) to \(F\) (that is, \(G\not\to F\)), then \[ f_{F,G}(n)\le C(\log n)^{\beta_F^{(k)}}, \qquad \beta_F^{(k)}= \max_{\emptyset\ne P\subseteq\partial_kF} \frac{e(P)}{v(P)-1}. \] The case \(r=3\) of our result resolves a conjecture of He and Nie. As a consequence, we obtain the Ramsey lower bound \(r(G,K_n^r)\ge2^{\Omega\bigl(n^{(r-1)/\binom rk}\bigr)}\) for every \(k\)-tightly connected non-\(r\)-partite \(r\)-graph \(G\). This extends a result of Conlon, Fox, Gunby, He, Mubayi, Suk, Verstraëte and Yu from the \(3\)-uniform setting.

A graph is balanced if its clique-matrix contains no square submatrix of odd order with exactly two $1$'s in each row and in each column. Although it is known that a graph is balanced if and only if it contains no induced extended odd sun, a characterization of balanced graphs by minimal forbidden induced subgraphs is still unknown. In this work, we prove that, within the class of distance-hereditary graphs, balanced graphs are exactly the hereditary clique-Helly graphs. Equivalently, they are characterized by a single forbidden induced subgraph, namely $\overline{3K_2}$. From this result, we derive an explicit linear-time algorithm that decides balancedness within the class of distance-hereditary graphs and returns an induced $\overline{3K_2}$ when the input graph is not balanced.

We extend the analysis of nonrepetitive sequences of Entringer et al. [Journal of Combinatorial Theory, 1974] to relaxations of equality testing under nonstandard equivalence relations, in particular parameterized equivalence and order-preserving equivalence. For this setting, we introduce $\ell^+$-squares, defined as squares whose total length is at least $2\ell$. We obtain an infinite $3^+$-parameterized-square-free ternary word and an infinite $3^+$-order-preserving-square-free binary word through an approach based on combinatorics on words. In addition, we report the longest $\ell^+$-square-free words across several equivalence relations.

We provide a recurrence for computing the terms of the OEIS sequence A393920, introduced in \cite{KS}. We also describe a surprising connection between A393920 and the Fibonacci sequence A000045, obtain non-trivial lower and upper exponential bounds for its growth, and investigate connections with partial orders, Catalan numbers, and convex topologies on finite chains. For the representation-theoretic lattice underlying A393920, we describe its atoms, coatoms, join-irreducible and meet-irreducible elements.

In a previous work, we defined (type A) c-Birkhoff polytopes and showed that they were unimodularly equivalent to order polytopes of heap posets. In this note we answer the question: What about type B?

A connected graph is matching covered if it has at least one edge and every edge lies in some perfect matching.Lovász proved that every matching covered graph G can be uniquely decomposed into a list of bricks and braces up to multiple edges. Denote by b(G) the number of bricks in such a decomposition. An edge e of G is removable if G-e is also matching covered; is b-invariant if e is removable and b(G-e)=b(G). Furthermore, an edge e of G is a forcing edge if it lies in precisely one perfect matching of G. Lucchesi and Murty proposed the problem of characterizing bricks, distinct from K_4, \overline{C_6}, and the Petersen graph, in which every b-invariant edge is a forcing edge. In this paper, we solve this problem for near-bipartite bricks by providing a complete characterization.

A graph is non-$r$-partite if its chromatic number exceeds $r$. For an edge-color-critical graph $F$ with $\chi(F)=r+1$, let $\mathrm{ex}_{r+1,\rho}(n,F)$ be the maximum adjacency spectral radius among non-$r$-partite $F$-free graphs of order $n$, and let $\mathrm{EX}_{r+1,\rho}(n,F)$ and $\mathrm{EX}_{r+1}(n,F)$ be the families of such graphs attaining, respectively, this maximum spectral radius and the maximum number of edges $\mathrm{ex}_{r+1}(n,F)$. Fang and Lin conjectured that $\mathrm{EX}_{r+1,\rho}(n,F)\subseteq\mathrm{EX}_{r+1}(n,F)$ for every such $F$ and all large $n$. We prove a reduction principle: if $F$ is \emph{$s$-embeddable} and $\mathrm{ex}_{r+1}(n,F)=|E(T_{n,r})|-\lfloor n/r\rfloor+2(s-1)$, where $T_{n,r}$ is the Turán graph, then the inclusion holds and, moreover, the spectral extremal graph is unique. The reduction replaces the spectral problem by an edge-counting one, and its proof rests on a direct comparison of secular functions together with a second-order residual refinement of the Rayleigh principle. We then determine the spectral extremal graphs for all edge-color-critical complete multipartite forbidden graphs. For $F=K_{1,1,t_3,\ldots,t_{r+1}}$ with $t_3,\ldots,t_{r+1}\ge 2$ we show \[ \mathrm{ex}_{r+1}(n,F)=|E(T_{n,r})|-\Bigl\lfloor\frac nr\Bigr\rfloor+2(t_{\min}-1), \qquad t_{\min}:=\min\{t_3,\ldots,t_{r+1}\}, \] for all sufficiently large $n$, and we identify the unique spectral extremal graph; in particular $\mathrm{EX}_{r+1,\rho}(n,F)\subseteq\mathrm{EX}_{r+1}(n,F)$. The endpoint $t_3=1$ lies outside the embeddability framework and is treated by a separate argument: for $F=K_{1,1,1,t_4,\ldots,t_{r+1}}$ with $r\ge3$, the unique non-$r$-partite spectral extremal graph is $Y_r(n)$, obtained through a saturation reduction followed by the spectral refinement of Turán's theorem. The complete graph $K_{r+1}$ and the complete split graph $B_{r,q}$

Quantum contextuality is a vital non-classical resource, yet illuminating the precise mechanisms through which it enables unconditional computational advantages remains a challenge. We translate graph-theoretic formulations of contextuality into an unconditional quantum memory advantage for formal language recognition. We define a promise problem on an exclusivity graph $G$ where any classical finite automaton respecting exclusivity requires $N \ge \chi(G)$ memory states, whereas a QFA requires a memory of dimension $d = \xi(G)$. The gap between these bounds isolates a structural, information-theoretic incompatibility between classical and quantum descriptions that we term representational contextuality. For Boolean orthogonality graphs, this exacts an exponential classical memory penalty ($d=\mathcal{O}(n)$ vs $N=2^{\Omega(n)}$). Finally, we demonstrate a sharp algorithmic phase transition: allowing the classical machine a finite confusability of mutually exclusive events reduces this exponential classical memory cost to $\mathcal{O}(n)$.

Let $\mathcal Q=\{Q_a:a\geq1\}$ be a nested family of finite posets such that $Q_a\subseteq Q_{a+1}$ and $|Q_a|<|Q_{a+1}|$. For a poset $Q$, let $\mathcal C_t(Q)$ denote the set of all strict $t$-chains in $Q$. Given an $r$-coloring of $\mathcal C_t(Q_a)$ and posets $P_1,\ldots,P_r$, a weak copy of $P_i$ is called monochromatic of color $i$ if all $t$-chains in the copy have color $i$; the strong version is defined in the same way for induced copies. The corresponding weak and strong multiplicity parameters are the minimum possible total number of such monochromatic copies in the host poset.For the Boolean lattice $B_n$, define $E_n={(S,T,U)\in B_n^3:S\subsetneq T\subsetneq U,\ |S|+|T|=|U|}.$ For a two-coloring $\chi:B_n\to{0,1}$, a triple $(S,T,U)\in E_n$ is monochromatic if $\chi(S)=\chi(T)=\chi(U)$. Let $R^{\mathrm{arith}}_2$ be the least integer $n$ such that every two-coloring of $B_n$ contains a monochromatic triple in $E_n$, and let $M^{\mathrm{arith}}_2(B_n)$ be the minimum number of monochromatic triples in $E_n$ over all two-colorings of $B_n$. We prove that $R^{\mathrm{arith}}_2=9.$ Moreover, $|E_n|=\binom{2n}{n}-[x^n](1+x+x^2)^n-2^n+1=\frac{4^n}{\sqrt{\pi n}}\bigl(1+o(1)\bigr),$ and $2^{\delta n+o(n)}\le M^{\mathrm{arith}}_2(B_n)\le 2^{\gamma n+o(n)}, $ where $\delta\approx 1.356779$ and $\gamma\approx 1.567837$ are explicit entropy constants. For general nested host families, we prove a double-counting lower bound for strong poset multiplicity. For an arbitrary finite host poset $R$, we also introduce a Fourier-Möbius method and give an exact Fourier expansion for strong multiplicity, a Parseval-type error bound, and a spectral lower bound.

We introduce and study a subalgebra $\mathcal{B}$ of the affine Hecke algebra, which arises from a centralizer construction in the double affine Hecke algebra, and which may be regarded as a $v$-deformation of the affine Fomin-Stanley subalgebra introduced by Lam as a combinatorial model for the affine Grassmannian homology ring. In types $\mathsf{A}_n$ and $\mathsf{B}_2$ and $\mathsf{G}_2$, we show that $\mathcal{B}_\mathrm{aff}$ admits a canonical basis indexed by the cosets of the finite Weyl group in the affine Weyl group. We also discuss conjectural positivity properties of the canonical basis and explain how it can be used to study the center of the affine Hecke algebra.

We study finite-field analogues of the Peres–Schlag nonempty-interior problem for product sets. Given \(A\subseteq\mathbb F_p\), we ask when a suitable one-dimensional linear image of \(A^n\) is full; equivalently, when there exist coefficients \(t_1,\ldots,t_n\in\mathbb F_p\) such that \[ t_1A+\cdots+t_nA=\mathbb F_p. \] For \(n\ge3\), we prove that, for every \(\eta>0\), this holds whenever \[ |A|\gg_{n,\eta} p^{\frac{3}{2n-1}+\eta}. \] This improves the exponent predicted by the direct product-set analogue of the Peres–Schlag threshold, namely \(|A|\gg p^{2/n}\). We also prove a two-dimensional near-half-density result. Motivated by sum-product phenomena, we also introduce and study a product-type variant in which linear forms are replaced by shifted product maps. We prove finite-field covering results for shifted products \[ (t_1 + A)(t_2 + A)\cdots(t_n + A) \] at the same density scale as in the linear case. Finally, we prove a Euclidean shifted-product analogue: if \(A\subseteq\mathbb R\) is Borel and \(\dim_H A>2/n\), then some shifted product of \(n\) copies of \(A\) contains a nonempty open interval.

Let $\vec F(2^{\mathbb Z^2})$ be the directed Schreier graph on the free part of the Bernoulli shift $\mathbb Z^2\curvearrowright 2^{\mathbb Z^2}$, with arcs in the two coordinate directions. We prove that the continuous oriented chromatic number of it is 7, that is, there is a tournament on 7 vertices receiving a continuous graph homomorphism from $\vec F(2^{\mathbb Z^2})$ and there is no continuous graph homomorphism from $\vec F(2^{\mathbb Z^2})$ to any tournament on 6 vertices. And we prove that the Borel and measurable oriented chromatic number of directed Schreier graph $\vec F(2^{\mathbb Z^n})$, $n>1$ is 5.

We investigate the Peres–Schlag nonempty interior problem for orthogonal projections in both the finite-field and Euclidean settings. Over finite fields $\mathbb F_q^n$, we employ the polynomial method to establish sharp projection results, and uncover a new connection with stability versions of the finite-field \((n,m)\)-set problem. Over Euclidean spaces $\mathbb R^n$, we obtain improved nonempty interior results beyond those of Peres and Schlag in certain parameter ranges. Our proof combines techniques from geometric measure theory and harmonic analysis, including $L^p$-estimates for Kakeya maximal operators and maximal $k$-plane transforms.