Seminar 2008-2009
Sessions and Abstracts
Sessions
(Download all abstracts in PDF.)| Real-valued flows of cubic graphs Martin Skoviera, Univerza Komenskega, Bratislava, Slovakia | Thursday June 11 2009 |
| Permutaciones alternantes y gráficas completas Criel Merino, Instituto de Matemáticas, UNAM, Mexico | Thursday May 28 2009 |
| The sum of digits of primes Michael Drmota, TU Wien | Thursday May 21 2009 |
| Bounds for complex roots of combinatorial polynomials Julian Pfeifle, UPC Barcelona | Thursday May 14 2009 |
| Algorithmic relations of the Tutte polynomial Martin Loebl, Univerzita Karlova v Praze | Thursday May 07 2009 |
| Graphs with many edges containing no complete bipartite graphs Valentina Pepe, Universita di Napoli, Federico II | Thursday April 30 2009 |
| Extension Diameter of Boolean Lattices Mareike Massow, TU Berlin | Thursday April 02 2009 |
| Random graphs on surfaces Marc Noy, UPC Barcelona | Thursday March 26 2009 |
| Extremal Graph Theory, old and new results Miklós Simonovits, Alfred Rényi Institute of Mathematics, Budapest | Thursday March 12 2009 |
| Ramsey Theory and Constraint Propagation Albert Atserias, UPC Barcelona | Thursday March 05 2009 |
| Noise Sensitivity, Noise Stability, Percolation and some connections to TCS Gil Kalai, Hebrew University of Jerusalem | Thursday February 26 2009 |
| Small regular bipartite graphs of girth 8 Camino Balbuena, UPC Barcelona | Thursday January 29 2009 |
| Gyula Karolyi, Eötvös University, Budapest | Thursday January 22 2009 |
| Perfect Codes from Cayley Graphs over Lipschitz Integers Carmen Martínez, Univ. Cantabria | Thursday January 15 2009 |
| Sum-free sets, sets with small sumset and the clique number of random Cayley graphs. Gyan Prakash, Univ. Bordeaux I | Thursday December 18 2008 |
| Construccion de grandes grafos de determinadas clases Herbert Perez-Roses, The University of Newcastle, Australia | Thursday December 11 2008 |
| Sylvester-Frobenius change problem for vectors Zdzislaw Skupien, AGH University, Krakow, Poland | Thursday December 04 2008 |
| Maps on orientable surfaces Guillaume Chapuy, Ecole Polytechnique, Paris | Thursday November 27 2008 |
| Extremal examples for the Davenport constant in rank two groups David Grynkiewicz, Graz Universitat, Austria | Thursday November 20 2008 |
| k-dominación en grafos Adriana Hansberg, Univ. Aachen | Thursday November 13 2008 |
| Structural Properties of Sparse Graphs Patrice Ossona de Mendez, CNRS, Paris | Thursday November 06 2008 |
| Graph homomorphism numbers and Tutte-Grothendieck invariants. Andrew Goodall, University of Bristol | Thursday October 30 2008 |
| Ramsey theory and the Regularity Lemma Miklos Ruzsinko, Computer and Automation Research Institute, Budapest | Thursday October 16 2008 |
| On k-Walk-Regular Graphs Miquel Angel Fiol, UPC Barcelona | Thursday October 09 2008 |
Abstracts
Thursday June 11, 2009
Real-valued flows in cubic graphs
Martin Skoviera, Comenius University, Bratislava, SlovakiaAbstract
Real valued flows on graphs were proposed by several authors as an alternative approach to the flow conjectures of Tutte, in particular to the celebrated 5-Flow Conjecture. The study of real valued flows concentrates on the invariant defined as the infimum of all real numbers r >= 2 such that a given graph G has a nowhere-zero r-flow, the real (or circular flow number of G. It is known that the real flow number of a graph is a minimum and is always rational. The fundamental question about real flows is, therefore, to determine which rational numbers can occur as real flow number of graphs. For general graphs, this question has been thoroughly investigated by Zhu, Steffen and others. In this talk we focus on the flow numbers of cubic graphs. We show, in particular, that for each rational number r such that 4 < r =< 5 there exist infinitely many cyclically 4-edge-connected cubic graphs of chromatic index 4 and girth at least 5 (that is, snarks) whose circular flow number equals r. This answers a question posed by Pan and Zhu [Construction of graphs with given circular flow numbers, J. Graph Theory 43 (2003), 304--318].
Thursday May 28, 2009
Permutaciones alternantes y gráficas completas
Criel Merino, Instituto de Matemáticas, UNAM Mexico
Abstract
A permutation \sigma is alternating if sigma(1)<\sigma(2)>\sigma(3)<\ldots. Alternating permutations are well--known objects in combinatorics. It is perhaps less known that the number of alternating permutations can be obtained as an evaluation of the inversion polynomial of the complete graph. This polynomial in turn is a specialisation of Tutte's polynomial on a line.
In this talk we will discuss these two known results to show that the number of alternating permutations can be obtained as the evaluation of Tutte's polynomial in two distinct points, namely T(K_n,2,-1)=T(K_{n+2}; 1, -1). By using the same technique we will show that (K_{n,m},2,-1)=T(K_{n+1,m+1}; 1, -1).
In this talk we will discuss these two known results to show that the number of alternating permutations can be obtained as the evaluation of Tutte's polynomial in two distinct points, namely T(K_n,2,-1)=T(K_{n+2}; 1, -1). By using the same technique we will show that (K_{n,m},2,-1)=T(K_{n+1,m+1}; 1, -1).
Thursday May 21, 2009
The sum of digits of primes
Michael Drmota, TU Wien
Abstract
It is relatively easy to show that the average number of non-zero binary digits of primes < x is almost the same as the average number of non-zero binary digits of all natural numbers < x, namely (1/2) \log_2 x + O(1). The main purpose of this talk is to provide asymptotic expansions for the number of primes < x with precisely k non-zero binary digits for k close to (1/2) \log_2 x.
The proof is based on a thorough analysis of exponential sums involving the sum-of-digits function (that is related to a recent solution of problem of Gelfond) and a refined central limit theorem for the sum-of-digits function of primes. Interestingly this result answers a question of Ben Green whether for every given k there exists a prime with k non-zero binary digits. There is also a very nice relation to the Thue-Morse sequence.
This is joint work with Christian Mauduit and Joel Rivat.
Thursday May 14, 2009
Bounds for complex roots of combinatorial polynomials
Julian Pfeifle, UPC BarcelonaAbstract
We bound the location of roots of polynomials that have nonnegative coefficients with respect to a fixed but arbitrary basis of the vector space of polynomials of degree at most~$d$. For this, we interpret the basis polynomials as vector fields in the real plane, and at each point in the plane analyze the combinatorics of the Gale dual vector configuration. This approach permits us to incorporate arbitrary linear equations and inequalities among the coefficients in a unified manner to obtain more precise bounds on the location of roots. We apply our technique to bound the location of roots of Ehrhart and chromatic polynomials. Finally, we give an explanation for the clustering seen in plots of roots of random polynomials.
Thursday May 07 2009, 15h
Algorithmic relations of the Tutte polynomial
Martin Loebl, Univerzita Karlova v PrazeAbstract
I will describe recent results in the study of some attractive optimization problems like graph isomorphism or statistics of web, which have a strong enumeration flavour.
Thursday April 30 2009, 15h
Graphs with many edges containing no complete bipartite graphs
Valentina Pepe, Universita di Napoli, Federico IIAbstract
Let H be a fixed graph. The Turan number ex(n,H) of H is the maximum number of edges in a graph with n vertices which does not contain a copy of H. When H is bipartite, the problem of finding the order of magnitude of ex(n,H) is open in most cases. When H=K_{s,t} (s>=t) is a complete bipartite graph there then it is known that ex(n,K)<(s-1)^(1/t) n^(2-1/t)+(t-1)n and there are graphs for s>(t-1)! that show that this is asymptotically tight. We shall highlight the geometry behind the constructions of these graphs by Furedi (t=2) and Alon, Ronyai and Szabo (t>2) and the role played by algebraic curves and surfaces over finite fields.
Thursday April 02 2009, 15h
Extension Diameter of Boolean Lattices
Mareike Massow, TU BerlinAbstract
The linear extension diameter of a finite poset P is the maximum distance between a pair of linear extensions of P, where the distance between two linear extensions is the number of pairs of elements of P appearing in different orders in the two linear extensions.
In this talk I will prove a formula for the linear extension diameter of Boolean lattices which was conjectured by Felsner&Reuter in '99.
We will also see that all pairs of linear extensions attaining the maximum distance have the same structure. The proof only uses elementary combinatorial arguments.
This is joint work with Stefan Felsner.
In this talk I will prove a formula for the linear extension diameter of Boolean lattices which was conjectured by Felsner&Reuter in '99.
We will also see that all pairs of linear extensions attaining the maximum distance have the same structure. The proof only uses elementary combinatorial arguments.
This is joint work with Stefan Felsner.
Thursday March 26 2009, 15h
Random graphs on surfaces
Marc Noy, UPC BarcelonaAbstract
Let A_n(g) be the number of labelled graphs on n vertices that can be embedded in the orientable surface of genus g.
Improving on previous results by McDiarmid we prove the following precise asymptotic estimate:
A_n(g) ~ c(g)*n^{5(g-1)/2-1}*gamma^n*n!
where the constant c(g) depends on the genus and gamma ~ 27.2269 is the planar growth constant determined earlier. We also show that several basic parameters, like number of edges, number of blocks, and size of the largest block, have a limit distribution law which does not depend on the genus. The proofs use the theory of enumeration of maps on surfaces (Bender, Canfield, Richmond, Wormald), the enumeration of planar graphs (Giménez, Noy), and embeding results based on the face-width parameter (Robertson, Vitray). Similar results hold for graphs embeddable in non-orientable surfaces.
Improving on previous results by McDiarmid we prove the following precise asymptotic estimate:
A_n(g) ~ c(g)*n^{5(g-1)/2-1}*gamma^n*n!
where the constant c(g) depends on the genus and gamma ~ 27.2269 is the planar growth constant determined earlier. We also show that several basic parameters, like number of edges, number of blocks, and size of the largest block, have a limit distribution law which does not depend on the genus. The proofs use the theory of enumeration of maps on surfaces (Bender, Canfield, Richmond, Wormald), the enumeration of planar graphs (Giménez, Noy), and embeding results based on the face-width parameter (Robertson, Vitray). Similar results hold for graphs embeddable in non-orientable surfaces.
Thursday March 12 2009, 15h
Extremal Graph Theory, old and new results
Miklós Simonovits , Alfred Rényi Institute of Mathematics, BudapestAbstract
In this lecture I will give a short introduction and an overview of one of the classical areas of Graph Theory, namely, of Extremal graph theory.
(a) I will start with a historical introduction: describe the roots of extremal graph theory. Then I will explain the general theory of extremal graphs, i.e. the asymptotic structure of extremal graphs and the ``reduction'' to degenerate extremal graph problems.
(b) In the second part of the lecture I shall explain the Stability method, using approximate results and self-improving estimates to get exact extremal graph theorems.
Stability results in Extremal Combinatorics mean that we first prove some structural results on the almost extremal configurations and then --using this special structure -- improve our original results, or prove sharp results, determine the exact optimum.
We discuss the application of Stability Methods in several branches of Extremal Graph Theory, primarily in Tur\'an type extremal graph problems and in Erd\H{o}s-Kleitman-Rothschild type (Erd\H{o}s-Frankl-R\"odl type) counting theorems.
I will also speak of the application of this method in several other fields.
The methods will be illustrated on old and new results.
(a) I will start with a historical introduction: describe the roots of extremal graph theory. Then I will explain the general theory of extremal graphs, i.e. the asymptotic structure of extremal graphs and the ``reduction'' to degenerate extremal graph problems.
(b) In the second part of the lecture I shall explain the Stability method, using approximate results and self-improving estimates to get exact extremal graph theorems.
Stability results in Extremal Combinatorics mean that we first prove some structural results on the almost extremal configurations and then --using this special structure -- improve our original results, or prove sharp results, determine the exact optimum.
We discuss the application of Stability Methods in several branches of Extremal Graph Theory, primarily in Tur\'an type extremal graph problems and in Erd\H{o}s-Kleitman-Rothschild type (Erd\H{o}s-Frankl-R\"odl type) counting theorems.
I will also speak of the application of this method in several other fields.
The methods will be illustrated on old and new results.
Thursday March 5 2009, 15h
Ramsey Theory and Constraint Propagation
Albert Atserias, UPC BarcelonaAbstract
Bounded consistency algorithms try to detect the unsatisfiability of a system of constraints by propagating constraints of bounded width until some plain contradiction is inferred. An on-going research program aims at classifying what types of combinatorial constraints can be solved by such algorithms. An early result along these lines is the characterization of the power of the arc-consistency algorithm. We offer an alternative proof using concept of Ramsey theory that looks more amenable to generalization.
Thursday February 26 2009, 15h
Noise Sensitivity, Noise Stability, Percolation and some connections to TCS
Gil Kalai, Hebrew University of JerusalemAbstract
Noise sensitivity was defined in a paper by Benjamini, Kalai, and Schramm (1999). A closely related notion was considered by Tsirelson and Vershik (1998). I will describe the notion of noise sensitivity of Boolean functions and some basic results and problems related to it. A fun way to explain it (especially after 2000) is in terms of the probability that small mistakes in counting the votes in an election will change the outcome. We will consider the following:
1) The definition of noise sensitivity, and how it is described in terms of the Fourier transform.
2) Noise sensitivity of the crossing event in Percolation (BKS 99, Schramm and Steiff 2005, and finally Garban, Pete, Schramm 2008 - http://front.math.ucdavis.edu/0803.3750 ), the scaling limit for the Spectral distribution (Schramm and Smirnov, 2007, GPS 2008), and dynamic percolation. (ScSt (2005), GPS (2008)). Other cases of noise sensitivity.
3) Noise stability of the majority function, of weighted majority. A conjecture regarding the situation for functions described by monotone depth monotone threshold circuits.
4) The "majority is stablest theorem" (Mossel, O'Donnell, Oleszkiewicz 05 http://front.math.ucdavis.edu/0503.5503) and the connection to hardness of approximation.
1) The definition of noise sensitivity, and how it is described in terms of the Fourier transform.
2) Noise sensitivity of the crossing event in Percolation (BKS 99, Schramm and Steiff 2005, and finally Garban, Pete, Schramm 2008 - http://front.math.ucdavis.edu/0803.3750 ), the scaling limit for the Spectral distribution (Schramm and Smirnov, 2007, GPS 2008), and dynamic percolation. (ScSt (2005), GPS (2008)). Other cases of noise sensitivity.
3) Noise stability of the majority function, of weighted majority. A conjecture regarding the situation for functions described by monotone depth monotone threshold circuits.
4) The "majority is stablest theorem" (Mossel, O'Donnell, Oleszkiewicz 05 http://front.math.ucdavis.edu/0503.5503) and the connection to hardness of approximation.
Thursday January 29 2009, 15h
Small regular bipartite graphs of girth 8
Camino Balbuena, UPC BarcelonaAbstract
Let q be a prime a power and k an integer such that 3\le k\le q. In this talk we present a method using Latin squares to construct adjacency matrices of k-regular bipartite graphs of girth 8 on 2(kq2-q) vertices. Some of these graphs have the smallest number of vertices known so far among the regular graphs with girth 8.
Thursday January 22 2009, 15h
The exterior algebra method in additive combinatorics
Gyula Karolyi, Eötvös University, BudapestAbstract
In 1994 Dias da Silva and Hamidoune solved a long-standing conjecture of Erdös and Heilbronn via the study of the spectrum of certain linear transformations of the exterior product spaces associated to the problem. Due to follow-up work of Alon, Nathanson, and Ruzsa, a more transparent proof is now available based on the so-called polynomial method. This allowed us previously to obtain structural results in this direction.
In the present talk I wish to indicate how such results can be obtained using the exterior algebra approach, and why it may be more successful on the long run than the application of the Combinatorial Nullstellensatz of Alon.
In the present talk I wish to indicate how such results can be obtained using the exterior algebra approach, and why it may be more successful on the long run than the application of the Combinatorial Nullstellensatz of Alon.
Thursday January 15 2009, 15h
Perfect Codes from Cayley Graphs over Lipschitz Integers
Carmen Martínez , Univ. CantabriaAbstract
The subject of looking for perfect error-correcting codes has deserved intense interest since the seminal work by Hamming. Decades ago, Golomb and Welch studied perfect codes for the Lee metric in multi-dimensional Torus constellations. In the present work, we fix our attention on a new class of four-dimensional signal spaces which include Tori as subcases. Our constellations are modeled by means of Cayley graphs defined over quotient rings of Lipschitz Integers. Perfect codes of length one will be provided in a constructive way by solving a typical problem of vertices domination in Graph Theory. The codewords of such perfect codes are constituted by the elements of a principal (left) ideal of the considered quotient ring. The generalization of these techniques for higher dimensional spaces are also considered in this work by modeling their signal sets through Cayley-Dickson algebras.
This is a joint work with Ramon Beivide (Dpto. Electronica y Computadores, Universidad de Cantabria) and Ernst M. Gabidulin (Department of Radio Engineering, Moscow Institute of Physics and Technology, State University).
This is a joint work with Ramon Beivide (Dpto. Electronica y Computadores, Universidad de Cantabria) and Ernst M. Gabidulin (Department of Radio Engineering, Moscow Institute of Physics and Technology, State University).
Thursday December 18, 2008, 15h
Sum-free sets, sets with small sumset and the clique number of random Cayley graphs.
Gyan Prakash, Univ. Bordeaux IAbstract
In a joint work with R. Balasubramanian and D.S. Ramana, we study sum-free subsets in finite abelian groups of type III.
A subset $A$ of an abelian group is said to be sum-free if there is no solution of the equation $x+y =z$ with $x,y, z \in A.$
Following the terminology of Ben Green and Imre Ruzsa, we say that a finite abelian group $G$ is of type III if all the divisors of the order of $G$ are congruent to $1$ modulo $3.$
In particular we obtain an upper bound for the number of sum-free subsets in a finite abelian group of type III with small exponent, which is substantially better than the bound implied by the bound for the number of sum-free subsets in an arbitrary finite abelian groups, due to Green and Ruzsa.
A subset $A$ of an abelian group is said to be sum-free if there is no solution of the equation $x+y =z$ with $x,y, z \in A.$
Following the terminology of Ben Green and Imre Ruzsa, we say that a finite abelian group $G$ is of type III if all the divisors of the order of $G$ are congruent to $1$ modulo $3.$
In particular we obtain an upper bound for the number of sum-free subsets in a finite abelian group of type III with small exponent, which is substantially better than the bound implied by the bound for the number of sum-free subsets in an arbitrary finite abelian groups, due to Green and Ruzsa.
The arguments to prove this make use of the machinery developed by Green and Ruzsa and relates the number of sum-free subsets to the number of sets with small sumset, that is the number of sets $B$ in a finite abelian group $H$ with $|B| = k_1$ and $|B+B| = k_2.$
The bounds for the number of sets with small sumset in a finite abelian group $H$ was obtained by Ben Green in case when $H$ is a vector space over a finite field. Using this he had obtained an upper bound for the Clique number of random Cayley graphs. In an another work, we generalised these results of Green and obtain a result valid for all finite abelian groups.
Thursday December 11, 2008
Construcción de grandes grafos de determinadas clases
Herbert Perez-Roses , The University of Newcastle, AustraliaAbstract
Dados un diámetro y un grado máximo, existe una cota superior para el orden de un grafo que se puede construir con estas restricciones, conocida como la cota de Moore. Sólo unos pocos grafos alcanzan esta cota, mientras que para la mayoría de las combinaciones de grado y diámetro, los mayores grafos conocidos se encuentran aun bastante lejos de la cota de Moore. El problema del grado/diámetro consiste en determinar cual es el mayor grafo que se puede construir para un grado máximo y un diámetro prefijados, y tiene dos direcciones principales:
1. Cotas superiores: Determinación de cotas superiores más ajustadas que la cota de Moore (determinar teóricamente cuál es el número máximo de vértices que puede alcanzar un grafo).
2. Cotas inferiores: Construcción de grafos cada vez más grandes, para cada combinación de grado/diámetro.
En esta segunda dirección se enmarcan diversos métodos de construcción explícita, y también los métodos basados en ordenador. Haremos un resumen de estos últimos, destacando su aplicación a la construcción de grandes grafos de clases particulares, como los grafos bipartidos, y de Cayley, a la luz de los nuevos resultados obtenidos recientemente en esa dirección.
Thursday December 4, 2008
Sylvester-Frobenius change problem for vectors
Zdzislaw Skupien , AGH University, Krakow, PolandAbstract
Fixed vectors in the m--dimensional integer lattice are called generators if they generate the lattice. An integral vector v is said to be reachable if v has representation as a nonnegative integer linear combination of generators.
If the cone C spanned by generators is pointed, a Frobenius vector is definedto be the smallest vector g such that each vector v in the interior of g + C is reachable. Given a positive integer q, a vector v is called q-fully reachable if for each nonnegative integer k<q, among the representations of v there is one in which the sum of the coefficients is congruent to 0 modulo q. We find a necessary and sufficient condition for the existence of a vector h(q), a modular pseudo-conductor, such that each vector v in h(q) + C is q-fully representable.
Detailed treatment of the case n = m+1 is presented. The formula is given for the Frobenius vector (resp. for the modular Frobenius vector which is the smallest vector g(q) such that each vector v in Int (g(q) + C) is q-fully reachable).
Moreover, a bijection between all reachable and specifed unreachable vectors is established; in modular case, too.
Related published results have been thus improved.
Cooperation with Mateusz Nikodem of AGH.
If the cone C spanned by generators is pointed, a Frobenius vector is definedto be the smallest vector g such that each vector v in the interior of g + C is reachable. Given a positive integer q, a vector v is called q-fully reachable if for each nonnegative integer k<q, among the representations of v there is one in which the sum of the coefficients is congruent to 0 modulo q. We find a necessary and sufficient condition for the existence of a vector h(q), a modular pseudo-conductor, such that each vector v in h(q) + C is q-fully representable.
Detailed treatment of the case n = m+1 is presented. The formula is given for the Frobenius vector (resp. for the modular Frobenius vector which is the smallest vector g(q) such that each vector v in Int (g(q) + C) is q-fully reachable).
Moreover, a bijection between all reachable and specifed unreachable vectors is established; in modular case, too.
Related published results have been thus improved.
Cooperation with Mateusz Nikodem of AGH.
Thursday November 27, 2008, 15h
Maps on orientable surfaces
Guillaume Chapuy, Ecole Polytechnique, ParisAbstract
Maps are combinatorial objects that describe the embedding of a graph in a (compact, orientable) surface. Until very recently, the main approaches to these objects were related to "abstract" mathematical methods, like representation of the symmetric group, matrix integrals, or power series computations.
I will describe new approaches to these objects, that stay at a purely combinatorial level. In particular, I will focus on the simplest maps, the "unicellular maps" (a.k.a. "polygon gluings"), and I will show how new bijective techniques enable to understand them (for example, count them) much more easily.
I will describe new approaches to these objects, that stay at a purely combinatorial level. In particular, I will focus on the simplest maps, the "unicellular maps" (a.k.a. "polygon gluings"), and I will show how new bijective techniques enable to understand them (for example, count them) much more easily.
Thursday November 20, 2008
Extremal examples for the Davenport constant in rank two groups
David Grynkiewicz , Graz Universitat, AustriaAbstract
An old problem in additive number theory is to determine how long a sequence of elements from a finite abelian group needs to be to guarantee that zero can be represented as the sum of terms of some subsequence. For a rank two group $G\cong C_{n}\oplus C_{m}$, where $n|m$, this number is known to be $n+m-1$. However, the structure of those subsequences of maximal length which avoid zero as a subsequence sum remains open. In this talk, we discuss an open conjecture characterizing such subsequences and the proof that this conjecture is multiplicative (that is, if the conjecture holds for $C_n\oplus C_n$ and $C_m\oplus C_m$, then it holds for $C_{nm}\oplus C_{nm}$), which allows further study of the conjecture to focus on the prime case and establishes the conjecture in several new cases as well.
Abstracto
Un problema antiguo de la teoria aditiva de los numeros pregunta que longitud es necesario para que una sequnecia de elementos de un grupo abeliano y finito contiene una subsequencia con sumo cero. Cuado el grupo es $G\cong C_{n}\oplus C_{m}$, con $n|m$, la respuesta es $n+m-1$. Pero, la estructura de las sequencias de longitud maxima sin una subsequencia con sumo cero es todavia abierta. Presentamos una conjectura abierta sobre ese tema y hablamos sobre una demostracion que esa conjectura es multiplicativa (es decir, si la conjectura es verdad para $C_n\oplus C_n$ y para $C_m\oplus C_m$ entonces es verdad para $C_{nm}\oplus C_{nm}$) con la que el caso general es ahora reducido al caso primo y además algunos nuevos casos son confirmados.
Thursday November 13, 2008
k-dominación en grafos
Adriana Hansberg, Univ. AachenAbstract
Dada una gráfica G = (V,E) y un número entero k \ge 1, un subconjunto D \subseteq V se llama k-dominante en G si todo vértice v \in V-D tiene al menos k vecinos en D. Si, de todos los conjuntos k-dominantes de G, D es uno de cardinalidad mínima, entonces D es un conjunto $k$-dominante mínimo y su cardinalidad la denotamos con \gamma_k(G). Evidentemente \gamma_k(G) \le n.
Es conocido que el problema de establecer la existencia de un conjunto k-dominante con cardinalidad menor a un entero q dado es NP-completo. Por esta razón, es natural o bien proceder a buscar cotas para el número de k-dominación \gamma_k(G) en función de otros parámetros de G como son el orden, el tamaño, el grado mínimo, el grado máximo, etc. o bien buscar su relación con otros parámetros conocidos como son el número de independencia, el número cromático y otros. En esta plática damos una introducción al concepto de k-dominación y presentamos una serie de cotas para \gamma_k(G) con respecto a otros parámetros de G. También analizaremos la estructura de ciertas familias de grafos frontera.
Es conocido que el problema de establecer la existencia de un conjunto k-dominante con cardinalidad menor a un entero q dado es NP-completo. Por esta razón, es natural o bien proceder a buscar cotas para el número de k-dominación \gamma_k(G) en función de otros parámetros de G como son el orden, el tamaño, el grado mínimo, el grado máximo, etc. o bien buscar su relación con otros parámetros conocidos como son el número de independencia, el número cromático y otros. En esta plática damos una introducción al concepto de k-dominación y presentamos una serie de cotas para \gamma_k(G) con respecto a otros parámetros de G. También analizaremos la estructura de ciertas familias de grafos frontera.
Thursday November 6, 2008
Structural Properties of Sparse Graphs
Patrice Ossona de Mendez, CNRS, ParisAbstract
Asymptotic properties of graphs (and more generally of ?nite relational structures) are expressed by colorings, separation and structural decompositions. Many of these notions can be captured by iterated edge densities of graphs.
On the other side the obstacles to decompositions lead to ?rst order properties and to dualities for special classes (bounded local expansion and nowhere dense graphs). The rich interplay of these notions will be surveyed.
On the other side the obstacles to decompositions lead to ?rst order properties and to dualities for special classes (bounded local expansion and nowhere dense graphs). The rich interplay of these notions will be surveyed.
Thursday October 30, 2008
Graph homomorphism numbers and Tutte-Grothendieck invariants.
Andrew Goodall, University of BristolAbstract
The topic of this talk comes from work in progress with Jarik Nesetril and Delia Garijo. I shall describe some results that we have been able to prove, but also indicate a few of the many open problems that remain.
I shall begin by briefly describing the two classes of graph parameter of the title, in particular using the extended definition of homomorphism numbers hom(G,H) that allows H to be a directed graph, loops permitted, with edge weights.
The intersection of these two classes comprises precisely partition functions of q-state Potts models on G (evaluations of the Tutte polynomial along certain hyperbolae). We establish that the graph H in hom(G,H) corresponding to a particular q-state Potts model on graphs G is uniquely determined. Moreover, here it suffices to determine H by evaluating hom(G,H) on a finite set of simple graphs G.
A second sort of uniqueness question arises. Given the value of hom(G,H) for a certain set of q-state Potts model graphs H, is the graph G uniquely determined?
This not only includes the long-standing questions of whether a graph is determined by its chromatic polynomial or by its Tutte polynomial, but also the new question of whether, for fixed q, a graph is determined by its q-state Potts model.
I shall begin by briefly describing the two classes of graph parameter of the title, in particular using the extended definition of homomorphism numbers hom(G,H) that allows H to be a directed graph, loops permitted, with edge weights.
The intersection of these two classes comprises precisely partition functions of q-state Potts models on G (evaluations of the Tutte polynomial along certain hyperbolae). We establish that the graph H in hom(G,H) corresponding to a particular q-state Potts model on graphs G is uniquely determined. Moreover, here it suffices to determine H by evaluating hom(G,H) on a finite set of simple graphs G.
A second sort of uniqueness question arises. Given the value of hom(G,H) for a certain set of q-state Potts model graphs H, is the graph G uniquely determined?
This not only includes the long-standing questions of whether a graph is determined by its chromatic polynomial or by its Tutte polynomial, but also the new question of whether, for fixed q, a graph is determined by its q-state Potts model.
Thursday October 16, 2008, 15h
Ramsey theory and the Regularity Lemma
Miklos Ruzsinko, Computer and Automation Research Institute, BudapestAbstract
Szemeredi's famous Regularity Lemma states that an arbitrary graph on sufficiently many vertices can be partitioned into clusters such that each bipartite graph between two clusters behave like a random graph. Recently, this method was used to obtain new results in Ramsey theory.
We will describe in this talk the method of monochromatic connected matchings invented by Luczak. This method led to several new exact bounds on Ramsey numbers, e.g., Kohayakawa, Simonovits and Skokan determined the exact 3-colored Ramsey numbers for triples of odd cycles, and Gyarfas, Sarkozy, Szemeredi and myself determined the exact 3-colored Ramsey numbers for triples of paths, affirming a 30 years old conjecture of Faudree and Schelp.
(Joint results of Gyarfas, Sarkozy, Szemeredi and myself.)
We will describe in this talk the method of monochromatic connected matchings invented by Luczak. This method led to several new exact bounds on Ramsey numbers, e.g., Kohayakawa, Simonovits and Skokan determined the exact 3-colored Ramsey numbers for triples of odd cycles, and Gyarfas, Sarkozy, Szemeredi and myself determined the exact 3-colored Ramsey numbers for triples of paths, affirming a 30 years old conjecture of Faudree and Schelp.
(Joint results of Gyarfas, Sarkozy, Szemeredi and myself.)
Dijous 9 d'Octubre 2008, 15h
On k-Walk-Regular Graphs
Miquel Angel Fiol, UPC BarcelonaAbstract
A connected graph G with diameter D is said to be k-walk-regular (0\leq k \leq D), if the number of walks of length l between vertices u and v only depends on the distance between them, provided that this distance does not exceed k. Thus, for k=0, this definition coincides with that of a walk-regular graph, where the number of cycles of length l rooted at a given vertex is a constant through all vertices of the graph. In the other extreme, for k=D, we get one of the possible definitions for a graph to be distance-regular.
In this talk we show some algebraic characterizations of k-walk-regularity, which are based on the so-called local spectrum and predistance polynomials of G. Moreover, some results concerning some parameters of a geometric nature, such as the cosines, and the spectrum of walk-regular graphs are presented.
(Joint work with C. Dalfo and E. Garriga.)
In this talk we show some algebraic characterizations of k-walk-regularity, which are based on the so-called local spectrum and predistance polynomials of G. Moreover, some results concerning some parameters of a geometric nature, such as the cosines, and the spectrum of walk-regular graphs are presented.
(Joint work with C. Dalfo and E. Garriga.)
Share: