Hypergraphs Generators API

Hypergraph Generators

graphcalc.hypergraphs.generators.uniform.affine_plane(q: int, **hg_kwargs) → Hypergraph

Construct the affine plane AG(2, q) for prime q.

Vertices are points of F_q^2 and edges are affine lines.

Parameters:

• q (int) – Prime order of the field.

• **hg_kwargs – Additional keyword arguments passed to Hypergraph.from_edges.

Returns:

Affine plane hypergraph with q^2 vertices, q^2 + q lines, and line size q.

Return type:

Hypergraph

Raises:

ValueError – If q is not prime.

graphcalc.hypergraphs.generators.uniform.arithmetic_progressions(n: int, k: int, cyclic: bool = True, include_reverse: bool = False, **hg_kwargs) → Hypergraph

Construct the k-term arithmetic progression hypergraph on Z_n.

The vertices are 0, 1, ..., n - 1 and hyperedges are k-term arithmetic progressions.

Parameters:

• n (int) – Number of vertices.

• k (int) – Progression length and edge size.

• cyclic (bool, default=True) – If True, progressions are taken modulo n. If False, only non-wrapping progressions inside [0, n-1] are included.

• include_reverse (bool, default=False) – In the cyclic model, whether to include both steps d and -d. When False, attempts to avoid double counting reverse progressions.

• **hg_kwargs – Additional keyword arguments passed to Hypergraph.from_edges.

Returns:

Arithmetic progression hypergraph.

Return type:

Hypergraph

Raises:

ValueError – If k < 2 or k > n.

graphcalc.hypergraphs.generators.uniform.complete_k_uniform(n: int, k: int, labels: Sequence[Vertex] | None = None, **hg_kwargs) → Hypergraph

Construct the complete k-uniform hypergraph on n vertices.

The hyperedges are all k-subsets of the vertex set.

Parameters:

• n (int) – Number of vertices.

• k (int) – Uniform edge size.

• labels (sequence, optional) – Vertex labels. If omitted, uses range(n).

• **hg_kwargs – Additional keyword arguments passed to Hypergraph.from_edges.

Returns:

Complete k-uniform hypergraph.

Return type:

Hypergraph

Raises:

ValueError – If k < 2 or k > n.

graphcalc.hypergraphs.generators.uniform.erdos_ko_rado_star(n: int, k: int, t: int = 1, core: Iterable[Hashable] | None = None, labels: Sequence[Vertex] | None = None, **hg_kwargs) → Hypergraph

Construct an Erdős-Ko-Rado t-star.

This is the family of all k-sets containing a fixed t-set called the core.

Parameters:

• n (int) – Number of vertices.

• k (int) – Uniform edge size.

• t (int, default=1) – Size of the fixed core.

• core (iterable, optional) – Chosen core. If omitted, the first t vertices are used.

• labels (sequence, optional) – Vertex labels. If omitted, uses range(n).

• **hg_kwargs – Additional keyword arguments passed to Hypergraph.from_edges.

Returns:

The EKR t-star.

Return type:

Hypergraph

Raises:

ValueError – If the parameters are inconsistent or if core is not a valid t-subset of the vertex set.

graphcalc.hypergraphs.generators.uniform.fano_plane(**hg_kwargs) → Hypergraph

Construct the Fano plane.

This is the projective plane PG(2, 2), a 3-uniform hypergraph on 7 vertices with 7 edges.

Parameters:

**hg_kwargs – Additional keyword arguments passed to Hypergraph.from_edges.

Returns:

Fano plane.

Return type:

Hypergraph

graphcalc.hypergraphs.generators.uniform.hilton_milner(n: int, k: int, labels: Sequence[Vertex] | None = None, **hg_kwargs) → Hypergraph

Construct the Hilton-Milner intersecting family.

Standard construction assumes n > 2k >= 4. On the vertex set V = [v_0, ..., v_{n-1}], let S = {v_0, ..., v_{k-1}} and x = v_k. The family is

{S} ∪ {A : |A| = k, x in A, A ∩ S != empty}.

Parameters:

• n (int) – Number of vertices.

• k (int) – Uniform edge size.

• labels (sequence, optional) – Vertex labels. If omitted, uses range(n).

• **hg_kwargs – Additional keyword arguments passed to Hypergraph.from_edges.

Returns:

Hilton-Milner family.

Return type:

Hypergraph

Raises:

ValueError – If k < 2 or n <= 2k.

graphcalc.hypergraphs.generators.uniform.k_uniform_matching(n: int, k: int, m: int, labels: Sequence[Vertex] | None = None, **hg_kwargs) → Hypergraph

Construct a matching of m disjoint k-edges.

Parameters:

• n (int) – Number of vertices.

• k (int) – Uniform edge size.

• m (int) – Number of disjoint edges.

• labels (sequence, optional) – Vertex labels. If omitted, uses range(n).

• **hg_kwargs – Additional keyword arguments passed to Hypergraph.from_edges.

Returns:

Hypergraph consisting of m pairwise disjoint edges.

Return type:

Hypergraph

Raises:

ValueError – If m < 0 or n < m * k.

graphcalc.hypergraphs.generators.uniform.k_uniform_star(n: int, k: int, center: Hashable | None = None, labels: Sequence[Vertex] | None = None, **hg_kwargs) → Hypergraph

Construct the k-uniform star centered at one vertex.

The hyperedges are all k-sets containing the chosen center.

Parameters:

• n (int) – Number of vertices.

• k (int) – Uniform edge size.

• center (hashable, optional) – Distinguished center vertex. If omitted, the first vertex is used.

• labels (sequence, optional) – Vertex labels. If omitted, uses range(n).

• **hg_kwargs – Additional keyword arguments passed to Hypergraph.from_edges.

Returns:

k-uniform star.

Return type:

Hypergraph

Raises:

ValueError – If n < k or center is not in the vertex set.

graphcalc.hypergraphs.generators.uniform.loose_cycle(r: int, k: int, start_label: int = 0, **hg_kwargs) → Hypergraph

Construct a k-uniform loose cycle with r edges.

Consecutive edges intersect in exactly one vertex, and nonconsecutive edges are disjoint. The vertex count is r * (k - 1).

Parameters:

• r (int) – Number of edges.

• k (int) – Uniform edge size.

• start_label (int, default=0) – Starting integer used for vertex labels.

• **hg_kwargs – Additional keyword arguments passed to Hypergraph.from_edges.

Returns:

Loose cycle. If r == 0, returns the empty hypergraph.

Return type:

Hypergraph

Raises:

ValueError – If k < 2 or r < 0.

graphcalc.hypergraphs.generators.uniform.loose_path(r: int, k: int, start_label: int = 0, **hg_kwargs) → Hypergraph

Construct a k-uniform loose path with r edges.

Consecutive edges intersect in exactly one vertex, and nonconsecutive edges are disjoint. The vertex count is r * (k - 1) + 1.

Parameters:

• r (int) – Number of edges.

• k (int) – Uniform edge size.

• start_label (int, default=0) – Starting integer used for vertex labels.

• **hg_kwargs – Additional keyword arguments passed to Hypergraph.from_edges.

Returns:

Loose path. If r == 0, returns the empty hypergraph.

Return type:

Hypergraph

Raises:

ValueError – If k < 2 or r < 0.

graphcalc.hypergraphs.generators.uniform.projective_plane(q: int, **hg_kwargs) → Hypergraph

Construct the projective plane PG(2, q) for prime q.

Vertices are projective points and hyperedges are projective lines.

Parameters:

• q (int) – Prime order of the field.

• **hg_kwargs – Additional keyword arguments passed to Hypergraph.from_edges.

Returns:

Projective plane hypergraph with q^2 + q + 1 vertices, q^2 + q + 1 lines, and line size q + 1.

Return type:

Hypergraph

Raises:

ValueError – If q is not prime.

graphcalc.hypergraphs.generators.uniform.random_k_regular_configuration(n: int, k: int, d: int, seed: object | None = None, max_tries: int = 2000, labels: Sequence[Vertex] | None = None, **hg_kwargs) → Hypergraph

Construct a random simple d-regular k-uniform hypergraph using a configuration-style model.

This attempts to partition vertex stubs into k-blocks. Candidate blocks containing repeated vertices are rejected. Duplicate edges are deduplicated, so exact regularity may fail if too many rejections occur. The best attempt found within max_tries is returned.

Parameters:

• n (int) – Number of vertices.

• k (int) – Uniform edge size.

• d (int) – Target vertex degree.

• seed (object, optional) – Seed passed to random.Random.

• max_tries (int, default=2000) – Maximum number of configuration attempts.

• labels (sequence, optional) – Vertex labels. If omitted, uses range(n).

• **hg_kwargs – Additional keyword arguments passed to Hypergraph.from_edges.

Returns:

A simple k-uniform hypergraph, often but not always exactly d-regular.

Return type:

Hypergraph

Raises:

ValueError – If n * d is not divisible by k.

graphcalc.hypergraphs.generators.uniform.random_k_uniform(n: int, k: int, p: float | None = None, m: int | None = None, seed: object | None = None, labels: Sequence[Vertex] | None = None, **hg_kwargs) → Hypergraph

Construct a random k-uniform hypergraph on n vertices.

Exactly one of p or m must be supplied.

• If p is provided, each k-subset is included independently with probability p.

• If m is provided, exactly m distinct edges are chosen uniformly without replacement.

Parameters:

• n (int) – Number of vertices.

• k (int) – Uniform edge size.

• p (float, optional) – Inclusion probability for the binomial model.

• m (int, optional) – Number of edges for the fixed-size model.

• seed (object, optional) – Seed passed to random.Random.

• labels (sequence, optional) – Vertex labels. If omitted, uses range(n).

• **hg_kwargs – Additional keyword arguments passed to Hypergraph.from_edges.

Returns:

Random k-uniform hypergraph.

Return type:

Hypergraph

Raises:

ValueError – If k > n, if both or neither of p and m are supplied, if p is outside [0, 1], or if m is out of range.

graphcalc.hypergraphs.generators.uniform.sunflower(k: int, petals: int, core_size: int = 1, start_label: int = 0, **hg_kwargs) → Hypergraph

Construct a k-uniform sunflower (delta-system).

All edges share the same core of size core_size and are otherwise pairwise disjoint.

Parameters:

• k (int) – Uniform edge size.

• petals (int) – Number of petals (edges).

• core_size (int, default=1) – Size of the common core.

• start_label (int, default=0) – Starting integer used for vertex labels.

• **hg_kwargs – Additional keyword arguments passed to Hypergraph.from_edges.

Returns:

Sunflower hypergraph.

Return type:

Hypergraph

Raises:

ValueError – If k < 2, petals < 0, or core_size is not in [0, k].

graphcalc.hypergraphs.generators.uniform.tight_cycle(n: int, k: int, labels: Sequence[Vertex] | None = None, **hg_kwargs) → Hypergraph

Construct the k-uniform tight cycle on n vertices.

The edges are the cyclic consecutive k-windows modulo n. There are exactly n edges.

Parameters:

• n (int) – Number of vertices.

• k (int) – Uniform edge size.

• labels (sequence, optional) – Vertex labels. If omitted, uses range(n).

• **hg_kwargs – Additional keyword arguments passed to Hypergraph.from_edges.

Returns:

Tight cycle.

Return type:

Hypergraph

Raises:

ValueError – If n < k.