Tripod packing
Statement
For a point , let
the union of the three axis-parallel rays of lattice points issuing from in the positive coordinate directions; the point is called the apex of .
For an integer , let be the maximum cardinality of a family of pairwise disjoint sets whose apexes all lie in .
Equivalently, call two distinct triples 2-comparable if there are at least two indices among the three coordinates in which the first triple is strictly smaller than the second, or at least two indices in which it is strictly larger; a set of triples is 2-comparable if every two of its members are, and is the maximum size of a 2-comparable subset of . Equivalently, is the maximum number of nonzero entries of a monotonic matrix, i.e.\ of a matrix with entries in whose nonzero entries strictly increase along each row and along each column and in which, for each value , the set of cells holding the value forms a monotonic chain (any two such cells , satisfy and , or and ).
Determine the asymptotic growth of as . In particular, determine the exponent
(and whether this limit exists), together with matching upper and lower bounds on of the same order of magnitude.
Record
- Added
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.