ProbXiv
Explorersign in
Problem archiveProblem record

Statement

For a point (x,y,z)∈Z3(x,y,z)\in\mathbb{Z}^3, let

T(x,y,z)={(x′,y,z):x′≥x}∪{(x,y′,z):y′≥y}∪{(x,y,z′):z′≥z}⊆Z3,T(x,y,z)=\{(x',y,z):x'\ge x\}\cup\{(x,y',z):y'\ge y\}\cup\{(x,y,z'):z'\ge z\}\subseteq\mathbb{Z}^3,

the union of the three axis-parallel rays of lattice points issuing from (x,y,z)(x,y,z) in the positive coordinate directions; the point (x,y,z)(x,y,z) is called the apex of T(x,y,z)T(x,y,z).

For an integer n≥1n\ge 1, let f(n)f(n) be the maximum cardinality of a family T\mathcal{T} of pairwise disjoint sets T(x,y,z)T(x,y,z) whose apexes (x,y,z)(x,y,z) all lie in {1,2,…,n}3\{1,2,\dots,n\}^3.

Equivalently, call two distinct triples (x1,y1,z1),(x2,y2,z2)∈{1,…,n}3(x_1,y_1,z_1),(x_2,y_2,z_2)\in\{1,\dots,n\}^3 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 f(n)f(n) is the maximum size of a 2-comparable subset of {1,…,n}3\{1,\dots,n\}^3. Equivalently, f(n)f(n) is the maximum number of nonzero entries of a monotonic n×nn\times n matrix, i.e.\ of a matrix with entries in {0,1,…,n}\{0,1,\dots,n\} whose nonzero entries strictly increase along each row and along each column and in which, for each value i∈{1,…,n}i\in\{1,\dots,n\}, the set of cells holding the value ii forms a monotonic chain (any two such cells (x1,y1)(x_1,y_1), (x2,y2)(x_2,y_2) satisfy x1<x2x_1<x_2 and y1<y2y_1<y_2, or x1>x2x_1>x_2 and y1>y2y_1>y_2).

Determine the asymptotic growth of f(n)f(n) as n→∞n\to\infty. In particular, determine the exponent

γ=lim⁡n→∞log⁡f(n)log⁡n\gamma=\lim_{n\to\infty}\frac{\log f(n)}{\log n}

(and whether this limit exists), together with matching upper and lower bounds on f(n)f(n) of the same order of magnitude.

Record

Added
Links

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 in

Solve with an agent

Open the statement in a chat, with the problem and the ground rules already written into the prompt.

This opens a third-party site. Nothing is posted back to ProbXiv and nothing you write there is recorded here — what a model gives you is an attempt, which a person still has to check.