CS Paper Radar

On cancellative pairs of families of subsets

Yijia Fang, Hao Huang

cs.IT math.CO ·submitted 2026-09-01 16:18 UTC · v2
theoryunusual

Abstract

A pair $(\mathcal{A}, \mathcal{B})$ of families of subsets of $[n]$ is cancellative if whenever $A, A' \in \mathcal{A}, B \in \mathcal{B}$ satisfy $A \cup B=A' \cup B$, then $A=A'$, and whenever $A \in \mathcal{A}, B, B' \in \mathcal{B}$ satisfy $A \cup B=A \cup B'$, then $B=B'$. We show that for every cancellative pair $(\mathcal{A}, \mathcal{B})$, the inequality $|\mathcal{A}||\mathcal{B}| \le 2.25^n$ holds, matching Tolhuizen's $(2.25-o(1))^n$ lower bound construction.

Closest papers

Nearest neighbours by meaning across the whole index.

An Improved Upper Bound for Recovering Pairs

cs.IT math.CO ·2026-10-02 ·Simone Costa
theory similarity 0.70
Abstract · Computational supplement, verifiers and outputs are available at https://doi.org/10.5281/zenodo.23093260

We prove that every recovering pair $(\mathcal{A},\mathcal{B})$ of nonempty families of subsets of an $n$-element set satisfies $$|\mathcal{A}||\mathcal{B}|\le\left(\frac{223949}{100000}\right)^n=(2.23949)^n.$$ A result of Mond, Souza and Versteegen, combined with the sharp $(9/4)^n$ bound of Fang and Huang for cancellative pairs, gives $(2.2499)^n$ for recovering pairs. We improve this to $(2.23949)^n$. The proof combines two entropy inequalities. One is derived directly from the recovering property, while the other applies the Fang-Huang bound to families obtained from the original pair by a construction of Mond, Souza and Versteegen. The two inequalities are then combined by a convex combination.

0.25

Non-redundant Independence Atoms

cs.DB math.CO ·2026-11-03 ·Attila Sali, Jun Yan
theory similarity 0.56
Abstract

Independence atom is a key concept in relational database theory. In the present paper, we prove that the maximum possible size of a non-redundant set of independence atoms on $n$ attributes is asymptotically $(1+o(1))\binom{n}{\floor{n/2}}$. It turns out that this problem is closely related to two extremal set theory problems, the Katona-Tarján question on ``V''-free families of subsets of $[n]$ for the lower bound, and Kleitman's bound on union-free families for the upper bound.

0.23

On the Number of Distinct Topological Bases of a Finite Set of Size $N$

cs.LO math.COmath.GN ·2026-09-12 ·Lars Warren Ericson
unusual similarity 0.51
Abstract · 29 pages

For a finite set $S$ with $\lvert S\rvert = N$, the number of families $\mathcal{B} \subseteq \mathcal{P}(S)$ that are topological bases is $\#(N) = \sum_{\mathcal{T} \in \operatorname{Top}(S)} 2^{\lvert\mathcal{T}\rvert - \lvert\mathcal{M}_{\mathcal{T}}\rvert}$, where $\mathcal{M}_{\mathcal{T}}$ is the canonical minimal basis of minimal open neighborhoods. The identity is proved in Lean 4 / Mathlib (`CARDB.lean`): bases generating $\mathcal{T}$ are exactly the sets with $\mathcal{M}_{\mathcal{T}} \subseteq \mathcal{B} \subseteq \mathcal{T}$. The small-$N$ table and the discrete-dominance sandwich are proved in `CARDB/SmallN.lean` and `CARDB/Asymptotics.lean`.

0.33

On the complexity of Medvedev reducibility

cs.CC math.LO ·2026-10-23 ·Remi Pallen
theory similarity 0.51
Abstract

The Medvedev lattice is a tool used to classify the complexity of effective closed sets. In this article, we are interested in the complexity of using this tool. In particular, we study the complexity of deciding whether two effective closed sets have the same degree, when one is fixed and the other is given as input. This problem is naturally~$Σ^0_3$, and among other results, we show that for all degrees except the maximal one, the problem reaches its maximal complexity. It turns out that the argument is not uniform and depends on the self-similarity of the fixed degree, a notion that we introduce in this article. The complexity of having maximal degree is particularly difficult to establish, but we obtain a lower bound that almost matches the upper bound. We also show that deciding whether an effective closed set has a degree incomparable with a fixed degree $d$ is $Π^0_3$-complete whenever $\mathbf{0}_s <_s d <_s \mathbf{1}_s$.

0.30

Bourgain's Theorem for a Union of Euclidean Metric Spaces

cs.DS cs.CGmath.MG ·2026-11-05 ·Dimitar Chakarov, Sepideh Mahabadi, Yury Makarychev, Ali Vakilian
theory similarity 0.50
Abstract · 33 pages

We study the distortion of embedding a union of $k$ Euclidean sets into Euclidean space. We show that a union of $k$ Euclidean sets can be embedded with distortion at most $O(k^{1.128} \log k)$, independent of the number of points. This is an exponential improvement over the previous best known upper bound of $2^{O(k)}$ obtained by iterating the result of Makarychev and Makarychev (2016) for the special case $k = 2$. Surprisingly, with the additional assumption that each Euclidean set remains Euclidean when we adjoin any other two points, we can obtain an asymptotically tight distortion of $O(\log k)$, thus, providing a generalization of Bourgain's Theorem (1985). Along the way, we also show that the distortion of the union can be upper bounded by $O(\log k)$ times the maximum of the Lipschitz extension constants of individual Euclidean sets.

0.22

$L$-systems on the large Witt design

cs.IT math.CO ·2026-11-16 ·Toshihiro Shimizu, Norihide Tokushige
theory similarity 0.49
Abstract · 14 pages

Let $L=\{0,1,2,3,4,8\}$, associated with the large Witt design $S(5,8,24)$, and let $m(n,24,L)$ be the maximum size of a family of $24$-element subsets of an $n$-element set whose distinct members have intersection sizes in $L$. We prove that there are positive constants $c,C,n_0$ such that, for every $n\geq n_0$, \[ cn^{316/63}\leq m(n,24,L)\leq Cn^{169/29}. \] We also obtain similar results for the systems associated with $S(4,7,23)$, $S(3,6,22)$, and $S(3,4,14)$. The upper bounds follow from a non-Shannon information inequality and disprove conjectures of Kupavskii and Terekhov. The lower bounds follow from an algebraic construction for arbitrary Steiner systems.

0.42

Universal set families for maximization of nonnegative submodular and XOS functions

cs.DS ·2026-09-17 ·Chandra Chekuri, Richard Ueltzen, Jan Vondrak
theoryhot direction similarity 0.48
Abstract · The main results were obtained with ChatGPT-5.6 Sol

We consider the question of designing a universal family of sets $F \subset 2^{[n]}$ such that for any function $f:2^{[n]} \to R_{\geq 0}$ in a certain class, we have $$\max_{S \in F} f(S) \geq c(n) \cdot \max_{S \subset [n]} f(S).$$ We prove that there is a family of subpolynomial size such that for any nonnegative submodular function, $c(n) = Ω(\frac{\log \log n}{\log n})$, and there is a family of logarithmic size such that $c(n) = Ω(\frac{1}{\log n})$. We also prove that pairwise independence (which achieves a constant factor for graph cut functions), or even $k$-wise independence, does not imply a bound better than $O(\frac{1}{\sqrt{\log n}})$ for submodular functions. On the other hand, we prove that for any polynomially representable subclass of nonnegative submodular functions (such as the matroid connectivity functions for matroid representable over $F_q$), a constant-factor universal family of polynomial size always exists. For absolute XOS functions (a class that we introduce, in the form $f(S) = \max_i |\sum_{j \in S} w_{ij} + c_i|$ where $w_{ij}, c_i \in R$), we design a family of polynomial size such that $c(n) \geq \sqrt{\frac{\log n}{n}}$, and prove that there is no polynomial-size family achieving a factor better than $O(\sqrt{\frac{\log n}{n}})$.

0.51

A short proof of the Aaronson-Ambainis Conjecture via the completion framework

cs.CC quant-ph ·2026-11-09 ·Thomas Huffstutler, David Miloschewsky, Supartha Podder
similarity 0.48
Abstract · 7 pages

We give a short proof of the Aaronson-Ambainis conjecture. If a partial Boolean function $f$ is defined on a $δ$-fraction of all $n$-bit strings and have quantum query complexity $Q(f)$, then, for every $0<ε<1$, a deterministic algorithm computes $f$ correctly on at least a $1-ε$ fraction of its domain using $O( Q(f)^6 / (εδ)^2)$ queries. Our proof uses the completion framework and establishes a more general bound in terms of the classical adversary measure. The only result we use from Turturean's recent proof is a special case of his certificate inequality, for which we provide a self-contained proof. We also derive the stronger variant of the Aaronson-Ambainis Conjecture, the bounded-polynomial influence conjecture, from our main result in the appendix.

0.17