Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, January 28, 2016, 12:15 pm
Duration: 30 minutes
Location: CAB G51
Speaker: Zur Luria (ITS)
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.
Automatic MiSe System Software Version 1.4803M | admin login