Leírás
In a sense, I will continue my talk from three years ago (23 April 2015) where I've presented a corollary of a generalization of the Marcus-Tardos theorem that I've proved with Abhishek. In this talk, I'll present another generalization which says that if a (non-uniform) hypergraph on n ordered vertices avoids a fixed d-permutation hypergraph, then its size is at most O(n^{d-1}). Here d-permutation hypergraph is defined as a d-uniform hypergraph on the vertex set [1,..,kd] with disjoint edges such that every edge contains exactly one vertex from each [(i-1)d+1,..,id] interval. This was known earlier only for d=2 (Balogh-Bollobas-Morris and Klazar-Marcus), so this result can be considered as a common generalization of both this result, and the higher dimensional Marcus-Tardos (proved by Klazar-Marcus, and much later by Abhishek and me). Needless to say that the proof will use our methods and this time I'll try to give as much details as possible. I'll also try to talk a bit about the consequences of this result about the number of certain set partitions that avoid a fixed set partition. Here we can get the asymptotics within an exponential factor.
Joint work with Benjamin Gunby.