MarriageTheoremのこと

_ プレプリント確認状況：arXiv:math 2月27日分まで、IACR ePrint 2012/451まで

_ 気になった論文１：How to write a permutation as a product of involutions (and why you might care) (T. Kyle Petersen, Bridget Eileen Tenner, arXiv:1202.5319)

It is well-known that any permutation can be written as a product of two involutions. We provide an explicit formula for the number of ways to do so, depending only on the cycle type of the permutation.

In many cases, these numbers are sums of absolute values of irreducible characters of the symmetric group evaluated at the same permutation, although apart from the case where all cycles are the same size, we have no good explanation for why this should be so.

_ 気になった論文２：Nondeterministic graph property testing (László Lovász, Katalin Vesztergombi, arXiv:1202.5337)

A property of finite graphs is called nondeterministically testable if it has a "certificate" such that once the certificate is specified, its correctness can be verified by random local testing. In this paper we study certificates that consist of one or more unary and/or binary relations on the nodes, in the case of dense graphs. Using the theory of graph limits, we prove that nondeterministically testable properties are also deterministically testable.