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, 2])
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.

This provides a simple lower bound on treewidth and gonality: δ(G) ≤ tw(G) ≤ gon(G)

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.

Based on the theory from “Chip-firing on the Platonic solids”, this provides a lower bound on treewidth and thus 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 k >= 2 partitions: gon(K_{n1,n2,…,nk}) = n - min(ni) where min(ni) is the smallest part. For k = 1 partition: gon(K_n) = n - 1 (complete graph gonality).

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}
4
>>> complete_multipartite_gonality([5])  # K_5 (complete graph)
4

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

Compute an upper bound for the scramble number of a graph.

The scramble number is related to gonality and chip firing dynamics. This provides a theoretical upper bound based on graph structure.

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

Compute an upper bound for the genus of a graph.

The genus is related to gonality through various inequalities.

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 various theoretical bounds for gonality.

This includes bounds from independence number, treewidth, bramble order, and minimum degree as described in the octahedron theory.

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.

As stated in “Chip-firing on the Platonic solids” by Beougher et al., the icosahedron has independence number α(I) = 3.

Returns:

The independence number (3)

Return type:

int

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

Implement the 2-uniform scramble construction for the icosahedron.

From the paper: “The icosahedron has a 2-uniform scramble with ||S|| = 8.” This implements the theoretical construction showing the scramble number.

Returns:

Dict containing scramble construction details

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

Compute screewidth bounds for the icosahedron.

From the paper: “scw(I) ≤ 8” where scw is the screewidth. The screewidth is related to the scramble number.

Returns:

Dict containing screewidth bounds

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

Implement Lemma 3 for subgraph outdegree bounds on the icosahedron.

This lemma provides bounds on the outdegree of effective divisors in subgraphs of the icosahedron, contributing to gonality analysis.

Returns:

Dict containing Lemma 3 analysis

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

Implement Dhar’s burning algorithm proof for icosahedron gonality.

This demonstrates the debt-free divisor analysis that proves the icosahedron gonality is exactly 9.

Returns:

Dict containing Dhar’s algorithm analysis

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

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, int]

Compute comprehensive theoretical bounds for icosahedron gonality.

This integrates all the theoretical results to show that gonality = 9.

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)
>>> print(f"Gonality: {result.gonality}")
>>> print(f"Winning strategies: {len(result.winning_strategies)}")

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")
>>> print(f"Player A wins: {result.player_a_wins}")

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]