# Seminar 2008-2009

## 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, Slovakia**

*Abstract*

Thursday May 28, 2009

##### Permutaciones alternantes y gráficas completas

**Criel Merino, Instituto de Matemáticas, UNAM Mexico**

*Abstract*

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).

##### 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 Barcelona**

*Abstract*

Thursday May 07 2009, 15h

##### Algorithmic relations of the Tutte polynomial

**Martin Loebl, Univerzita Karlova v Praze**

*Abstract*

Thursday April 30 2009, 15h

##### Graphs with many edges containing no complete bipartite graphs

**Valentina Pepe, Universita di Napoli, Federico II**

*Abstract*

Thursday April 02 2009, 15h

##### Extension Diameter of Boolean Lattices

**Mareike Massow, TU Berlin**

*Abstract*

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 Barcelona**

*Abstract*

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, Budapest**

*Abstract*

(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 Barcelona**

*Abstract*

Thursday February 26 2009, 15h

##### Noise Sensitivity, Noise Stability, Percolation and some connections to TCS

**Gil Kalai, Hebrew University of Jerusalem**

*Abstract*

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.

##### Small regular bipartite graphs of girth 8

**Camino Balbuena, UPC Barcelona**

*Abstract*

^{2}-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, Budapest**

*Abstract*

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. Cantabria**

*Abstract*

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 I**

*Abstract*

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.

Thursday December 11, 2008

##### Construcción de grandes grafos de determinadas clases

**Herbert Perez-Roses , The University of Newcastle, Australia**

*Abstract*

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, Poland**

*Abstract*

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, Paris**

*Abstract*

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, Austria**

*Abstract*

*Abstracto*

Thursday November 13, 2008

##### k-dominación en grafos

**Adriana Hansberg, Univ. Aachen**

*Abstract*

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, Paris**

*Abstract*

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 Bristol**

*Abstract*

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, Budapest**

*Abstract*

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 Barcelona**

*Abstract*

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.)