Quasi-ran­dom prop­er­ties of com­bi­na­to­r­ial struc­tures such as graphs, hy­per­graphs or per­mu­ta­tions are de­ter­min­is­tic con­di­tions that forces a given (de­ter­min­is­tic) struc­ture to have ``ran­dom-like'' be­hav­ior. In the late 1980s, sem­i­nal pa­pers of Rodl, Thoma­son, and Chung, Gra­ham and Wil­son ini­ti­ated a sys­tem­atic study of prop­er­ties that forces a large graph to be quasi-ran­dom. For ex­am­ple, if a graph $G$ with den­sity $p$ has the cor­rect sub­graph den­si­ties of all 4-ver­tex graphs, i.e., the same as a typ­i­cal ran­dom graph $G(n,p)$, then $G$ has the cor­rect sub­graph den­sity of any fixed graph.

Gra­ham asked whether a sim­i­lar phe­nom­e­non can be es­tab­lished for per­mu­ta­tions, i.e., whether there is an in­te­ger $k$ such that if $P$ is a per­mu­ta­tion where every $k$-point per­mu­ta­tion has pack­ing den­sity about $1/k!$, then $P$ has the cor­rect pack­ing den­sity of any fixed per­mu­ta­tion. In 2013, this was an­swered af­fir­ma­tively by Kral and Pikhurko, who proved that in fact $k=4$ is suf­fi­cient. About 10 years ear­lier, Cooper ob­served that $k$ must be at least 4, so their bound on $k$ is best pos­si­ble. The proof of Kral and Pikhurko uti­lizes in­for­ma­tion about all the 24 pack­ing den­si­ties of 4-point per­mu­ta­tions, so it was nat­ural to ask how much can this list be re­duced. In this talk, we pre­sent an al­ter­na­tive proof of Kral-Pikhurko the­o­rem that forces the quasi-ran­dom be­hav­ior of a large per­mu­ta­tion using only spe­cific 8 pack­ing den­si­ties of 4-point per­mu­ta­tions.

This is a joint work with T. Chan, D. Kral and J. Noel.