Gonality Game Module

Combinatorial tools for chip firing and gonality studies.

This module provides functions for parking functions, independent sets, treewidth calculations, and scramble numbers as mentioned in the academic literature.

chipfiring.CFCombinatorics.is_parking_function(sequence: List[int], n: int | None = None) → bool

Check if a sequence is a parking function.

A parking function of length n is a sequence (a1, a2, …, an) where ai ∈ {1, 2, …, n} such that if we sort the sequence in non-decreasing order to get (b1, b2, …, bn), then bi ≤ i for all i.

Parameters:

• sequence – The sequence to test

• n – Length constraint (if None, uses len(sequence))

Returns:

True if sequence is a parking function

Return type:

bool

Examples

>>> is_parking_function([1, 1, 2])
True
>>> is_parking_function([1, 3, 3])
False
>>> is_parking_function([2, 1, 1])
True

chipfiring.CFCombinatorics.generate_parking_functions(n: int) → List[List[int]]

Generate all parking functions of length n.

Parameters:

n – Length of parking functions to generate

Returns:

All parking functions of length n

Return type:

List[List[int]]

Examples

>>> funcs = generate_parking_functions(2)
>>> len(funcs)
3
>>> sorted(funcs)
[[1, 1], [1, 2], [2, 1]]

chipfiring.CFCombinatorics.parking_function_count(n: int) → int

Return the number of parking functions of length n.

The number of parking functions of length n is (n+1)^(n-1).

Parameters:

n – Length of parking functions

Returns:

Number of parking functions of length n

Return type:

int

Examples

>>> parking_function_count(1)
1
>>> parking_function_count(2)
3
>>> parking_function_count(3)
16

chipfiring.CFCombinatorics.is_connected(graph: CFGraph) → bool

Check if a graph is connected.

Parameters:

graph – The graph to check

Returns:

True if graph is connected

Return type:

bool

chipfiring.CFCombinatorics.maximal_independent_sets(graph: CFGraph) → List[Set[str]]

Find all maximal independent sets in a graph.

An independent set is a set of vertices with no edges between them. A maximal independent set cannot be extended by adding another vertex.

Parameters:

graph – The graph to analyze

Returns:

List of maximal independent sets (vertex names)

Return type:

List[Set[str]]

Examples

>>> vertices = {"0", "1", "2"}
>>> edges = [("0", "1", 1)]
>>> graph = CFGraph(vertices, edges)
>>> mis = maximal_independent_sets(graph)
>>> len(mis) >= 1
True

chipfiring.CFCombinatorics.independence_number(graph: CFGraph) → int

Compute the independence number (size of largest independent set).

Parameters:

graph – The graph to analyze

Returns:

The independence number

Return type:

int

Examples

>>> vertices = {"0", "1", "2"}
>>> edges = [("0", "1", 1)]
>>> graph = CFGraph(vertices, edges)
>>> independence_number(graph) >= 1
True

chipfiring.CFCombinatorics.minimum_degree(graph: CFGraph) → int

Compute the minimum degree of a graph.

For connected simple graphs, this provides a lower bound on treewidth and gonality: δ(G) ≤ tw(G) ≤ gon(G). With parallel edges, this function returns weighted valence and that inequality need not hold.

Parameters:

graph – The graph to analyze

Returns:

The minimum degree

Return type:

int

Examples

>>> vertices = {"0", "1", "2"}
>>> edges = [("0", "1", 1), ("1", "2", 1), ("0", "2", 1)]
>>> graph = CFGraph(vertices, edges)
>>> minimum_degree(graph)
2

chipfiring.CFCombinatorics.maximum_degree(graph: CFGraph) → int

Compute the maximum degree of a graph.

Parameters:

graph – The graph to analyze

Returns:

The maximum degree

Return type:

int

Examples

>>> vertices = {"0", "1", "2", "3"}
>>> edges = [("0", "1", 1), ("1", "2", 1), ("2", "3", 1)]
>>> graph = CFGraph(vertices, edges)
>>> maximum_degree(graph)
2

chipfiring.CFCombinatorics.is_bipartite(graph: CFGraph) → bool

Check if a graph is bipartite.

Parameters:

graph – The graph to check

Returns:

True if the graph is bipartite

Return type:

bool

Examples

>>> vertices = {"0", "1", "2", "3"}
>>> edges = [("0", "2", 1), ("0", "3", 1), ("1", "2", 1), ("1", "3", 1)]
>>> graph = CFGraph(vertices, edges)
>>> is_bipartite(graph)
True

chipfiring.CFCombinatorics.bramble_order_lower_bound(graph: CFGraph) → int

Compute a lower bound on the maximum bramble order.

This uses the relation between bramble order, treewidth, and gonality.

Parameters:

graph – The graph to analyze

Returns:

Lower bound on maximum bramble order

Return type:

int

Examples

>>> vertices = {"0", "1", "2"}
>>> edges = [("0", "1", 1), ("1", "2", 1), ("0", "2", 1)]
>>> graph = CFGraph(vertices, edges)
>>> bramble_order_lower_bound(graph) >= 1
True

chipfiring.CFCombinatorics.complete_multipartite_gonality(partition_sizes: List[int]) → int

Compute the exact gonality of a complete multipartite graph K_{n1,n2,…,nk}.

For at least two nonempty parts, gon(K_{n1,...,nk}) = n - max(ni).

Parameters:

partition_sizes – List of partition sizes

Returns:

The exact gonality

Return type:

int

Examples

>>> complete_multipartite_gonality([2, 2, 2])  # Octahedron K_{2,2,2}
4
>>> complete_multipartite_gonality([3, 4])  # K_{3,4}
3

chipfiring.CFCombinatorics.octahedron_independence_number() → int

Compute the independence number of the octahedron (K_{2,2,2}).

As proven in the theory, the octahedron has independence number 2.

Returns:

The independence number (2)

Return type:

int

chipfiring.CFCombinatorics.octahedron_bramble_construction() → Dict[str, Any]

Construct the bramble of order 5 on the octahedron as described in the theory.

This bramble proves that the treewidth of the octahedron is at least 4.

Returns:

Information about the bramble construction

Return type:

Dict[str, Any]

chipfiring.CFCombinatorics.treewidth_upper_bound(graph: CFGraph) → int

Compute an upper bound for the treewidth of a graph.

This uses a simple greedy elimination ordering to get an upper bound. The actual treewidth may be smaller.

Parameters:

graph – The graph to analyze

Returns:

Upper bound on treewidth

Return type:

int

Examples

>>> vertices = {"0", "1", "2", "3"}
>>> edges = [("0", "1", 1), ("1", "2", 1), ("2", "3", 1), ("3", "0", 1)]
>>> graph = CFGraph(vertices, edges)
>>> treewidth_upper_bound(graph) >= 1
True

chipfiring.CFCombinatorics.scramble_number_upper_bound(graph: CFGraph) → int

Return the trivial vertex-count upper bound for scramble number.

Parameters:

graph – The graph to analyze

Returns:

Upper bound on scramble number

Return type:

int

Examples

>>> vertices = {"0", "1", "2"}
>>> edges = [("0", "1", 1), ("1", "2", 1)]
>>> graph = CFGraph(vertices, edges)
>>> scramble_number_upper_bound(graph) >= 1
True

chipfiring.CFCombinatorics.genus_upper_bound(graph: CFGraph) → int

Return the chip-firing genus (first Betti number) of a connected graph.

The historical function name is retained for compatibility; the returned value is exact, not merely an upper bound.

Parameters:

graph – The graph to analyze

Returns:

Upper bound on genus

Return type:

int

Examples

>>> vertices = {"0", "1", "2", "3"}
>>> edges = [("0", "1", 1), ("1", "2", 1), ("2", "3", 1), ("3", "0", 1)]
>>> graph = CFGraph(vertices, edges)
>>> genus_upper_bound(graph) >= 0
True

chipfiring.CFCombinatorics.gonality_theoretical_bounds(graph: CFGraph) → Dict[str, int]

Compute certified divisorial-gonality bounds for a connected simple graph.

The lower bounds use vertex connectivity, minimum degree, and bramble order. The upper bounds use the vertex count, independence number, and the graph Riemann-Roch bound g + 1. Multigraphs are rejected because the simple-graph independence and treewidth inequalities used here do not account for edge multiplicity.

Parameters:

graph – The graph to analyze

Returns:

Dictionary of bound names to values

Return type:

Dict[str, int]

Examples

>>> vertices = {"0", "1", "2", "3"}
>>> edges = [("0", "1", 1), ("1", "2", 1), ("2", "3", 1), ("3", "0", 1)]
>>> graph = CFGraph(vertices, edges)
>>> bounds = gonality_theoretical_bounds(graph)
>>> 'independence_upper_bound' in bounds
True

chipfiring.CFCombinatorics.analyze_graph_properties(graph: CFGraph) → Dict[str, Any]

Analyze various combinatorial properties relevant to gonality.

Parameters:

graph – The graph to analyze

Returns:

Dictionary of properties and their values

Return type:

Dict[str, Any]

Examples

>>> vertices = {"0", "1", "2"}
>>> edges = [("0", "1", 1), ("1", "2", 1)]
>>> graph = CFGraph(vertices, edges)
>>> props = analyze_graph_properties(graph)
>>> 'num_vertices' in props
True

chipfiring.CFCombinatorics.graph_complement(graph: CFGraph) → CFGraph

Compute the complement of a graph.

Parameters:

graph – The input graph

Returns:

The complement graph

Return type:

CFGraph

chipfiring.CFCombinatorics.icosahedron_independence_number() → int

Compute the independence number of the icosahedron.

The icosahedron has independence number α(I) = 3.

Returns:

The independence number (3)

Return type:

int

chipfiring.CFCombinatorics.icosahedron_2_uniform_scramble() → Dict[str, Any]

Return the all-edges 2-uniform scramble on the icosahedron.

Beougher et al., “Chip-firing on the Platonic solids: a primer for studying graph gonality,” use all 30 edges as the connected two-vertex eggs. Its hitting number is 9 and its egg-cut number is 8, so its norm is 8.

Returns:

Dict containing scramble construction details

chipfiring.CFCombinatorics.icosahedron_screewidth_bound() → Dict[str, int]

Return the known scramble-number and screewidth values for the icosahedron.

The all-edge scramble gives sn(I) >= 8. A width-8 tree-cut decomposition gives scw(I) <= 8, and sn(I) <= scw(I), so both parameters equal 8.

Returns:

Dict containing screewidth bounds

chipfiring.CFCombinatorics.icosahedron_subgraph_outdegree_bounds() → Dict[str, Any]

Compute edge-boundary minima for vertex subsets of the icosahedron.

The reference lower bounds are 8 for subset orders 2 and 10, and 9 for orders 3 through 9. This function exhaustively computes the actual minimum cut size for every nontrivial subset order and verifies those bounds directly.

Returns:

Dictionary containing actual and reference lower bounds by subset size.

chipfiring.CFCombinatorics.icosahedron_gonality_proof_summary() → Dict[str, Any]

Return a literature-backed summary of the gonality-9 result.

This function does not execute an exhaustive Dhar calculation. It records the published upper- and lower-bound statements so callers can distinguish reference data from values computed by this package.

Returns:

Dictionary containing the exact published value and proof methods.

chipfiring.CFCombinatorics.icosahedron_lemma_3_subgraph_bounds() → Dict[str, Any]

Deprecated compatibility wrapper for subgraph outdegree data.

chipfiring.CFCombinatorics.icosahedron_dhars_burning_algorithm() → Dict[str, Any]

Deprecated compatibility wrapper for the published proof summary.

chipfiring.CFCombinatorics.icosahedron_egg_cut_number() → Dict[str, Any]

Compute the egg-cut number for the icosahedron.

The egg-cut number is related to scramble theory and provides another perspective on gonality bounds.

Returns:

Dict containing egg-cut number analysis

chipfiring.CFCombinatorics.icosahedron_hitting_set_analysis() → Dict[str, Any]

Analyze hitting sets for the icosahedron scramble construction.

This implements the hitting set computations that appear in the scramble number analysis.

Returns:

Dict containing hitting set analysis

chipfiring.CFCombinatorics.icosahedron_gonality_theoretical_bounds() → Dict[str, Any]

Return literature-backed invariants and exact gonality of the icosahedron.

Returns:

Dict containing all theoretical bounds

Gonality calculation and gonality games for chip-firing graphs.

This module provides functionality for computing graph gonality and playing gonality games, based on the mathematical framework described in “Chip-firing on the Platonic solids: A primer for studying graph gonality” by Beougher et al.

The gonality of a graph G, denoted gon(G), is the minimum number of chips Player A needs to guarantee a win in the Gonality Game, regardless of where Player B places the -1 chip.

class chipfiring.CFGonality.GonalityGameResult(player_a_wins: bool, initial_placement: CFDivisor, player_b_placement: str, final_divisor: CFDivisor, winnability: bool, winning_sequence: List[str] | None = None)

Bases: object

Represents the result of a single gonality game instance.

Variables:

• player_a_wins (bool) – True if Player A wins, False if Player B wins

• initial_placement (CFDivisor) – Player A’s initial chip placement

• player_b_placement (str) – Vertex name where Player B placed the -1 chip

• final_divisor (CFDivisor) – The divisor after Player B’s move

• winnability (bool) – Whether the final divisor is winnable via chip-firing

• winning_sequence (Optional[List[str]]) – Sequence of vertices fired to win (if applicable)

__init__(player_a_wins: bool, initial_placement: CFDivisor, player_b_placement: str, final_divisor: CFDivisor, winnability: bool, winning_sequence: List[str] | None = None)

class chipfiring.CFGonality.GonalityResult

Bases: object

Represents the result of a gonality calculation.

Variables:

• gonality (int) – The computed gonality value

• winning_strategies (List[CFDivisor]) – List of N-chip placements that guarantee Player A wins

• logs (List[str]) – Detailed logs of the calculation process

• verification_games (Dict[int, List[GonalityGameResult]]) – Game results for verification

__init__()

log(message: str)

Add a log message.

get_log_summary() → str

Get complete log of the gonality calculation.

class chipfiring.CFGonality.CFGonality(graph: CFGraph)

Bases: object

Main class for gonality calculations and gonality games.

__init__(graph: CFGraph)

Initialize gonality calculator for a given graph.

Parameters:

graph – The CFGraph to analyze

play_gonality_game(n_chips: int, player_a_placement: CFDivisor, player_b_vertex: str, verbose: bool = False) → GonalityGameResult

Play a single instance of the Gonality Game.

Parameters:

• n_chips – Number of chips Player A is allowed to place

• player_a_placement – Player A’s chip placement (must have total degree n_chips)

• player_b_vertex – Vertex name where Player B places the -1 chip

• verbose – Whether to include detailed winning sequence

Returns:

Complete result of the game instance

Return type:

GonalityGameResult

Raises:

ValueError – If player_a_placement doesn’t have exactly n_chips total degree

_find_winning_sequence(divisor: CFDivisor) → List[str]

Find a sequence of chip-firing moves that wins the Dollar Game. This is a simplified implementation - a full implementation would use more sophisticated algorithms.

test_n_chip_strategy(n_chips: int, placement: CFDivisor) → Tuple[bool, List[str]]

Test if a given N-chip placement guarantees Player A wins against all possible Player B moves.

Parameters:

• n_chips – Number of chips (for validation)

• placement – Player A’s chip placement strategy

Returns:

Tuple of (strategy_works, losing_vertices) where strategy_works is True if the placement beats all Player B responses, and losing_vertices lists vertices where Player B can place -1 to win

find_all_n_chip_strategies(n_chips: int, max_strategies: int | None = None) → List[CFDivisor]

Find all N-chip placements that guarantee Player A wins the Gonality Game.

Parameters:

• n_chips – Number of chips Player A can place

• max_strategies – Maximum number of strategies to find (None for all)

Returns:

List of winning CFDivisor placements

compute_gonality(max_gonality: int | None = None, find_strategies: bool = True) → GonalityResult

Compute the gonality of the graph.

The gonality is the minimum number N such that Player A has a winning strategy in the Gonality Game with N chips.

Parameters:

• max_gonality – Maximum gonality to check (defaults to number of vertices)

• find_strategies – Whether to find and store winning strategies

Returns:

Complete result including gonality value and winning strategies

Return type:

GonalityResult

verify_gonality_bounds(suspected_gonality: int) → Tuple[bool, bool, List[str]]

Verify gonality bounds by checking that suspected_gonality works but suspected_gonality-1 doesn’t.

Parameters:

suspected_gonality – The suspected gonality value to verify

Returns:

Tuple of (upper_bound_verified, lower_bound_verified, messages) where upper_bound_verified means suspected_gonality works, and lower_bound_verified means suspected_gonality-1 doesn’t work

chipfiring.CFGonality.gonality(graph: CFGraph, max_gonality: int | None = None, find_strategies: bool = True) → GonalityResult

Compute the gonality of a graph.

The gonality of a graph G is the minimum number of chips Player A needs to guarantee winning the Gonality Game, regardless of Player B’s strategy.

Algorithm: 1. For N = 1, 2, 3, …, find all possible ways Player A can place N chips 2. For each placement, test if Player A wins against all possible Player B responses 3. Return the minimum N for which Player A has a guaranteed winning strategy

Parameters:

• graph – The CFGraph to analyze

• max_gonality – Maximum gonality to check (defaults to number of vertices)

• find_strategies – Whether to find and return winning strategies

Returns:

Object containing gonality value, winning strategies, and logs

Return type:

GonalityResult

Example

>>> from chipfiring import CFGraph, gonality
>>> # Create a simple triangle graph
>>> vertices = {"A", "B", "C"}
>>> edges = [("A", "B", 1), ("B", "C", 1), ("A", "C", 1)]
>>> graph = CFGraph(vertices, edges)
>>> result = gonality(graph)
>>> result.gonality
2
>>> len(result.winning_strategies)
5

chipfiring.CFGonality.play_gonality_game(graph: CFGraph, n_chips: int, player_a_placement: CFDivisor, player_b_vertex: str, verbose: bool = False) → GonalityGameResult

Play a single instance of the Gonality Game.

Game Rules: 1. Player A places n_chips on the vertices of the graph 2. Player B places -1 chip on any vertex 3. Player A wins if they can eliminate all debt through chip-firing moves

Parameters:

• graph – The CFGraph on which to play

• n_chips – Number of chips Player A is allowed

• player_a_placement – Player A’s chip placement

• player_b_vertex – Vertex where Player B places -1 chip

• verbose – Whether to include detailed winning information

Returns:

Complete result of the game

Return type:

GonalityGameResult

Example

>>> from chipfiring import CFGraph, CFDivisor, play_gonality_game
>>> vertices = {"A", "B", "C"}
>>> edges = [("A", "B", 1), ("B", "C", 1), ("A", "C", 1)]
>>> graph = CFGraph(vertices, edges)
>>> placement = CFDivisor(graph, [("A", 2), ("B", 0), ("C", 0)])
>>> result = play_gonality_game(graph, 2, placement, "B")
>>> result.player_a_wins
True

Enhanced Dhar’s burning algorithm specifically optimized for gonality games.

This module extends the standard Dhar’s burning algorithm with specialized functions for gonality calculations, including optimizations for finding winning strategies and determining gonality bounds efficiently.

class chipfiring.CFGonalityDhar.GonalityDharAlgorithm(graph: CFGraph, initial_divisor: CFDivisor, q_name: str)

Bases: DharAlgorithm

Enhanced Dhar’s algorithm specialized for gonality game computations.

This class extends the standard DharAlgorithm with methods specifically designed for efficiency in gonality calculations, including batch testing of strategies and optimized burning processes.

__init__(graph: CFGraph, initial_divisor: CFDivisor, q_name: str)

Initialize the enhanced Dhar algorithm for gonality games.

Parameters:

• graph – A CFGraph object representing the graph

• initial_divisor – A CFDivisor object representing the initial chip configuration

• q_name – The name of the distinguished vertex (fire source)

test_strategy_batch(strategies: List[List[str]]) → List[bool]

Test multiple strategies efficiently using cached burning results.

Parameters:

strategies – List of strategies, where each strategy is a list of vertex names

Returns:

Results for each strategy (True if winning, False otherwise)

Return type:

List[bool]

test_strategy(strategy: List[str]) → bool

Test if a given strategy is winning. A strategy is winning if, after placing chips according to the strategy and having Player B place -1 at q, the resulting configuration is winnable using the same criterion as the EWD algorithm.

Parameters:

strategy – List of vertex names representing the strategy (chips added to V-{q})

Returns:

True if the strategy is winning, False otherwise

Return type:

bool

_enhanced_burning(config: CFConfig) → Set[str]

Enhanced burning algorithm optimized for gonality calculations.

Parameters:

config – CFConfig object with the chip configuration

Returns:

Names of all burnt vertices (excluding q)

Return type:

Set[str]

_should_burn(vertex: Vertex, burnt_vertices: Set[str], config: CFConfig) → bool

Determine if a vertex should burn given current burnt set.

Parameters:

• vertex – The vertex to test

• burnt_vertices – Set of currently burnt vertex names

• config – The chip configuration

Returns:

True if vertex should burn

Return type:

bool

_config_to_tuple(config: CFConfig) → tuple

Convert a configuration to a hashable tuple for caching.

Parameters:

config – CFConfig object

Returns:

Hashable representation of the configuration

Return type:

tuple

find_minimal_winning_strategies(max_chips: int) → List[List[str]]

Find all minimal winning strategies using at most max_chips chips.

Parameters:

max_chips – Maximum number of chips to use

Returns:

List of minimal winning strategies

Return type:

List[List[str]]

_is_subset_multiset(subset: List[str], superset: List[str]) → bool

Check if one multiset is a subset of another.

Parameters:

• subset – Potential subset as list

• superset – Potential superset as list

Returns:

True if subset is a subset of superset

Return type:

bool

gonality_lower_bound() → int

Compute a lower bound for gonality using burning algorithm analysis.

Returns:

Lower bound for gonality

Return type:

int

clear_cache()

Clear all cached results to free memory.

chipfiring.CFGonalityDhar.enhanced_dhar_gonality_test(graph: CFGraph, q_vertex_name: str, max_gonality: int | None = None) → Tuple[int, List[List[str]]]

Use enhanced Dhar’s algorithm to compute gonality and find winning strategies. This computes the smallest k such that placing k chips on V-{q} results in a configuration that is winnable after -1 chip is placed on q.

Parameters:

• graph – The graph to analyze

• q_vertex_name – Name of the distinguished vertex (Player B’s target)

• max_gonality – Maximum number of chips (k) to test (if None, uses V-1)

Returns:

(gonality_k, list of minimal winning strategies of size k)

Return type:

Tuple[int, List[List[str]]]

chipfiring.CFGonalityDhar.batch_gonality_analysis(graphs: List[Tuple[CFGraph, str]], max_gonality: int | None = None) → Dict[str, Dict]

Analyze gonality for multiple graphs efficiently.

Parameters:

• graphs – List of (graph, q_vertex_name) pairs

• max_gonality – Maximum gonality to test for each graph

Returns:

Results for each graph

Return type:

Dict[str, Dict]