Automated Discharging Arguments for Density Problems in Grids

MaRDI QIDQ6254827zbMATH OpenFDO

Authors Derrick Stolee

Publication date 20 September 2014

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Abstract: Discharging arguments demonstrate a connection between local structure and global averages. This makes it an effective tool for proving lower bounds on the density of special sets in infinite grids. However, the minimum density of an identifying code in the hexagonal grid remains open, with an upper bound of $frac37approx0.428571$ and a lower bound of $frac512approx0.416666$. We present a new, experimental framework for producing discharging arguments using an algorithm. This algorithm replaces the lengthy case analysis of human-written discharging arguments with a linear program that produces the best possible lower bound using the specified set of discharging rules. We use this framework to present a lower bound of $frac2355approx0.418181$ on the density of an identifying code in the hexagonal grid, and also find several sharp lower bounds for variations on identifying codes in the hexagonal, square, and triangular grids.

This page was built for publication: Automated Discharging Arguments for Density Problems in Grids

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