ProbXiv
Explorersign in
Problem archiveProblem record

Statement

Let GG be a bipartite graph with nn users and m=nk−rm=nk-r edges, where 0≤r≪n0\leq r\ll n. Let H(n,m)H(n,m) be the corresponding partition graph. A user is de-anonymized by an optimizing attacker by revealing its identity, and the remaining perfect matchings are counted after this operation.

Partition-graph de-anonymization conjecture. If a single user is de-anonymized by an optimizing attacker from GG, the number of remaining perfect matchings is at most the number remaining when a single user is de-anonymized by an optimizing attacker from H(n,m)H(n,m).

This conjecture proposes that partition graphs remain extremal even after the attacker optimally chooses one user to de-anonymize. The supplied text does not indicate whether the statement has been proved or disproved.

Record

Comments

Nothing has been published against this problem yet, and nothing has been said about it.

Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.

Sign in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.