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 show that the worst-case combinatorial discrepancy of $n$ points in the plane with respect to axis-parallel rectangles is $\Theta(\log^{3/2}n)$. The known bounds were $\Omega(\log n)$ and $O(\log^{3/2}n)$; we prove the matching lower bound. It holds for random point sets: for every $A>0$, there is a constant $c_A>0$...
We give an elementary proof that every positive rational number $a/b$ with $b$ squarefree is a finite sum of distinct unit fractions $1/n$, where each $n$ is a product of two distinct primes (Erd\H{o}s Problem #306). After a reduction to small targets, we take a single complete bipartite graph between the primes in $(y...
We prove that some pairs of binary words of every sufficiently large prescribed length $n$ require $\Omega(\log n\log\log n)$ states to separate by a deterministic finite automaton whose letters act as permutations. We obtain this bound by constructing distinct equal-length positive binary words that form an identity o...
We show that optimally pseudorandom $K_4$-free graphs of order $n$ and degree $d = \Theta(n^{4/5})$ exist by constructing a graph in the split Cayley hexagon, matching the known upper bound. This resolves the first open case for $K_k$-free graphs after $k=3$ for which Alon gave a tight construction in 1994. This has a...
Jie Han, F. Ihringer, H. Van Maldeghem· 2 citations
For practical $N$ let $h(N)$ be the least $k$ such that every integer $1\le m\le N$ is a sum of at most $k$ distinct divisors of $N$. We prove $h(n!)\le(2\log2+o(1))\,n/\log n$. This improves the bounds of order $n/(\log n)^{1/2-\varepsilon}$ established in Tenenbaum-Yokota's Lemma 4 and Yokota's 1995 knapsack note. We...
Let $f(k)$ denote the smallest integer such that every oriented graph $D$ with chromatic number at least $f(k)$ contains every oriented tree on $k$ vertices. Burr (1980) showed that $f(k)\le (k-1)^2$ and conjectured that $f(k)=2k-2$. Bessy, Gon\c{c}alves and Reinald (2025) proved that $f(k)=O(k^{3/2})$. In this paper,...
