Sophia Elia
(FU Berlin)

A comparison of Quotient Posets

Patrick Morris
(FU Berlin)

On the discrepancy of permutation families

Tamás Mészáros
(FU Berlin)

Sample compression schemes

Perfect Matchings in Random Subgraphs of Regular Bipartite Graphs

Abstract: Given an equivalence relation on the elements of a poset, place a new relation on the equivalence classes of elements. If this new relation is reflexive, antisymmetric, and transitive, then a quotient poset is created. We survey different types of quotient posets and see how they compare. In particular, we look at quotient posets that arise from lattice congruences, order-preserving group actions, and as images of surjective maps. We characterize quotient posets that correspond to a certain relation on equivalence classes by defining a sequence related to transitivity. Then we look at an application of quotient posets arising from order-preserving group actions. Let Hom(P,n) be the set of order-preserving maps from a poset P to a chain with  elements. Stanley showed that |Hom(P,n)| is given by a polynomial in . Given an order-preserving group action on P, there is an induced group action on Hom(P,n). Katharina Jochemko showed that the number of maps in Hom(P,n)up to equivalence under the induced group action is also polynomial in  using quotient posets. We touch on an alternative approach to the proof through the Ehrhart theory of order polytopes.

Abstract: For a set family S⊆ 2ⁿ, the discrepancy of S is 

disc(S):=min_χ:[n]→±1 max_S∈ S |∑_x∈S χ(x)|.

One can think of this as a colouring problem. Given a set system, we are interested in colouring the ground set red/blue such that in every set the difference between the number of red and number of blue points is as small as possible. Given a set of permutations π₁,...,π_k on [n], we can define a set family S(π₁,...,π_k) by taking all sets that occur as intervals in each of the permutations. Formally, 

S(π₁,...,π_k):={ {π_j(x),π_j(x+1),...,π_j(y)} : 1≤x≤y≤n, j∈[k] }.

How large can the discrepancy of such a family be?

It turns out that for any n∈ ℕ and two permutations, π,σ on [n], we have that disc(S(π,σ))≤ 2. What about three permutations?  Beck conjectured (around 1987) that this should also be bounded by a constant. In 2009, Matoušek described this as ``one of the most tantalising questions in combinatorial discrepancy". In this talk, we will present the eventual resolution of this conjecture by Newman and Nikolov in 2011. The talk will end with an invitation to an open problem. 

Abstract: In this talk we concentrate on two fundamental concepts of classical machine learning theory: learning and compression. Motivated by the fact that if a concept class admits a small sample compression scheme then it is efficiently learnable (Littlestone and Warmuth), we propose to study the relationship between the size of sample compression schemes and the combinatorial notion of VC dimension. In particular, we propose several directions to tackle the compression scheme conjecture which states that the smallest possible size of a sample compression scheme is linear in the VC dimension of the underlying concept class.

Abstract: Consider the random process in which the edges of a graph G are added one by one in a random order. A classical result states that if G is the complete graph K_2n or the complete bipartite graph K_n,n, then typically a perfect matching appears at the moment at which the last isolated vertex disappears. We extend this result to arbitrary k-regular bipartite graphs G on 2n vertices for all k=Ω(n). Surprisingly, this is not the case for smaller values of k. We construct sparse bipartite k-regular graphs in which the last isolated vertex disappears long before a perfect matching appears.  Joint work with Zur Luria and Michael Simkin.