pith. sign in

arxiv: 2606.26244 · v1 · pith:J7GUGCDNnew · submitted 2026-06-24 · 💻 cs.CC · cs.DS· math.CO· math.RT

Graph Isomorphism and Representation Theory

Joshua A. Grochow , Jacob Urisman This is my paper

Pith reviewed 2026-06-26 01:01 UTC · model grok-4.3

classification 💻 cs.CC cs.DSmath.COmath.RT
keywords graph isomorphismseparating modulesWeisfeiler-Lemansymmetric group representationscycle indexinvariant polynomialsautomorphism groupssubgraph counts
0
0 comments X

The pith

Separating modules of symmetric circuit size n to the theta k distinguish graphs exactly when theta k Weisfeiler-Leman does.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper introduces separating modules, vector spaces of set-wise invariant polynomials under permutations, as a way to distinguish non-isomorphic graphs. It proves that modules whose monomials touch at most k vertices match the information from counting O(k)-vertex subgraphs. Modules whose symmetric circuits have size n to the theta k match the distinguishing power of theta k dimensional Weisfeiler-Leman in both directions. When only the multiplicities of these modules are considered, distinction occurs exactly when the automorphism groups of the graphs have different cycle indices. This supplies an algebraic route to the same separation power as the standard combinatorial test.

Core claim

Separating modules of symmetric circuit size n^Θ(k) are equivalent to Θ(k)-WL. This generalizes and strengthens prior one-direction results by proving both directions for separating modules rather than only invariant polynomials, while support-degree k modules equate to O(k)-subgraph counts and multiplicities equate to differences in automorphism group cycle indices.

What carries the argument

Separating modules, vector spaces of polynomials that are set-wise invariant under permutations and thus representations of the symmetric group.

If this is right

  • Support-degree k separating modules are equivalent to counts of O(k)-vertex subgraphs and strictly weaker than O(k)-WL.
  • Multiplicities of separating modules distinguish graphs if and only if their automorphism groups have different cycle indices.
  • Multiplicity obstructions are stronger than occurrence obstructions for graphs.
  • The approach connects invariant polynomials to the graph reconstruction conjectures.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The cycle-index characterization of multiplicities may extend to distinguishing other objects acted on by the symmetric group.
  • The equivalence could be tested on small explicit pairs of graphs where WL and circuit sizes are computable by hand.
  • If the circuit-size bound is tight, it suggests a direct translation between algebraic circuit lower bounds and combinatorial algorithm bounds for isomorphism.

Load-bearing premise

The distinguishing power of separating modules is fully captured by the stated equivalences to subgraph counts, Weisfeiler-Leman, and cycle indices under the chosen definitions of support-degree, circuit size, and multiplicity extraction.

What would settle it

Two non-isomorphic graphs separated by a separating module of symmetric circuit size n^Θ(k) but not by Θ(k)-WL, or the reverse.

read the original abstract

We introduce an approach to distinguishing isomorphism types of graphs based on vector spaces of polynomials that are set-wise invariant under permutations ("separating modules," which are representations of the symmetric group), inspired by the Geometric Complexity Theory approach to separating complexity classes (Mulmuley & Sohoni, SIAM J. Comput., 2001). We characterize the power of this method for distinguishing non-isomorphic graphs under several different complexity measures: - We show that separating modules of "support-degree" $k$ (each monomial touches at most $k$ vertices) are equivalent to the counts of $O(k)$-vertex subgraphs. This is strictly weaker than $O(k)$-dimensional Weisfeiler--Leman (F\"urer, ICALP '01). - We show that separating modules of symmetric circuit size $n^{\Theta(k)}$ are equivalent to $\Theta(k)$-WL. This generalizes and strengthens a result of Dawar & Wilsenach (CSL '18; ICALP '20; ACM Trans. Comput. Log., 2022; Theory Comput., 2025): they proved one direction of this equivalence for invariant polynomials; we generalize to separating modules and prove both directions. - When considering only the multiplicities of separating modules (as was proposed in GCT by Mulmuley & Sohoni, ibid., rather than the polynomials themselves), we show that two graphs are separated by multiplicities if and only if their automorphism groups have different cycle indices. The latter result is notable in the analogy with GCT, as it is the only result we are aware of in which the multiplicity approach to separating isomorphism types of objects has been given an "intrinsic" characterization in terms of the objects themselves. We use this to show that for graphs, multiplicity obstructions are stronger than occurrence obstructions. We also connect invariant polynomials to the Graph Reconstruction Conjectures and Forman's "invariants of finite type" (Adv. Math., 2004).

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript introduces separating modules as vector spaces of set-wise invariant polynomials (representations of the symmetric group) inspired by GCT. It characterizes their distinguishing power for non-isomorphic graphs: support-degree k modules are equivalent to counts of O(k)-vertex subgraphs (strictly weaker than O(k)-WL); symmetric circuit size n^Θ(k) modules are equivalent to Θ(k)-WL, proving both directions and strengthening the one-directional result of Dawar & Wilsenach for invariant polynomials; multiplicities of separating modules separate graphs if and only if their automorphism groups have different cycle indices. It further connects invariant polynomials to the Graph Reconstruction Conjectures and Forman's invariants of finite type.

Significance. If the stated equivalences hold, the work supplies a representation-theoretic framework that precisely calibrates algebraic methods against standard combinatorial tools for graph isomorphism. The two-directional equivalence for modules, the intrinsic cycle-index characterization of multiplicities, and the explicit strengthening of prior results are substantive contributions that could inform both GI complexity and GCT-style approaches.

major comments (2)
  1. [Abstract] Abstract (equivalence claim for symmetric circuit size): the two-directional equivalence between separating modules of size n^Θ(k) and Θ(k)-WL is load-bearing for the central contribution; the manuscript must supply the explicit construction and reduction in both directions, including how the circuit-size bound interacts with the support-degree and multiplicity-extraction definitions, to confirm it does not rely on unstated assumptions about the underlying polynomial spaces.
  2. [Multiplicity section] Multiplicity section (cycle-index claim): the if-and-only-if statement that multiplicities separate graphs precisely when automorphism groups have distinct cycle indices is a key strengthening; the direction from differing cycle indices to separation by multiplicities requires a concrete argument that the multiplicity map is injective on the relevant representation spaces, without additional combinatorial hypotheses.
minor comments (2)
  1. The notation n^Θ(k) for symmetric circuit size should be defined formally with an explicit reference to the circuit model (e.g., which gates are permitted) when first introduced in the main text.
  2. A short comparison table summarizing the three measures (support-degree, circuit size, multiplicities) and their equivalent combinatorial characterizations would improve readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the thoughtful summary and for highlighting the central claims. Below we respond point-by-point to the two major comments. We are prepared to revise the manuscript to improve clarity where the referee indicates the current presentation may be insufficient.

read point-by-point responses

  1. Referee: [Abstract] Abstract (equivalence claim for symmetric circuit size): the two-directional equivalence between separating modules of size n^Θ(k) and Θ(k)-WL is load-bearing for the central contribution; the manuscript must supply the explicit construction and reduction in both directions, including how the circuit-size bound interacts with the support-degree and multiplicity-extraction definitions, to confirm it does not rely on unstated assumptions about the underlying polynomial spaces.

    Authors: The manuscript already contains explicit constructions for both directions in Sections 4 and 5. Section 4 reduces separating modules of symmetric circuit size n^Θ(k) to Θ(k)-WL by showing that any such module can be simulated by a color-refinement procedure whose depth and width are controlled by k; the circuit-size bound is obtained by enumerating the possible monomial supports of size O(k) and applying the representation-theoretic decomposition. The converse reduction (WL to modules) appears in Section 5, where each WL iteration is encoded as a symmetric circuit whose gates compute the required invariant polynomials; the n^Θ(k) size follows directly from the number of color classes at each round. Support-degree is enforced by restricting all monomials in the circuit definition to touch at most k vertices, and multiplicity extraction is performed by the standard projection onto isotypic components. If the referee finds the current level of detail insufficient for verification, we will add a new subsection with pseudocode for the two reductions and an explicit accounting of how the circuit-size parameter interacts with support-degree. revision: partial

  2. Referee: [Multiplicity section] Multiplicity section (cycle-index claim): the if-and-only-if statement that multiplicities separate graphs precisely when automorphism groups have distinct cycle indices is a key strengthening; the direction from differing cycle indices to separation by multiplicities requires a concrete argument that the multiplicity map is injective on the relevant representation spaces, without additional combinatorial hypotheses.

    Authors: Section 6 proves the if-and-only-if claim. The direction from distinct cycle indices to separation by multiplicities proceeds by observing that the cycle index of Aut(G) is the character of the permutation representation on the set of graphs; the multiplicity of each irreducible representation ρ in the separating module is then the inner product ⟨cycle index, χ_ρ⟩. Because the cycle-index polynomials of subgroups of S_n span the space of class functions and the character table is invertible, the map sending a cycle index to its vector of multiplicities is injective on the relevant representation spaces. The argument uses only the orthogonality relations for the symmetric group and the definition of separating modules; no extra combinatorial hypotheses on the graphs are required. We are happy to extract this injectivity statement as a standalone lemma with a short proof if the referee believes it would improve readability. revision: partial

Circularity Check

0 steps flagged

No significant circularity; equivalences derived independently

full rationale

The claimed equivalences (support-degree k modules to O(k)-subgraph counts; symmetric circuit size n^Θ(k) modules to Θ(k)-WL, strengthening Dawar & Wilsenach in both directions; multiplicities to cycle indices of Aut groups) are presented as proven via combinatorial and representation-theoretic arguments. The Dawar & Wilsenach citation is external (different authors) and used only for the one-directional base case that is then extended, not as load-bearing self-reference. No self-definitional reductions, fitted parameters renamed as predictions, or ansatzes smuggled via citation appear in the stated results. The multiplicity characterization is explicitly novel and intrinsic.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The central claims rest on standard facts from the representation theory of the symmetric group and on the prior theory of Weisfeiler-Leman; the main addition is the application of separating modules to graph isomorphism.

axioms (1)
  • standard math Standard facts from the representation theory of the symmetric group S_n
    Used to define separating modules as representations.
invented entities (1)
  • separating module no independent evidence
    purpose: Vector space of set-wise invariant polynomials used to separate graph isomorphism types
    Introduced in the paper as the central object, inspired by GCT.

pith-pipeline@v0.9.1-grok · 5900 in / 1470 out tokens · 54909 ms · 2026-06-26T01:01:52.363654+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

31 extracted references · 23 canonical work pages · 8 internal anchors

  1. [1]

    Zero knowledge and circuit minimization.Inf

    [AD17a] Eric Allender and Bireswar Das. Zero knowledge and circuit minimization.Inf. Comput., 256:2–8, 2017.doi:10.1016/j.ic.2017.04.004. [AD17b] Matthew Anderson and Anuj Dawar. On symmetric circuits and fixed-point logics.The- ory Comput. Syst., 60(3):521–551,

    work page doi:10.1016/j.ic.2017.04.004 2017

  2. [2]

    On Symmetric Circuits and Fixed-Point Logics

    Originally appeared in STACS 2014; preprint arXiv:1401.1125.doi:10.1007/S00224-016-9692-2. [AM13] Albert Atserias and Elitza N. Maneva. Sherali–Adams relaxations and indistinguishabil- ity in counting logics.SIAM J. Comput., 42(1):112–137, 2013.doi:10.1137/120867834. [AYZ95] Noga Alon, Raphael Yuster, and Uri Zwick. Color-coding.J. Assoc. Comput. Mach., 4...

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1007/s00224-016-9692-2 2014

  3. [3]

    Preliminary version appeared in STOC ’94.doi:10.1145/210332. 210337. [Bab16] L´ aszl´ o Babai. Graph isomorphism in quasipolynomial time [extended abstract]. In Daniel Wichs and Yishay Mansour, editors,Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18-21, 2016, pages 684–697. ACM,

    work page doi:10.1145/210332 2016

  4. [4]

    Preprint arXiv:1512.03547.doi:10.1145/2897518. 2897542. [BG15] Christoph Berkholz and Martin Grohe. Limitations of algebraic approaches to graph iso- morphism testing. In Magn´ us M. Halld´ orsson, Kazuo Iwama, Naoki Kobayashi, and Bet- tina Speckmann, editors,Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, ...

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1145/2897518 2015

  5. [5]

    Limitations of Algebraic Approaches to Graph Isomorphism Testing

    Preprint arXiv:1502.05912.doi:10.1007/978-3-662-47672-7\_13. [BG17] Christoph Berkholz and Martin Grohe. Linear Diophantine equations, group CSPs, and graph isomorphism. In Philip N. Klein, editor,Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 327–339. SIAM,

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1007/978-3-662-47672-7 2017

  6. [6]

    Linear Diophantine Equations, Group CSPs, and Graph Isomorphism

    Preprint arXiv:1607.04287 [cs.CC].doi:10.1137/1.9781611974782.21. [BGS99] Andreas Blass, Yuri Gurevich, and Saharon Shelah. Choiceless polynomial time.Ann. Pure Appl. Log., 100(1-3):141–187, 1999.doi:10.1016/S0168-0072(99)00005-6. [BIP19] Peter B¨ urgisser, Christian Ikenmeyer, and Greta Panova. No occurrence obstructions in geometric complexity theory.J....

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1137/1.9781611974782.21 1999

  7. [7]

    No occurrence obstructions in geometric complexity theory

    Originally appeared in FOCS 2016; Preprint arXiv:1604.06431.doi:10.1090/jams/908. [BL08] Peter A. Brooksbank and Eugene M. Luks. Testing isomorphism of modules.J. Algebra, 320(11):4020–4029, 2008.doi:10.1016/j.jalgebra.2008.07.014. 40 [CEF15] Thomas Church, Jordan S. Ellenberg, and Benson Farb. FI-modules and stability for representations of symmetric gro...

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1090/jams/908 2016

  8. [8]

    Cai and M

    Originally appeared in FOCS 1989.doi:10.1007/BF01305232. [CIK97] Alexander L. Chistov, G´ abor Ivanyos, and Marek Karpinski. Polynomial time algorithms for modules over finite dimensional algebras. In Bruce W. Char, Paul S. Wang, and Wolfgang K¨ uchlin, editors,Proceedings of the 1997 International Symposium on Symbolic and Algebraic Computation, ISSAC 19...

    work page doi:10.1007/bf01305232 1989

  9. [9]

    Com- plexity measures on the symmetric group and beyond (extended abstract)

    [DFL+21] Neta Dafni, Yuval Filmus, Noam Lifshitz, Nathan Lindzey, and Marc Vinyals. Com- plexity measures on the symmetric group and beyond (extended abstract). In James R. Lee, editor,12th Innovations in Theoretical Computer Science Conference, ITCS 2021, Virtual Conference, January 6-8, 2021, volume 185 ofLIPIcs, pages 87:1–87:5. Schloss Dagstuhl - Leib...

    2021

  10. [10]

    [DGKP25] Anuj Dawar, Erich Gr¨ adel, Leon Kullmann, and Benedikt Pago

    Preprint arXiv:2010.07405.doi: 10.4230/LIPICS.ITCS.2021.87. [DGKP25] Anuj Dawar, Erich Gr¨ adel, Leon Kullmann, and Benedikt Pago. Symmetric Proofs in the Ideal Proof System. In Pawe l Gawrychowski, Filip Mazowiecki, and Micha l Skrzypczak, editors,50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025), volume 345 ofLeibn...

    work page doi:10.4230/lipics.itcs.2021.87 2010

  11. [11]

    [DIP20] Julian D¨ orfler, Christian Ikenmeyer, and Greta Panova

    Schloss Dagstuhl – Leibniz-Zentrum f¨ ur Informatik.doi:10.4230/LIPIcs.MFCS.2025.40. [DIP20] Julian D¨ orfler, Christian Ikenmeyer, and Greta Panova. On geometric complexity the- ory: multiplicity obstructions are stronger than occurrence obstructions.SIAM J. Appl. Algebra Geom., 4(2):354–376,

    work page doi:10.4230/lipics.mfcs.2025.40 2025

  12. [12]

    On geometric complexity theory: Multiplicity obstructions are stronger than occurrence obstructions

    Originally appeared in ICALP 2019; Preprint arXiv:1901.04576.doi:10.1137/19M1287638. [DK15] Harm Derksen and Gregor Kemper.Computational invariant theory. With two appen- dices by Vladimir L. Popov and an addendum by Nobert A. Campo and Vladimir L. Popov, volume 130 ofEncycl. Math. Sci.Berlin: Springer, 2nd enlarged edition edition, 2015.doi:10.1007/978-3...

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1137/19m1287638 2019

  13. [13]

    doi:10.4230/LIPICS.ITCS.2026.46

    Preprint of full version at arXiv:2502.06740. doi:10.4230/LIPICS.ITCS.2026.46. [DW22] Anuj Dawar and Gregory Wilsenach. Symmetric circuits for rank logic.ACM Trans. Comput. Log., 23(1):6:1–6:35,

    work page doi:10.4230/lipics.itcs.2026.46 2026

  14. [14]

    [DW25] Anuj Dawar and Gregory Wilsenach

    Originally appeared in CSL 2018.doi:10.1145/ 3476227. [DW25] Anuj Dawar and Gregory Wilsenach. Symmetric arithmetic circuits.Theory of Comput- ing, 21(14):1–32,

    2018

  15. [15]

    doi:10.4086/toc.2025.v021a014

    Originally appeared in ICALP 2020; preprint arXiv:2002.06451. doi:10.4086/toc.2025.v021a014. [EFP11] David Ellis, Ehud Friedgut, and Haran Pilpel. Intersecting families of permutations. J. Am. Math. Soc., 24(3):649–682,

    work page doi:10.4086/toc.2025.v021a014 2020

  16. [16]

    Intersecting Families of Permutations

    Corrected version on arXiv 1011.3342.doi: 10.1090/S0894-0347-2011-00690-5. [ER63] P´ al Erd˝ os and Alfr´ ed R´ enyi. Asymmetric graphs.Acta Math. Acad. Sci. Hung., 14:295– 315, 1963.doi:10.1007/BF01895716. [Far20] Ameneh Farhadian. Almost everyn-vertex graph is determined by its 3 log 2 n- vertex subgraphs.Int. J. Found. Comput. Sci., 31(5):611–619, 2020...

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1090/s0894-0347-2011-00690-5 2011

  17. [17]

    Preliminary version appeared at ITCS ’21.doi:10.1137/21M1441110

    Part of the preprint arXiv:1907.00309 [cs.CC]. Preliminary version appeared at ITCS ’21.doi:10.1137/21M1441110. [Gro12a] Joshua A. Grochow. Matrix Lie algebra isomorphism. InIEEE Conference on Computational Complexity (CCC12), pages 203–213,

    work page doi:10.1137/21m1441110 1907

  18. [18]

    4 of [Gro12b].doi:10.1109/ CCC.2012.34

    Preprint of full version arXiv:1112.2012, ECCC Technical Report TR11-168, Ch. 4 of [Gro12b].doi:10.1109/ CCC.2012.34. 42 [Gro12b] Joshua A. Grochow.Symmetry and equivalence relations in classical and geometric complexity theory. PhD thesis, University of Chicago, Chicago, IL, 2012.https:// home.cs.colorado.edu/~jgrochow/grochow-thesis.pdf. [Gro15] Joshua ...

    Pith/arXiv arXiv 2012

  19. [19]

    1007/s00037-015-0103-x

    Originally appeared in CCC ’14.doi:10. 1007/s00037-015-0103-x. [GV06] Martin Grohe and Oleg Verbitsky. Testing graph isomorphism in parallel by playing a game. In Michele Bugliesi, Bart Preneel, Vladimiro Sassone, and Ingo Wegener, editors, Automata, Languages and Programming, 33rd International Colloquium, ICALP 2006, Venice, Italy, July 10-14, 2006, Pro...

    2006

  20. [20]

    1007/11786986\_2

    Preprint arXiv:cs/0603054.doi:10. 1007/11786986\_2. [Har64] Frank Harary. On the reconstruction of a graph from a collection of subgraphs. InTheory Graphs Appl., Proc. Symp. Smolenice 1963, 47-52 (1964).Publ. House Czechoslovak Acad. Sci., Prague,

    Pith/arXiv arXiv 1963

  21. [21]

    [JK09] Gordon James and Adalbert Kerber.The representation theory of the symmetric group

    Originally appeared in MFCS ’04.doi:10.1016/j.dam.2006.04.038. [JK09] Gordon James and Adalbert Kerber.The representation theory of the symmetric group. Foreword by P. M. Cohn, introduction by G. de B. Robinson., volume 16 ofEncycl. Math. Appl.Cambridge: Cambridge University Press, reprint of the 1985 hardback ed. edition, 2009.doi:10.1017/CBO978110734073...

    work page doi:10.1016/j.dam.2006.04.038 2006

  22. [22]

    [Kel42] Paul J

    Scribed by Sumant Heyde; Spring 2015 course run with Chandan Saha. [Kel42] Paul J. Kelly.On isometric transformations. PhD thesis, University of Wisconsin– Madison,

    2015

  23. [23]

    [Kel57] Paul J. Kelly. A congruence theorem for trees.Pac. J. Math., 7:961–968, 1957.doi: 10.2140/pjm.1957.7.961. [Koc82] W. L. Kocay. Some new methods in reconstruction theory. InCombinatorial mathematics IX, Proc. 9th Aust. Conf., Brisbane/ Aust. 1981, Lect. Notes Math. 952, 89-114 (1982). 1982.doi:10.1007/bfb0061974. [KSV02] Jeong Han Kim, Benny Sudako...

    work page doi:10.2140/pjm.1957.7.961 1957

  24. [24]

    [Lie87] Martin W. Liebeck. The affine permutation groups of rank three.Proc. Lond. Math. Soc. (3), 54:477–516, 1987.doi:10.1112/plms/s3-54.3.477. [LW25] Vladimir Lysikov and Michael Walter. Complexity theory of orbit closure intersection for tensors: reductions, completeness, and graph isomorphism hardness. In66th IEEE Annual Symposium on Foundations of C...

    work page doi:10.1112/plms/s3-54.3.477 1987

  25. [25]

    2025 , pages =

    Preprint arXiv:2411.04639. doi:10.1109/FOCS63196.2025.00027. 43 [Mar10] D´ aniel Marx. Can you beat treewidth?Theory Comput., 6:85–112,

    work page doi:10.1109/focs63196.2025.00027 2025

  26. [26]

    [MS01] Ketan D

    doi:10.4086/toc.2010.v006a005. [MS01] Ketan D. Mulmuley and Milind Sohoni. Geometric complexity theory. I: An approach to the P vs. NP and related problems.SIAM J. Comput., 31(2):496–526, 2001.doi: 10.1137/S009753970038715X. [Neu24] Daniel Neuen. Homomorphism-distinguishing closedness for graphs of bounded tree- width. In Olaf Beyersdorff, Mamadou Moustap...

    work page doi:10.4086/toc.2010.v006a005 2010

  27. [27]

    [N´ yd92] V´ aclav N´ ydl

    Preprint of full version arXiv:2304.07011.doi:10.4230/LIPICS.STACS.2024.53. [N´ yd92] V´ aclav N´ ydl. Finite undirected graphs which are not reconstructible from their large cardinality subgraphs.Discrete Math., 108(1-3):373–377, 1992.doi:10.1016/ 0012-365X(92)90689-D. [Pee75] M. H. Peel. Specht modules and symmetric groups.J. Algebra, 36:88–97, 1975.doi...

    work page doi:10.4230/lipics.stacs.2024.53 2024

  28. [28]

    Graph Isomorphism and the Lasserre Hierarchy

    [Pou79] Maurice Pouzet. Note sur le probl` eme de Ulam.J. Comb. Theory, Ser. B, 27:231–236, 1979.doi:10.1016/0095-8956(79)90015-7. [PT01] Maurice Pouzet and Nicolas M. Thi´ ery. Algebraic graph invariants and reconstruc- tion.C. R. Acad. Sci., Paris, S´ er. I, Math., 333(9):821–826, 2001.doi:10.1016/ S0764-4442(01)02137-1. [Ram81] S. Ramachandran. On a ne...

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1016/0095-8956(79)90015-7 1979

  29. [29]

    [Thi00] Nicolas M

    URL:scholarworks.wm.edu/aspubs/1120,doi: 10.1002/jgt.3190010108. [Thi00] Nicolas M. Thi´ ery. Algebraic invariants of graphs; a study based on computer explo- ration.SIGSAM Bull., 34(3):9–20,

    work page doi:10.1002/jgt.3190010108

  30. [30]

    [TW23] Jacobo Tor´ an and Florian W¨ orz

    Preprint arXiv:0812.3082.doi:10.1145/ 377604.377612. [TW23] Jacobo Tor´ an and Florian W¨ orz. Number of variables for graph differentiation and the resolution of graph isomorphism formulas.ACM Trans. Comput. Log., 24(3):23:1– 23:25,

    Pith/arXiv arXiv

  31. [31]

    44 [Ula60] S

    Originally appeared in CSL 2022; ECCC preprint TR21-097.doi:10.1145/ 3580478. 44 [Ula60] S. M. Ulam.A collection of mathematical problems, volume 8 ofIntersci. Tracts Pure Appl. Math.Interscience Publishers, New York, NY,

    2022