Partition graphs maximize the remaining perfect matchings after one-user de-anonymization
Statement
Let be a bipartite graph with users and edges, where . Let 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 , the number of remaining perfect matchings is at most the number remaining when a single user is de-anonymized by an optimizing attacker from .
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 inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.