Forbidden subposets for bounded fractional weak discrepancy of posets

For a finite poset P = (X, <) the fractional weak discrepancy (denoted by wd_F(P)) is defined as the minimum value t for which there is a function f: X → R such that (1) f(x) + 1 ≤ f(y) whenever x < y and (2) |f(x) - f(y)| ≤ t whenever x || y in P. It is known that wd_F(P) < 1 if and only if P is a semiorder. In other words, using a forbidden characterization of semiorders, wd_F(P) < 1 if and only if P does not contain either 2 + 2 or 1 + 3 as its subposet. In this talk, for each nonnegative integer m we will provide a family of forbidden subposets of P as an equivalent condition of being that wd_F(P) ≤ m.

Event Topic

Discrete Applied Math Seminar