PMI-Sequence-Discrete-Math-

PMI Sequence — An Erdős-Szekeres Type Result

Mudassir Shabbir · LUMS Pakistan

With connections to work with W. Abbas, A. Y. Yazıcıoğlu, X. Koutsoukos (Vanderbilt / UT Dallas)

Discrete Mathematics Combinatorial Geometry In Preparation

What is a PMI Sequence?

A Pairwise Monotone Increasing (PMI) sequence in a set X ⊆ ℤ^d is a sequence of points x⁽¹⁾, x⁽²⁾, …, x^(k) such that every coordinate of x^(t+1) is strictly greater than the corresponding coordinate of x^(t) — i.e., they form a chain in the product order on ℤ^d.

The classical Erdős-Szekeres theorem (1935) guarantees that any sequence of more than (r-1)(s-1) distinct integers contains a monotone increasing subsequence of length r or a monotone decreasing subsequence of length s. The PMI problem is a multi-dimensional analogue.

Main Result

Theorem (Lower Bound, d Dimensions). For every integer d ≥ 1 and every set X ⊆ ℤ_≥0^d with |X| = n, the longest PMI sequence in X has length at least

⌈(d! · n)^1/d⌉ − C_d

where C_d is a constant depending only on d. Together with a matching upper bound, this shows the maximum PMI length over all n-point sets in ℤ_≥0^d is (d! · n)^1/d up to lower-order terms.

Abstract

We study the maximum length of a Pairwise Monotone Increasing (PMI) sequence in a set of n points in the d-dimensional non-negative integer grid ℤ_≥0^d. This is an Erdős-Szekeres type question in the multi-dimensional product order.

We prove tight asymptotic bounds: the answer is Θ((d! · n)^1/d), resolving a question motivated by applications to network controllability (strong structural controllability via zero-forcing sets) and combinatorial geometry. The proof introduces a layered induction on "levels" of the grid, decomposing the point set along the minimum coordinate, and applies the inductive hypothesis on the resulting lower-dimensional faces with carefully tracked intersection multiplicities.

Keywords: PMI sequence · Erdős-Szekeres · Product order · Combinatorial bounds · Network controllability

Motivation from Network Theory

PMI sequences arise naturally in the study of strong structural controllability of networks. A key quantity — the distance-based bound on zero-forcing number — can be characterized using the length of the longest PMI sequence in a set derived from pairwise distances in the network graph. This connection, established in earlier work (Shabbir, Abbas, Yazıcıoğlu, Koutsoukos, IEEE TAC 2023), motivates tight combinatorial bounds on PMI sequence length.