Balancing Extensions in Posets of Large Width

Start Date: February 3, 2025
Event Start Time: 2:00 PM
Event End Time: 3:00 PM
Seminar Series: Rutgers Discrete Mathematics Seminar
Presenter(s): Max Aires - Rutgers University
Event Location: Conference Room 705 | Rutgers University | Hill Center | 110 Frelinghuysen Rd
Event Additional Info: <p>See: <a href="https://sites.google.com/view/rutgersdmseminar">https://sites.google.com/view/rutgersdmseminar</a></p>
Presentation Type: Stand Alone Presentation
Abstract:
A linear extension of P is a linear ordering compatible with the poset relations. Let p(x<y) be the probability that x precedes y in a uniformly random linear extension, and let δ(x,y)=min(p(x<y),p(y<x)) and δ(P) be the maximum value of δ(x,y) over all x,y in P. The following two conjectures about δ(P) are both well-known:
1. (The "1/3-2/3 Conjecture") δ(P) ≥ 1/3 whenever P is not a chain.
2. (The "Kahn-Saks Conjecture") δ(P) → 1/2 as w(P) → ∞ (where w(P) is the maximum size of an antichain in P).
While still far from either of these, we prove a number of conditions for δ(P) → 1/2 and δ(P) ≥ 1/e - o(1), using a mix of geometric and probabilistic techniques.

Joint with Jeff Kahn.

Events