Seminar 2013-2014
Sessions and Abstracts
Seminar sessions and other activities
Thursday July 17, 2014, 12h
C3-Room 005, Campus Nord, UPC
Mirka Miller and Joe Ryan (University of Newcastle, Australia)
Some Developments in Sum Graph Labelling
Abstract:
Sum graph labelling was defined by Harary in 1989. It is a labelling of vertices by unique positive integers in such a way that there is an edge between vertices labeled u and v if and only if u+v is a label of another vertex in the graph.
In this talk we will give an overview of the known results in sum graph labelling as well as the more recent developments in the so-called exclusive sum graph labelling.
The talk will finish with several open problems.
Sum graph labelling was defined by Harary in 1989. It is a labelling of vertices by unique positive integers in such a way that there is an edge between vertices labeled u and v if and only if u+v is a label of another vertex in the graph.
In this talk we will give an overview of the known results in sum graph labelling as well as the more recent developments in the so-called exclusive sum graph labelling.
The talk will finish with several open problems.
Joint ALAMA - GAMM/ANLA'2014
Facultat de Matemàtiques i Estadística (FME), July 14-16, 2014
www.cimne.com/websasp/ALAMA-GAMM/es/frontal/default.asp
JMDA 2014
IX Jornadas de Matemática Discreta y Algorítmica
Tarragona, July 7-9, 2014.
http://deim.urv.cat/~discrete-math/JMDA2014/
Thursday July 3, 2014, 12h
C3-Room 005, Campus Nord, UPC
José Ignacio Royo (Universitat del País Vasc)
José Ignacio Royo (Universitat del País Vasc)
Abelian and nonabelian numbers via 3D origami
Abstract:
It is well known that the description of the origami folding operations via the Huzita-Justin axioms leads to the set of points constructible with origami, which is the smallest subfield O of the complex plane which is closed under square roots, cubic roots and complex conjugation.
Those axioms form a complete set of axioms in some sense, but if we assume more moves axiomatically, the scope of the constructible points can be extended. For example, if alignments involving arbitrarily many simultaneous folds at the same time are permitted, it has been shown by Alperin and Lang that Lill’s method allows one to construct any real algebraic number.
In this talk we intend to push forward the arithmetic limits of O by introducing some manoeuvres which involve the use of the third dimension, that is, allowing the paper not to remain flat after being folded, but in such a way that actually determines new points. The moves we propose are easy to perform physically, and consist in a simple usage of a flat surface, say the table, and the rigidity properties of polyhedra. With those moves, we show that it is easy to obtain all the Abelian numbers, that is, the algebraic numbers whose Galois group is Abelian, and some other non-Abelian numbers, too. We discuss the formalization and axiomatization of those 3D manoeuvres and explore the limits of what can be achieved with those constructions, posing some open questions for further research.
Joint work with Eulàlia Tramuns.
It is well known that the description of the origami folding operations via the Huzita-Justin axioms leads to the set of points constructible with origami, which is the smallest subfield O of the complex plane which is closed under square roots, cubic roots and complex conjugation.
Those axioms form a complete set of axioms in some sense, but if we assume more moves axiomatically, the scope of the constructible points can be extended. For example, if alignments involving arbitrarily many simultaneous folds at the same time are permitted, it has been shown by Alperin and Lang that Lill’s method allows one to construct any real algebraic number.
In this talk we intend to push forward the arithmetic limits of O by introducing some manoeuvres which involve the use of the third dimension, that is, allowing the paper not to remain flat after being folded, but in such a way that actually determines new points. The moves we propose are easy to perform physically, and consist in a simple usage of a flat surface, say the table, and the rigidity properties of polyhedra. With those moves, we show that it is easy to obtain all the Abelian numbers, that is, the algebraic numbers whose Galois group is Abelian, and some other non-Abelian numbers, too. We discuss the formalization and axiomatization of those 3D manoeuvres and explore the limits of what can be achieved with those constructions, posing some open questions for further research.
Joint work with Eulàlia Tramuns.
Thursday June 26, 2014, 12h
C3-Room 005, Campus Nord, UPC
Iñaki Pelayo (UPC Barcelona)
Quasiperfect Dominations in Graphs
Abstract:
Given a graph G, a set D of vertices is a dominating set of G if every vertex not in D is adjacent to at least one vertex of D. The domination number \gamma(G) is the minimum cardinality of a dominating set of G.
If moreover, every vertex not in D is adjacent to exactly one vertex of D, then D is called a perfect dominating set of G. The perfect domination number $\gamma_ {\stackrel{}{11}}(G)$ is the minimum cardinality of a perfect dominating set of G. For every integer k>0, a dominating set D is called a k-quasiperfect dominating set if every vertex not in D is adjacent to at most k vertices of D. The k-quasiperfect domination number $\gamma_ {\stackrel{}{1k}}(G)$ is the minimum cardinality of a k-quasiperfect dominating set of G.
Certainly, 1-quasiperfect dominating sets and \Delta-quasiperfect dominating sets are precisely the perfect dominating sets and dominating sets, respectively, where \Delta stands for the maximum degree of the graph. It is also clear that, if G is a graph of order n and maximum degree \Delta, then: $n \ge \gamma_ {\stackrel{}{11}}(G) \ge \gamma_ {\stackrel{}{12}}(G)\ge \ldots \ge \gamma_ {\stackrel{}{1\Delta}}(G)=\ gamma(G)$.
In this talk, we present both the state of the art and our main contributions to the study of this decreasing chain when restricting ourselves to the following graph families: graphs with maximum degree either \Delta >= n-3 or \Delta <= 3, cographs, claw-free graphs, trees, Cartesian product graphs and strong product graphs.
(Joint work with José Cáceres, Carmen Hernando, Mercè Mora and Mari Luz Puertas.)
Thursday June 19, 2014, 11h
Sala d'Actes FME
PhD defense
Advisors: Ángeles Carmona and Andrés Encinas
PhD defense
El problema invers en xarxes finites
Cristina ArauzAdvisors: Ángeles Carmona and Andrés Encinas
Wednesday June 18, 2014, 12h
C3-Room 005, Campus Nord, UPCRinovia Simantujak (ITB Bandung)
How to uniquely determine your location in a graph?
A metric dimension problem
Abstract:
The metric dimension problem was first introduced in 1975 by Slater [4], and independently by Harary and Melter [3] in 1976; however the problem for hypercube was studied (and solved asymptotically) much earlier in 1963 by Erdös and Rényi [2]. A set of vertices S resolves a graph G if every vertex is uniquely determined by its vector of distances to the vertices in S. The metric dimension of G is the minimum cardinality of a resolving set of G. An analog problem for directed graphs was then considered by Chartrand, Raines and Zhang [1] in 2000.
In this talk I will present a short historical account, known techniques, recent results, and open problems in the area of metric dimension for undirected and directed graphs.
The metric dimension problem was first introduced in 1975 by Slater [4], and independently by Harary and Melter [3] in 1976; however the problem for hypercube was studied (and solved asymptotically) much earlier in 1963 by Erdös and Rényi [2]. A set of vertices S resolves a graph G if every vertex is uniquely determined by its vector of distances to the vertices in S. The metric dimension of G is the minimum cardinality of a resolving set of G. An analog problem for directed graphs was then considered by Chartrand, Raines and Zhang [1] in 2000.
In this talk I will present a short historical account, known techniques, recent results, and open problems in the area of metric dimension for undirected and directed graphs.
References:
[1] G. Chartrand, M. Raines, P. Zhang, The Directed Distance Dimension of Oriented Graphs, Math. Bohemica 125 (2000) 155-168.
[2] P. Erdös and A. Rényi, On two problems of information theory, Magyar Tud. Akad. Mat. Kutat Int. Kzl 8 (1963), 229-243.
[3] F. Harary, and R.A. Melter, On the metric dimension of a graph, Ars Combin. 2 (1976), 191-195.
[4] P.J. Slater, Leaves of trees, Congr. Numer. 14 (1975) 549-559.
Click here to see or download the abstract in PDF.
Thursday May 15, 2014, 12h
C3-Room 005, Campus Nord, UPC
Miquel Àngel Fiol (UPC Barcelona)On the Spectral Excess Theorem
Tuesday May 13, 2014, 12h
C3-Room 005, Campus Nord, UPC
Willem Haemers (Tilburg Univ.)
An Interlacing Approach for Bounding the Sum of Laplacian Eigenvalues of Graphs
Thursday May 8, 2014, 12h
C3-Room 005, Campus Nord, UPCWillem Haemers (Tilburg Univ.)
Graphs with maximal energy
Click here to see or download the presentation slides.
Wednesday May 7, 2014, 12h
C3-Room 005, Campus Nord, UPC
Nuno B. Freitas (Bayreuth University)
Nuno B. Freitas (Bayreuth University)
An asymptotic Fermat Last Theorem for totally real fields
Abstract:
Jarvis and Meekin showed that the strategy leading to the proof of Fermat's last theorem generalizes to proving that the classical Fermat equation x^p + y^p = z^p has no non-trivial solutions over Q(\sqrt{2}). Two of the major obstacles to extending this result to other number fields are the modularity of the Frey curves and the existence of newforms in the spaces obtained after level lowering.
In this talk, we will discuss how recent modularity theorems, along with applying level lowering twice, allow us to circumvent the aforementioned obstacles. In particular, we will describe conditions on a totally real field K that, when satisfied, the asymptotic FLT holds. That is, there is a constant B_K (depending only on K) such that, for primes p > B_K, the equation x^p + y^p = z^p only admits solutions (a,b,c) satisfying abc=0. Moreover, we will also see that the conditions are satisfied for most real quadratic fields.
Jarvis and Meekin showed that the strategy leading to the proof of Fermat's last theorem generalizes to proving that the classical Fermat equation x^p + y^p = z^p has no non-trivial solutions over Q(\sqrt{2}). Two of the major obstacles to extending this result to other number fields are the modularity of the Frey curves and the existence of newforms in the spaces obtained after level lowering.
In this talk, we will discuss how recent modularity theorems, along with applying level lowering twice, allow us to circumvent the aforementioned obstacles. In particular, we will describe conditions on a totally real field K that, when satisfied, the asymptotic FLT holds. That is, there is a constant B_K (depending only on K) such that, for primes p > B_K, the equation x^p + y^p = z^p only admits solutions (a,b,c) satisfying abc=0. Moreover, we will also see that the conditions are satisfied for most real quadratic fields.
****Special talk****
Thursday April 10, 2014, 15h30
Department of Information and Communication Technologies
Universitat Pompeu Fabra
C/ Roc Boronat, 138
08018 Barcelona, Spain
Room 52.321
Mehdi Molkaraie (University of Waterloo)
Partition Function of the Ising Model via Factor Graph Duality
Abstract:
The partition function of a factor graph and the partition function of the dual factor graph are related to each other by the normal factor graph duality theorem. We apply this result to the classical problem of computing the partition function of the Ising model to show that, at low temperature, Monte Carlo methods are more efficient on the dual graph than on the original graph.
We will also discuss applications to the q-state Potts model.
http://arxiv.org/abs/1307.3645
http://arxiv.org/abs/1401.4912
Thursday April 10, 2014, 12h
C3-Room 005, Campus Nord, UPC
Sonja Riedel (Universität Bremen)Combinatorial models of toric arrangements
Abstract:
A toric arrangement is a finite family A of level sets of characters on the torus (C^*)^n or S_1^n. Recent work of De Concini and Procesi generated new interest in combinatorial invariants of the topology of the complement of A.
In the case of so-called 'complexified' toric arrangements, the induced stratification of the compact torus S_1^n determines the homotopy type of the complement. To establish in greater generality the link between the combinatorics of these face structures and the topology of A we will use the techniques of matroid theory. Starting from the theory of semimatroids and oriented matroids, we develop a toric oriented matroid with the goal to characterize the face structure of the stratification.
The talk will include an introduction to toric arrangements and the necessary background in matroid theory.
A toric arrangement is a finite family A of level sets of characters on the torus (C^*)^n or S_1^n. Recent work of De Concini and Procesi generated new interest in combinatorial invariants of the topology of the complement of A.
In the case of so-called 'complexified' toric arrangements, the induced stratification of the compact torus S_1^n determines the homotopy type of the complement. To establish in greater generality the link between the combinatorics of these face structures and the topology of A we will use the techniques of matroid theory. Starting from the theory of semimatroids and oriented matroids, we develop a toric oriented matroid with the goal to characterize the face structure of the stratification.
The talk will include an introduction to toric arrangements and the necessary background in matroid theory.
**Special talk
Friday April 4, 2014, 12h
C1-001, Campus Nord UPC
Charles Johnson (William and Mary College, Virginia)
Hollow Symmetric Nonnegative Matrices
Abstract:
An n-by-n matrix is "hollow" if all its diagonal entries are 0. We study the eigenvalue distribution of hollow symmetric nonnegative (HSN) matrices. In the process, some very unusual combinatorial structure is uncovered. Examples of HSN matrices include adjacency matrices of graphs and distance matrices in various metrics.
An n-by-n matrix is "hollow" if all its diagonal entries are 0. We study the eigenvalue distribution of hollow symmetric nonnegative (HSN) matrices. In the process, some very unusual combinatorial structure is uncovered. Examples of HSN matrices include adjacency matrices of graphs and distance matrices in various metrics.
Thursday April 3, 2014, 12h
C3-Room 005, Campus Nord, UPCMartyn Mulder (Erasmus Univ. Rotterdam)
What do trees and hypercubes have in common?
Abstract:
At first sight trees and hypercubes are very different classes of graphs (except for the trivial cases K_1 and K_2, of course). Non-trivial trees are cycle-free, highly irregular and have very few automorphisms. Hypercubes are regular, contain many cycles (for dimension at least 2), and have many automorphims. But there is a nice common property of trees and hypercubes. We explore this property and develop a rich structure theory based on it.
At first sight trees and hypercubes are very different classes of graphs (except for the trivial cases K_1 and K_2, of course). Non-trivial trees are cycle-free, highly irregular and have very few automorphisms. Hypercubes are regular, contain many cycles (for dimension at least 2), and have many automorphims. But there is a nice common property of trees and hypercubes. We explore this property and develop a rich structure theory based on it.
Thursday March 27, 2014, 12h
C3-Room 005, Campus Nord, UPC
Martin Golumbic (Univ. of Haifa)
The Elusive Nature of Intersecting Paths on a Grid
Abstract:
In this lecture, we will survey the mathematical and algorithmic results on the edge intersection graphs of paths in a grid (EPG) together with several restrictions on the representations such as allowing just a single bend in any path.
Let P be a collection of nontrivial simple paths on a host graph H. The edge intersection graph of P, denoted by EP_H(P), has vertex set that corresponds to the members of P, where two vertices are joined by an edge if and only if the corresponding members of P share at least one common edge in H. An undirected graph G is called an edge intersection graph of paths in a grid (EPG) if G = EP_{\Gamma}(P) for some P and grid \Gamma.
Similarly, G is called an edge intersection graph of paths in a tree (EPT) if G = EP_T(P) for some P and tree T. The EPT and EPG graphs can be useful in network and circuit applications, where scheduling and layout problems are often equivalent to coloring an EPT or EPG graph.
The class of EPT graphs was first investigated by Golumbic and Jamison in two papers appearing in 1985, and subsequently, further research has been carried out by a number of algorithmic graph theorists. In a series of papers during the past 5 years, Golumbic, Lipshteyn and Stern studied the hierarchy of related EPT graph classes giving some structure theorems.
More recently, Golumbic, Lipshteyn and Stern introduced EPG graphs, proving that every graph is an EPG graph, and then turning their attention to the subclass of graphs that admit an EPG representation in which every path has at most a single bend, called B_1-EPG graphs. They proved that any tree is a B_1-EPG graph and gave a structural property that enables generating non B_1-EPG graphs. A characterization of the representation of cliques and chordless 4-cycles in B_1-EPG graphs was given, and also prove that single bend paths on a grid have Strong Helly number 4, and when the paths satisfy the usual Helly property, they have Strong Helly number 3.
We will survey these and other recent results by our colleagues Andrei Asinowski, Andrew Suk and Bernard Ries on edge intersection graphs of systems of paths on a grid with a bounded number of bends, and mention some further research by a team in Germany. We will conclude with some new algorithmic results, open problems and future work.
In this lecture, we will survey the mathematical and algorithmic results on the edge intersection graphs of paths in a grid (EPG) together with several restrictions on the representations such as allowing just a single bend in any path.
Let P be a collection of nontrivial simple paths on a host graph H. The edge intersection graph of P, denoted by EP_H(P), has vertex set that corresponds to the members of P, where two vertices are joined by an edge if and only if the corresponding members of P share at least one common edge in H. An undirected graph G is called an edge intersection graph of paths in a grid (EPG) if G = EP_{\Gamma}(P) for some P and grid \Gamma.
Similarly, G is called an edge intersection graph of paths in a tree (EPT) if G = EP_T(P) for some P and tree T. The EPT and EPG graphs can be useful in network and circuit applications, where scheduling and layout problems are often equivalent to coloring an EPT or EPG graph.
The class of EPT graphs was first investigated by Golumbic and Jamison in two papers appearing in 1985, and subsequently, further research has been carried out by a number of algorithmic graph theorists. In a series of papers during the past 5 years, Golumbic, Lipshteyn and Stern studied the hierarchy of related EPT graph classes giving some structure theorems.
More recently, Golumbic, Lipshteyn and Stern introduced EPG graphs, proving that every graph is an EPG graph, and then turning their attention to the subclass of graphs that admit an EPG representation in which every path has at most a single bend, called B_1-EPG graphs. They proved that any tree is a B_1-EPG graph and gave a structural property that enables generating non B_1-EPG graphs. A characterization of the representation of cliques and chordless 4-cycles in B_1-EPG graphs was given, and also prove that single bend paths on a grid have Strong Helly number 4, and when the paths satisfy the usual Helly property, they have Strong Helly number 3.
We will survey these and other recent results by our colleagues Andrei Asinowski, Andrew Suk and Bernard Ries on edge intersection graphs of systems of paths on a grid with a bounded number of bends, and mention some further research by a team in Germany. We will conclude with some new algorithmic results, open problems and future work.
Thursday March 20, 2014, 12h
C3-Room 005, Campus Nord, UPCBill Kantor (U. Oregon)
Mutually Unbiased Bases
Abstract:
Two orthonormal bases of an n-dimensional complex vector space are called "mutually unbiased" if all inner products of members of different bases have the same absolute value. The maximal possible number of bases pairwise behaving in this manner is n+1. Finding such large sets of bases arose independently in research in electrical engineering, quantum physics, Euclidean configurations and coding theory.
This talk will assume nothing about any of those subjects, and focus instead on the relationships between such sets of bases and affine planes.
Two orthonormal bases of an n-dimensional complex vector space are called "mutually unbiased" if all inner products of members of different bases have the same absolute value. The maximal possible number of bases pairwise behaving in this manner is n+1. Finding such large sets of bases arose independently in research in electrical engineering, quantum physics, Euclidean configurations and coding theory.
This talk will assume nothing about any of those subjects, and focus instead on the relationships between such sets of bases and affine planes.
Thursday March 13, 2014, 12h
C3-Room 005, Campus Nord, UPC
Juanjo Rué (Freie Univ. Berlin)
Applications of Tutte's tree decomposition in enriched families of graphs
Abstract:
We adapt the grammar introduced by Chapuy, Fusy, Kang and Shoilekova to study enriched graph families which are defined by their 3-connected components.
More precisely, we will discuss two different problems:
1.- The counting formulas for bipartite series-parallel graphs (and more generally of the Ising model over this family of graphs), as well as asymptotic estimates for the number of such graphs with a fixed size.
2.- The expected number of spanning trees in a random series-parallel graph of size n choosen uniformly at random.
This talk is based in different works in progress joint with Kerstin Weller (point 1, ETH Zürich & Oxford) and Julia Ehrenmüller (point 2, TU Hamburg).
We adapt the grammar introduced by Chapuy, Fusy, Kang and Shoilekova to study enriched graph families which are defined by their 3-connected components.
More precisely, we will discuss two different problems:
1.- The counting formulas for bipartite series-parallel graphs (and more generally of the Ising model over this family of graphs), as well as asymptotic estimates for the number of such graphs with a fixed size.
2.- The expected number of spanning trees in a random series-parallel graph of size n choosen uniformly at random.
This talk is based in different works in progress joint with Kerstin Weller (point 1, ETH Zürich & Oxford) and Julia Ehrenmüller (point 2, TU Hamburg).
Thursday March 6, 2014, 12h
C3-Room 005, Campus Nord, UPC
Cristina Araúz (UPC Barcelona)
Discrete Serrin's Problem
Abstract:
We consider here the discrete analogue of Serrin’s problem: if the equilibrium measure of a network with boundary satisfies that its normal derivative is constant, what can be said about the structure of the network and the symmetry of the equilibrium measure? In the original Serrin’s problem, the conclusion is that the domain is a ball and the solution is radial. To study the discrete Serrin’s problem, we first introduce the notion of radial function and then prove a generalization of the minimum principle, which is one of the main tools in the continuous case. Moreover, we obtain similar results to those of the continuous case for some families of networks with a ball-like structure, which include spider networks with radial conductances, distance-regular graphs or, more generally, regular layered networks.
Friday February 21
2nd Graph-TA Workshop 2014
http://www.dama.upc.edu/seminars/2nd-graph-ta
Thursday February 20, 2014, 12h
C3-Room 005, Campus Nord, UPCAnna de Mier (UPC Barcelona)
Transversal extensions of transversal matroids
Abstract:
Given a matroid M, one can wonder in how many ways a new element x can be added to obtain another matroid N. The answer to this question is well understood since H. Crapo developed the theory of single-element extensions in 1965. Our goal is to explore the same question if we require that both M and N are transversal matroids. In this case we say that N is a transversal extension of M.
Recall that a matroid is transversal if its independendent sets are the partial transversals of a collection of sets (A_1,..., A_r). Thus, adding the new element x to some of these sets would give another transversal matroid. The problem is that a given transversal matroid can be presented by many different collections of sets, so it is not obvious how to obtain all transversal extensions efficiently.
In this talk we will present two results in this direction: we show that all extensions obtained from a minimal presentation are different, and that every extension can be obtained by extending some minimal presentation.
Naturally we will review all necessary facts about matroids and transversal matroids.
(Joint work with J. Bonin.)
Given a matroid M, one can wonder in how many ways a new element x can be added to obtain another matroid N. The answer to this question is well understood since H. Crapo developed the theory of single-element extensions in 1965. Our goal is to explore the same question if we require that both M and N are transversal matroids. In this case we say that N is a transversal extension of M.
Recall that a matroid is transversal if its independendent sets are the partial transversals of a collection of sets (A_1,..., A_r). Thus, adding the new element x to some of these sets would give another transversal matroid. The problem is that a given transversal matroid can be presented by many different collections of sets, so it is not obvious how to obtain all transversal extensions efficiently.
In this talk we will present two results in this direction: we show that all extensions obtained from a minimal presentation are different, and that every extension can be obtained by extending some minimal presentation.
Naturally we will review all necessary facts about matroids and transversal matroids.
(Joint work with J. Bonin.)
Click here to see or download the presentation slides.
Thursday February 13, 2014, 12h
C3-Room 005, Campus Nord, UPC
Angeles Carmona (UPC Barcelona)
Generalized Linear Polyominoes, Green functions and Green matrices
Abstract:
A Polyomino is an edge-conected union of cells in the planar square lattice. Because the chemical constitution of a molecule is conventionally represented by a molecular graph or network, the polyominoes have deserved the attention of the Organic Chemistry community. So, several molecular structure descriptors based in network structural descriptors, have been introduced. In particular, in the last decade a great amount of works devoted to calculate the Kirchhoff Index of linear polyominoes-like networks, have been published. In this work we deal with this class of polyominoes, that we call generalized linear polyominoes, that besides the most popular class of linear polyomino chains, also includes cycles, Phenylenes and Hexagonal chains to name only a few. Because the Kirchhoff Index is the trace of the Green function of the network, here we obtain the Green function of such a network. To do this, we understand a polyomino as a perturbation of a path by adding weighted edges between opposite vertices. Therefore, unlike the techniques used previously that are based on the decomposition of the combinatorial Laplacian in structured blocks, here we obtain the Green function of a linear polyomino from a perturbation of the combinatorial Laplacian. We end with an extension of the above work to general connected networks.
Joint work with Andrés M. Encinas and Margarida Mitjana.
Click here to see or download the presentation slides.
Thursday February 6, 2014, 12h
C3-Room 005, Campus Nord, UPC
Francesc Aguiló (UPC Barcelona)
Some metric results on weighted Cayley digraphs
Abstract:
Let G_c=<a,b> be a finite (additive) 2-generated Abelian group of order c. Let us consider the weighted Cayley digraph Cay(G_c,{a,b},{W_a,W_b}), where W_a and W_b are the weighs of the arcs (g,g+a) and (g,g+b) respectively, for any g in G_c. When W_a=W_b=1, also known as the non-weighted case, there are many known metric results of the cyclic case G_c=Z_c: diameter's sharp lower bound, optimal diameter families of digraphs, efficent algorithms for computing the distance between any pair of vertices, algorithms for computing the diameter, etc. Most of these items can be studied using the well-known minimum distance diagrams. These diagrams can also be used for the weighted and non-cyclic cases. We introduce here the minimum path diagrams that can be used to count the number of minimum paths between two vertices in a weighted (cyclic or non-cyclic) 2-Cayley digraph when the weighs are W_a=a and W_b=b; they can be used for studying some properties of numerical 3-semigroups <a,b,c> with $1<a<b<c$ (and gcd(a,b,c)=1).
In this session two main results will be introduced on numerical 3-semigroups. First, some properties of the semigroup will be derived from the minimum distance diagram of the related digraph. This fact can be useful for computer filtered search on 3-semigroups. The second main result is a closed expression for
G(N)=max{g(a,b,c): 1<a<b<c leq N, gcd(a,b,c)=1}
where g(a,b,c) is the genus of the semigroup <a,b,c>.
Joint work with Alicia Miralles and Marisa Zaragozá.
Click here to see or download the presentation slides.
Let G_c=<a,b> be a finite (additive) 2-generated Abelian group of order c. Let us consider the weighted Cayley digraph Cay(G_c,{a,b},{W_a,W_b}), where W_a and W_b are the weighs of the arcs (g,g+a) and (g,g+b) respectively, for any g in G_c. When W_a=W_b=1, also known as the non-weighted case, there are many known metric results of the cyclic case G_c=Z_c: diameter's sharp lower bound, optimal diameter families of digraphs, efficent algorithms for computing the distance between any pair of vertices, algorithms for computing the diameter, etc. Most of these items can be studied using the well-known minimum distance diagrams. These diagrams can also be used for the weighted and non-cyclic cases. We introduce here the minimum path diagrams that can be used to count the number of minimum paths between two vertices in a weighted (cyclic or non-cyclic) 2-Cayley digraph when the weighs are W_a=a and W_b=b; they can be used for studying some properties of numerical 3-semigroups <a,b,c> with $1<a<b<c$ (and gcd(a,b,c)=1).
In this session two main results will be introduced on numerical 3-semigroups. First, some properties of the semigroup will be derived from the minimum distance diagram of the related digraph. This fact can be useful for computer filtered search on 3-semigroups. The second main result is a closed expression for
G(N)=max{g(a,b,c): 1<a<b<c leq N, gcd(a,b,c)=1}
where g(a,b,c) is the genus of the semigroup <a,b,c>.
Joint work with Alicia Miralles and Marisa Zaragozá.
Click here to see or download the presentation slides.
Thursday January 30, 2014, 12h
C3-Room 005, Campus Nord, UPC
Mercè Mora (UPC Barcelona)
Location and domination in graphs
Abstract:
Many problems related to location and domination in graphs give raise to consider some special subsets of vertices and parameters. The main goal is to determine the existence or the location of some facility, object or item by placing the minimum number of detection devices or watchers in some vertices of the graph. The different parameters are defined by considering restrictions of the detection devices. In this talk I will give the definitions and basic properties of some of the parameters, including bounds and values on some families. I will also show some recent results in this subject, concretely the relation of these parameters in a graph and its complement.
Many problems related to location and domination in graphs give raise to consider some special subsets of vertices and parameters. The main goal is to determine the existence or the location of some facility, object or item by placing the minimum number of detection devices or watchers in some vertices of the graph. The different parameters are defined by considering restrictions of the detection devices. In this talk I will give the definitions and basic properties of some of the parameters, including bounds and values on some families. I will also show some recent results in this subject, concretely the relation of these parameters in a graph and its complement.
Click here to see or download the presentation slides.
Thursday January 23, 2014, 12h
C3-Room 005, Campus Nord, UPC
Camino Balbuena (UPC Barcelona)
An overview on {C_3,...,C_s}-free extremal graphs
Abstract:
For integers s>3 and n>s, let ex(n;{C_3,...,C_s}) denote the maximum number of edges in a graph on n vertices and girth at least s+1. We refer to it as the extremal function. By EX(n;{C_3,...,C_s}) we denote the set of all simple graphs of order n, girth at least s+1 and with ex(n;{C_3,...,C_s}) edges. A graph G in EX(n;{C_3,...,C_s}) is called an extremal graph.
Graphs constructed by researchers interested in the Cage Problem provide good constructive lower bounds for the extremal number. In this talk we will see some exact values of the extremal function for s=4,5,6,7,10,11, and also some lower bounds. Moreover, we will review the last results on the lower bounds on the order of a extremal graph guaranteeing that the girth is equal to s+1 and other structural properties.
For integers s>3 and n>s, let ex(n;{C_3,...,C_s}) denote the maximum number of edges in a graph on n vertices and girth at least s+1. We refer to it as the extremal function. By EX(n;{C_3,...,C_s}) we denote the set of all simple graphs of order n, girth at least s+1 and with ex(n;{C_3,...,C_s}) edges. A graph G in EX(n;{C_3,...,C_s}) is called an extremal graph.
Graphs constructed by researchers interested in the Cage Problem provide good constructive lower bounds for the extremal number. In this talk we will see some exact values of the extremal function for s=4,5,6,7,10,11, and also some lower bounds. Moreover, we will review the last results on the lower bounds on the order of a extremal graph guaranteeing that the girth is equal to s+1 and other structural properties.
Click here to see or download the presentation slides.
Thursday January 16, 2014, 12h
C3-Room 005, Campus Nord, UPC
Miquel Àngel Fiol (UPC Barcelona)
Miquel Àngel Fiol (UPC Barcelona)
The Preintersection Numbers and Some of Their Properties
Abstract:
The preintersection numbers are, in fact, some Fourier coefficients which depend only on the spectrum of (the adjacency matrix $A$ of) a graph $G$. They can be seen as a generalization of the so-called intersection numbers of a distance-regular graph, which are parameters of a purely combinatorial nature. (In general, this is not true for the preintersection numbers.)
In this talk we first discuss which well-known properties of the intersection numbers are shared by the preintersection numbers, and which are not.
Then we present some results about the structure of $G$, mainly related with distance-regularity, in terms of the preintersection numbers.
(joint work with A. Abiad, C. Dalfó, E. Garriga, and E.R. van Dam)
Tuesday December 10, 17h, and Thursday December 12, 17h
Facultat de Matemàtiques i Estadística, UPC, Room 005
Special lectures of the Random Structures course
http://www.bgsmath.cat/random-structures-and-the-probabilistic-method
on Graph coloring and the probabilistic method
http://www.springer.com/new+%26+forthcoming+titles+(default)/book/978-3-540-42139-9
delivered by Bruce Reed.
Thursday December 12, 2013, 12h
C3-Room 005, Campus Nord, UPC
Bruce Reed (McGill Univ., Montreal)The typical structure of H-free graphs
Abstract:
We show that the vertex set of almost every graph which does not contain a cycle of length six as an induced subgraph can be partitioned into a stable set and a subgraph containing neither a stable set of size three nor an induced matching of size 2. We discuss similar precise characterizations of typical graphs without induced cycles of length k for all k. We present a conjecture about the structure of almost every graph without H as an induced subgraph for arbitrary H. We discuss various pieces of evidence in support of this conjecture.
We show that the vertex set of almost every graph which does not contain a cycle of length six as an induced subgraph can be partitioned into a stable set and a subgraph containing neither a stable set of size three nor an induced matching of size 2. We discuss similar precise characterizations of typical graphs without induced cycles of length k for all k. We present a conjecture about the structure of almost every graph without H as an induced subgraph for arbitrary H. We discuss various pieces of evidence in support of this conjecture.
Thursday December 5, 2013, 12h
C3-Room 005, Campus Nord, UPC
Victor Diego (UPC Barcelona)
Victor Diego (UPC Barcelona)
On a problem of Shapozenko
Abstract:
The Johnson graph J(n,m) has the m-subsets of [n] as vertices and two subsets are adjacent in the graph if they share m-1 elements. The isoperimetric function of a graph gives, for each k, the cardinality of the smallest boundary among sets with cardinality k.
The isoperimetric function is known for a small class of graphs, including the n-cube. Shapozenko, and later Leader, asked about the isoperimetric function in Johnson graphs, which, as the n-cube, are distance transitive.
In order to study the isoperimetric function of Johnson graphs we use combinatorial tools. The combinatorial tools are based on compression techniques, which allow us to transform sets of vertices without increasing their boundary. In the compression process we will show that sets of vertices that induce Johnson subgraphs are optimal with respect to the isoperimetric problem. Upper bounds are obtained by displaying nested families of sets which interpolate optimal ones. Finally, the values of the form {t \choose m} can be generalized to any m-binomial expression of any value of $k$, giving the complete isoperimetric function for all the Johnson graphs.
The isoperimetric function is known for a small class of graphs, including the n-cube. Shapozenko, and later Leader, asked about the isoperimetric function in Johnson graphs, which, as the n-cube, are distance transitive.
In order to study the isoperimetric function of Johnson graphs we use combinatorial tools. The combinatorial tools are based on compression techniques, which allow us to transform sets of vertices without increasing their boundary. In the compression process we will show that sets of vertices that induce Johnson subgraphs are optimal with respect to the isoperimetric problem. Upper bounds are obtained by displaying nested families of sets which interpolate optimal ones. Finally, the values of the form {t \choose m} can be generalized to any m-binomial expression of any value of $k$, giving the complete isoperimetric function for all the Johnson graphs.
Thursday November 21, 2013, 12h
C3-Room 005, Campus Nord, UPC
Benny Sudakov (ETH Zürich and UCLA Los Angeles)
The minimum number of nonnegative edges in hypergraphs
Abstract:
An r-uniform n-vertex hypergraph H is said to have the Manickam-Miklos-Singhi (MMS) property if for every assignment of weights to its vertices with nonnegative sum, the number of edges whose total weight is nonnegative is at least the minimum degree of H. In this talk I will show that for n>10r^3, every r-uniform n-vertex hypergraph with equal codegrees has the MMS property, and the bound on n is essentially tight. One of the immediate corollaries of this result is the vector space Manickam-Miklos-Singhi conjecture from 1988 which determines the minimum number of nonnegative k-dimensional subspaces in any weighting of the 1-dimensional subspaces of (F_q)^n with nonnegative sum.
Joint work with Hao Huang.
Thursday November 14, 2013, 12h
C3-Room 005, Campus Nord, UPCJavier Cilleruelo (UAM and ICMAT, Madrid)
Extremal graphs and extremal sets of integers
Abstract:
The study of sets of integers which do not contain special subsets, like arithmetic progressions, solutions of a given linear equation or some other kind of additive structure, is central in additive combinatorics. In the same vein, the study of graphs which do not contain a given subgraph has a rich history in extremal graph theory. In this talk we will connect these two worlds and we will present new results in each of them.
Thursday November 7, 2013, 12h
C3-Room 005, Campus Nord, UPC
Juraj Hromkovic (ETH Zürich)
Towards measuring the information content of problems
Abstract:
Information is a fundamental notion in science but we do not have any reasonable exact definition of this term. Shannon, Kolmogorov and Chaitin tried to define the information content of finite objects and introduced in this way very powerful research instruments. Shannon entropy is measurable but it is definitely not a robust definition of the information content. Kolmogorov complexity is a robust definition of the information content but one cannot use it to measure the information content of concrete finite objects. We think that there is no way to measure the information content of finite objects as well as it is no way to measure the computational complexity of particular problem instances. This is the motivation to introduce the information content of computing problems in online setting as a function of the problem instance size. Using this concept we discover the information content of several fundamental online problems and observe very different kinds of behaviors of the tradeoffs between the amount of information provided and the quality of reachable solutions.
Information is a fundamental notion in science but we do not have any reasonable exact definition of this term. Shannon, Kolmogorov and Chaitin tried to define the information content of finite objects and introduced in this way very powerful research instruments. Shannon entropy is measurable but it is definitely not a robust definition of the information content. Kolmogorov complexity is a robust definition of the information content but one cannot use it to measure the information content of concrete finite objects. We think that there is no way to measure the information content of finite objects as well as it is no way to measure the computational complexity of particular problem instances. This is the motivation to introduce the information content of computing problems in online setting as a function of the problem instance size. Using this concept we discover the information content of several fundamental online problems and observe very different kinds of behaviors of the tradeoffs between the amount of information provided and the quality of reachable solutions.
Thursday October 31, 2013, 12h
C3-Room 005, Campus Nord, UPC
Christian Rubio Montiel (Instituto de Matemáticas UNAM)
A new characterization of trivially perfect graphs
Abstract:
A graph G is trivially perfect if for every induced subgraph the cardinality of the largest set of pairwise nonadjacent vertices (the stability number) α(G) equals the number of (maximal) cliques m(G). We characterize the trivially perfect graphs in terms of vertex-coloring, we relate them to some well-known classes of perfect graphs and extend the definitions to infinite graphs.
A graph G is trivially perfect if for every induced subgraph the cardinality of the largest set of pairwise nonadjacent vertices (the stability number) α(G) equals the number of (maximal) cliques m(G). We characterize the trivially perfect graphs in terms of vertex-coloring, we relate them to some well-known classes of perfect graphs and extend the definitions to infinite graphs.
Thursday October 24, 2013, 12h
C3-Room 005, Campus Nord, UPC
Joan Vilaltella (UPC Barcelona)
Joan Vilaltella (UPC Barcelona)
Complete and irreducible multipoles
Abstract:
Multipoles are the pieces we obtain by cutting some edges of a cubic graph. As a result of the cut, a multipole M has dangling edges with one free end, which we call semiedges. Then, every 3-edge-coloring of a multipole induces a coloring or state of its semiedges, which must satisfy a parity restriction called the Parity Lemma.
Multipoles have been extensively used in the study of snarks, that is, cubic graphs which are not 3-edge-colorable.
A multipole is complete if it has all states allowed by the Parity Lemma. We give lower and upper linear bounds on the minimum order of a complete multipole, and the exact number of states of any complete multipole as a function of its number of semiedges.
Given two multipoles M1 and M2 with the same number of semiedges, we say that M1 is reducible to M2 if the state set of M2 is a non-empty subset of the state set of M1 and M2 has less vertices than M1. If no multipole M2 fulfills this conditions for a given multipole M1, then we say that M1 is irreducible.
The function v(m) is defined as the maximum number of vertices of an irreducible multipole with m semiedges. The exact values of v(m) are only known for m <= 5. Recently, we obtained the result that tree and cycle multipoles are irreducible and, as a byproduct, that v(m) has a linear lower bound.
This is joint work with Miquel Àngel Fiol (UPC Barcelona).
Monday October 14 and Tuesday October 15, 2013
C3-Room 005, Campus Nord, UPC
Journées Combinatoire et Algorithmes du Littoral Méditerranéen, JCALM
Graph MinorsClick here to see the program or visit the JCALM 2013 web page:
http://www.lirmm.fr/~sau/JCALM2013Bcn.html
Thursday October 10, 2013, 12h
C3-Room 005, Campus Nord, UPC
Gabriela Araujo (UNAM, Mexico)
Projective planes and colorings
Thursday October 3, 2013, 12h
C3-Room 005, Campus Nord, UPC
Aline Parreau (Univ. de Lille)Identifying codes and Vapnik–Chervonenkis dimension
Abstract:
An identifying code is a subset of vertices of a graph such that each vertex is uniquely determined by its closed neighbourhood within the identifying code. Using Vapnik–Chervonenkis dimension, we give a dicothomy result for identifying codes in classes of graphs closed under induced subgraphs: either a class has infinite VC dimension and has arbitrarily large logarithmic identifying codes or it has finite VC dimension and an identifying code will always be of polynomial size. We also prove that in the first case, the problem of determining the smallest size of an identifying code is hard to approximate within a constant factor.
An identifying code is a subset of vertices of a graph such that each vertex is uniquely determined by its closed neighbourhood within the identifying code. Using Vapnik–Chervonenkis dimension, we give a dicothomy result for identifying codes in classes of graphs closed under induced subgraphs: either a class has infinite VC dimension and has arbitrarily large logarithmic identifying codes or it has finite VC dimension and an identifying code will always be of polynomial size. We also prove that in the first case, the problem of determining the smallest size of an identifying code is hard to approximate within a constant factor.
Tuesday October 1, 2013
PhD defense by Guillem Perarnau
Random Combinatorial Structures with low dependencies: existence and enumeration
Thesis advisor: Oriol Serra.
Sala d'actes FME, 11:30h.
Thursday September 26, 2013, 12h
C3-Room 005, Campus Nord, UPC
Arnau Padrol (FU Berlin)
A universality theorem for projectively unique polytopes and a conjecture of Shephard
Abstract:
In this talk I will present the following universality theorem for projectively unique polytopes: every polytope described by algebraic coordinates is the face of a projectively unique polytope.
This result can be used to construct a combinatorial type of polytope that is not realizable as a subpolytope of any stacked polytope. This disproves a classical conjecture in polytope theory, first formulated by Shephard in the seventies.
This is joint work with Karim Adiprasito.
In this talk I will present the following universality theorem for projectively unique polytopes: every polytope described by algebraic coordinates is the face of a projectively unique polytope.
This result can be used to construct a combinatorial type of polytope that is not realizable as a subpolytope of any stacked polytope. This disproves a classical conjecture in polytope theory, first formulated by Shephard in the seventies.
This is joint work with Karim Adiprasito.
Share: