Date: Thursday June 27, 2019, 12h at Room C3-005, Campus Nord UPC
Speaker: Matthew Coulson (University of Birmingham)
Title: The critical window in random digraphs
Abstract: We consider the component structure of the random digraph D(n,p) inside
the critical window p = n^{-1} + \lambda n^{-4/3}. We show that the
largest component C_1 has size of order n^{1/3} in this range. In
particular we give explicit bounds on the tail probabilities of
|C_1|n^{-1/3}.
____________________________
Date: Wednesday May 29, 2019, 12h at Room C3-005, Campus Nord UPC
Speaker: Oznur Yasar Diner (UPC, Barcelona)
Title: Characterizing the minimal forbidden minors for graphs with small edge search number
Abstract: Edge search number is a graph invariant that is inherited by minors. Graphs with edge search number at most k are called k-searchable graphs. When k is fixed, there is a finite number of minor minimal graphs that we have to forbid to characterize k-searchable graphs. In this talk, we give the structural characterization of 4-searchable outerplanar graphs, series parallel graphs, and generalized wheel graphs, together with the complete sets of forbidden minors.
____________________________
Date: Wednesday May 15, 2019 at 12h, Room C3-005, Campus Nord UPC
Speaker: Bartłomiej Bosek (Jagiellonian University, Krakow)
Ttile: Weight choosability of oriented hypergraphs
Abstract: The 1-2-3 conjecture states that every simple graph (with no isolated edges) has an edge weighting by numbers 1,2,3 such that the resulting weighted vertex degrees form a proper coloring of the graph. We study a similar problem for oriented hypergraphs. We prove that every oriented hypergraph has an edge weighting satisfying a similar condition, even if the weights are to be chosen from arbitrary lists of size two. The proof is based on the Combinatorial Nullstellensatz and a theorem of Schur for permanents of positive semi-definite matrices. We derive several consequences of the main result for uniform hypergraphs. We also point on possible applications of our results to problems of 1-2-3 type for non-oriented hypergraphs.
This is joint work with Marcin Anholcer and Jarosław Grytczuk.
____________________________
Date: On 09.05.2019, 12:00, Room C3-005 Campus Nord UPC
Speaker: Miquel Angel Fiol, UPC Barcelona
Title: Regular partitions, spectra, and eigenspaces of Cayley (di)graphs of permutation groups
Abstract: In this talk we present a method to obtain regular partitions of Cayley (di)graphs (that is, graphs, digraphs, or mixed graphs) of permutation groups. By using representation theory, we also obtain the complete spectra and eigenspaces of the corresponding quotient (di)graphs. More precisely, we provide two different methods to find all the eigenvalues and eigenvectors of such (di)graphs, one based on the characters of the symmetric group, and the other on its irreducible representations. As an example, we apply these methods to the Pancake graphs and to a recent known family of mixed graphs (having edges with and without direction).
(Joint work with C. Dalfó, S. Pavlíková, and J. Sirán)
____________________________
Date: 04.04.2019, 12:15, Room C3-005 Campus Nord UPC
Speaker: Xing Shi Cai, Uppsala University
Title: Cutting resilient networks
Abstract: We define the (random) k-cut number of a rooted graph to model the difficulty of the destruction of a resilient network. The process is as the cut model of Meir and Moon except now a node must be cut k times before it is destroyed. We will discuss the k-cut number on paths, complete binary trees, split trees and conditional Galton-Watson trees.
____________________________
____________________________
Date: 06.03.2019, 12:30, Aula Màster del Campus Nord UPC
Speaker: Robert Sedgewick, Princeton University
Title: A 21st Century Model for Disseminating Knowledge
Abstract: In the early years of the third millenium, most professors are still teaching in virtually the same way they were taught and their teachers were taught, stretching back centuries. As we all know, this situation is ripe for change. University students seeking to learn a topic who now have little if any choice are about to be presented with a vast array of choices. What student would not want to swap a tired professor writing slowly on a chalkboard for a well-produced series of videos and associated content, given by a world leader in the field? We are on the verge of a transformation on the scale of the transformation wrought by Gutenburg. This imminent change raises a host of fascinating and far-reaching questions. In this talk, we describe a scalable model for teaching and learning that has already enabled us to reach millions of people around the world.
|
Vita: Robert Sedgewick is the founding chair and the William O. Baker Professor in the Department of Computer Science at Princeton and served for many years as a member of the board of directors of Adobe Systems. He previously served on the faculty at Brown University and has held visiting research positions at Xerox PARC, IDA, INRIA, and Bell Laboratories.
Prof. Sedgewick's research interests include analytic combinatorics, algorithm science, curriculum development, and innovations in the dissemination of knowledge. He has published widely in these areas and is the author of twenty books, which have sold nearly one million copies. He has also published extensive online content (including studio-produced video lectures) on analysis of algorithms and analytic combinatorics and (with Kevin Wayne) algorithms and computer science. Their MOOC on algorithms has been named one of the "top 10 MOOCs of all time" and their online content draws millions of pageviews
|
 |
____________________________
Date: 6.02.2019 at 12h at Room C3-005, Campus Nord UPC
Speaker: Patrick Morris (Freie Universität Berlin)
Title: Clique tilings in randomly perturbed graphs
Abstract: A major theme in both extremal and probabilistic combinatorics is to find the appearance thresholds for certain spanning structures. Classical examples of such spanning structures include perfect matchings, Hamilton cycles and $H$-tilings, where we look for vertex disjoint copies of $H$ covering all the vertices of some host graph $G$. In this talk we will focus on $H$-tilings in the case that $H$ is a clique, a natural generalisation of a perfect matching.
On the one hand there is the extremal question, how large does the minimum degree of an $n$ vertex graph $G$ have to be to guarantee the existence of a clique factor in $G$? On the other hand, there is the probabilistic question. How large does $p$ need to be to almost surely ensure the appearance of a clique factor in the Erd\H{o}s R\'enyi random graph G(n,p)? Optimal answers to these questions were given in two famous papers. The extremal question was answered by Hajnal and Szemerédi in 1970 and the probabilistic question by Johansson, Kahn and Vu in 2008. In this talk we bridge the gap between these two results by approaching the following question which contains the previous
questions as special cases. Given an arbitrary graph of some fixed minimum degree, how many random edges need to be added on the same set of vertices to ensure the existence of a clique tiling? We give optimal answers to this question in all cases. Such results are part of a recent research trend studying properties of what is known as the randomly perturbed graph model, introduced by Bohman, Frieze and Martin in 2003.
This is joint work with Jie Han and Andrew Treglown.
____________________________
Date: 19.12.2018 at 12h at Room C3-005, Campus Nord UPC
Speaker: Alberto Espuny (University of Birmingham)
Title: Edges on random regular hypergraphs and applications to subgraph testing
Abstract: Compared to the classical binomial random (hyper)graph model, the study of random regular hypergraphs is made more challenging due to correlations between the occurrence of different edges. I will present an edge-switching technique for hypergraphs which allows us to show that these correlations are limited for a large range of densities. This extends some previous results of Kim, Sudakov and Vu for graphs. From this, we will deduce several corollaries on subgraph counts in random d-regular hypergraphs. We also prove a conjecture of Dudek, Frieze, Ruciński and Šileikis on the threshold for the existence of an l-overlapping Hamilton cycle in a random d-regular r-graph. Moreover, I will introduce the basic notions of property testing. The previous results can be applied to prove bounds on the query complexity of testing subgraph-freeness. This problem was first studied by Alon, Kaufman, Krivelevich and Ron, who obtained several bounds on the query complexity of testing triangle-freeness. We extend some of these previous results beyond the triangle setting and to the hypergraph setting.This is joint work with Felix Joos, Daniela Kühn and Deryk Osthus.
____________________________
Day: 12.12.2018 at 12h at Room C3-005, Campus Nord UPC
Speaker: Sergey Dovgal (LIPN Paris)
Title: Asymptotic distribution of parameters in random maps
Abstract: In this joint work with Olivier Bodini, Julien Courtiel, Hsien-Kuei Hwang, we consider random rooted maps without regard to their genus. We address the problem of limiting distributions for six different parameters:
- vertices
- leaves
- loops
- root edges
- root isthmic construction
- root vertex degree
Each parameter has a different limiting distribution, varying from (discrete) geometric and Poisson to (continuous) Beta, normal, uniform, and an unusual bounded distribution characterised by its moments.
____________________________
Speaker: Ma Àngeles Serrano (ICREA-UB)
Title: Network geometry
Abstract: Networks are critical to understand human nature ---from genome to brain and society--- and our environment ---the Internet, food webs, international trade... ---, and are changing the way in which we model and predict complex systems in many different disciplines. Surprisingly, all complex networks talk a common language, regardless of their origin, and are imprinted with universal features. They are small-world, strongly clustered and hierarchical, modular, robust yet fragile, and may exhibit unexpected responses like cascades and other critical and extreme events.
Many of these fundamental properties are well explained by a family of hidden metric space network models that led to the discovery that the latent geometry of many real networks is hyperbolic. Hyperbolicity emerges as a result of the combination of popularity and similarity dimensions into an effective distance between nodes, such that more popular and similar nodes have more chance to interact. The geometric approach permits the production of truly cartographic maps of real networks that are not only visually appealing, but enable applications like efficient navigation and the detection of communities of similar nodes. Recently, it has also enabled the introduction of a geometric renormalization group that unravels the multiple length scales coexisting in complex networks, strongly intertwined due to their small world property.
Interestingly, real-world scale-free networks are self-similar when observed at the different resolutions unfolded by geometric renormalization, a property that might find its origin in an evolutionary drive. Practical applications of the geometric renormalization group for networks include high-fidelity downscaled network replicas, a multiscale navigation protocol in hyperbolic space that takes advantage of the increased navigation efficiency at higher scales, and many others.
____________________________
Day: 21.11.2018 at 12h at Aula Master, Campus Nord UPC
Speaker: Luca Trevisan (University of California at Berkeley)
Title: A Theory of Spectral clustering
Abstract: Spectral clustering algorithms find clusters in a given network by exploiting properties of the eigenvectors of matrices associated with the network. As a first step, one computes a spectral embedding, that is a mapping of nodes to points in a low-dimensional real space; then one uses geometric clustering algorithms such as k-means to cluster the points corresponding to the nodes.
Such algorithms work so well that, in certain applications unrelated to network analysis, such as image segmentation, it is useful to associate a network to the data, and then apply spectral clustering to the network. In addition to its application to clustering, spectral embeddings are a valuable tool for dimension-reduction and data visualization. The performance of spectral clustering algorithms has been justified rigorously when applied to networks coming from certain probabilistic generative models.
A more recent development, which is the focus of this lecture, is a worst-case analysis of spectral clustering, showing that, for every graph that exhibits a certain cluster structure, such structure can be found by geometric algorithms applied to a spectral embedding. Such results generalize the graph Cheeger’s inequality (a classical result in spectral graph theory), and they have additional applications in computational complexity theory and in pure mathematics.
____________________________
Day: 15.11.2018 at 12h at Room C3-005, Campus Nord UPC
Speaker: Miquel Àngel Fiol (Universitat Politècnica de Catalunya)
Title: A new class of polynomials related to the spectrum of a graph, and its application to bound the k-independence parameter.
Abstract: The k-independence number of a graph is the maximum size of a set of vertices at pairwise distance greater than k. A graph is called walk-regular if the number of closed walks of a given length l, rooted at a vertex v, only depends on l. In particular, a distance-regular graph is also walk-regular (but the converse does not hold).
In this work, we introduce a new family of polynomials obtained from the spectrum of a graph.
These polynomials, together with the interlacing technique, allow us to give tight spectral bounds on the k-independence number of a walk-regular graph.
____________________________
Day:8.10.2018 at 12h at Room C3-005, Campus Nord UPC
Speaker: Joe Ryan (The University of Newcastle, Australia)
Title: Degree Sequences in Multigraphs
Abstract: In 1988, Chartrand et al., [1] posed the question "Assign positive integer labels to the edges of a simple connected graph of order at least 3 in such a way that the graph becomes irregular, i.e., the weights (label sums) at each vertex are distinct. What is the minimum value of the largest label over all such irregular assignments?"
This problem arose from a consideration of multigraphs and the 'positive integer labels' assigned to each edge represent the number of edges parallel to that edge with 1 representing a simple edge connection between 2 vertices.
In this talk we consider degree sequences of certain graphs under the above Chartrand constraint when we extend the concept of multigraph to include loops.
[1] G. Chartrand, M.S. Jacobson, J. Lehel, O.R. Oellermann, S. Ruiz and F. Saba, Irregular networks, Cong. Numer. 64 (1988), 187--192.
____________________________
Day: 31.10.2018 at 12h at Room C3-005, Campus Nord UPC
Speaker: Shagnik Das (Freie Universität Berlin)
Title: Pertubed Ramsey problems
Abstract: We say a graph G is Ramsey for a pair of graphs (H1, H2) if any red-/blue-colouring of E(G) contains either a red H1 or a blue H2. Much research has been devoted to determining the thresholds at which the Erdős-Rényi random graph G(n,p) becomes Ramsey for (H1, H2). In this talk, we instead consider the perturbed random graph model, where one sprinkles some random edges on top of a deterministic dense graph, and ask how much less randomness is needed to ensure the resulting graph is Ramsey.This line of research was initiated by Krivelevich, Sudakov and Tetali in 2006, who determined the thresholds for the pairs (K3, Kt) with t ≥ 3. Here we extend their work, considering pairs of larger cliques. We also present results for cycles, and cycles versus cliques.
This is joint work with Andrew Treglown.
____________________________
Day: 10.10.2018 at 12h at Room C3-005, Campus Nord UPC
Speaker: Svetlana Poznanović (Clemson University, South Carolina)
Title:Mahonian-Stirling pairs of combinatorial statistics for labeled forests
Abstract: Björner and Wachs defined a major index for labeled plane forests and showed that it has the same distribution as the number of inversions. This can be viewed as a generalization of the classical result for permutations. In this talk I will discuss a few other natural statistics on labeled forests.
Specifically, I will introduce the notions of bottom-to-top maxima, cyclic bottom-to-top maxima, sorting index, and cycle minima. These statistics are such that the pairs (inv, Bt-max), (sor, Cyc), and (maj, Cbt-max) are equidistributed. Even though our results extend the result of Björner and Wachs and further generalize results for permutations, the picture is not complete and I will discuss some current work on how to improve this.
____________________________
Day: 19.09.2018 at 12h at Room C3-005, Campus Nord UPC
Speaker: Daniel Palacín (Hebrew University of Jerusalem)
Title: Product-free sets, a nonstandard approach
Abstract: A subset of a group is said to be product-free if it does not contain three elements satisfying the equation xy=z. Babai and Sós asked whether there exists a constant c>0 such that every finite group of order n has a product-free subset of size at least cn. While they proved the existence of such a constant for solvable groups, Gowers gave a negative answer to the question.
In this talk I will use model theoretic techniques to give an alternative proof of the aforementioned result of Gowers. No previous knowledge in model theory will be assumed.
Share: