Combinatorics and Computing Weekly Seminar
Hypergraphs with Property O and with Erdos-Szekeres Property
Hypergraphs with Property O and with Erdos-Szekeres Property
Meysam Miralaei, University of Sao Paulo, Brazil
12 NOV 2025
3:00 - 4:00
An oriented k-uniform hypergraph (a family of ordered k-sets) has Property O if, for every total order of its vertices, there exists an edge whose orientation is consistent with that order. In contrast, the Erdos-Szekeres Property concerns pairs of orders: for two linear orders <_1 and <_2 on a vertex set V, there exists a k-subset e \subset V that is monotone with respect to both, meaning that <_1 and <_2 induce either the same or the reverse order on e.
We present bounds on the minimum number of edges required for these properties and give explicit (non-random) constructions achieving them.
This talk is based on a joint work with Regis Barbosa, Yoshiharu Kohayakawa and Vojtech Rodl.
Zoom room information:
https://us06web.zoom.us/j/86247043799?pwd=KH1lKfYt1rGLzSgKk31MwprllTiOef.1
Meeting ID: 862 4704 3799
Passcode: 362880
Venue: Niavaran, Khosrovshahi Lecture Hall


