k-Anonymity by Partitions Maximizes Perfect Matchings
The number of perfect matchings in a user-behavior bipartite graph is a natural measure of anonymity: more matchings mean greater uncertainty for an attacker. A fundamental question is which graph structure maximizes this count for a fixed infrastructure cost, represented by the number of edges. We prove that the answer is $k$-anonymity by partitions. Using Brègman's Theorem, we show that partitioning users into equal-sized groups and making each group a complete bipartite component achieves the theoretical upper bound on perfect matchings. For edge counts where an exact partition is…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2606.10133
curl -X POST /api/v1/records/arxiv/2606.10133/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2606.10133/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'