Vasek Rozhon

Vasek Rozhon·Adrian Zámečník

For a nonempty finite set X in R^d, consider the Gaussian kernel-density estimate K_X(y), the average over x in X of exp(-||x-y||_2^2 / sigma^2). We construct a randomized data structure which, for every fixed query y in R^d, returns an additive-epsilon approximation to K_X(y) with probability greater than 1 - delta. Its query time is O((d + epsilon^-2) log(d+1) log(2/delta)) and its stored representation has O((d + epsilon^-2) log(2/delta)) real coordinates. No bounded-domain or effective-diameter parameter occurs. The feature map is built from independent blocks W = D H G H B, where D is the next power of two at least d, H is the normalized Walsh–Hadamard matrix, G is diagonal Gaussian, and B is diagonal Rademacher. Although the rows within one block are correlated, Gaussian damping and an exact signed Walsh-autocorrelation identity give a norm-uniform bound on the variance for every fixed displacement z. This estimate lifts to an arbitrary KDE average without independence across data points. The guarantee is pointwise in the query; fixed finite query batches follow by a union bound, whereas uniform or adaptive queries require different control.

Vasek Rozhon·Adrian Zámečník

For a complete d-partite d-uniform hypergraph K(A1, ..., Ad), define its weight as the sum of |Ai|. Consider covers and edge-disjoint exact partitions of an n-vertex d-uniform hypergraph into such pieces. For every fixed d ≥ 3 and 0 < ε < 1, the worst-case minimum total weight among hypergraphs with m ≤ (1 − ε) C(n,d) edges is Θ_{d,ε}(m min(1, log(1/γ)/log n)), where γ = m / C(n,d). The formula is the same for covers and exact partitions. The lower bound uses an exact-density random hypergraph; the upper bound repeatedly extracts density-sensitive balanced boxes and then partitions the sparse remainder. Espuña's extraction algorithm makes the construction deterministic and polynomial-time. Cone examples show that the average total-weight scale W/n need not control the maximum number of pieces through one vertex. Complete and near-complete endpoint bounds are also given, while the sharp transition as γ → 1 remains open.

Vasek Rozhon·Adrian Zámečník

Let Rn(q) be the all-terminal reliability polynomial of the complete graph Kn, written in the edge-failure variable. We prove that, for every n ≥ 256 with n ≡ 0, 3 (mod 4), the polynomial Rn has a real zero qn satisfying −1 < qn < −n^(−2/n). Consequently, 0 < qn + 1 < 2 log n/n. More precisely, Rn(−n^(−2/n)) > 1/3 throughout this range and Rn(−n^(−2/n)) → 1. The endpoint sign is supplied by an exact sign theorem, while positivity at the moving point follows from Möbius inversion on the partition lattice and explicit estimates for partitions with and without a block larger than n/2. This gives an effective quantitative refinement of the known accumulation of complete-graph reliability roots at −1.

Vasek Rozhon·Adrian Zámečník

For a nonempty finite set X in R^d, consider the Gaussian kernel-density estimate K_X(y), the average over x in X of exp(-||x-y||_2^2 / sigma^2). We construct a randomized data structure which, for every fixed query y in R^d, returns an additive-epsilon approximation to K_X(y) with probability greater than 1 - delta. Its query time is O((d + epsilon^-2) log(d+1) log(2/delta)) and its stored representation has O((d + epsilon^-2) log(2/delta)) real coordinates. No bounded-domain or effective-diameter parameter occurs. The feature map is built from independent blocks W = D H G H B, where D is the next power of two at least d, H is the normalized Walsh–Hadamard matrix, G is diagonal Gaussian, and B is diagonal Rademacher. Although the rows within one block are correlated, Gaussian damping and an exact signed Walsh-autocorrelation identity give a norm-uniform bound on the variance for every fixed displacement z. This estimate lifts to an arbitrary KDE average without independence across data points. The guarantee is pointwise in the query; fixed finite query batches follow by a union bound, whereas uniform or adaptive queries require different control.

Vasek Rozhon·Adrian Zámečník

For a complete d-partite d-uniform hypergraph K(A1, ..., Ad), define its weight as the sum of |Ai|. Consider covers and edge-disjoint exact partitions of an n-vertex d-uniform hypergraph into such pieces. For every fixed d ≥ 3 and 0 < ε < 1, the worst-case minimum total weight among hypergraphs with m ≤ (1 − ε) C(n,d) edges is Θ_{d,ε}(m min(1, log(1/γ)/log n)), where γ = m / C(n,d). The formula is the same for covers and exact partitions. The lower bound uses an exact-density random hypergraph; the upper bound repeatedly extracts density-sensitive balanced boxes and then partitions the sparse remainder. Espuña's extraction algorithm makes the construction deterministic and polynomial-time. Cone examples show that the average total-weight scale W/n need not control the maximum number of pieces through one vertex. Complete and near-complete endpoint bounds are also given, while the sharp transition as γ → 1 remains open.

Vasek Rozhon·Adrian Zámečník

Let Rn(q) be the all-terminal reliability polynomial of the complete graph Kn, written in the edge-failure variable. We prove that, for every n ≥ 256 with n ≡ 0, 3 (mod 4), the polynomial Rn has a real zero qn satisfying −1 < qn < −n^(−2/n). Consequently, 0 < qn + 1 < 2 log n/n. More precisely, Rn(−n^(−2/n)) > 1/3 throughout this range and Rn(−n^(−2/n)) → 1. The endpoint sign is supplied by an exact sign theorem, while positivity at the moving point follows from Möbius inversion on the partition lattice and explicit estimates for partitions with and without a block larger than n/2. This gives an effective quantitative refinement of the known accumulation of complete-graph reliability roots at −1.

Vaclav Rozhon·Adrian Zámečník

A q-matroid is a rank function on the subspaces of a vector space over Fq. A coordinate q-matroid on Fq^n is determined by an ordinary matroid on [n] through their weighted cyclic flats. For q = p^a, we prove that such a q-matroid is representable over a finite extension of Fq if and only if the corresponding ordinary matroid is representable over a field of characteristic p. The sufficiency direction uses a generic diagonal rescaling of an ordinary representation, matroid intersection, and simultaneous specialization over a finite field. We also establish closure of transversal q-matroids under the Ceria–Jurrius direct sum. More precisely, for arbitrary presentations of two transversal q-matroids, the list obtained by inflating every presenting subspace by the other ambient summand presents their direct sum. Its presentation-rank minimum agrees, on every subspace, with the direct-sum rank minimum. Iteration gives a natural presentation and a flattened rank formula for every finite direct sum.