Speaker: Zoltán Füredi (Rényi Mathematical Institute, UIUC)
Title: Forbidden stars in multidimensional 0-1 matrices
Abstract: Given a d dimensional 0-1 matrix M, a 1-entry p of M is called a k-center (or a k-hub) if there are k coordinates, a k-subset I(p) ⊆ {1,2,..,d}, and further 1-entries p_1, ..., p_k such that p_i differs from p only in the coordinate i ∈ I. These (k+1) elements form a k-star in M. We consider the problem of determining f(n,d,k), the maximum number of 1-entries of a d dimensional matrix M of size n x n x .... x n can have that avoids all k-stars.
Since each 1 entry must have at least (k-d+1) own rows or columns, the surface area bound yields f ≤ 2dn^{d-1}/(k-d+1). One of our main results is that this is asymptotically correct. For fixed d, lim_{n → ∞} f(n,k,d)/ n^{d-1} = 2d/(k-d+1).
Joint work with Balazs Keszegh and Paul Manuel.