You are invited to our Monday Lecture & Colloquium on January 13, 2020 at 14:15 h & 16:00 h & 17:00 h at FU Berlin. Exceptionally, there will be *ANOTHER COLLOQUIUM* at 17:00. Lecture: Monday, April 15th - 14:15 h =============================================================== Eric Fusy (École Polytechnique Paris): Bijections between families of walks using oriented planar maps =============================================================== Abstract: When counting walks (with a given step-set), an equi-enumeration phenomenom is often observed between a stronger constraint on the domain and a stronger constraint on the position of the endpoint (a classical 1d example is the fact that positive walks of length 2n are in bijection with walks of length 2n ending at 0, both being counted by the central binomial coefficient). I will show examples of such relations for 2d walks where the equi-enumeration can be bijectively explained using planar maps endowed with certain orientations (Schnyder woods, bipolar orientations). Coffee & Tea Break: Room MA 316 - Third Floor First Colloquium: 16:00 h ========================================================= Andrei Asinowski (Universität Klagenfurt): The vectorial kernel method and patterns in lattice paths ========================================================= Abstract: A directed lattice path is a polygonal line which starts at the origin and consists of several vectors of the form (1, y) (where y belongs to a fixed set of integers) appended to each other. Enumeration of different kinds of lattice paths (walks/bridges/meanders /excursions) was accomplished by Banderier and Flajolet in 2002. We refine and generalize their results by studying lattice paths that avoid a fixed pattern (or several patterns). To this end, we develop a "vectorial kernel method" – a unified framework for enumeration of words generated by a counter automaton. Another improtant tool is the "autocorrelation polynomial" that encodes self-overlappings of a pattern, and its generalization: the "mutual correlation matrix" for several patterns. This talk is based on joint work with Cyril Banderier, Axel Bacher, Bernhard Gittenberger and Valerie Rointer. Second Colloquium: 17:00 h ============================================== Shahrzad Haddadan (MPI Informatik Saarbrücken): Algorithms for top-k lists and social networks ============================================== Abstract: Today’s massive and dynamic data sets have motivated many computer scientists and mathematicians to study classical problems in combinatorics and graph theory in various settings. In certain settings the algorithms’ access to the data is restricted while in others the resources are limited. In this talk we explore such settings in three directions: ranking of objects, property testing in social networks and finding communities in dynamic graphs. In the first part, we discuss algorithms on permutations as well as prefixes of permutations also known as top-k lists. The study of later particularly arises in big data scenarios when analysis of the entire permutation is costly or not interesting. We start by discussing random walks on the set of full rankings or permutations of n objects, a set whose size is n!. Since the 1990s to today, various versions of this problem have been studied, each for a different motivation. The second part of the talk is devoted to property testing in social networks: Given a graph, an algorithm seeks to approximate several parameters of a graph just by accessing the graph by means of oracles and while querying these oracles as few times as possible. We introduce a new oracle access model which is applicable to social networks, and assess the complexity of estimating parameters such as the number of users (vertices) in this model. In the third part of the talk, we introduce a new dynamic graph model which is based on triadic closure: a friendship is more likely to be formed between a pair of users with a larger number of mutual friends. We find upper bounds for the rate of graph evolution in this model and using such bounds we devise algorithms discovering communities. I will finish this talk by proposing new directions and presenting related open problems. ========================================================================================= Location: Room MA 041 (Ground Floor) Technische Universität Berlin Institut für Mathematik Straße des 17. Juni 136 10623 Berlin