## Theory of Combinatorial Algorithms

Prof. Emo Welzl and Prof. Bernd Gärtner

# Mittagsseminar (in cooperation with A. Steger, D. Steurer and B. Sudakov)

 Mittagsseminar Talk Information

Date and Time: Thursday, January 28, 2016, 12:15 pm

Duration: 30 minutes

Location: OAT S15/S16/S17

Speaker: Zur Luria (ITS)

## Discrepancy in high-dimensional permutations

An order-n d-dimensional permutation is a 0-1 (d+1)-dimensional array A of side length n, such that each line contains a single 1 element. Here a line is the set of elements of A obtained by fixing all but one index and letting that index vary from 1 to n. A 1-dimensional permutation is a permutation matrix, and 2-dimensional permutations are equivalent to Latin squares. We define the discrepancy of A to be the maximum over all tuples of subsets X = (X_1, ... ,X_d+1) of V of ||A(X)|-|X_1||X_2|...|X_d+1|/n|. Here A(X) counts the number of 1-elements in A in the combinatorial box X. Motivated by the expander mixing lemma, we conjecture that a typical A satisfies disc(A) < O((|X_1||X_2|...|X_d+1|)^(1/2)). A consequence of this conjecture is that the maximal volume of an empty box (for any d) is O(n^2). Using Peter Keevash's recent construction of designs, we showed that this is true in dimension 2. Joint work with Nati Linial.

Information for students and suggested topics for student talks