Past LIMDA seminars
Summary of LIMDA seminars of the last years
Academic year 2018-2019
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}.
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)
(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.
____________________________
From February 27 to 20 March on the usual schedule of the LIMDA Seminar we had the BGSMath Graduate Course
BGSMath Graduate Course Introduction to Statistical Learning
Gabor Lugosi, ICREA-UPF
https://bgsmath.cat/event/introduction-statistical-learning-theory/
____________________________
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.
|  |
|---|
____________________________
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
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.
____________________________
Day: 28.11.2018 at 12h at Conference Room FME-UPC **Col·loqui de Matemàtiques FME-UPC**
Speaker: Ma Àngeles Serrano (ICREA-UB)
Title: Network geometry
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.
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.
Academic year 2017-2018
Date: April 12th 2018
Speaker: Nina Kamcev (ETH Zurich)
Title: Zero forcing in random and pseudorandom graphs
Abstract: A subset S of initially infected vertices of a graph G is called forcing if we can infect the entire
graph by iteratively applying the following process. At each step, any infected vertex which has a unique
uninfected neighbour, infects this neighbour. The forcing number of G is the minimum cardinality of a
forcing set in G. It was introduced independently as a bound for the minimum rank of a graph, and as a
tool in quantum information theory.
The focus of this talk is on the forcing number of the random graph. Furthermore, we will state our
bounds on the forcing number of pseudorandom graphs and related problems.
The results are joint work with Thomas Kalinowski and Benny Sudakov.
uninfected neighbour, infects this neighbour. The forcing number of G is the minimum cardinality of a
forcing set in G. It was introduced independently as a bound for the minimum rank of a graph, and as a
tool in quantum information theory.
The focus of this talk is on the forcing number of the random graph. Furthermore, we will state our
bounds on the forcing number of pseudorandom graphs and related problems.
The results are joint work with Thomas Kalinowski and Benny Sudakov.
____________________________
Date: March 21th 2018
Speaker: Marc Noy (UPC, Barcelona)
Title: Logic and graphs on surfaces
Abstract: The zero-one law holds in a class G of graphs if, for each graph property A expressible in first order (FO) logic, the probability that A is satisfied converges to either 0 or 1 when the number of vertices goes to infinity. We say that the convergence law holds if every FO property has a limiting probability, not necessarily 0 or 1.
We will discuss zero-one and convergence laws in the class of graphs embeddable on a fixed surface in FO
and also in monadic second order (MSO) logic, where one can quantify over sets of vertices in addition to quantifying over vertices. For FO properties the results do not depend on the surface, but for MSO there is a striking difference between the plane (or the sphere) and surfaces of higher genus.
Based on joint work with P. Heinig, T. Müller and A. Taraz, and with A. Atserias and S. Kreutzer.
We will discuss zero-one and convergence laws in the class of graphs embeddable on a fixed surface in FO
and also in monadic second order (MSO) logic, where one can quantify over sets of vertices in addition to quantifying over vertices. For FO properties the results do not depend on the surface, but for MSO there is a striking difference between the plane (or the sphere) and surfaces of higher genus.
Based on joint work with P. Heinig, T. Müller and A. Taraz, and with A. Atserias and S. Kreutzer.
____________________________
Date: January 16th 2018
Speaker: Matthew Tointon (Université de Neuchâtel, Switzerland)
Title: Commuting probability in infinite groups
Abstract: In a finite group G one can ask what the probability is that two elements chosen independently uniformly at random commute. It is clear that if G has an abelian subgroup of bounded index then this probability should be bounded from below. In the 1980s Peter Neumann proved a beautiful quantitative converse to this observation.
Antolin, Martino and Ventura consider the same question for infinite groups, choosing the two random elements with respect to a certain limit of finite probability measures. They conjecture that for any 'reasonable' sequence of measures Neumann's result should still hold. They also prove some special cases of this conjecture.
In this talk I will show that the Antolin-Martino-Ventura conjecture holds with effective quantitative bounds if we take the sequence of measures defined by the successive steps of a simple random walk, or the uniform measures on a Folner sequence. I will also present a concrete interpretation of the word 'reasonable' that is sufficient to force a sequence of measures to obey the conjecture. If I have time I will present an application to conjugacy growth.
____________________________
Date: December 13th 2017
Speaker: Simon Griffiths (Pontifical Catholic University of Rio de Janeiro)
Title: Moderate deviations of subgraph counts
Abstract: We study the probability of deviations of subgraph counts in the Erd\H os-R\'enyi random graph $G(n,m)$. In particular, for a particular range of moderately large deviations we determine the associated rate asymptotically. We also discuss the relation between subgraph count deviations.
Based on joint work with Christina Goldschmidt and Alex Scott.
____________________________
Date: November 28, 2017
Speaker: Pablo Candela (UAM-ICMAT)
Title: On sets with small sumset in the circle
Abstract: It is known by a theorem of Raikov that for any measurable subset A of the circle group, if the sumset A+A has Haar measure |A+A| <1, then this measure must be at least 2|A|. We shall discuss recent joint work with Anne de Roton concerning subsets A of the circle with |A+A| < (2+c) |A|. The results include partial progress towards an analogue in this setting of a conjecture of Freiman known as the 3k-4 conjecture. We shall also discuss applications of these results to the problem of estimating how large can the measure of a subset of the circle be if the set avoids solutions to an equation of the form x+y=kz, for k>2 an integer.
____________________________
Date: November 22nd 2017
Speaker: M. Ángeles Serrano (ICREA-UB)
Title: Multiscale unfolding of real networks by geometric renormalization
Abstract: Renormalization has proven to be a very powerful method for a rigorous investigation of systems as viewed at different distance scales. When implemented as a renormalization group to explore critical phenomena and universal properties, it is based on geometric concepts like self-similarity and scale-invariance. In complex networks multiple scales coexist but, due to the small world property, are so entangled that a proper definition of these symmetries remained elusive. However, complex networks display a hidden metric structure that can be exploited to define a geometric renormalization group.
We find that real scale-free networks embedded in a hidden metric space show geometric scaling under this renormalization group transformation. This feature enables us to unfold real networks in a self-similar multilayer shell which reveals the coexisting scales and their interplay. The multiscale unfolding brings about immediate practical applications. Among many possibilities, it yields a natural way of building high-fidelity smaller-scale replicas of large real networks, and sustains the design of a new multiscale navigation protocol in hyperbolic space which boosts the success of single-scale versions.
____________________________
Date: Wednesday November 15, 2017
Speaker: Anna de Mier (UPC)
Title: Approximating and decomposing clutters with matroids
Abstract: There are several clutters (aka antichains of sets) that can be associated with a matroid, as the clutter of circuits, the clutter of bases or the clutter of hyperplanes. This talk is about the following question: given an arbitrary clutter L, which are the matroidal clutters that are closest to L? To answer it we must first decide on the meaning of closest, and select one of the different matroidal clutters.
We show that for almost all reasonable choices above there is a finite set of matroidal clutters that approximate L and, moreover, that L can be recovered from them. We speak in this case of a decomposition of L. In addition to proving the existence of the decompositions
theoretically, we also give an algorithmic procedure to compute them.
The same framework also allows us to decompose matroidal clutters of non-representable matroids into representable ones, or into other classes of matroids. More generally, we prove that under mild conditions one can decompose the the clutter L with members of a favourite family of clutters, not necessarily a matroidal one.
This is joint work with Jaume Martí-Farré.
We show that for almost all reasonable choices above there is a finite set of matroidal clutters that approximate L and, moreover, that L can be recovered from them. We speak in this case of a decomposition of L. In addition to proving the existence of the decompositions
theoretically, we also give an algorithmic procedure to compute them.
The same framework also allows us to decompose matroidal clutters of non-representable matroids into representable ones, or into other classes of matroids. More generally, we prove that under mild conditions one can decompose the the clutter L with members of a favourite family of clutters, not necessarily a matroidal one.
This is joint work with Jaume Martí-Farré.
____________________________
Date: November 8th 2017
Speaker: Maximilian Wötzel (UPC-BGSMath)
Title: On Testing Minor-Freeness in Bounded Degree Graphs with One-Sided Error
Abstract: We present a one-sided error property testing algorithm for H-minor freeness in bounded-degree graphs for any minor H that is a minor of the (k \times 2)-grid (for any positive integer k). This includes, for example, testing whether a graph is a cactus graph and testing minor-freeness for minors which are cycles with parallel chords. The query complexity of our algorithm in terms of the number of vertices in the graph, n, is \tilde{O}(n^{2/3} / \eps^5).
Czumaj et~al. showed that C_k-minor freeness can be tested with query complexity \tilde{O}(\sqrt{n}). In contrast to these results, we analyze the structure of the graph and show that either we can find a subgraph of sublinear size that includes the forbidden minor, H, or we can find a pair of disjoint subsets of vertices whose edge-cut is large, and such that the induced subgraph of each subset is connected. We then prove a combinatorial lemma which shows that the latter structure includes H as a minor.
____________________________
Date: October 25th 2017
Speaker: Christoph Spiegel (UPC)
Title: Sparse Supersaturation and Extremal Results for Linear Homogeneous Systems
Title: Sparse Supersaturation and Extremal Results for Linear Homogeneous Systems
Abstract: We study the thresholds for the property of containing a solution to a linear homogeneous system in random sets. We expand a previous sparse Szémeredi-type result of Schacht to the broadest class of matrices possible. We also provide a shorter proof of a sparse Rado result of Friedgut, Rödl, Ruciński and Schacht based on a hypergraph container approach due to Nenadov and Steger. Lastly we further extend these results to include some solutions with repeated entries using a notion of non-trivial solutions due to Rúzsa as well as Rué et al.
____________________________
Date: October 18th 2017
Speaker: Gonzalo Fiz (UPC-BGSMath)
Title: The triangle-free process and R(3,k)
Abstract: Consider the following random graph process (G_m)_{m\in \N} on the vertex set [n] . Let G_0 be the empty graph and, for each m \in \N, let G_m be obtained from G_{m−1} by adding a single edge, chosen uniformly from those non-edges of G_{m−1} which do not create a triangle. The process ends when we reach a maximal triangle-free graph; we denote by G_{n,\triangle} this (random) final graph. This "triangle-free process" was suggested by Bollob\'as and Erd\H{o}s in 1990 as a possible method of producing good Ramsey graphs, but until Bohman's breakthrough paper in 2009, which determined the order of magnitude of e(G_{n,\triangle}), very little was known about the random triangle-free graph G_{n,\triangle} it produces.
A technique which has proved extremely useful in the study of random graph processes is the so-called ‘differential equations method’, which was introduced by Wormald in the late 1990s. In this method, the idea is to ‘track’ a collection of graph parameters, by showing that (with high probability) they closely follow the solution of a corresponding family of differential equations.
The aim of this talk is to give an overview of this method and to discuss a recent refinement of Bohman's result, which determines asymptotically the number of edges in G_{n,\triangle}, and moreover shows that it shares many properties with the Erd\H{o}s-R\'enyi random graph G(n,m) of the same density. As an application, we improve Kim's lower bound on the Ramsey number R(3,k), obtaining a bound within a factor of four of Shearer's upper bound.
This is joint work with Simon Griffiths and Rob Morris. Similar results were obtained independently by Tom Bohman and Peter Keevash.
Abstract: Consider the following random graph process (G_m)_{m\in \N} on the vertex set [n] . Let G_0 be the empty graph and, for each m \in \N, let G_m be obtained from G_{m−1} by adding a single edge, chosen uniformly from those non-edges of G_{m−1} which do not create a triangle. The process ends when we reach a maximal triangle-free graph; we denote by G_{n,\triangle} this (random) final graph. This "triangle-free process" was suggested by Bollob\'as and Erd\H{o}s in 1990 as a possible method of producing good Ramsey graphs, but until Bohman's breakthrough paper in 2009, which determined the order of magnitude of e(G_{n,\triangle}), very little was known about the random triangle-free graph G_{n,\triangle} it produces.
A technique which has proved extremely useful in the study of random graph processes is the so-called ‘differential equations method’, which was introduced by Wormald in the late 1990s. In this method, the idea is to ‘track’ a collection of graph parameters, by showing that (with high probability) they closely follow the solution of a corresponding family of differential equations.
The aim of this talk is to give an overview of this method and to discuss a recent refinement of Bohman's result, which determines asymptotically the number of edges in G_{n,\triangle}, and moreover shows that it shares many properties with the Erd\H{o}s-R\'enyi random graph G(n,m) of the same density. As an application, we improve Kim's lower bound on the Ramsey number R(3,k), obtaining a bound within a factor of four of Shearer's upper bound.
This is joint work with Simon Griffiths and Rob Morris. Similar results were obtained independently by Tom Bohman and Peter Keevash.
____________________________
____________________________
Academic year 2016-2017
Date: July 6th 2017
Speaker: Miquel Angel Fiol, UPC Barcelona
Title: The spectra of liffted digraphs
Abstract: We present a method to derive the complete spectrum of the lift \Gamma^\alpha of a base digraph \Gamma, with voltage assignment alpha on a (finite) group G.
The method is based on assigning to $\Gamma$ a quotient-like matrix whose entries are elements of the group algebra C[G], which fully represents Gamma^{\alpha}. This allows us to derive the eigenvectors and eigenvalues of the lift in terms of those of the base digraph and the irreducible characters of G. Thus, our main theorem generalize some previous results of Lovász and Babai concerning the spectra of Cayley digraphs.
Abstract: We present a method to derive the complete spectrum of the lift \Gamma^\alpha of a base digraph \Gamma, with voltage assignment alpha on a (finite) group G.
The method is based on assigning to $\Gamma$ a quotient-like matrix whose entries are elements of the group algebra C[G], which fully represents Gamma^{\alpha}. This allows us to derive the eigenvectors and eigenvalues of the lift in terms of those of the base digraph and the irreducible characters of G. Thus, our main theorem generalize some previous results of Lovász and Babai concerning the spectra of Cayley digraphs.
Joint work with C. Dalfó and J. Sirán.
____________________________
Date: June 29th 2017
Speaker: Mohan Prabu, British University, Hanoi (Vietnam)
Title: Product of digraphs, (super) edge-magic valences and related problems
Abstract: A (p, q)-graph G is called edge-magic if there is a bijective function f : V(G)∪E(G) → {1,2,...,p+q} such that the sum f(x)+f(xy)+f(y) for any xy in E(G) is constant. Such a function is called an edge-magic labelling of G and the constant is called the valence. An edge-magic labelling with the extra property that f (V (G)) = {1, 2, ..., p} is called super edge-magic. A graph is called perfect (super) edge-magic if all theoretical (super) edge-magic valences are possible.
In this seminar, we will present some results related to:
- the valences of (super) edge-magic labelings of crowns Cm ⊙ Kn, where m = pq, p and q are different odd primes;
- the edge-magic valences of cycles (motivated by the conjecture of Godbold and Slated which states that all cycles, or order n > 7 are perfect edge-magic).
Finally, we will discuss the super edge-magicness of some graphs of equal order and size (motivated by their applications by means of the ⊗h-product).
- the valences of (super) edge-magic labelings of crowns Cm ⊙ Kn, where m = pq, p and q are different odd primes;
- the edge-magic valences of cycles (motivated by the conjecture of Godbold and Slated which states that all cycles, or order n > 7 are perfect edge-magic).
Finally, we will discuss the super edge-magicness of some graphs of equal order and size (motivated by their applications by means of the ⊗h-product).
____________________________
Date: Thursday, June 15th 2017
Speaker: Benny Sudakov, ETH, Zurich
Title: Rainbow cycles and trees in properly edge-colored complete graphs
Abstract: A rainbow subgraph of a properly edge-colored complete graph is a subgraph all of whose edges have different colors. One reason to study such subgraphs arises from the canonical version of Ramsey's theorem, proved by Erdos and Rado. Another motivation comes from problems in design theory. In this talk we discuss several old conjectures about finding spanning rainbow cycles and trees in properly edge-colored complete graphs and present some recent progress on these problems.
Joint work with A. Pokrovskiy and in part with N. Alon
____________________________
Date: Thursday, June 15th 2017
Speaker: Dieter van Melkebeek, University of Wisconsin-Madison, USA
Title: Kernelization lower bounds from AP(3)-free sets
Abstract: Many hard computational problems contain a parameter k other than the input size n that has a large impact on the computational complexity but in practice only takes on small values. A good example is the vertex cover problem, where one seeks a subset of at most k vertices of a given n-vertex graph that hit every edge of the graph. The trivial algorithm runs in time O(n^k), but there exist algorithms that take time O(f(k)+n^c) where c is a constant and f is an arbitrary function - a running time that is typically much better than the trivial algorithm.
One way to achieve such running times is through kernelization: Reduce in time polynomial in n to an equivalent instance of size bounded by some function g of the parameter k only, and then run a brute-force algorithm on the reduced instance. In order to obtain good parameterized algorithms, the functions f and g should not behave too badly, which motivates the quest for kernels of small size g(k).
For the vertex cover problem, the best known kernelizations yield graphs with O(k^2) edges. If P=NP there trivially exist kernelizations with O(1) edges. Under a hypothesis that is considered not much stronger than P<>NP, we'll show that kernelizations with O(k^{2-epsilon}) edges do not exist for any positive constant epsilon. The proof hinges on the existence of AP(3)-free sets of high density, i.e., large subsets of {1,2,...,N} that do not contain arithmetic progressions of length 3.
Similar results hold for other NP-complete problems. For example, under the same hypothesis we can show that for any constant d>=3, d-CNF formulas cannot be sparsified in polynomial time below the trivial bound of O(n^k) bits while preserving satisfiability.
Joint work with A. Pokrovskiy and in part with N. Alon
____________________________
Date: Thursday, June 15th 2017
Speaker: Dieter van Melkebeek, University of Wisconsin-Madison, USA
Title: Kernelization lower bounds from AP(3)-free sets
Abstract: Many hard computational problems contain a parameter k other than the input size n that has a large impact on the computational complexity but in practice only takes on small values. A good example is the vertex cover problem, where one seeks a subset of at most k vertices of a given n-vertex graph that hit every edge of the graph. The trivial algorithm runs in time O(n^k), but there exist algorithms that take time O(f(k)+n^c) where c is a constant and f is an arbitrary function - a running time that is typically much better than the trivial algorithm.
One way to achieve such running times is through kernelization: Reduce in time polynomial in n to an equivalent instance of size bounded by some function g of the parameter k only, and then run a brute-force algorithm on the reduced instance. In order to obtain good parameterized algorithms, the functions f and g should not behave too badly, which motivates the quest for kernels of small size g(k).
For the vertex cover problem, the best known kernelizations yield graphs with O(k^2) edges. If P=NP there trivially exist kernelizations with O(1) edges. Under a hypothesis that is considered not much stronger than P<>NP, we'll show that kernelizations with O(k^{2-epsilon}) edges do not exist for any positive constant epsilon. The proof hinges on the existence of AP(3)-free sets of high density, i.e., large subsets of {1,2,...,N} that do not contain arithmetic progressions of length 3.
Similar results hold for other NP-complete problems. For example, under the same hypothesis we can show that for any constant d>=3, d-CNF formulas cannot be sparsified in polynomial time below the trivial bound of O(n^k) bits while preserving satisfiability.
In fact, the results can be cast more generally as (conditional) lower bounds on the communication cost in the following two-player communication protocol to decide certain languages L: Alice holds he entire input x but is polynomially bounded; Bob is computationally unbounded but does not know any part of x; their goal is to cooperatively decide whether x belongs to L at small cost, where the cost measure is the number of bits of communication from Alice to Bob. As another application, under the same hypothesis we show the optimality of the size of the known probabilistically checkable proofs (PCPs) for the satisfiability problem on d-CNF formulas.
____________________________
Date: June 6th 2017
Speaker: Robert Hancock, Univ. of Birmingham
Title: Independent sets in hypergraphs and Ramsey properties of graphs and the integers
Abstract: Many important problems in combinatorics and other related areas can be phrased in the language of independent sets in hypergraphs. Recently Balogh, Morris and Samotij, and independently Saxton and Thomason developed very general container theorems for independent sets in hypergraphs; both of which have seen numerous applications to a wide range of problems. We use the container method to prove results that correspond to problems concerning tuples of disjoint independent sets in hypergraphs.
We generalise the random Ramsey theorem of Rödl and Rucinski by providing a resilience analogue. This result also implies the random version of Turán’s theorem due to Conlon and Gowers, and Schacht. We prove a general subcase of the asymmetric random Ramsey conjecture of Kohayakawa and Kreuter. Both of these results in fact hold for uniform hypergraphs. We also strengthen the random Rado theorem of Friedgut, Rödl and Schacht by proving a resilience version of the result.
Title: Independent sets in hypergraphs and Ramsey properties of graphs and the integers
Abstract: Many important problems in combinatorics and other related areas can be phrased in the language of independent sets in hypergraphs. Recently Balogh, Morris and Samotij, and independently Saxton and Thomason developed very general container theorems for independent sets in hypergraphs; both of which have seen numerous applications to a wide range of problems. We use the container method to prove results that correspond to problems concerning tuples of disjoint independent sets in hypergraphs.
We generalise the random Ramsey theorem of Rödl and Rucinski by providing a resilience analogue. This result also implies the random version of Turán’s theorem due to Conlon and Gowers, and Schacht. We prove a general subcase of the asymmetric random Ramsey conjecture of Kohayakawa and Kreuter. Both of these results in fact hold for uniform hypergraphs. We also strengthen the random Rado theorem of Friedgut, Rödl and Schacht by proving a resilience version of the result.
____________________________
Date: June 6th 2017
Speaker: David Wood, Monash University
Title: Improper relaxations of Hadwiger’s Conjecture
Abstract: Hadwiger’s Conjecture asserts that every K_t-minor-free graph has a proper (t-1)-colouring. This talk is about improper relaxations of Hadwiger’s Conjecture. We prove that every K_t-minor-free graph is (2t-2)-colourable with monochromatic components of order at most ⌈(t-2)/2⌉. This result has no more colours and much smaller monochromatic components than all previous results in this direction. We then prove that every K_t-minor-free graph is (t-1)- colourable with monochromatic degree at most t-2. This is the best known degree bound for such a result. Both these theorems are based on a simple decomposition result of independent interest.
Improper colourings are interesting for other graph classes. For example, Archdeacon (1987) proved that graphs embeddable on a fixed surface can be 3- coloured with bounded monochromatic degree. We generalise this theorem for graphs excluding a complete bipartite graph, leading to new improper colouring results for graphs with linear crossing number, graphs with given stack- or queue-number, linklessly or knotlessly embeddable graphs, graphs with given Colin de Verdière parameter, and graphs with given thickness (with relevance to the earth-moon problem).
This is joint work with Jan van den Heuvel (arXiv:1704.06536) and Patrice Ossona de Mendez and Sang-il Oum (arXiv:1611.09060).
____________________________
Date: May 30th 2017
Speaker: Gilles Zemor, Univ. Bordeaux
Title: Unconditionally private communication through error correction
Title: Unconditionally private communication through error correction
Abstract: In the model that has become known as "Perfectly Secure Message Transmission"(PSMT), a sender Alice is connected to a receiver Bob through n parallel two-way channels. A computationally unbounded adversary Eve controls t of these channels, meaning she can acquire and alter any data that is transmitted over these channels. The sender Alice wishes to communicate a secret message to Bob privately and reliably, i.e. in such a way that Eve will not get any information about the message while Bob will be able to recover it completely.
In this talk, we focus on protocols that work in two transmission rounds for n= 2t+1. We break from previous work by following a conceptually simpler blueprint for achieving a PSMT protocol. We reduce the previously best-known communication complexity, i.e. the number of transmitted bits necessary to communicate a 1-bit secret, from O(n^3 log n) to O(n^2 log n). Our protocol also answers a question raised by Kurosawa and Suzuki and hitherto left open: their protocol reaches optimal transmission rate for a secret of size O(n^2 log n) bits, and the authors raised the problem of lowering this threshold. The present solution does this for a secret of O(n log n) bits. Additionally, we show how our protocol can be adapted to a Network Coding context.
In this talk, we focus on protocols that work in two transmission rounds for n= 2t+1. We break from previous work by following a conceptually simpler blueprint for achieving a PSMT protocol. We reduce the previously best-known communication complexity, i.e. the number of transmitted bits necessary to communicate a 1-bit secret, from O(n^3 log n) to O(n^2 log n). Our protocol also answers a question raised by Kurosawa and Suzuki and hitherto left open: their protocol reaches optimal transmission rate for a secret of size O(n^2 log n) bits, and the authors raised the problem of lowering this threshold. The present solution does this for a secret of O(n log n) bits. Additionally, we show how our protocol can be adapted to a Network Coding context.
____________________________
Date: May 30th 2017
Speaker: Wouter Cames van Batenburg, Radboud University Nijmegen
Title: Packing graphs of bounded codegree
Abstract: Two graphs G1 and G2 of order n are said to pack if there exist injective mappings of their vertex sets into 1,...,n such that the images of their edge sets are disjoint. A longstanding conjecture due to Bollobas and Eldridge and, independently, Catlin, asserts that, if (Delta(G1)+1) (Delta(G2)+1) > n, then
G1 and G2 pack. We consider the validity of this assertion under the additional assumption that G1 or G2 has bounded codegree. In particular, we prove for all t>=2 that if G1 does not contain a copy of the complete bipartite graph K_{2,t} and Delta(G1) > 17 t Delta(G2), then (Delta(G1)+1) (Delta(G2)+1) > n implies that G1 and G2 pack.
____________________________
Date: May 17th 2017
Speaker: Christoph Spiegel, UPC, Barcelona
Speaker: Christoph Spiegel, UPC, Barcelona
Title: Random Strategies are Nearly Optimal for Generalized van der Waerden Games
Abstract: We study the biased version of a strong generalization of the van der Waerden games introduced by Beck as well as the hypergraph generalization of the biased H-games previously studied by Bednarska and Luczak . In particular,we determine the threshold biases of these games up to constant factors by proving general winning criteria for Maker and Breaker based on their ideas. As in the result of Bednarska and Luczak,the random strategy for Maker is again the best known strategy.
____________________________
Date: May 10th 2017
Speaker: Piotr Zwiernik, UPF, Barcelona
Title: Cumulants and generalizations
Abstract: Under mild conditions, moments contain all the information about the underlying probability distribution. Cumulants form a convenient alternative to moments with many useful properties. Recently cumulant-like quantities proved to be useful in operator algebra and algebraic geometry. The reasons why it is relevant to talk about cumulants in a combinatorics seminar are threefold. First, the basic theory of cumulants is very combinatorial and it parallels some of the important results for set partition lattices. Second, cumulants have been used to prove asymptotic normality of certain combinatorial quantities. Finally, cumulants were central to the development of Gian-Carlo Rota’s umbral calculus. In this talk I will present some links between combinatorics and cumulants and show how their generalizations can be useful in algebraic geometry.
____________________________
Date: April 26th 2017
Speaker: Clement Requilé, UPC, Barcelona
Title: Enumeration of 4-regular planar graphs
Abstract: In this talk, we will show how to derive the exponential generating function counting labeled 4-regular planar graphs via a system of equations. In particular, this will allow us to enumerate this family. As by-product of this method, we can also access the exponential generating functions counting 3-connected simple 4-regular maps, which turns out to be algebraic, and connected 4-regular planar graphs, which is D-finite.
Title: Enumeration of 4-regular planar graphs
Abstract: In this talk, we will show how to derive the exponential generating function counting labeled 4-regular planar graphs via a system of equations. In particular, this will allow us to enumerate this family. As by-product of this method, we can also access the exponential generating functions counting 3-connected simple 4-regular maps, which turns out to be algebraic, and connected 4-regular planar graphs, which is D-finite.
This is joint work with Marc Noy and Juanjo Rué.
____________________________
Date: April 5th 2017
Speaker: Shagnik Das, Freie University Berlin
Title: Supersaturation for disjoint pairs
Abstract: Let F be a family of subsets of [n] such that all sets have size k and every pair of sets has non-empty intersection. The celebrated theorem of Erdos--Ko--Rado from 1961 says that when n \geq 2k, any such family has size at most {n-1 \choose k-1}. This classic theorem has since inspired a great number of subsequent papers, and by now much is known about intersecting families.
One tantalising line of research, however, is to investigate what lies beyond the EKR threshold. Once our families are larger than the EKR bound, they must contain disjoint pairs. The supersaturation problem, first raised by Ahlswede in 1980, is to determine which families of a given size have the fewest disjoint pairs. In this talk we shall survey the progress made since then and present some new results. We hope to inspire you to join in on the fun, and will helpfully point out some of the pitfalls that lie in wait.
Joint work with J. Balogh, W. Gan, H. Liu, M. Sharifzadeh, B. Sudakov and T. Tran.
Title: Supersaturation for disjoint pairs
Abstract: Let F be a family of subsets of [n] such that all sets have size k and every pair of sets has non-empty intersection. The celebrated theorem of Erdos--Ko--Rado from 1961 says that when n \geq 2k, any such family has size at most {n-1 \choose k-1}. This classic theorem has since inspired a great number of subsequent papers, and by now much is known about intersecting families.
One tantalising line of research, however, is to investigate what lies beyond the EKR threshold. Once our families are larger than the EKR bound, they must contain disjoint pairs. The supersaturation problem, first raised by Ahlswede in 1980, is to determine which families of a given size have the fewest disjoint pairs. In this talk we shall survey the progress made since then and present some new results. We hope to inspire you to join in on the fun, and will helpfully point out some of the pitfalls that lie in wait.
Joint work with J. Balogh, W. Gan, H. Liu, M. Sharifzadeh, B. Sudakov and T. Tran.
____________________________
Date: April 3rd 2017
Speaker: Mozhgan Pourmoradnasseri, University of Tartu, Estonia
Title: The (minimum) rank of typical fooling-set matrices
Abstract: Fooling set is known under different names in computer science and mathematics. It is usually used to provide lower bounds on some desired computational factors. In polytope theory and combinatorial optimization, the fooling set gives a lower bound on the extension complexity of a polytope and the minimum size of a linear program. In computational complexity, the logarithm of the size of a fooling set induces a lower bound on the communication complexity of a function. In graph theory, considering the matrix as the adjacency matrix of a bipartite graph, the fooling set corresponds to a cross-free matching, which provides a lower bound on the size of the biclique covering of a graph. A fooling-set matrix is a square matrix with nonzero diagonal, but at least one in every pair of diagonally opposite entries is 0. Dietzfelbinger et al. ’96 proved that the rank of such a matrix is at least \sqrt{n}, for a matrix of order n. It is known that the bound is tight (up to a multiplicative constant). Due to the diverse application of fooling set type lower bounds in deferent areas, knowing a priori upper bound on the size of the fooling set can show the usefulness of the method in advance. In this talk, the typical minimum rank of a fooling-set matrix will be discussed: For a fooling-set zero-nonzero pattern chosen at random, is the minimum rank of a matrix with that zero-nonzero pattern over a field F closer to its lower bound \sqrt{n} or to its upper bound n? We study random patterns with a given density p, and prove an \Omega(n) bound for the cases when (a) p tends to 0 quickly enough; (b) p tends to 0 slowly, and |F| = O(1); (c) p \in ]0,1] is a constant.
Title: The (minimum) rank of typical fooling-set matrices
Abstract: Fooling set is known under different names in computer science and mathematics. It is usually used to provide lower bounds on some desired computational factors. In polytope theory and combinatorial optimization, the fooling set gives a lower bound on the extension complexity of a polytope and the minimum size of a linear program. In computational complexity, the logarithm of the size of a fooling set induces a lower bound on the communication complexity of a function. In graph theory, considering the matrix as the adjacency matrix of a bipartite graph, the fooling set corresponds to a cross-free matching, which provides a lower bound on the size of the biclique covering of a graph. A fooling-set matrix is a square matrix with nonzero diagonal, but at least one in every pair of diagonally opposite entries is 0. Dietzfelbinger et al. ’96 proved that the rank of such a matrix is at least \sqrt{n}, for a matrix of order n. It is known that the bound is tight (up to a multiplicative constant). Due to the diverse application of fooling set type lower bounds in deferent areas, knowing a priori upper bound on the size of the fooling set can show the usefulness of the method in advance. In this talk, the typical minimum rank of a fooling-set matrix will be discussed: For a fooling-set zero-nonzero pattern chosen at random, is the minimum rank of a matrix with that zero-nonzero pattern over a field F closer to its lower bound \sqrt{n} or to its upper bound n? We study random patterns with a given density p, and prove an \Omega(n) bound for the cases when (a) p tends to 0 quickly enough; (b) p tends to 0 slowly, and |F| = O(1); (c) p \in ]0,1] is a constant.
____________________________
Date: February 23rd 2017
Speaker: Camino Balbuena
Title: Vertex disjoint 4-cycles in bipartite tournaments.
Abstract: Let k ≥ 2 be an integer. Bermond and Thomassen conjectured that every digraph with minimum out-degree at least 2k − 1 contains k vertex disjoint cycles. In this paper we prove that every bipartite tournament with minimum out-degree at least 2k −2 and minimum in-degree at least 1 contains k disjoint 4-cycles whenever k ≥ 3. Also we show a bipartite tournament with out-degree 2 and in-degree 1 having no two disjoint C4. Finally, we show that every bipartite tournament with minimum degree = min{+, −} at least 1.5k − 1 contains k disjoint 4-cycles.
____________________________
Date: February 16th 2017
Speaker: Miquel Àngel Fiol
Title: Complexity measures of edge-uncolorability in cubic graphs
Speaker: Miquel Àngel Fiol
Title: Complexity measures of edge-uncolorability in cubic graphs
Abstract: In this talk we survey the different complexity measures of edge-uncolorability in cubic graphs that have been defined in the literature, and also consider some new ones. We discuss their similarities and differences, and related results in the classification of non-edge-colorable graphs, mainly snarks (the case of cubic graphs). We prove that some of such measures are equivalent. Besides colorings, we comment upon flows (e.g., Tutte's 5-flow conjecture), factors (e.g., Berge's conjecture, Fulkerson's conjecture) and other structural parameters, and relate them to each other. We end by showing that, besides the objective to gain new insight into the structure of snarks, such complexity measures give partial results with respect to these important conjectures.
Joint work with G. Mazzuoccolo and E. Steffen.
____________________________
Date: February 14th 2017
Speaker: Dieter van Melkebeek, University of Wisconsin - Madison, USA
Title: Derandomizing Isolation in the Space-Bounded Setting
Abstract: Isolation is the process of singling out a solution to a problem that may have many solutions. It plays an important role in the design of efficient parallel algorithms as it ensures that the various parallel processes all work towards a single global solution rather than towards individual solutions that may not be compatible with one another. For example, the best parallel algorithms for finding perfect matchings in graphs hinge on isolation for this reason. Isolation is also an ingredient in some efficient sequential algorithms. For example, the best running times for certain NP-hard problems like finding hamiltonian paths in graphs are achieved via isolation.
All of these algorithms are randomized, and the only reason is the use of the Isolation Lemma -- that for any set system over a finite universe, a random assignment of small integer weights to the elements of the universe has a high probability of yielding a unique set of minimum weight in the system. For each of the underlying problems it is open whether deterministic algorithms of similar efficiency exist.
This talk is about the possibility of deterministic isolation in the space-bounded setting. The question is: Can one always make the accepting computation paths of nondeterministic space-bounded machines unique without changing the underlying language and without blowing up the space by more than a constant factor? Or equivalently, does there exist a deterministic logarithmic space mapping reduction from directed st-connectivity to itself that transforms positive instances into ones where there is a unique path from s to t?
I will present some recent results towards a resolution of this question, obtained jointly with Gautam Prakriya. Our approach towards a positive resolution can be viewed as derandomizing the Isolation Lemma in the context of space-bounded computation.
____________________________
Date: February 6th 2017
Speaker: Ilario Bonacina, Royal Institute of Technology, Stockholm, Sweden
Title: Total space in Resolution is at least width squared
Abstract: In this talk we cover some results on the space complexity of Resolution and in particular the new recent connection between total space and width in the title. Given a k-CNF formula F, the width is theminimal integer W such that there exists a Resolution refutation of F with clauses of at most W literals. The total space is the minimal sizeT of a memory used to write down a Resolution refutation of F, where the size of the memory is measured as the total number of literals it can contain. We show that T = \Omega((W-k)^2). This connection between total space and width relies on some basic properties of another,perhaps less known, complexity measure in Resolution: the asymmetric width.
The talk is based on a paper appeared in ICALP’16.
Title: Total space in Resolution is at least width squared
Abstract: In this talk we cover some results on the space complexity of Resolution and in particular the new recent connection between total space and width in the title. Given a k-CNF formula F, the width is theminimal integer W such that there exists a Resolution refutation of F with clauses of at most W literals. The total space is the minimal sizeT of a memory used to write down a Resolution refutation of F, where the size of the memory is measured as the total number of literals it can contain. We show that T = \Omega((W-k)^2). This connection between total space and width relies on some basic properties of another,perhaps less known, complexity measure in Resolution: the asymmetric width.
The talk is based on a paper appeared in ICALP’16.
____________________________
Date: January 30th 2017
Speaker: Jakob Nordström, Royal Institute of Technology, Stockholm, Sweden
Title: How Limited Interaction Hinders Real Communication (and What It Means for Proof and Circuit Complexity
Abstract: We obtain the first true size-space trade-offs for the cutting planes proof system, where the upper bounds hold for size and total space for derivations with constant-size coefficients, and the lower bounds apply to length and formula space (i.e., number of inequalities in memory) even for derivations with exponentially large coefficients. These are also the first trade-offs to hold uniformly for resolution, polynomial calculus and cutting planes, thus capturing the main methods of reasoning used in current state-of-the-art SAT solvers.
We prove our results by a reduction to communication lower bounds in a round-efficient version of the real communication model of [Krajicek '98], drawing on and extending techniques in [Raz and McKenzie '99] and [Goos et al. '15]. The communication lower bounds are in turn established by a reduction to trade-offs between cost and number of rounds in the game of [Dymond and Tompa '85] played on directed acyclic
graphs.
As a by-product of the techniques developed to show these proof complexity trade-off results, we also obtain an exponential separation between monotone-AC^(i-1) and monotone-AC^i, improving exponentially over the superpolynomial separation in [Raz and McKenzie '99]. That is, we give an explicit Boolean function that can be computed by monotone Boolean circuits of depth log^i n and polynomial size, but for which circuits of depth O(log^(i-1) n) require exponential size.
This is joint work with Susanna F. de Rezende and Marc Vinyals.
Title: How Limited Interaction Hinders Real Communication (and What It Means for Proof and Circuit Complexity
Abstract: We obtain the first true size-space trade-offs for the cutting planes proof system, where the upper bounds hold for size and total space for derivations with constant-size coefficients, and the lower bounds apply to length and formula space (i.e., number of inequalities in memory) even for derivations with exponentially large coefficients. These are also the first trade-offs to hold uniformly for resolution, polynomial calculus and cutting planes, thus capturing the main methods of reasoning used in current state-of-the-art SAT solvers.
We prove our results by a reduction to communication lower bounds in a round-efficient version of the real communication model of [Krajicek '98], drawing on and extending techniques in [Raz and McKenzie '99] and [Goos et al. '15]. The communication lower bounds are in turn established by a reduction to trade-offs between cost and number of rounds in the game of [Dymond and Tompa '85] played on directed acyclic
graphs.
As a by-product of the techniques developed to show these proof complexity trade-off results, we also obtain an exponential separation between monotone-AC^(i-1) and monotone-AC^i, improving exponentially over the superpolynomial separation in [Raz and McKenzie '99]. That is, we give an explicit Boolean function that can be computed by monotone Boolean circuits of depth log^i n and polynomial size, but for which circuits of depth O(log^(i-1) n) require exponential size.
This is joint work with Susanna F. de Rezende and Marc Vinyals.
____________________________
Date: December 7th 2016
Speaker: George Gottlob, University of Oxford
Title: General and Fractional Hypertree Decompositions: Hard and Easy Cases
Abstract: Hypertree decompositions, the more powerful generalized hypertree decompositions (GHDs), and the yet more general fractional hypertree decompositions (FHD) are hypergraph decomposition methods successfully used for answering conjunctive queries and for solving constraint satisfaction problems. Each hypergraph H has a width relative to each of these methods: its hypertree width hw(H), its generalized hypertree width ghw(H), and its fractional hypertree width fhw(H), respectively. While hw(H)<=k can be checked in polynomial time, the complexity of checking whether fhw(H)<=k holds for a fixed constant k was unknown. We settle this problem by proving that checking whether fhw(H)<=k is NP-complete, even for k=2 and by same construction also the problem deciding whether ghw(H)<=k is NP-complete for k>=2. Hardness was previously known for k>=3, whilst the case k=2 has remained open since 2001.
Abstract: Hypertree decompositions, the more powerful generalized hypertree decompositions (GHDs), and the yet more general fractional hypertree decompositions (FHD) are hypergraph decomposition methods successfully used for answering conjunctive queries and for solving constraint satisfaction problems. Each hypergraph H has a width relative to each of these methods: its hypertree width hw(H), its generalized hypertree width ghw(H), and its fractional hypertree width fhw(H), respectively. While hw(H)<=k can be checked in polynomial time, the complexity of checking whether fhw(H)<=k holds for a fixed constant k was unknown. We settle this problem by proving that checking whether fhw(H)<=k is NP-complete, even for k=2 and by same construction also the problem deciding whether ghw(H)<=k is NP-complete for k>=2. Hardness was previously known for k>=3, whilst the case k=2 has remained open since 2001.
Given these hardness results, we investigate meaningful restrictions, for which checking for bounded ghw is easy. We study classes of hypergraphs that enjoy the bounded edge-intersection property (BIP) and the more general bounded multi-edge intersection property (BMIP). For such classes, for each constant k, hecking whether ghw(H) <=k, and if so, computing a GHD of width k of H is tractable and actually FPT. Finally we derive some approximability results for fhw. We consider classes of hypergraphs whose fhw is bounded by a constant k and which also enjoy the BIP or MIP, or bounded VC-dimension. For each hypergraph in such a class, we are able to compute an FHD of width O(k log k) efficiently. A different restriction on classes of hypergraphs gives a linear approximation in PTIME. Hypergraphs of bounded rank are a simple example of such a class. Joint work with Wolfgang Fischl and Reingard Pichler.
____________________________
Date: November 24th 2016
Speaker: Joan Vilaltella
Title: Autograph, a simple and evolving tool for graphs / Autograph, una eina per grafs senzilla i en evolució
Abstract: There are many excellent software packages for the everyday calculation of graph properties, and other packages, also very good, for the creation of diagrams, but finding both functions in the same tool is not that easy. Autograph modestly tries to fill that void, combining the power of the NetworkX software with an edition area where graphs can be drawn as they would be drawn on a blackboard, but fostering greater interactivity, since the values of many properties are automatically updated with each modification. It is also possible to undo and redo changes, graphs can be stored and retrieved, and even different topologies can be used. We will be able to see this graph editor at work, not forgetting its possible competitors, and also to comment on which new features would be interesting for their addition in future versions.
____________________________
Date: November 23th 2016
Speaker: Valentin Féray, Institut für Mathematik, Universität Zürich
Title: Weighted dependency graphs
Abstract: The theory of dependency graphs is a powerful toolbox to prove asymptotic normality of sums of random variables. I will explain how this works, and then present a more general notion of weighted dependency graphs. Applications to random graphs, random permutations and subwords in a Markov chain will be given.
____________________________
Date: Wednesday November 16, 2016
Speaker: Michael Albert, University of Otago (New Zealand)
Title: First order logic of permutations
Abstract: Finite permutations can be thought of as models of the theory of two linear orders. This viewpoint sits well with the study of permutation patterns since, in that context, permutation classes are simply theories with universal axioms. However, it sits much less well with the algebraic view of permutations since we cannot recover the effect of the permutation as a function. We consider some cases where it is possible to reconcile the two views and answer questions such as: in which permutation classes is it possible to recognise the existence of fixed points (or more generally k-cycles) with a formula from the logic of two linear orders?
____________________________
Date: November 15th 2016
Speaker: Martin Koutecký, Department of Applied Mathematics, Charles University, Prague
Title: Voting and Bribing in Single-Exponential Time
Abstract: In social choice theory, many combinatorial problems have been addressed from the viewpoint of parameterized complexity. For many of these problems, though, either their fixed-parameter tractability is not known, or the fastest known algorithms have doubly-exponential dependence on the parameters. These shortcomings (among others) led Bredereck et al. to pose their “Nine Research Challenges in Social Choice Theory”.
Title: Voting and Bribing in Single-Exponential Time
Abstract: In social choice theory, many combinatorial problems have been addressed from the viewpoint of parameterized complexity. For many of these problems, though, either their fixed-parameter tractability is not known, or the fastest known algorithms have doubly-exponential dependence on the parameters. These shortcomings (among others) led Bredereck et al. to pose their “Nine Research Challenges in Social Choice Theory”.
In this work we provide a general approach to many fundamental voting and bribing problems in social choice theory, when parameterized by the number of candidates. Our approach shows, for the first time, fixed-parameter tractability of those problems, or provides the first algorithms with singly-exponential dependence on the parameter. Thereby, we solve “Challenge #2” by Bredereck et al., and substantially contribute towards resolving their “Challenge #1”.
In particular, we show that R-Swap Bribery is fixed-parameter tractable parameterized by the number of candidates and solvable in single-exponential time, for many voting rules R; this extends an earlier double-exponential time algorithm by Dorn and Schlotter that is restricted to the unit-cost case.
____________________________
Date: November 10th 2016
Speaker: Gabriela Araujo, Universidad Nacional Autónoma de México (UNAM)
Title: El problema de Moore en gráficas mixtas
Abstract: En esta charla abordaremos el problema de Moore en Gráficas Mixtas, el cual fue introducido por Bosàk en 1979, a partir de ese momento este problema ha sido abordado por varios autores y se han logrado distintos resultados de los cuales hablaremos en esta charla, además expondremos nuestras recientes aportaciones en este tema. Por otro lado, buscando generalizar este problema, debido a que dicho problema está relacionado de manera natural con el problema de las Jaulas, plantearemos el problema de Jaulas Mixtas y mostraremos los avances que tenemos en dicho problema.
____________________________
Date: November 3rd 2016
Speaker: Adriana Hansberg, Universidad Nacional Autónoma de México (UNAM)
Title: Subsecuencias de suma acotada en secuencias de -1’s y 1’s con suma acotada
Abstract: En esta charla, presentaré el siguiente resultado: sean $t$, $k$ y $q$ enteros tal $q\geq 0$, $0\leq t < k$ y $t \equiv k \,({\rm mod}\, 2)$ y sea $s\in [0,t+1]$ el único entero que satisface $s \equiv q + \frac{k-t-2}{2} \,({\rm mod} \, (t+2))$. Entonces, para todo entero $n$ tal que
Title: Subsecuencias de suma acotada en secuencias de -1’s y 1’s con suma acotada
Abstract: En esta charla, presentaré el siguiente resultado: sean $t$, $k$ y $q$ enteros tal $q\geq 0$, $0\leq t < k$ y $t \equiv k \,({\rm mod}\, 2)$ y sea $s\in [0,t+1]$ el único entero que satisface $s \equiv q + \frac{k-t-2}{2} \,({\rm mod} \, (t+2))$. Entonces, para todo entero $n$ tal que
\[n \ge \max\left\{k,\frac{1}{2(t+2)}k^2 + \frac{q-s}{t+2}k - \frac{t}{2} + s\right\}\]
y cualquier función $f:[n]\to \{-1,1\}$ con $|\sum_{i=1}^nf(i)| \le q$, existe un subconjunto $B \subseteq [n]$ de $k$ enteros consecutivos tal que $|\sum_{y\in B}f(y)| \le t$. Este resultado es justo para todos los parámetros implicados. Daremos también una caracterización de las secuencias extremales.
Además de este teorema, presentaremos otros resultados similares involucrando diferentes subsecuencias y descomposiciones de secuencias en ciertas subsecuencias de suma acotada.
Este es un trabajo en colaboración con Yair Caro y Amanda Montejano.
____________________________
Date: November 2nd 2016
Speaker: Arnau Padrol, Institut de Mathématiques de Jussieu, Université Pierre et Marie Curie (Paris 6)
Title: Colorful simplicial depth, Minkowski sums, and generalized Gale transforms
Abstract: The colorful simplicial depth of a collection of d+1 finite sets of points in Euclidean d-space is the number of choices of a point from each set such that the origin is contained in their convex hull. We use methods from combinatorial topology to prove a tight upper bound on the colorful simplicial depth. This implies a conjecture of Deza et al. (2006). Furthermore, we introduce colorful Gale transforms as a bridge between colorful configurations and Minkowski sums. Our colorful upper bound then yields a tight upper bound on the number of totally mixed facets of certain Minkowski sums of simplices. This resolves a conjecture of Burton (2003) in the theory of normal surfaces.
Title: Colorful simplicial depth, Minkowski sums, and generalized Gale transforms
Abstract: The colorful simplicial depth of a collection of d+1 finite sets of points in Euclidean d-space is the number of choices of a point from each set such that the origin is contained in their convex hull. We use methods from combinatorial topology to prove a tight upper bound on the colorful simplicial depth. This implies a conjecture of Deza et al. (2006). Furthermore, we introduce colorful Gale transforms as a bridge between colorful configurations and Minkowski sums. Our colorful upper bound then yields a tight upper bound on the number of totally mixed facets of certain Minkowski sums of simplices. This resolves a conjecture of Burton (2003) in the theory of normal surfaces.
This is joint work with Adiprasito, Brinkmann, Paták, Patáková and Sanyal.
____________________________
Date: September 14th 2016
Speaker: Domenico Labbate
Title: Characterizations of regular graphs with conditions on their 2-factors
Abstract: In this talk, we present existence results and partial characterizations of regular graphs having all 2–factors Hamiltonian, isomorphic or with the same parity of number of circuits. We will present several conjectures and a counterexample to one of those. Finally, we will investigate relations between some of these classes and the class of snarks with all 2-factors having circuits of odd length.
Title: Characterizations of regular graphs with conditions on their 2-factors
Abstract: In this talk, we present existence results and partial characterizations of regular graphs having all 2–factors Hamiltonian, isomorphic or with the same parity of number of circuits. We will present several conjectures and a counterexample to one of those. Finally, we will investigate relations between some of these classes and the class of snarks with all 2-factors having circuits of odd length.
____________________________
____________________________
Academic year 2015-2016
Date: June 16th 2016
Speaker: Christian Elsholtz, Graz University of Technology
Title: Hilbert cubes in arithmetic sets
Abstract: We show upper bounds on the maximal dimension d of Hilbert cubes H=a_0+{0,a_1}+ ... + {0, a_d} in several sets S of arithmetic interest such as the squares.
Abstract: We show upper bounds on the maximal dimension d of Hilbert cubes H=a_0+{0,a_1}+ ... + {0, a_d} in several sets S of arithmetic interest such as the squares.
____________________________
Date: June 2nd 2016
Speaker: Víctor Diego, Departament de Matemàtiques, UPC
Title: Distance mean-regular graphs
Abstract: We introduce the concept of distance mean-regular graph, which can be seen as a generalization of both vertex-transitive and distance-regular graphs. Let $\G$ be a graph with vertex set $V$, diameter $D$, adjacency matrix $\A$, and adjacency algebra ${\cal A}$. Then, $\G$ is {\em distance mean-regular} when, for a given $u\in V$, the averages of the intersection numbers $p_{ij}^h(u,v)=|\G_i(u)\cap \G_j(v)|$ (number of vertices at distance $i$ from $u$ and distance $j$ from $v$) computed over all vertices $v$ at a given distance $h\in \{0,1,\ldots,D\}$ from$u$, do not depend on $u$. In this work we study some properties and characterizations of these graphs. For instance, it is shown that a distance mean-regular graph is always distance degree-regular, and we give a condition for the converse to be also true. Some algebraic and spectral properties of distance mean-regular graphs are also investigated. We show that, for distance mean regular-graphs, the role of the distance matrices of distance-regular graphs is played for the so-called distance mean-regular matrices. These matrices are computed from a sequence of orthogonal polynomials evaluated at the adjacency matrix of $\G$ and, hence, they generate a subalgebra of ${\cal A}$. Some other algebras associated to distance mean-regular graphs are also characterized.
____________________________
Date: May 26th 2016
Speaker: Jack Koolen, University of Science and Technology of China
Speaker: Jack Koolen, University of Science and Technology of China
Title: Recent progress on 2-walk-regular graphs
Abstract: In this talk I will present some recent progress on 2-walk-regular graphs.
This is based on joint work with Zhi Qiao, Jongyook Park and Shao-Fei Du.
____________________________
Date: February 17th 2016
Speaker: Christoph Spiegel, Freie Universität Berlin
Title: Threshold functions for systems of equations in random sets
Abstract: We present a unified framework to deal with threshold functions for the existence of solutions to systems of linear equations in random sets. This covers the study of several fundamental combinatorial families such as k-arithmetic progressions, k-sum-free sets, B_h(g)- sequences and Hilbert cubes of dimension k.
Title: Threshold functions for systems of equations in random sets
Abstract: We present a unified framework to deal with threshold functions for the existence of solutions to systems of linear equations in random sets. This covers the study of several fundamental combinatorial families such as k-arithmetic progressions, k-sum-free sets, B_h(g)- sequences and Hilbert cubes of dimension k.
We show that there exists a threshold function for the property "A^m contains a non-trivial solution of Mx=0” where A is a random set. This threshold function depends on a parameter maximized over all subsystems, a notion previously introduced by Rödl and Rucinski. The talk will contain a formal definition of trivial solutions for any combinatorial structure, extending a previous definition by Ruzsa.
Joint work with Juanjo Rué and Ana Zumalacárregui.
____________________________
Date: December 10th 2015
Speaker: Miquel Àngel Fiol, UPC Barcelona
Title: Cospectral digraphs from locally line digraphs
Abstract: A digraph $G=(V,E)$ is a line digraph when every pair of vertices $u,v\in V$ have either equal or disjoint in-neighborhoods. When this condition only applies for vertices in a given subset, we say that $G$ is a locally line digraph. In this paper we give a new method to obtain a digraph $G'$ cospectral with a given locally line digraph $G$ with diameter $D$, where the diameter $D'$ of $G'$ is in the interval $[D-1,D+1]$.
Title: Cospectral digraphs from locally line digraphs
Abstract: A digraph $G=(V,E)$ is a line digraph when every pair of vertices $u,v\in V$ have either equal or disjoint in-neighborhoods. When this condition only applies for vertices in a given subset, we say that $G$ is a locally line digraph. In this paper we give a new method to obtain a digraph $G'$ cospectral with a given locally line digraph $G$ with diameter $D$, where the diameter $D'$ of $G'$ is in the interval $[D-1,D+1]$.
In particular, when the method is applied to De Bruijn or Kautz digraphs, we can obtain cospectral digraphs with the same algebraic properties that characterize the formers.
Joint work with Cristina Dalfó.
____________________________
Date: December 2nd 2015
Speaker: Szymon Toruńczyk, Department of CS, UPC and University of Warsaw, Poland
Title: CSPs with infinite instances
Abstract: Constraint Satisfaction Problems (CSP) are a generalization of 3-SAT, consisting of problems of the form: given an instance consisting of a set of variables, and a set of constraints on them (where each constraint is a relation from a fixed vocabulary on a fixed domain), decide whether there exists an assignment of domain values, which satisfies every constraint. Depending on the allowed set of relations, the CSP problem can have various complexities within NP. We consider CSP problems in which the instance is allowed to be infinite, but has a finite description (an interpretation) in a fixed, countable first-order structure with enough decidability properties, e.g. (N,=) or (Q,<). Then, I will specify tight complexity bounds for this problem, showing that the complexity increases exponentially when we allow infinite instances. In the upper bound, we use results from Ramsey theory and topological dynamics. In this talk, I will recall all the notions mentioned above, and sketch a proof of the upper bound.
Title: CSPs with infinite instances
Abstract: Constraint Satisfaction Problems (CSP) are a generalization of 3-SAT, consisting of problems of the form: given an instance consisting of a set of variables, and a set of constraints on them (where each constraint is a relation from a fixed vocabulary on a fixed domain), decide whether there exists an assignment of domain values, which satisfies every constraint. Depending on the allowed set of relations, the CSP problem can have various complexities within NP. We consider CSP problems in which the instance is allowed to be infinite, but has a finite description (an interpretation) in a fixed, countable first-order structure with enough decidability properties, e.g. (N,=) or (Q,<). Then, I will specify tight complexity bounds for this problem, showing that the complexity increases exponentially when we allow infinite instances. In the upper bound, we use results from Ramsey theory and topological dynamics. In this talk, I will recall all the notions mentioned above, and sketch a proof of the upper bound.
____________________________
Date: November 18th 2015
Speaker: Clément Requilé, Freie Universität Berlin
Title: Variants of Plane Diameter Completion
Abstract:Given a plane graph G and a positive integer d, the Plane Diameter Completion problem asks whether G is a spanning subgraph of a plane graph H that has diameter at most d. Plane graphs are defined as planar graphs given together with a fixed embedding on the unit-sphere.
We are interested in the complexity of this problem, and to this end examine two variants of it where the input comes with another parameter k. In the first variant, k upper bounds the total number of edges to be added and in the second, k upper bounds the number of additional edges per face. Both problems appear to be NP-complete, the first even for 3-connected graphs of face-degree at most 4 and the second even when k = 1 on 3-connected graphs of face-degree at most 5.
A traditional way to deal with difficult problems is the design of parameterized algorithms, i.e. algorithms for which the complexity is polynomial in the size of the input and at least exponential in some other parameters independent of the size. This talk will be focused on the presentation of such an algorithm, solving a generalisation of both problems, that is parameterized by both k and d and run in time O(n^3) + 2^{ 2^{O((kd)^2*log(d))} }*n.
This talk represents joint work with Petr A. Golovach and Dimitrios M. Thilikos.
____________________________
Date: November 5th 2015
Speaker: Guillem Perarnau, University of Birmingham (UK)
Title: Connectivity in bridge-addable graph classes: the McDiarmid-Steger-Welsh conjecture
Abstract: A class of graphs is bridge-addable if, given a graph G in the class, any graph obtained by adding an edge between two connected components of G is also in the class. We prove a conjecture of McDiarmid, Steger and Welsh, that says that if G_n is taken uniformly at random from a class of bridge-addable graphs on n vertices, then G_n is connected with probability at least exp(-1/2)+o(1), when n tends to infinity. This lower bound is asymptotically best possible and it is reached for the class of forests. Our proof uses a "local double counting" strategy that enables us to compare the size of two sets of combinatorial objects by solving a related multivariate optimization problem.
Title: Connectivity in bridge-addable graph classes: the McDiarmid-Steger-Welsh conjecture
Abstract: A class of graphs is bridge-addable if, given a graph G in the class, any graph obtained by adding an edge between two connected components of G is also in the class. We prove a conjecture of McDiarmid, Steger and Welsh, that says that if G_n is taken uniformly at random from a class of bridge-addable graphs on n vertices, then G_n is connected with probability at least exp(-1/2)+o(1), when n tends to infinity. This lower bound is asymptotically best possible and it is reached for the class of forests. Our proof uses a "local double counting" strategy that enables us to compare the size of two sets of combinatorial objects by solving a related multivariate optimization problem.
This is joint work with Guillaume Chapuy.
____________________________
Date: November 4th 2015
Speaker:Amanda Montejano, Instituto de Matemáticas, UNAM (Mexico)
Title: A Rainbow Ramsey Analogue of Rado's Theorem
Abstract: Given a rational matrix A, consider the homogeneous system of linear equations Ax=0. This system or the matrix is called k-regular, if for every k-coloring of the natural numbers the system has a monochromatic solution. A matrix is called regular if it is k-regular for all k. Generalizing both Schur and Van der Waerden's Theorems a celebrated result by Richard Rado characterizes regular matrices. In the context of the arithmetic anti-Ramsey Theory, which concerns the study of the existence of rainbow structures instead of monochromatic ones, we present a rainbow Ramsey version of Rado's Theorem. We also disprove two conjectures proposed in the literature. We use techniques from the Geometry of Numbers.
Title: A Rainbow Ramsey Analogue of Rado's Theorem
Abstract: Given a rational matrix A, consider the homogeneous system of linear equations Ax=0. This system or the matrix is called k-regular, if for every k-coloring of the natural numbers the system has a monochromatic solution. A matrix is called regular if it is k-regular for all k. Generalizing both Schur and Van der Waerden's Theorems a celebrated result by Richard Rado characterizes regular matrices. In the context of the arithmetic anti-Ramsey Theory, which concerns the study of the existence of rainbow structures instead of monochromatic ones, we present a rainbow Ramsey version of Rado's Theorem. We also disprove two conjectures proposed in the literature. We use techniques from the Geometry of Numbers.
____________________________
Date: October 14th 2015
Speaker: Mordecai Golin, Department of Computer Science, Hong Kong University of Science and Technology
Title: Optimal Binary Comparison Search Trees
Abstract: Constructing optimal (minimum average search time) binary search trees (BSTs) is one of the canonical early uses of dynamic programming. In 1971, Knuth described how to solve this problem in O(n^2) time, with input specifying the probability of the different successful and unsuccessful searches. While the trees constructed were binary, the comparisons used were ternary. Successful searches terminated at internal nodes and unsuccessful searches at leaves.
Abstract: Constructing optimal (minimum average search time) binary search trees (BSTs) is one of the canonical early uses of dynamic programming. In 1971, Knuth described how to solve this problem in O(n^2) time, with input specifying the probability of the different successful and unsuccessful searches. While the trees constructed were binary, the comparisons used were ternary. Successful searches terminated at internal nodes and unsuccessful searches at leaves.
By contrast, in binary comparison trees (BCSTs), internal nodes perform binary comparisons; the search branches left or right depending upon the comparison outcome and all searches terminate at leaves. Polynomial algorithms exist for solving the optimal BCST problem in special cases with input restricted to successful searches. Hu and Tucker gave an O(n log n) algorithm when all comparisons are the inequality “<”; Anderson et. al. developed an O(n^4) algorithm when both “<” and “=” comparisons are allowed.
In this talk we present the first polynomial time algorithms for solving the optimal BCST problem when unsuccessful searches are included in the input and any set of comparisons are permitted. Our running times depend upon the comparisons allowed. If equality is not allowed, our algorithm runs in O(n log n) time; if equality is allowed, O(n^4). We also demonstrate O(n) time algorithms that yield almost optimal binary comparison trees, with tree cost within constant additive factor of optimal.
This is joint work with Marek Chrobak, Ian Munro and Neal Young.
This is joint work with Marek Chrobak, Ian Munro and Neal Young.
____________________________
Date: October 1st 2015
Speaker: Ilario Bonaccina, Computer Science Department, University of Rome Sapienza, Rome, Italy
Title: Strong Size Lower Bounds in Resolution via Games
Abstract: The Strong Exponential Time Hypothesis (SETH) says that solving the SATISFIABILITY problem on formulas that are k-CNFs in n variables require running time 2^((1 - c_k) n) where c_k goes to 0 as k goes to infinity. Of course SETH is much stronger than P vs NP hence proving (or disproving) SETH seems to be out of reach at the moment. However one could ask if SETH is consistent with some particular algorithm or some class of algorithms. For example the fact that SETH holds for the DPLL algorithm could be derived from lower bounds on the size of tree-like resolution refutations. Despite the fact that exponential lower bounds on size of resolution proofs are 30 years old [Haken 85], only in 2000 Pudlak and Impagliazzo proved lower bounds for tree-like resolution strong enough to support SETH. Recently Beck and Impagliazzo (2013) proved that SETH is consistent with regular resolution. Informally this tell us that any SAT solver that could be formalised in regular resolution cannot disprove SETH. At the moment is not known whether SETH is consistent with full resolution, that is without constraints. Here we present a different/simpler proof of the lower bound for regular resolution by Beck and Impagliazzo. Our proof pass trough game characterisations of width and size of resolution proofs and a multiplication of strategies in those games. This technique actually works for some proof systems between regular resolution and resolution. In such systems the refutations are allowed to have some (fairly small) amount of irregularity, that is some (fairly small) number of variables is allowed to be resolved multiple times along paths of the refutations.
Title: Strong Size Lower Bounds in Resolution via Games
Abstract: The Strong Exponential Time Hypothesis (SETH) says that solving the SATISFIABILITY problem on formulas that are k-CNFs in n variables require running time 2^((1 - c_k) n) where c_k goes to 0 as k goes to infinity. Of course SETH is much stronger than P vs NP hence proving (or disproving) SETH seems to be out of reach at the moment. However one could ask if SETH is consistent with some particular algorithm or some class of algorithms. For example the fact that SETH holds for the DPLL algorithm could be derived from lower bounds on the size of tree-like resolution refutations. Despite the fact that exponential lower bounds on size of resolution proofs are 30 years old [Haken 85], only in 2000 Pudlak and Impagliazzo proved lower bounds for tree-like resolution strong enough to support SETH. Recently Beck and Impagliazzo (2013) proved that SETH is consistent with regular resolution. Informally this tell us that any SAT solver that could be formalised in regular resolution cannot disprove SETH. At the moment is not known whether SETH is consistent with full resolution, that is without constraints. Here we present a different/simpler proof of the lower bound for regular resolution by Beck and Impagliazzo. Our proof pass trough game characterisations of width and size of resolution proofs and a multiplication of strategies in those games. This technique actually works for some proof systems between regular resolution and resolution. In such systems the refutations are allowed to have some (fairly small) amount of irregularity, that is some (fairly small) number of variables is allowed to be resolved multiple times along paths of the refutations.
Joint work with N. Talebanfard (Tokyo Institute of Technology) IPEC 2015.
____________________________
Date: September 17th 2015
Speaker: Bruce Reed, School of Computer Science, McGill Univ. (Montreal)
Title: Random Models Of 21st Century Networks And Their Connectivity Structure
Abstract: The traditional Erdos-Renyi model of a random network is of little use in modeling the type of complex networks which modern researchers study. It postulates that each node has the same likelihood of being attached to every other node. However, in, e.g. the web, certain authoritative pages will have many more links entering them. A 1995 paper of Molloy and Reed, cited over 1500 times, sets out some conditions guaranteeing the existence of a giant component in a network with a specified degree sequence. This work has attracted such a great deal of attention because it can be applied to random models of a wide range of complicated 21st century networks such as the web or biological networks operating at a sub-molecular level. A heuristic argument suggests that a giant component will exist provided the sum of the squares of the degrees of the nodes of the network is at least twice the sum of the degrees. Molloy and Reed proved that this is indeed true subject to certain technical conditions. Many authors, have obtained related results by specifying different technical conditions, or by tying down the size of the giant component.
Since the interest in this result is its wide applicability, it is natural to try and prove it under as few assumptions as possible. Recently, Joos, Perarnau-Llobet, Rautenbach, and Reed proved the result under essentially no conditions.
I will present, in an accessible way, a variety of complex networks and their random models to which the Molloy-Reed result has been applied. I will then sketch the proof of our result and how it differs from the proof of the Molloy-Reed result.
____________________________
____________________________
Academic year 2014-2015
Date: July 16th 2015
Speaker: Edita Máčajová, Comenius University, Bratislava, Slovakia
Speaker: Edita Máčajová, Comenius University, Bratislava, Slovakia
Title: Large cycles and matchings in cubic graphs
Abstract: The Cycle Double Cover Conjecture claims that every bridgeless graph contains a family of cycles that together cover each edge exactly twice. This conjecture is equivalent to its restriction to the family of cubic graphs. The Fulkerson Conjecture asserts that any bridgeless cubic graphs contains a family of six perfect matchings that together cover every edge exactly twice.
We discuss old and new results and research directions on the way towards these long-standing conjectures. Our talk will include results concerning extensions, bipartizing matchings, Fano colourings, and others.
We discuss old and new results and research directions on the way towards these long-standing conjectures. Our talk will include results concerning extensions, bipartizing matchings, Fano colourings, and others.
____________________________
Date: May 21st 2015
Speaker: Dieter Mitsche, Univ. Nice
Title: On the bondage number of random graphs
Abstract: A dominating set of a graph is a subset D of its vertices such that every vertex not in D is adjacent to at least one member of D. The domination number of a graph G is the number of vertices in a smallest dominating set of G. The bondage number of a nonempty graph G is the size of a smallest set of edges whose removal from G results in a graph with domination number greater than the domination number of G. We study the bondage number of binomial random graph G(n,p). We obtain a lower bound that matches the order of the trivial upper bound. As a side product, we give a one-point concentration result for the domination number of G(n,p) under certain restrictions.
Joint work with X. Pérez-Giménez and P. Pralat.
____________________________
Date: May 7th 2015
Speaker: Ignasi Sau, CNRS-LIRMM Montpellier
Date: May 7th 2015
Speaker: Ignasi Sau, CNRS-LIRMM Montpellier
Title: The List Allocation problem and some of its applications in parameterized algorithms
Abstract: In this talk we will sketch the main ideas of a Fixed-Parameter Tractable (FPT) algorithm for a quite general cut problem on general graphs, which we call List Allocation. Our algorithm strongly uses the "edge contraction" technique introduced by Chitnis et al. [2012]. Besides being a natural cut problem by itself, the relevance of List Allocation is best demonstrated by the following algorithms, which we obtain by reducing in FPT time each corresponding problem to particular cases of List Allocation:
(1) An FPT algorithm for a generalization of Digraph Homomorphism, which we call Arc-Bounded List Digraph Homomorphism.
(2) An FPT algorithm for a graph partitioning problem, called Min-Max Graph Partitioning.
(3) An FPT 2-approximation algorithm for computing the "tree-cut width" of a graph, a graph invariant recently introduced by Wollan [2013] and that has proved of fundamental importance in the structure of graphs not admitting a fixed graph as an immersion.
If time permits, we will partially discuss the above applications of our main algorithm. No previous knowledge of Paramerized Complexity will be assumed in the talk.
(2) An FPT algorithm for a graph partitioning problem, called Min-Max Graph Partitioning.
(3) An FPT 2-approximation algorithm for computing the "tree-cut width" of a graph, a graph invariant recently introduced by Wollan [2013] and that has proved of fundamental importance in the structure of graphs not admitting a fixed graph as an immersion.
If time permits, we will partially discuss the above applications of our main algorithm. No previous knowledge of Paramerized Complexity will be assumed in the talk.
This is joint work with EunJung Kim, Sang-Il Oum, Christophe Paul, and Dimitrios M. Thilikos.
____________________________
Date: April 30th 2015
Speaker: Joaquim Bruna, UAB-CRM Barcelona
Title: Un exemple de transferència en matemàtiques: què tenen a veure els encoders òptics amb els conjunts de Sidon, els Golomb rulers i l'autocorrelació discreta?
Abstract: S'explicarà com la solució a un problema de tipus industrial proposat per una empresa al Servei de Consultoria del CRM es relaciona i serveix de nexe entre diferents camps de les matemàtiques, alguns d'ells molt treballats a nivell teòric. Això passa sovint en transferència, però en aquest cas- i això és més rar- s'explicarà com determinats teoremes de la teoria additiva de nombres mostren que la solució aportada pel CRM és òptima.
____________________________
Date: April 23rd 2015
Date: April 23rd 2015
Speaker: Juraj Hromkovic, ETH Zurich
Title: Towards a better understanding of the hardness of NP-hard optimization problems
Abstract: We present the concept of the stability of approximation. The basic idea is to partition the set of the instances of a given hard optimization problem into infinitely many infinite classes with respect to the quality of efficiently achievable approximation. This approach enables to recognize classes of easy instances as well as to fix which kind of instances is really hard and whether the hard instances are more or few exotic or typical. In this way one revise the classification of the hardness of discrete optimization problems.
____________________________
Date: March 19th 2015
Speaker: Juanjo Rué, Freie Universitat Berlin
Title: Arithmetic Removal Lemmas and Independent sets in hypergraphs
Abstract: In the last years, several authors have studied sparse and random analogues of a wide variety of results in extremal combinatorics. Very recently, due to the work of Balogh, Morris, and Samotij, and the work of Saxton and Thomasson on the structure of independent sets on hypergraphs, several of these questions have been addressed in a new framework by using the so-called containers in hypergraphs.
In this talk I will present how to use this technology together with arithmetic removal lemmas due to Serra, Vena and Kral in the context of arithmetic combinatorics. We will show how to get sparse (and random) analogues of well-known additive combinatorial results even in the non-abelian situation.
This talk is based on a work in progress joint with Oriol Serra and Lluís Vena.
____________________________
Date: March 5th 2015
Speaker: Elisabet Burjons, UPC Barcelona
Date: March 5th 2015
Speaker: Elisabet Burjons, UPC Barcelona
Title: On-line graph coloring with random adversary
Abstract: We introduce the concept of on-line algorithms under different models and assumptions, and in particular we consider the problem of on-line graph coloring. We show a new model consisting of infinite advice and random adversary and show upper and lower bounds for the expected competitive ratio in terms of the number of random bits the adversary accesses.
This is joint work with Juraj Hromkovič, Xavier Muñoz and Walter Unger.
____________________________
Date: February 19th 2015
Speaker: Jaroslav Nešetřil, IUUK MFF, Charles University Prague
Title: Sparsity and fast algorithms for combinatorial problems
Abstract: Combinatorial problems model many important situations from both theoretical and applied computer science. To find broad classes of problems which can be effectively solved is of prime importance which leads to several popular dichotomies.
In the lecture we survey the recent actual development from the point of view sparse vs dense dichotomy.
(Joint work with P. Ossona de Mendez -Paris and Prague.)
In the lecture we survey the recent actual development from the point of view sparse vs dense dichotomy.
(Joint work with P. Ossona de Mendez -Paris and Prague.)
____________________________
Date: February 19th 2015
Speaker: Jarek Grytczuk, Jagiellonian University in Krakow
Speaker: Jarek Grytczuk, Jagiellonian University in Krakow
Title: Fanciful variations on non-repetitiveness
Abstract: A repetition is a finite sequence whose first half looks exactly the same as the second half. For instance, aa, abab, abcabc, abacabac are repetitions. A sequence is nonrepetitive if it does not contain any repetitions (as subsequences of consecutive terms). In 1906 Thue proved that there exist arbitrarily long nonrepetitive sequences built of only three symbols. This result initiated lots of research leading to deep results, important applications, and interesting generalizations in different areas of mathematics and computer science. In the talk I will present some problems inspired by the theorem of Thue for various combinatorial structures. Here is a new one for example: suppose that we are given a finite set of lines in the plane and we want to color all intersection points of these lines so that there is no repetition on any line. How many colors are needed? It can be proved that 405 colors suffice, but it does not seem optimal.
____________________________
Date: February 19th 2015
Speaker: Aida Abiad, Tilburg University, The Netherlands
Speaker: Aida Abiad, Tilburg University, The Netherlands
Title: Switched symplectic graphs and their 2-ranks
Abstract: We apply Godsil-McKay switching to the symplectic graphs over F_2 with at least 63 vertices and prove that the 2-rank of (the adjacency matrix of) the graph increases after switching. This shows that the switched graph is a new strongly regular graph with the same parameters as the symplectic graph over F_2 but different 2-rank.
For the symplectic graph on 63 vertices we investigate repeated switching by computer and find many new strongly regular graphs with the same parameters but different 2-ranks.
By using these results and a recursive construction method for the symplectic graph from Hadamard matrices, we also obtain several graphs with the same parameters as the symplectic graphs over F_2, but different 2-ranks.
This is joint work with Willem Haemers.
For the symplectic graph on 63 vertices we investigate repeated switching by computer and find many new strongly regular graphs with the same parameters but different 2-ranks.
By using these results and a recursive construction method for the symplectic graph from Hadamard matrices, we also obtain several graphs with the same parameters as the symplectic graphs over F_2, but different 2-ranks.
This is joint work with Willem Haemers.
____________________________
Date: November 20th 2014
Date: November 20th 2014
Speaker: Simeon Ball, UPC Barcelona
Title: Applications of the polynomial method in combinatorial geometry to Kakeya and Bourgain sets
Abstract: In recent years significant advances have been made in the application of algebraic methods to finite geometrical objects, see the recent survey by Tao [1]. Whether these objects are in real, finite or complex space, the finiteness of the object allows for some combinatorial methods to be used. Combining these with algebraic methods, most notably from algebraic geometry, one can hope to obtain theorems concerning the geometrical object under consideration.
In this talk I will consider Kakeya sets and Bourgain sets.
Let F be a field and let AG_k(F) denote the k-dimensional affine space over F. Let F_q denote the finite field with q elements.
A Kakeya set in AG_n(F) is a set L of lines with the property that L contains no two lines with the same direction. I will explain an iterative geometric construction of Kakeya sets in AG_n(F) starting from a Kakeya set in AG_2(F). I will say something about Dvir's proof (from [2]) that if L is a Kakeya set in AG_n(F) which contains a line in every direction then there is a constant c=c(n) such that if S is the set of points incident with some line of L then |S|>cq^n.
A Bourgain set in AG_n(F) is a set L of lines with the property that a plane contains few lines of L. Amongst other things I will sketch Guth and Katz's proof [3] that if L is a set of N^2 lines in AG_3(R), with at most N contained in any plane, and S is a set of points with the property that every line of L is incident with at least N points of S then there is a constant c such that |S|>cN^3.
Furthermore, I will talk about Ellenberg and Hablicsek's article [2] on the finite analogue of this in which L is a set of aq^2 lines in AG_3(F_q) with at most bq lines in a plane, for some constant b. They prove that if q is prime then there is a constant c=c(a,b) such that if S is the set of points incident with some line of L then |S|>cq^3. This does not hold true over non-prime finite fields and we shall also consider this finite non-prime case. I will also detail some results about Bourgain sets in higher dimensions.
[1] Zeev Dvir, On the size of Kakeya sets in finite fields, arXiv:0803.2336v3.
[2] Jordan S. Ellenberg and Márton Hablicsek, An incidence conjecture of Bourgain over fields of positive characteristic, arXiv:1311.1479v1.
[3] Larry Guth and Nets Hawk Katz, Algebraic methods in discrete analogs of the Kakeya problem, Adv. Math., 225 (2010), 2828--2839.
[4] Terence Tao, Algebraic combinatorial geometry: the polynomial method in arithmetic combinatorics, incidence combinatorics, and number theory, arXiv:1310.6482v5.
In this talk I will consider Kakeya sets and Bourgain sets.
Let F be a field and let AG_k(F) denote the k-dimensional affine space over F. Let F_q denote the finite field with q elements.
A Kakeya set in AG_n(F) is a set L of lines with the property that L contains no two lines with the same direction. I will explain an iterative geometric construction of Kakeya sets in AG_n(F) starting from a Kakeya set in AG_2(F). I will say something about Dvir's proof (from [2]) that if L is a Kakeya set in AG_n(F) which contains a line in every direction then there is a constant c=c(n) such that if S is the set of points incident with some line of L then |S|>cq^n.
A Bourgain set in AG_n(F) is a set L of lines with the property that a plane contains few lines of L. Amongst other things I will sketch Guth and Katz's proof [3] that if L is a set of N^2 lines in AG_3(R), with at most N contained in any plane, and S is a set of points with the property that every line of L is incident with at least N points of S then there is a constant c such that |S|>cN^3.
Furthermore, I will talk about Ellenberg and Hablicsek's article [2] on the finite analogue of this in which L is a set of aq^2 lines in AG_3(F_q) with at most bq lines in a plane, for some constant b. They prove that if q is prime then there is a constant c=c(a,b) such that if S is the set of points incident with some line of L then |S|>cq^3. This does not hold true over non-prime finite fields and we shall also consider this finite non-prime case. I will also detail some results about Bourgain sets in higher dimensions.
[1] Zeev Dvir, On the size of Kakeya sets in finite fields, arXiv:0803.2336v3.
[2] Jordan S. Ellenberg and Márton Hablicsek, An incidence conjecture of Bourgain over fields of positive characteristic, arXiv:1311.1479v1.
[3] Larry Guth and Nets Hawk Katz, Algebraic methods in discrete analogs of the Kakeya problem, Adv. Math., 225 (2010), 2828--2839.
[4] Terence Tao, Algebraic combinatorial geometry: the polynomial method in arithmetic combinatorics, incidence combinatorics, and number theory, arXiv:1310.6482v5.
____________________________
Date: October 30th, 2014
Speaker: Klara Stokes, University of Skövde
Date: October 30th, 2014
Speaker: Klara Stokes, University of Skövde
Title: Pentagonal maps of Moore graphs and geometric pentagonal geometries
Abstract: A map is a drawing of a graph on a Riemann surface such that the complement of the drawing is the disjoint union of finitely many topological discs called faces. It will be explained how to construct geometric point-circle configurations embedded on Riemann surfaces from uniform maps. In particular, geometric realizations of all pentagonal geometries with k lines through each point and either k or k-1 points on each line can be obtained in this way. All these pentagonal geometries come from Moore graphs. Therefore this work involves a study of maps of Moore graphs. In particular we give the minimum genus of the Hoffman-Singleton graph.
____________________________
Date: October 23rd 2014
Speaker: Francesc Aguiló, UPC Barcelona
Title: Some Structural Properties of optimal diameter 2-Cayley digraphs on finite abelian groups
Abstract: Given a Cayley digraph G of degree two on a finite Abelian group, we study optimal structural properties related with the diameter. We call such a digraphs 2-Cayley digraphs. An expansion of G is a 2-Cayley digraph G' with the same generating set, that contains an isomorphic copy of G. A contraction of G is a 2-Cayley digraph G'' contained in G. Optimal digraphs that attain the diameter lower bound are called tight digraphs.
In this work we define two processes for obtaining contractions and expansions of 2-Cayley digraphs. These definitions are well suited from the metrical point of view. In particular, a contraction of an optimal diameter digraph has also optimal diameter. This is not true for expansions. Tight expansions from tight digraphs are characterized. Tight 2-Cayley digraphs having infinite tight expansions are also analized.
Joint work with A. Miralles and M. Zaragozá.
____________________________
Date: October 16th 2014Speaker: Miquel Àngel Fiol, UPC Barcelona
Title: Distance-regular graphs where the distance-d graph has fewer distinct eigenvalues
Abstract: Let the Kneser graph K of a distance-regular graph Γ be the graph on the same vertex set as Γ, where two vertices are adjacent when they have maximal distance in Γ. We study the situation where the Bose-Mesner algebra of Γ is not generated by the adjacency matrix of K. In particular, we obtain strong results in the so-called 'half-antipodal' case.
(joint work with A.E. Brouwer)
(joint work with A.E. Brouwer)
____________________________
Date: October 9th 2014
Speaker: Felix Lazebnik, University of Delaware
Title: On Graphs Defined by Some Systems of Equations
Abstract: In this talk I will present a simple method for constructing infinite families of graphs defined by a class of systems of equations over commutative rings. The graphs in all such families possess some general properties including regularity or bi-regularity, existence of special vertex colorings, and existence of covering maps between every two members of the same family (hence, embedded spectra). Another general property is that nearly every graph constructed in this manner edge-decomposes either the complete, or complete bipartite, graph which it spans.
In many instances, specializations of these constructions have proved useful in various graph theory problems, but especially in many extremal problems which deal with cycles in graphs. I will explain motivations for these constructions, survey both old and new related results, applications, and state open questions.
In many instances, specializations of these constructions have proved useful in various graph theory problems, but especially in many extremal problems which deal with cycles in graphs. I will explain motivations for these constructions, survey both old and new related results, applications, and state open questions.
____________________________
Date: October 2nd 2014
Speaker: José Aliste-Prieto, Universidad Andrés Bello, Santiago de Chile
Title: Recognizing caterpillars by U-polynomials
Abstract: En este trabajo con J. Zamora, estudiamos como reconocer grafos tipo orugas a partir de los U-polinomios. Usando su estructura lineal, relacionamos una versión restringida del U-polinomio con una función de Schur naturalmente asociada con composiciones de enteros. Luego usamos la clasificación de equivalencias de dichas funciones de Schur para mostrar que dos orugas tendrán el mismo U-polinomio si y solo si son isomorfas.
Share: