Laboratory of Mathematical Logic at PDMI

Вторник, 5 сентября, комната 412. Начало в 12:00.

Докладчик: М. А. Всемирнов.

ЯВНЫЕ КОНСТРУКЦИИ СЕМЕЙСТВ ПЕРЕСТАНОВОК, НЕЗАВИСИМЫХ ОТНОСИТЕЛЬНО МИНИМУМА
множество перестановок s называется независимым по k относительно минимума (k-min-wise independent), если для любого набора x_1,...,x_k количество таких перестановок s из s, что s(x_1) < s(x_2), ... , s(x_1) < s(x_k), равно |s|/k. разумеется, представляют интерес множества s как можно меньшей мощности, в частности, отличные от симметрической и знакопеременной групп.
в общем случае известны либо теоремы существования, либо конструкции таких множеств, требующие решения задачи большой вычислительной сложности.
в докладе будет изложена явная простая конструкция при k=4. конструкция использует проективную геометрию. кроме того, будет предложен ряд открытых вопросов.