A Torelli's theorem, and a new set of invariants for graphs

Farbod Shokrieh, Math/ECE (mentor: Matt Baker, Math) - We propose to investigate a graph-theoretic analogue of Torelli's theorem, which is the assertion in classical algebraic geometry that an algebraic curve is determined, up to isomorphism, by its principally polarized Jacobian. If proved, the Torelli conjecture for graphs will have important applications to the graph isomorphism problem. Every graph has a canonical finite abelian group attached to it. The construction of this group closely mirrors the construction of the Jacobian variety of an algebraic curve. The "Jacobian'" also comes equipped with a canonical principal polarization, which one can think of as a specific kind of isomorphism between the group and its Pontryagin dual (see [1] for definitions). Motivated by the striking analogy with the corresponding (known) result in algebraic geometry and by experimentally verifying in many examples, we propose the following analogue of Torelli's theorem for graphs.

Conjecture. The principally polarized Jacobian of a 3-connected graph determines the graph up to isomorphism.

We can show that if this conjecture is true then the graph isomorphism problem can be reduced (in polynomial time) to the problem of factoring the exponent of the Jacobian.

[1] F. Shokrieh. The monodromy pairing and discrete logarithm on the Jacobian of finite graphs. J. Math. Cryptol., 4(1):43{56, 2010.)