Counterexamples to conjectures about subset takeaway and counting linear extensions of a Boolean lattice

DOI10.1007/S11083-017-9431-6MaRDI QIDQ722587zbMATH OpenOpenAlexWikidataFDO

Authors Andries E. Brouwer, J. Daniel Christensen

Publication date 27 July 2018

Published in Order (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1702.03018

zbMATH Keywords

partially ordered setcombinatorial gameGrundy numberimpartial gametotal order

Mathematics Subject Classification ID

Combinatorics of partially ordered sets (06A07) Combinatorial games (91A46) Computational methods for problems pertaining to game theory, economics, and finance (91-08) Computational methods for problems pertaining to ordered structures (06-08)

Abstract: We develop an algorithm for efficiently computing recursively defined functions on posets. We illustrate this algorithm by disproving conjectures about the game Subset Takeaway (Chomp on a hypercube) and computing the number of linear extensions of the lattice of a 7-cube and related lattices.

Recommendations

• Counting linear extensions
• Counting linear extensions of restricted posets
• Generating Linear Extensions Fast
• Algorithms over partially ordered sets
• scientific article; zbMATH DE number 16221

Cites work

• scientific article; zbMATH DE number 3521877 (Why is no real title available?)
• A computation of the eighth Dedekind number
• Counting linear extensions
• David Gale's Subset Take-Away Game
• Nim-type games
• The number of linear extensions of subset ordering
• The number of linear extensions of the Boolean lattice

Cited in

(5)

• Counterexamples to Hedetniemi's conjecture and infinite Boolean lattices
• The number of linear extensions of the Boolean lattice
• De Finetti lattices and magog triangles
• Chomp on generalized Kneser graphs and others
• A vertex and edge deletion game on graphs

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: Counterexamples to conjectures about subset takeaway and counting linear extensions of a Boolean lattice

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q722587)