Polynomial-time computation of the hull number of atomistic lattices
Statement
Let be an atomistic lattice with maximum element and set of atoms . For a subset , write for its join.
Atomistic-lattice hull-number conjecture. The minimum size of a subset such that
can be computed in polynomial time.
The preceding proposition gives a quasi-polynomial-time algorithm by bounding the hull number in terms of the logarithm of the lattice size, assuming joins can be computed in polynomial time. The conjecture generalizes the corresponding question for linear extension graphs and would provide a polynomial-time method for this lattice optimization problem.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.