Contents Menu Expand Light mode Dark mode Auto light/dark, in light mode Auto light/dark, in dark mode Skip to content
Combinatorics
Light Logo Dark Logo
Version 10.6 Reference Manual
  • Home - Combinatorics
  • Comprehensive Module List
    • Abstract Recursive Trees
    • Affine Permutations
    • Algebraic combinatorics
    • Combinatorics
    • Alternating Sign Matrices
    • Backtracking
    • Baxter permutations
    • A bijectionist’s toolkit
    • Binary Recurrence Sequences
    • Binary Trees
    • Blob Algebras
    • Cartesian Products
    • Enumerated sets of partitions, tableaux, …
    • Combinatorial Hopf algebras
    • Poirier-Reutenauer Hopf algebra of standard tableaux
    • Word Quasi-symmetric functions
    • Cluster algebras and quivers
    • ClusterSeed
    • mutation_class
    • Helper functions for mutation types of quivers
    • Quiver
    • Quiver mutation types
    • Cluster complex (or generalized dual associahedron)
    • Colored Permutations
    • Combinatorial Functions
    • Fast computation of combinatorial functions (Cython + mpz)
    • Combinations
    • Combinatorial maps
    • Integer compositions
    • Signed Compositions
    • Composition Tableaux
    • Constellations
    • Cores
    • Counting
    • Affine Crystals
    • Affine factorization crystal of type \(A\)
    • Affinization Crystals
    • Alcove paths
    • Crystals
    • Benkart-Kang-Kashiwara crystals for the general-linear Lie superalgebra
    • Catalog Of Crystals
    • Catalog Of Elementary Crystals
    • Catalog Of Crystal Models For \(B(\infty)\)
    • Catalog Of Crystal Models For Kirillov-Reshetikhin Crystals
    • An introduction to crystals
    • Direct Sum of Crystals
    • Elementary Crystals
    • Fast Rank Two Crystals
    • Fully commutative stable Grothendieck crystal
    • Crystals of Generalized Young Walls
    • Highest weight crystals
    • Induced Crystals
    • \(\mathcal{B}(\infty)\) Crystals of Tableaux in Nonexceptional Types and \(G_2\)
    • Crystals of Kac modules of the general-linear Lie superalgebra
    • Kirillov-Reshetikhin Crystals
    • Kyoto Path Model for Affine Highest Weight Crystals
    • Crystals of letters
    • Littelmann paths
    • Crystals of Modified Nakajima Monomials
    • Crystal of Bernstein-Zelevinsky Multisegments
    • Crystal Of Mirković-Vilonen (MV) Polytopes
    • \(\mathcal{B}(\infty)\) Crystal Of PBW Monomials
    • PBW Data
    • Polyhedral Realization of \(B(\infty)\)
    • Spin Crystals
    • Star-Crystal Structure On \(B(\infty)\)
    • Tensor Products of Crystals
    • Tensor Products of Crystal Elements
    • Cyclic sieving phenomenon
    • De Bruijn sequences
    • Degree sequences
    • Derangements
    • Descent Algebras
    • Combinatorial designs and incidence structures
    • Balanced Incomplete Block Designs (BIBD)
    • Resolvable Balanced Incomplete Block Design (RBIBD)
    • Group-Divisible Designs (GDD)
    • Block designs
    • Covering Arrays (CA)
    • Covering designs: coverings of \(t\)-element subsets of a \(v\)-set by \(k\)-sets
    • Database of small combinatorial designs
    • Catalog of designs
    • Cython functions for combinatorial designs
    • Difference families
    • Difference Matrices
    • Evenly distributed sets in finite fields
    • External Representations of Block Designs
    • Database of generalised quadrangles with spread
    • Incidence structures (i.e. hypergraphs, i.e. set systems)
    • Mutually Orthogonal Latin Squares (MOLS)
    • Orthogonal arrays (OA)
    • Orthogonal arrays (build recursive constructions)
    • Orthogonal arrays (find recursive constructions)
    • Steiner Quadruple Systems
    • Hypergraph isomorphic copy search
    • Two-graphs
    • Combinatorial diagrams
    • Diagram and Partition Algebras
    • Exact Cover Problem via Dancing Links
    • Dyck Words
    • Substitutions over unit cube faces (Rauzy fractals)
    • Enumerated sets and combinatorial objects
    • Tools for enumeration modulo the action of a permutation group
    • Compute Bell and Uppuluri-Carpenter numbers
    • Families
    • Brent Yorgey’s fast algorithm for integer vector (multiset) partitions.
    • Fully commutative elements of Coxeter groups
    • Finite state machines, automata, transducers
    • Common Automata and Transducers (Finite State Machines Generators)
    • Free Quasi-symmetric functions
    • Free modules
    • Free Dendriform Algebras
    • Free Pre-Lie Algebras
    • Fully packed loops
    • Gelfand-Tsetlin Patterns
    • Paths in Directed Acyclic Graphs
    • Gray codes
    • Growth diagrams and dual graded graphs
    • Grossman-Larson Hopf Algebras
    • Hall Polynomials
    • The Hillman-Grassl correspondence
    • Enumerated set of lists of integers with constraints: base classes
    • Enumerated set of lists of integers with constraints: front-end
    • Enumerated set of lists of integers with constraints, in inverse lexicographic order
    • Counting, generating, and manipulating nonnegative integer matrices
    • (Non-negative) Integer vectors
    • Weighted Integer Vectors
    • Integer vectors modulo the action of a permutation group
    • Tamari Interval-posets
    • Strong and weak tableaux
    • Kazhdan-Lusztig Polynomials
    • Key polynomials
    • Knutson-Tao Puzzles
    • Combinatorics on matrices
    • Dancing Links internal pyx code
    • Dancing links C++ wrapper
    • Hadamard matrices
    • Latin Squares
    • Miscellaneous
    • Ordered Multiset Partitions into Sets and the Minimaj Crystal
    • Non-commutative symmetric functions and quasi-symmetric functions
    • Common combinatorial tools
    • Generic code for bases
    • Non-Commutative Symmetric Functions
    • Quasisymmetric functions
    • Introduction to Quasisymmetric Functions
    • Symmetric functions in non-commuting variables
    • Bases for \(NCSym\)
    • Dual Symmetric Functions in Non-Commuting Variables
    • Symmetric Functions in Non-Commuting Variables
    • Necklaces
    • Non-Decreasing Parking Functions
    • \(\nu\)-Dyck Words
    • \(\nu\)-Tamari lattice
    • Ordered Rooted Trees
    • Output functions
    • Parallelogram Polyominoes
    • Parking Functions
    • Catalog of Path Tableaux
    • Dyck Paths
    • Frieze Patterns
    • Path Tableaux
    • Semistandard Tableaux
    • Plane Partitions
    • Integer partitions
    • Partition/Diagram Algebras
    • Kleshchev partitions
    • Partition Shifting Algebras
    • Partition tuples
    • Iterators over the partitions of an integer
    • Perfect matchings
    • Permutations
    • Permutations (Cython file)
    • Posets
    • Cartesian products of Posets
    • D-Complete Posets
    • Mobile posets
    • Elements of posets, lattices, semilattices, etc.
    • Forest Posets
    • Hasse diagrams of posets
    • Incidence Algebras
    • Finite lattices and semilattices
    • Linear Extensions of Posets
    • Möbius Algebras
    • Catalog of posets and lattices
    • Finite posets
    • \(q\)-Analogues
    • \(q\)-Bernoulli Numbers and Polynomials
    • Combinatorics quickref
    • Rankers
    • Recognizable Series
    • \(k\)-regular sequences
    • Restricted growth arrays
    • Ribbons
    • Ribbon Shaped Tableaux
    • Ribbon Tableaux
    • Rigged configurations
    • Abstract classes for the rigged configuration bijections
    • Bijection between rigged configurations for \(B(\infty)\) and marginally large tableaux
    • Bijection classes for type \(A_n^{(1)}\)
    • Bijection classes for type \(A_{2n}^{(2)\dagger}\)
    • Bijection classes for type \(A_{2n}^{(2)}\)
    • Bijection classes for type \(A_{2n-1}^{(2)}\).
    • Bijection classes for type \(B_n^{(1)}\)
    • Bijection classes for type \(C_n^{(1)}\)
    • Bijection classes for type \(D_n^{(1)}\)
    • Bijection classes for type \(D_{n+1}^{(2)}\)
    • Bijection classes for type \(D_4^{(3)}\)
    • Bijection between rigged configurations and KR tableaux
    • Kleber Trees
    • Kirillov-Reshetikhin Tableaux
    • Crystal of Rigged Configurations
    • Rigged Configurations of \(\mathcal{B}(\infty)\)
    • Rigged Configuration Elements
    • Rigged Configurations
    • Rigged Partitions
    • Tensor Product of Kirillov-Reshetikhin Tableaux
    • Tensor Product of Kirillov-Reshetikhin Tableaux Elements
    • Root Systems
    • Ambient lattices and ambient spaces
    • Associahedron
    • Braid Move Calculator
    • Braid Orbit
    • Branching Rules
    • Cartan matrices
    • Cartan types
    • Coxeter Groups
    • Coxeter Matrices
    • Coxeter Types
    • Dynkin diagrams
    • Hecke algebra representations
    • Integrable Representations of Affine Lie Algebras
    • Nonsymmetric Macdonald polynomials
    • Pieri Factors
    • Tutorial: visualizing root systems
    • Finite complex reflection groups
    • Finite real reflection groups
    • Group algebras of root lattice realizations
    • Root lattice realizations
    • Root lattices and root spaces
    • Root systems
    • Root system data for super type A
    • Root system data for type A
    • Root system data for (untwisted) type A affine
    • Root system data for type A infinity
    • Root system data for type B
    • Root system data for type BC affine
    • Root system data for (untwisted) type B affine
    • Root system data for type C
    • Root system data for (untwisted) type C affine
    • Root system data for type D
    • Root system data for (untwisted) type D affine
    • Root system data for type E
    • Root system data for (untwisted) type E affine
    • Root system data for type F
    • Root system data for (untwisted) type F affine
    • Root system data for type G
    • Root system data for (untwisted) type G affine
    • Root system data for type H
    • Root system data for type I
    • Root system data for type Q
    • Root system data for affine Cartan types
    • Root system data for dual Cartan types
    • Extended Affine Weyl Groups
    • Fundamental Group of an Extended Affine Weyl Group
    • Root system data for folded Cartan types
    • Root system data for Cartan types with marked nodes
    • Root system data for reducible Cartan types
    • Root system data for relabelled Cartan types
    • Weight lattice realizations
    • Weight lattices and weight spaces
    • Weyl Character Rings
    • Weyl Groups
    • Rooted (Unordered) Trees
    • Robinson-Schensted-Knuth correspondence
    • Schubert Polynomials
    • Set Partitions
    • Fast set partition iterators
    • Ordered Set Partitions
    • Symmetric Functions
    • Characters of the symmetric group as bases of the symmetric functions
    • Classical symmetric functions
    • Generic dual bases symmetric functions
    • Elementary symmetric functions
    • Hall-Littlewood Polynomials
    • Hecke Character Basis
    • Homogeneous symmetric functions
    • Jack Symmetric Functions
    • Quotient of symmetric function space by ideal generated by Hall-Littlewood symmetric functions
    • Kostka-Foulkes Polynomials
    • LLT symmetric functions
    • Macdonald Polynomials
    • Monomial symmetric functions
    • Multiplicative symmetric functions
    • \(k\)-Schur Functions
    • Non-symmetric Macdonald Polynomials
    • Orthogonal Symmetric Functions
    • Symmetric functions defined by orthogonality and triangularity
    • Power sum symmetric functions
    • Schur symmetric functions
    • Symplectic Symmetric Functions
    • Symmetric functions, with their multiple realizations
    • Symmetric Functions
    • Witt symmetric functions
    • Shard intersection order
    • Shifted primed tableaux
    • Shuffle product of iterables
    • Sidon sets and their generalizations, Sidon \(g\)-sets
    • Similarity class types of matrices with entries in a finite field
    • sine-Gordon Y-system plotter
    • Six Vertex Model
    • Skew Partitions
    • Skew Tableaux
    • Functions that compute some of the sequences in Sloane’s tables
    • Combinatorial species
    • Characteristic Species
    • Composition species
    • Cycle Species
    • Empty Species
    • Functorial composition species
    • Generating Series
    • Examples of Combinatorial Species
    • Linear-order Species
    • Miscellaneous Functions
    • Partition Species
    • Permutation species
    • Product species
    • Recursive Species
    • Set Species
    • Combinatorial Species
    • Species structures
    • Subset Species
    • Sum species
    • Specht Modules
    • Subsets
    • Subsets satisfying a hereditary property
    • Subsets whose elements satisfy a predicate pairwise
    • Subwords
    • Subword complex
    • Super Tableaux
    • Super Partitions
    • Symmetric Group Algebra
    • Representations of the Symmetric Group
    • T-sequences
    • Tableaux
    • Residue sequences of tableaux
    • TableauTuples
    • Generalized Tamari lattices
    • Tiling Solver
    • Transitive ideal closure tool
    • Combinatorial triangles for posets and fans
    • Tuples
    • Introduction to combinatorics in Sage
    • Vector Partitions
    • Abstract word (finite or infinite)
    • Combinatorics on words
    • Alphabet
    • Finite word
    • Infinite word
    • Lyndon words
    • Word morphisms/substitutions
    • Word paths
    • Shuffle product of words
    • Suffix Tries and Suffix Trees
    • Word classes
    • Fast word datatype using an array of unsigned char
    • Datatypes for finite words
    • Common words
    • Datatypes for words defined by iterators and callables
    • User-customizable options for words
    • Set of words
    • Yang-Baxter Graphs
    • C-Finite Sequences
Back to top
View this page
Edit this page

Hypergraph isomorphic copy search¶

This module implements a code for the following problem:

INPUT: two hypergraphs \(H_1, H_2\)

OUTPUT: a copy of \(H_2\) in \(H_1\)

It is also possible to enumerate all such copies, and to require that such copies be induced copies. More formally:

A copy of \(H_2\) in \(H_1\) is an injection \(f:V(H_2)\mapsto V(H_1)\) such that for any set \(S_2\in E(H_2)\) we have \(f(S_2)\in E(H_1)\).

It is an induced copy if no other set of \(E(H_1)\) is contained in \(f(V(H_2))\), i.e. \(|E(H_2)|=\{S:S\in E(H_1)\text{ and }S\subseteq f(V(H_2))\}\).

The functions implemented here lists all such injections. In particular, the number of copies of \(H\) in itself is equal to \(|Aut(H)|\).

The feature is available through IncidenceStructure.isomorphic_substructures_iterator().

Implementation¶

A hypergraph is stored as a list of edges, each of which is a “dense” bitset over \(|V(H_1)|\) points. In particular, two sets of distinct cardinalities require the same memory space. A hypergraph is a C struct with the following fields:

  • n, m – (int) number of points and edges

  • limbs – (int) number of 64-bits blocks per set

  • set_space – (uint64_t *) address of the memory used to store the sets

  • sets – (uint64_t **) sets[i] points toward the limbs blocks encoding set \(i\). Note also that sets[i][limbs] is equal to the cardinality of set[i], so that sets has length m*(limbs+1)*sizeof(uint64_t).

  • names – (int *) associates an integer ‘name’ to each of the n points

The operations used on this data structure are:

  • void permute(hypergraph * h, int n1, int n2) – exchanges points \(n1\) and \(n2\) in the data structure. Note that their names are also exchanged so that we still know which is which.

  • int induced_hypergraph(hypergraph * h1, int n, hypergraph * tmp1) – stores in tmp1 the hypergraph induced by the first \(n\) points, i.e. all sets \(S\) such that \(S\subseteq \{0,...,n-1\}\). The function returns the number of such sets.

  • void trace_hypergraph64(hypergraph * h, int n, hypergraph * tmp) – stores in tmp1 the trace of \(h\) on the first \(n\) points, i.e. all sets of the form \(S\cap \{0, \ldots, n-1\}\).

Algorithm¶

We try all possible assignments of a representant \(r_i\in H_1\) for every \(i\in H_2\). When we have picked a representant for the first \(n<\) points \(\{0, \ldots, n-1\}\subsetneq V(H_2)\), we check that:

  • The hypergraph induced by the (ordered) list \(0, \ldots, n-1\) in \(H_2\) is equal to the one induced by \(r_0, \ldots, r_{n-1}\) in \(H_1\).

  • If \(S\subseteq \{0,...,n-1\}\) is contained in \(c\) sets of size \(k\) in \(H_2\), then \(\{r_i:i\in S\}\) is contained in \(\geq c\) sets of size \(k\) in \(H_1\). This is done by comparing the trace of the hypergraphs while remembering the original size of each set.

As we very often need to build the hypergraph obtained by the trace of the first \(n\) points (for all possible \(n\)), those hypergraphs are cached. The hypergraphs induced by the same points are handled similarly.

Limitations¶

Number of points For efficiency reason the implementation assumes that \(H_2\) has \(\leq 64\) points. Making this work for larger values means that calls to qsort have to be replaced by calls to qsort_r (i.e. to sort the edges you need to know the number of limbs per edge) and that induces a big slowdown for small cases (~50% when this code was implemented). Also, 64 points for \(H_2\) is already very very big considering the problem at hand. Even \(|V(H_1)|> 64\) seems too much.

Vertex ordering The order of vertices in \(H_2\) has a huge influence on the performance of the algorithm. If no set of \(H_2\) contains more that one of the first \(k<n\) points, then almost all partial assignments of representants are possible for the first \(k\) points (though the degree of the vertices is taken into account). For this reason it is best to pick an ordering such that the first vertices are contained in as many sets as possible together. A heuristic is implemented at relabel_heuristic().

AUTHORS:

  • Nathann Cohen (November 2014, written in various airports between Nice and Chennai).

Methods¶

class sage.combinat.designs.subhypergraph_search.SubHypergraphSearch¶

Bases: object

relabel_heuristic()[source]¶

Relabel \(H_2\) in order to make the algorithm faster.

Objective: we try to pick an ordering \(p_1,...,p_k\) of the points of \(H_2\) that maximizes the number of sets involving the first points in the ordering. One way to formalize the problems indicates that it may be NP-Hard (generalizes the max clique problem for graphs) so we do not try to solve it exactly: we just need a sufficiently good heuristic.

Assuming that the first points are \(p_1,...,p_k\), we determine \(p_{k+1}\) as the point \(x\) such that the number of sets \(S\) with \(x\in S\) and \(S\cap \{p_1,...,p_k\}\neq \emptyset\) is maximal. In case of ties, we take a point with maximum degree.

This function is called when an instance of SubHypergraphSearch is created.

EXAMPLES:

sage: d = designs.projective_plane(3)                                       # needs sage.schemes
sage: d.isomorphic_substructures_iterator(d).relabel_heuristic()            # needs sage.schemes
>>> from sage.all import *
>>> d = designs.projective_plane(Integer(3))                                       # needs sage.schemes
>>> d.isomorphic_substructures_iterator(d).relabel_heuristic()            # needs sage.schemes
Next
Two-graphs
Previous
Steiner Quadruple Systems
Copyright © 2005--2025, The Sage Development Team
Made with Sphinx and @pradyunsg's Furo
On this page
  • Hypergraph isomorphic copy search
    • Implementation
    • Algorithm
    • Limitations
    • Methods
    • SubHypergraphSearch
      • relabel_heuristic()