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

DOI10.1007/S11083-017-9431-6zbMATH Open1469.91017arXiv1702.03018OpenAlexW3103858337WikidataQ122963322 ScholiaQ122963322MaRDI QIDQ722587FDOQ722587

Authors: Andries E. Brouwer, J. Daniel Christensen 

Publication date: 27 July 2018

Published in: Order (Search for Journal in Brave)

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Counting linear extensions
• The number of linear extensions of the Boolean lattice
• A computation of the eighth Dedekind number
• The number of linear extensions of subset ordering
• Nim-type games
• David Gale's Subset Take-Away Game

Cited In (5)

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

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)