Seminar 2010-2011
Sessions and Abstracts
Unless otherwise stated, all sessions take place in Room 005, Mòdul C3, Campus Nord UPC. Please browse the left menu for additional activities organized by CombGraph. Dependent Random Choice Guillem Perarnau, UPC Tuesday, June 28 and Thursday June 30, 11h Biblioteca de Matemàtiques Mòdul C3, Campus Nord Edge distance-regularity Marc Càmara, UPC Barcelona Thursday, June 2, 2011, 12h On 3-domination critical graphs Adriana Hansberg, UPC Barcelona Thursday, May 26 2011, 12h Graph Isomorphism, Sherali-Adams Relaxations and Expressibility in Counting Logics Albert Atserias, UPC Barcelona Thursday, May 19 2011, 12h Line-identifying codes Florent Foucaud, LABRI, Univ. Bordeaux Thursday, May 12 2011, 12h Els Treballs i els Dies amb l'Ernest Miquel Angel Fiol, UPC Barcelona Thursday, May 5 2011, 12h Integer lattice points in the plane Sukumar Adhikari, Harish Chandra Research Institute, Allahabad, India Thursday, April 28 2011, 12h Bandidos malvados: ¿cómo luchar contra ellos aleatoriamente? Gabor Lugosi (ICREA y UPF) Thursday April 14, 2011, 12h On a slicing formula for bipartite graphs Eric Fusy, LIX Ecole Polytechnique, Paris Thursday April 7, 2011, 12h Regular Star Complements in strongly regular graphs Peter Rowlinson, University of Stirling, Scotland Thursday March 31 2011, 12h A tribute to Yahya ould Hamidoune Oriol Serra, UPC, Barcelona Thursday March 24, 2011, 12h Dynamic programming in sparse graphs Ignasi Sau (CNRS, LIRMM, Montpellier, France) Thursday March 10 2011, 12h Some stability problems in finite geometry Jan de Beule, Gent Univ. Thursday March 3 2011, 12h Erdös year: Erdös problems on repeated and distinct distances Marc Noy, UPC Barcelona Thursday February 17 2011, 12h Identifying codes for regular graphs Guillem Perarnau, UPC Barcelona Thursday February 10 2011, 12h On the girth of {C_3,...,C_s}-free extremal graphs Camino Balbuena, UPC Barcelona Thursday January 27, 2011, 12h Graph Coverings and the degree-diameter problem Maria Zdimalova, Slovak University of Technology Thursday January 20, 2011, 12h The h-product of digraphs and its applications to labelings Susana López masip, UPC Barcelona Thursday January 13 2011, 12h Permutations and $\beta$-shifts Sergi Elizalde, Dartmouth College Thursday December 16, 2010 (12h) | ||
| Erdös' Year: Sums and Products Oriol Serra, UPC Thursday December 2, 2010 (12h) | ||
| On graphs representable by words Sergey Kitaev, Reykjavik University Thursday November 25, 2010 (12h) | ||
| Julián Salas, UPC Thursday November 18, 2010 (12h) | ||
On Perturbations of Punctually Walk-Regular Graphs Miquel A. Fiol, UPC Thursday November 4, 2010 (12 h) | ||
| Interval orders and equinumerous objects Sergey Kitaev, Reykjavik University Thursday October 7, 2010 (12h) | ||
| Difference sets, Fourier analysis, and Delsarte's method Mate Matolcsi, Alfred Renyi Institute of Mathematics, Budapest Thursday September 30, 2010 (12h) |
Abstracts
Tuesday, June 28 and Thursday June 30, 11h
Biblioteca de Matemàtiques, Mòdul C3, Campus Nord
Dependent Random Choice
Guillem Perarnau, UPC
Two informal sessions will be devoted to an exposition of the paper 'Dependent random Choice' by J. Fox and B. Sudakov, addressed to an interested audience. The paper is available at http://onlinelibrary.wiley.com/doi/10.1002/rsa.20344/pdf.
Thursday, June 2, 2011, 12h
Aula 005, Mòdul C3, Campus Nord
Edge distance-regularity
Marc Càmara, UPC Barcelona
Abstract
Edge-distance-regularity is a concept recently introduced which is similar to that of distance-regularity, but now the graph is seen from each of its edges instead of its vertices. In this talk, we study this concept, give some of its properties, such as regularity, and derive some characterizations. In particular it is shown that a graph is edge-distance-regular if and only if its k-incidence matrix is a polynomial in the adjacency matrix multiplied by the (standard) incidence matrix. Also an analogue of the spectral excess theorem is proved, so giving a quasi-spectral characterization of edge-distance-regularity. Finally, we show that every non bipartite graph which is both distance-regular and edge-distance-regular is a generalized odd graph. We also introduce the concept of edge-spectrum-regularity, and characterize the graphs which are both spectrum-regular and edge-spectrum regular as those that are 1-walk-regular.
This is a joint work with C. Dalfó, J. Fàbrega, M.A. Fiol and E. Garriga.
Thursday, May 26 2011, 12h
Aula 005, Mòdul C3, Campus Nord
On 3-domination critical graphs
Adriana Hansberg, UPC Barcelona
Abstract
Given a graph G, a subset D of the vertex set V of G is a dominating set if every vertex in V\D has at lest one neighbor in D. The minimum cardinality among all dominating sets of G is called the domination number of G and is denoted by gamma(G). The graph G is said to be k-domination critical if gamma(G) =k and the addition of any non existing edge makes its domination number decrease by one. The k-domination critical graphs were introduced by Sumner and Blitch in 1983 and have awaken great interest among graph theorists. Specially the 3-domination critical graphs have been intensively studied by many authors. In this talk, we revisit this topic reviewing many known results and presenting new achievements on 3-domination critical graphs. In particular, we give the characterization of some 3-domination critical graphs, among them those with minimum degree one.
(joint work with Camino Balbuena)
(joint work with Camino Balbuena)
Thursday, May 19 2011, 12h
Aula 005, Mòdul C3, Campus Nord
Graph Isomorphism, Sherali-Adams Relaxations and Expressibility
in Counting Logics
Albert Atserias, UPC Barcelona
Abstract
Two graphs with adjacency matrices A and B are isomorphic if there exists a permutation matrix P for which the identity P^T A P = B holds. Multiplying through by P and relaxing the permutation matrix to a doubly stochastic matrix leads to the notion of fractional isomorphism. We show that the levels of the Sherali-Adams hierarchy of linear programming relaxations applied to fractional isomorphism interleave in power with the levels of a well known color-refinement heuristic for graph isomorphism called the Weisfeiler-Lehman algorithm. This tight connection has quite striking consequences. For example, it follows immediately from a deep result of Grohe in the context of logics with counting quantifiers, that a fixed number of levels of SA suffice to determine isomorphism of planar graphs. We also offer applications both in finite model theory and polyhedral combinatorics. First, we show that certain properties of graphs such as that of having a flow-circulation of a prescribed value, are definable in the infinitary logic with counting with a bounded number of variables. Second, we exploit a lower bound construction due to Cai, Fürer and Immerman in the context of counting logics to give simple explicit instances that show that the SA relaxations of the vertex-cover and cut polytopes do not reach their integer hulls for up to \Omega(n) levels, where n is the number of vertices in the graph.
Thursday, May 12 2011, 12h
Aula 005, Mòdul C3, Campus Nord
Line-identifying codes
Florent Foucaud, LABRI, Univ. Bordeaux
Abstract
An identifying code of a graph is a subset of its vertices such that the set of code vertices which dominate each vertex are unique and nonempty. This concept was introduced in 1998 by Karpovsky et al. In this talk we introduce the related concept of line-identifying code, that is, the same concept defined over the edges of $G$. Equivalently, a line-identifying code of $G$ is an identifying code of the line-graph of $G$. The line-identifying code number of $G$ is the minimum size of a line-identifying code in $G$. We derive some lower and upper bounds on this parameter. These bounds imply that identifying codes behave quite differently in the class of line-graphs (with respect to general graphs). We also show that the problem of determining the minimum value of this parameter is NP-hard in a very restricted class of graphs (planar bipartite graphs of maximum degree 3 and arbitrarily large girth).
This is joint work with Sylvain Gravier, Reza Naserasr, Aline Parreau and Petru Valicov.
This is joint work with Sylvain Gravier, Reza Naserasr, Aline Parreau and Petru Valicov.
Thursday, May 5 2011, 12h
Aula 005, Mòdul C3, Campus Nord
Els Treballs i els Dies amb l'Ernest
Miquel Angel Fiol, UPC Barcelona
Abstract
En el diccionari Català-Valencià-Balear d'A.M. Alcover i F. de B. Moll podem llegir la següent definició del verb JUBILAR: "Experimentar una alegria viva, expansiva".
Bé, això és el que l'Ernest Garriga, el nostre company i amic del departament, ha pogut experimentar recentment i el que, com a petit homenatge, justifica aquesta xerrada. Aquesta és la història d'una col·laboració que s'ha perllongat durant una quinzena d'anys i ha donat lloc a una trentena de treballs (articles, conferències, tesis,...). Vam començar a treballar amb l'Ernest, juntament amb el Luis Yebra i el Jordi Barguilla (malauradament ja traspassat), a mitjans dels anys 90 del segle passat. Des d'aleshores, han passat moltes coses: unes bones i d'altres, no tant. Afortunadament, en tots els casos i circumstàncies, els treballs han tirat endavant i han anat sortint coses com "polinomis alternants","grafs frontera", "pertorbacions de grafs i equacions diferencials", "espectres locals", "polinomis predistància", "el teorema de l'excés espectral", "pseudo-distància-regularitat" "odd grafs retorçats", "grafs k-camí-regulars", "grafs quasi-distància-regulars",...
En aquesta xerrada farem cinc cèntims d'aquests treballs que hem fet (i dels que encara esperem seguir fent) i dels dies que hem passat (i que encara esperem seguir passant) amb l'Ernest. Parafrasejant un comentari de l'Ernest al "Pròleg i agraïments" de la seva tesi, no sé si la Ciència li agrairà el que ha fet, però jo (i molts d'altres) sí.
Bé, això és el que l'Ernest Garriga, el nostre company i amic del departament, ha pogut experimentar recentment i el que, com a petit homenatge, justifica aquesta xerrada. Aquesta és la història d'una col·laboració que s'ha perllongat durant una quinzena d'anys i ha donat lloc a una trentena de treballs (articles, conferències, tesis,...). Vam començar a treballar amb l'Ernest, juntament amb el Luis Yebra i el Jordi Barguilla (malauradament ja traspassat), a mitjans dels anys 90 del segle passat. Des d'aleshores, han passat moltes coses: unes bones i d'altres, no tant. Afortunadament, en tots els casos i circumstàncies, els treballs han tirat endavant i han anat sortint coses com "polinomis alternants","grafs frontera", "pertorbacions de grafs i equacions diferencials", "espectres locals", "polinomis predistància", "el teorema de l'excés espectral", "pseudo-distància-regularitat" "odd grafs retorçats", "grafs k-camí-regulars", "grafs quasi-distància-regulars",...
En aquesta xerrada farem cinc cèntims d'aquests treballs que hem fet (i dels que encara esperem seguir fent) i dels dies que hem passat (i que encara esperem seguir passant) amb l'Ernest. Parafrasejant un comentari de l'Ernest al "Pròleg i agraïments" de la seva tesi, no sé si la Ciència li agrairà el que ha fet, però jo (i molts d'altres) sí.
Thursday, April 28 2011, 12h
Aula 005, Mòdul C3, Campus Nord
Integer lattice points in the plane
Sukumar Adhikari, Harish Chandra Research Institute, Allahabad, India
Abstract
We shall discuss a couple of problems related to integer lattice points in the plane. The first one involves finite colourings of integer lattice points in the plane. The question may be said to belong to the subject of Euclidean Ramsey Theory and is related to a conjecture which was suggested by Gurevich which says that for any finite colouring of the Euclidean plane $E2$, there always exists a triangle of unit area with monochromatic vertices. The second problem is on a question of Erd\H{o}s regarding visibility of integer lattice points in the plane. For both the problems, before going into the exact problems involved, we give necessary introductions to those themes. We also mention results related to these problems in higher dimensions.
Thursday April 14, 2011, 12h
Aula 005, Mòdul C3, Campus Nord
Bandidos malvados: ¿cómo luchar contra ellos aleatoriamente?
Gabor Lugosi (ICREA y UPF)
Abstract
En esta charla repasamos algunos problemas de aprendizaje "online". En este tipo de problemas uno intenta a predecir una sucesión completamente arbitraria. Vamos a mostrar cómo el uso de predicción aleatorizada puede garantizar un buen rendimiento. Un variante interesante es el "multi-armed bandit problem" donde la información recibida por el predictor se limita a su propia pérdida. Cuando el conjunto de posibles acciones es grande pero estructurada, surgen algunos problemas combinatorios y algorítmicos interesantes. (La charla no requiere ningún conocimiento previo del tema.)
Thursday April 7, 2011, 12h
Aula 005, Mòdul C3, Campus Nord
On a slicing formula for bipartite graphs
Eric Fusy, LIX Ecole Polytechnique, ParisAbstract
The slicings formula, discovered by Tutte and recovered bijectively by Schaeffer, gives an exact expression for the number of (rooted) bipartite planar maps with a prescribed number n_i of faces in each even degree 2i. We show bijectively that a very similar exact formula exists for bipartite planar maps without multiple edges. The expression in terms of generating functions can be generalized to higher girth.
Joint work with Olivier Bernardi.
Joint work with Olivier Bernardi.
Thursday March 31 2011, 12h
Aula 005, Mòdul C3, Campus Nord
Regular Star Complements in strongly regular graphs
Peter Rowlinson, University of Stirling, Scottland
Abstract
Let G be a graph of order n, with \mu as an eigenvalue of multiplicity k. A star complement for \mu in G is an induced subgraph of order n-k which does not have \mu as an eigenvalue. We discuss the strongly regular graphs that can be constructed from a regular star complement of prescribed degree.
Thursday March 24 2011, 12h
Aula 005, Mòdul C3, Campus Nord
A tribute to Yahya ould Hamidoune
Oriol Serra, UPC, BarcelonaOn Friday March 11 Yahya ould Hamidoune passed away. The talk will survey the mathematical work Anna Llado and myself shared with him in the last 15 years.
Thursday March 10 2011, 12h
Aula 005, Mòdul C3, Campus Nord
Dynamic programming in sparse graphs
Ignasi Sau (CNRS, LIRMM, Montpellier, France)Abstract
A fundamental parameter in the design and analysis of graph algorithms is the branchwidth of a graph, which can be seen as a measure of the topological resemblance of a graph to a tree (similar to treewidth). Its algorithmic importance is justified by Courcelle's theorem, stating that graph problems expressible in Monadic Second Order Logic can be solved in f(bw)n steps (here bw is the branchwidth and n is the number of vertices of the input graph). As the bounds for f(bw) provided by Courcelle's theorem are huge, it is of great interest
the design algorithms so that f(bw) is a simple function.
In this talk we overview a general framework for the design and analysis of dynamic programming algorithms for graphs embedded in arbitrary surfaces where f(bw)=2^{O(bw)}. Our approach combines tools from topological graph theory and analytic combinatorics. In particular, we introduce a new type of branch decomposition called "surface cut decomposition", which generalizes "sphere cut decompositions" introduced by Seymour and Thomas for planar graphs. That way, we unify and improve all previous results in this direction.
If time permits, we will also outline the main ideas in order to extend our framework to deal with families of graphs excluding a fixed
graph as a minor.
This is joint work with Juanjo Rué and Dimitrios M. Thilikos.
the design algorithms so that f(bw) is a simple function.
In this talk we overview a general framework for the design and analysis of dynamic programming algorithms for graphs embedded in arbitrary surfaces where f(bw)=2^{O(bw)}. Our approach combines tools from topological graph theory and analytic combinatorics. In particular, we introduce a new type of branch decomposition called "surface cut decomposition", which generalizes "sphere cut decompositions" introduced by Seymour and Thomas for planar graphs. That way, we unify and improve all previous results in this direction.
If time permits, we will also outline the main ideas in order to extend our framework to deal with families of graphs excluding a fixed
graph as a minor.
This is joint work with Juanjo Rué and Dimitrios M. Thilikos.
Thursday March 3 2011, 12h
Aula 005, Mòdul C3, Campus Nord
Some stability problems in finite geometry
Jan de Beule, Gent Univ.Abstract
Some stability problems in finite geometry will be introduced anddescribed as problems in vector spaces over finite fields. It will be explained how some of these problems correspond to problems on cliques (or co-cliques) in graphs. Then we will focus on a class of recently studied problems in a particular finite geometry, discuss the methodology used, and end with some open problems.
Thursday February 17 2011, 12h
Aula 005, Mòdul C3, Campus Nord
Erdös Year. Erdös problems on distinct and repeated distances
Marc Noy, UPC BarcelonaAbstract
In 1946 Erdos published a short paper introducing two apparently simple problems on discrete geometry that turned out to be very deep. They are the following:
- Given n points in the plane, at most how many pairs of points are at distance 1?
Call f(n) the maximum over all sets of n points.
- Given n points in the plane, at least how many different distances they determine.
Call g(n) the minimum over all sets of n points.
Erdos proved that n^(1+c/log log n) < f(n) < n^(3/2)
and that n^(1/2) < g(n) < n/sqrt(log n)
Some of these bounds have been improved over the years, for instance the best current upper bound for the unit distances problem is f(n) < n^(4/3). In the talk we will discuss some of these results, as well as the recent breakthrough by Guth and Katz in the distinct distances problem, showing the almost tight lower bound n/log n < g(n).
- Given n points in the plane, at most how many pairs of points are at distance 1?
Call f(n) the maximum over all sets of n points.
- Given n points in the plane, at least how many different distances they determine.
Call g(n) the minimum over all sets of n points.
Erdos proved that n^(1+c/log log n) < f(n) < n^(3/2)
and that n^(1/2) < g(n) < n/sqrt(log n)
Some of these bounds have been improved over the years, for instance the best current upper bound for the unit distances problem is f(n) < n^(4/3). In the talk we will discuss some of these results, as well as the recent breakthrough by Guth and Katz in the distinct distances problem, showing the almost tight lower bound n/log n < g(n).
Thursday February 10 2011, 12h
Aula 003, Mòdul C3, Campus Nord
Identifying codes for regular graphs.
Guillem Perarnau, UPC BarcelonaAbstract
Given a graph G, an identifying code can be defined as a dominating set that identifies each vertex of G with a unique code. They have applications on detecting and locating a "failure" in some vertex. We are mainly interested in bounding the size of a minimal code in terms of the maximum or minimum degree of G. In particular, we will talk about the regular case, which in some case is easier to solve. The first part is centred in giving a new result that provides an asymptotically better approximation to a conjecture stated by Foucaud et al. (2009) than the previous ones. In the second part we talk about graphs with girth five. We use them to compute the minimal size of a code for random regular graphs with high probability.
This is a joint work with Florent Foucaud.
Thursday January 27 2011, 12h
Aula 003, Mòdul C3, Campus Nord
On the girth of {C_3,...,C_s}-free extremal graphs
Camino Balbuena, UPC BarcelonaAbstract
Let G be a {C_3,...,C_s\}-free graph with as many edges as possible. In this paper we consider a question studied by several authors, the compulsory existence of the cycle C_{s+1} in G. It has been proved that the answer is affirmative for s =3,4,5,6. In this talk we revise the last results on the lower bounds on the order of G guaranteeing that the girth is equal to s+1. Furthermore, we focus on s=7 and characterize all the extremal graphs whose girth is not 8.
Joint work with E. Abajo and Ana Diánez, (Univ. Sevilla)Thursday January 20 2011, 12h
Aula 003, Mòdul C3, Campus Nord
Graph coverings and the degree-diameter problem
Maria Zdimalova
Slovak University of Technology
Abstract
The covering graph construction is a well known method used in algebraic graph theory. We will survey the history of graph coverings, explain the method in terms of voltage aasignment and discuss its application in the degree-diameter problem.
Thursday January 13 2011, 12h
Aula 003, Mòdul C3, Campus Nord
The h-product of digraphs and its applications to labelings
Susana López Masip, UPC Barcelona
Abstract
In 2008, Figueroa et al., defined the following product:
let $D$ be a digraph and let $\Gamma =\{F_i\}_{i=1}^m$ be a family of digraphs such that $V(F_i)=V$.
Consider a function $h :E(D)\longrightarrow\Gamma $.
Then the product $D\otimes_{h} \Gamma$ is the digraph with vertex set
$V(D\bigotimes_{h}\Gamma)=V(D)\times V$
and $((a_1,b_1),(a_2,b_2))\in E(D\bigotimes_{h}\Gamma)\Longleftrightarrow (a_1,a_2)\in E(D)\land (b_1,b_2)\in E(h (a_1,a_2))$.
In this talk, after providing structural results related to the product, we will focus on the relation existing among the product and different labelings. We will finish the talk with some labeling enumerating results and related problems.
let $D$ be a digraph and let $\Gamma =\{F_i\}_{i=1}^m$ be a family of digraphs such that $V(F_i)=V$.
Consider a function $h :E(D)\longrightarrow\Gamma $.
Then the product $D\otimes_{h} \Gamma$ is the digraph with vertex set
$V(D\bigotimes_{h}\Gamma)=V(D)\times V$
and $((a_1,b_1),(a_2,b_2))\in E(D\bigotimes_{h}\Gamma)\Longleftrightarrow (a_1,a_2)\in E(D)\land (b_1,b_2)\in E(h (a_1,a_2))$.
In this talk, after providing structural results related to the product, we will focus on the relation existing among the product and different labelings. We will finish the talk with some labeling enumerating results and related problems.
Thursday December 16, 2010 (12h)
Aula 003, Mòdul C3, Campus Nord
Permutations and $\beta$-shifts
Sergi Elizalde, Dartmouth College
Abstract
A permutation $\pi$ is realized by the shift on $N$ letters if there is an infinite word on an $N$-letter alphabet whose successive shifts by one position are lexicographically in the same relative order as $\pi$. Understanding the set of permutations realized by shifts, as well as other one-dimensional dynamical systems, is important because it provides tests to distinguish deterministic sequences from random ones.
In this talk I will give a characterization of permutations realized by shifts, and also by a natural generalization of them, where instead of $N$ we have a real number $\beta$.
Thursday December 2, 2010 (12h)
Aula 003, Mòdul C3, Campus Nord
Erdos' Year: Sums and Products
Oriol Serra, UPCAbstract
This is a survey talk on some selected problems posed by Erdos in occasion of the Erdos' year at the FME.
Erdos and Szemeredi conjectured that, for every set A of integers, either the sumset A+A or the product set A.A are large (actually, min{|A+A|,|A.A|}\ge |A|^{2-e} for every e>0). The talk will survey some breakthroughs in the problem, including the beautiful proofs of Elekes for the exponent 5/4 and the improvement of Solimosi to the exponent 4/3.
Erdos and Szemeredi conjectured that, for every set A of integers, either the sumset A+A or the product set A.A are large (actually, min{|A+A|,|A.A|}\ge |A|^{2-e} for every e>0). The talk will survey some breakthroughs in the problem, including the beautiful proofs of Elekes for the exponent 5/4 and the improvement of Solimosi to the exponent 4/3.
Thursday November 25, 2010 (12h)
Aula 003, Mòdul C3, Campus Nord
Abstract
Aula 003, Mòdul C3, Campus Nord
On graphs representable by words
Sergey Kitaev, Reykjavik UniversityAbstract
A simple graph $G=(V,E)$ is representable if there exists a word $W$ over the alphabet $V$ such that any two distinct letters $x$ and $y$ alternate in $W$ if and only if $(x,y)$ is an edge in $E$. If $W$ is $k$-uniform (each letter of $W$ occurs exactly $k$ times in it) then $G$ is called $k$-representable. It is known that a graph is representable if and only if it is $k$-representable for some $k$. Minimum $k$ for which a representable graph $G$ is $k$-representable is called its representation number.
Representable graphs appeared first in algebra, in study of the Perkins semigroup which has played a central role in semigroup theory since 1960, particularly as a source of examples and counterexamples. However, these graphs have connections to robotic scheduling and they are interesting from combinatorial and graph theoretical point of view (for example, representable graphs are a generalization of circle graphs, which are exactly 2-representable graphs). Some of questions one can ask about representable graphs are as follows. Are all graphs representable? How do we characterize those graphs that are (non-)representable? How many representable graphs are there? How large the representation number can be for a graph on $n$ nodes?
In this talk, we will go through these and some other questions stating what progress has been made in answering them. In particular, we will see that a graph is representable if and only if it admits a so called semi-transitive orientation. This allows us to prove a number of results about representable graphs, not the least that 3-colorable graphs are representable. We also prove that the representation number of a graph on $n$ nodes is at most $n$, from which one concludes that the recognition problem for representable graphs is in NP. This bound is tight up to a constant factor, as there are graphs whose representation number is $n/2$.
Representable graphs appeared first in algebra, in study of the Perkins semigroup which has played a central role in semigroup theory since 1960, particularly as a source of examples and counterexamples. However, these graphs have connections to robotic scheduling and they are interesting from combinatorial and graph theoretical point of view (for example, representable graphs are a generalization of circle graphs, which are exactly 2-representable graphs). Some of questions one can ask about representable graphs are as follows. Are all graphs representable? How do we characterize those graphs that are (non-)representable? How many representable graphs are there? How large the representation number can be for a graph on $n$ nodes?
In this talk, we will go through these and some other questions stating what progress has been made in answering them. In particular, we will see that a graph is representable if and only if it admits a so called semi-transitive orientation. This allows us to prove a number of results about representable graphs, not the least that 3-colorable graphs are representable. We also prove that the representation number of a graph on $n$ nodes is at most $n$, from which one concludes that the recognition problem for representable graphs is in NP. This bound is tight up to a constant factor, as there are graphs whose representation number is $n/2$.
Thursday November 18, 2010 (12h)
Aula 003, Mòdul C3, Campus Nord
Aula 003, Mòdul C3, Campus Nord
Some results on connectivity of cages
Julián Salas, UPCAbstract
An $(r;g)$-cage is a $r$-regular graph of girth $g$ of minimum order. Most work in this subject has been devoted to their existence and construction, nevertheless their structural properties have also been studied.
Fu, Huang and Rodger conjectured that all $(r,g)$-cages are $r$-connected. In this seminar we present different approaches that support this conjecture.
(Joint research with Camino Balbuena)
Fu, Huang and Rodger conjectured that all $(r,g)$-cages are $r$-connected. In this seminar we present different approaches that support this conjecture.
(Joint research with Camino Balbuena)
Thursday November 4, 2010 (12h)
Aula 003, Mòdul C3, Campus Nord
On Perturbations of Punctually Walk-Regular Graphs
Miquel A. Fiol, UPCAbstract
In this talk we show that certain almost distance-regular graphs, the so-called $h$-punctually walk-regular graphs, can be characterized though the cospectrality of their perturbed graphs. A graph $G$ with diameter $D$ is $h$-punctually walk-regular if the number of paths of length $\ell$ between a pair of vertices $u,v$ at distance $h$ depends only on $\ell$ and $h$. The graphs perturbations considered are the most common ones. Namely, deletion of one or two vertices, addition of a pendant edge, and addition, deletion or contraction of an edge. Our results are based on the theory of graph perturbations developed by Cvetkovi\'c, Godsil, Rowlinson, and coauthors. As a consequence, some new characterizations of distance-regular graphs are obtained.
(This is joint work with C. Dalfó, E.R. van Dam, E. Garriga and W. Haemers.)
Thursday October 7, 2010 (12h)
Aula 101, Mòdul C3, Campus Nord
Interval orders and equinumerous objects
Sergey Kitaev, Reykjavik UniversityAbstract
Fishburn proved that intensively studied interval orders are in one-to-one correspondence with (2+2)-free posets. Recently, Bousquet-Melou et al. discovered a way to think on (2+2)-free posets in terms of so called ascent sequences which not only allowed to enumerate the posets in question, but also to connect them to other combinatorial objects, namely to Stoimanow's diagrams, certain upper triangular matrices, and to certain pattern avoiding permutations. Several other papers appeared following the influential work by Bousquet-Melou et al. Among other results, two conjectures were solved while dealing with (2+2)-free posets.
In my talk, I will provide an overview of relevant results and research directions.
In my talk, I will provide an overview of relevant results and research directions.
Thursday September 30, 2010 (12h)
Aula 101, Mòdul C3, Campus Nord
Difference sets, Fourier analysis, and Delsarte's method
Mate Matolcsi, Alfred Renyi Institute of Mathematics, BudapestAbstract
We will discuss a general scheme with applications to several problems from strikingly different parts of mathematics. The scheme is as follows: a symmetric subset A of a compact Abelian group G is given (A will be called the "forbidden" set). What is the maximal possible cardinality of a set B in G such that all differences b_1-b_2 do not belong to A? Possible applications range through sphere-packings, Littlewood's conjecture on simultaneous approximation, and mutually unbiased bases.
Share: