Seminar 2011-2012

In the k-tournament game, the two players, called Maker and Breaker, alternately claim and direct edges from the complete graph K_n on n vertices. At the beginning of the game, Breaker chooses a goal tournament T (an orientation of the complete graph) on k vertices. Maker wins the game if her digraph contains a copy of T.

In 2008, Beck showed that the largest undirected clique Maker can build is of order k_c = (2-o(1)) log n. Based on a "random graph intuition" he conjectured that the largest k_t such that Maker wins the k_t-tournament game is of order k_t = (1-o(1)) log n.

Given n large enough, we show that Maker wins the k-tournament game for k = (2-o(1)) log n = k_c - 10. That is, building a tournament is almost as easy for Maker as building an undirected clique.

In the talk, I will explain the necessary background from positional games, the random graph intuition, and how it relates to our result.

Joint work with Dennis Clemens and Heidi Gebauer.

The combinatorial degree of a polytope is the maximal codimension of one of its interior faces. This definition is motivated from a corresponding Ehrhart-theoretic notion for lattice polytopes.

We will use Gale duality to prove that the only polytopes of combinatorial degree 1 are k-fold pyramids over polygons and k-fold pyramids over prisms over simplices.

We introduce the concept of a pentagonal geometry as a generalisation of the pentagon and the Desargues configuration, in the same vein that the generalised polygons share the fundamental properties of ordinary polygons. In short, a pentagonal geometry is a regular partial linear space in which for all points x, the points not collinear with the point x, form a line.

In the talk we will see some constructions of pentagonal geometries, obtain some non-existence results for seemingly feasible parameters and suggest a cryptographic application related to identifying codes of partial linear spaces.

I will also offer a prize to the first person to construct a pentagonal geometry with at least four points on a line with a connected deficiency graph.

Recently, it has been shown that a connected (but not necessarily regular) graph $G$ with $d+1$ distinct eigenvalues and odd-girth $2d+1$ is distance-regular. The proof of this result was based on two versions of the spectral excess theorem. In this talk we present an alternative and more direct proof which does not rely on the spectral excess theorem, but on a known characterization of distance-regular graphs in terms of the predistance polynomial of degree $d$.

(joint work with E.R. van Dam)

Abstract:

We give a method for obtaining first a projective plane of order $q$ and second the adjacency matrix of the polarity graphs of order $q$ where $q$ is a prime power. Then, we apply this result to obtain some lower bound on the extremal function $ex(n; C_4 )$, that is, the maximum number of edges of a graph free of squares.

Among other results we obtain the adjacency matrix of a $C_4$-free graph on $n=q^2-\sqrt{q}$ vertices and $\frac{1}{2} q(q^2-1)-\frac{1}{2}\sqrt{q} (q-1)$ edges when $q$ is a square prime power.

Joint work with M. Abreu and D. Labbate.

A vertex v in a graph G=(V,E) is dominated (resp. totally dominated) by a subset S of vertices  if the closed (resp. open) neighborhood of v intersects S.

A dominating set is called locating-dominating (resp. distinguishing-dominating or simply identifying) if distinct vertices not in S (resp. in V) are dominated by distinct subsets of S. Similarly, a total dominating set is locating-total dominating (resp. distinguishing-total dominating) if distinct vertices not in S (resp. in V) are totally dominated by distinct subsets of S.

In this talk we will survey a number of basic properties related to these sets, such as exact values of basic graph families, general  bounds, extremal values and bounds for trees. We will also show some of our most recent contributions to this subject, including a Nordhaus-Gaddum type result for the locating-dominating number, which is the minimum cardinality of a locating-dominating set.

Joint research work with Carmen Hernando and Mercè Mora.

We will discuss recent results and open problems on strongly regular graphs.
Special attention will be paid to the Euclidean representation of strongly regular graphs.
In particular we will outline the proof of the following our results:
There is no strongly regular graph with parameters (289,54,1,12);
there is a unique strongly regular graph with parameters (729,112,1,20) (the Games graph).

Abstract:

We study the problem of isomorphism (equivalence up to relabelling of the input variables) between two boolean functions $f,g:\{0,1\}^n \to \{0,1\}$ under the property testing framework (or, what amounts to the same thing, testing isomorphism between general hypergraphs). In the most widely studied variant of the problem, g is known  and the algorithm has black-box access to f. We present a series of recent results establishing nearly tight worst-case query-complexity bounds for the problem, as well as some progress towards the research goal of characterizing the functions g to which isomorphism can be tested with O(1) queries.

Our results also have applications to a number of other property testing problems, in particular those of testing for ``concise representations'' in the sense of Diakonikolas et al. (FOCS 2007), such as having low Fourier degree or circuits of small size. Namely, the existing upper bounds can be improved via the construction of ``sample extractors'', and new or sharper lower bounds for these problems can be derived from our lower bounds for testing isomorphism.

Based on joint work with Sourav Chakraborty, Eldar Fischer and Arie Matsliah.

Abstract:

Let $G$ be a connected graph with vertex set $V$ and a {\em weight function} $\rho$ that assigns a nonnegative number to each of its vertices. Then, the {\em $\rho$-moment} of $G$ at vertex $u$ is defined to be

$M_G^{\rho}(u)=\sum_{v\in V} \rho(v)\dist (u,v)$,

where $\dist(\cdot,\cdot)$ stands for the distance function. Adding up all these numbers, we obtain the {\em $\rho$-moment of $G$}:

$$
M_G^{\rho}=\sum_{u\in V}M_G^{\rho}(u)
=\frac{1}{2}\sum_{u,v\in V}\dist(u,v)[\rho(u)+\rho(v)].
$$

This parameter generalizes, or it is closely related to, some well-known graph invariants, such as the {\em Wiener index} $W(G)$, when $\rho(u)=1/2$ for every $u\in V$, and the {\em degree distance} $D'(G)$, obtained when $\rho(u)=\delta(u)$, the degree of vertex $u$.

In this talk we derive some exact formulas for computing the $\rho$-moment of a graph obtained by a general operation called graft product, which can be seen as a generalization of the hierarchical product,  in terms of the corresponding $\rho$-moments of its factors. As a consequence, we provide a method for obtaining nonisomorphic graphs with the same $\rho$-moment (and, hence, with equal mean distance, Wiener index, degree distance, etc). In the case when the factors are trees and/or cycles, techniques from linear algebra allow us to give formulas for the degree distance of their product.

Joint work with C. Dalfó and E. Garriga

We say that a d-polytope P is neighborly if every subset of at most d/2 vertices is a face of P. We present a new construction that uses Gale duality to build many neighborly polytopes. With it, we can prove that the number of different neighborly d-polytopes with n vertices is at least of order n^(nd/2), which even improves previously known lower bounds for the number of different combinatorial types of polytopes (not necessarily neighborly!).

Abstract:

Given a sequence of distinct positive integers s = s_1,...,s_k, the reduction st(s) is the permutation of length k obtained by relabelling the elements of s with {1,...,k} so that the order relations among the elements remains the same. For instance, st(46382) = 34251. A permutation p of length n contains a permutation \sigma of length m as a consecutive pattern if st(p_i...p_{i+m-1}) = \sigma for some i in {1,...,n-m+1}. Two permutations \sigma and \tau of the same length are called Wilf-equivalent if for all n the number of permutations of length n avoding \sigma is the same as the number of permutations avoiding \tau. We use the cluster method of Goulden and Jackson in order to enumerate permutations avoiding consecutive patterns. We reprove and generalize in a unified way several known results and obtain new results on certain patterns. Among others we solve completely the patterns 1324, 123...(s-1)(s+1)s(s+2)(s+3)...(2s), and 134...(s+1)2(s+2)(s+3)...(2s), for s > 2. We also prove several conjectures of Nakamura on Wilf-equivalence of several patterns. Finally we prove that the monotone pattern dominates asymptotically all non-overlapping patterns of the same length, thus proving a conjecture of Elizalde and Noy for a positive fraction of all patterns. This is joint work with Sergi Elizalde.

La conjetura de Erdös-Faber-Lovasz tiene 40 años y muy pocos avances. El mismo Paul Erdös la consideraba uno de sus tres problemas favoritos y se puede plantear así: dado un hipergrafo H donde cada una de sus n aristas tiene exactamente n vértices, y tal que dos aristas cualquiera se interceptan en cuando más un vértice, es posible encontrar una n-coloración de los vértices de H de modo que ninguna arista de H tenga dos vértices del mismo color. Se presenta un caso especial donde la conjetura es cierta.

Mientras la teoria de Ramsey se ocupa de estudiar la existencia de estructuras monocromáticas en universos coloreados, la teoría anti-Ramsey se ocupa de garantizar la existencia de estructuras multicolor (en la literatura llamadas rainbow). Dada una coloración de un conjunto X, decimos que un subconjunto Y de X es  multicolor si cada uno de sus elementos recibe un color diferente. Versiones aritméticas de esta teoría han sido estudiadas por Jungi\'c, Fox, Mahdian, Ne\v{s}et\v{r}il y Radoi\v{c}i\'c entre otros. Dichos autores han llamado  Rainbow Ramsey Theory a la rama específica en que la existencia de estructuras multicolor se garantiza bajo ciertas condiciones en la densidad de las clases cromáticas.

En términos generales nos interesa estudiar la ``forma'' de aquellas coloraciones que no contengan estructuras multicolor (llamaremos a estas coloraciones  libres-multicolor (rainbow-free). En vez de estudiar condiciones en el tamaño de las clases cromáticas para garantizar la existencia de estructuras multicolor, buscaremos describir todas las coloraciones libres-multicolor. En esta charla presentaremos tres resultados que siguen esta filosofía.

En el primero (trabajo conjunto con Oriol Serra) damos una caracterización estructural de las coloraciones libre-multicolor en grupos abelianos de orden impar, con respecto a progresiones aritméticas de tres términos (equivalentemente, soluciones a la ecuación x+y=2z). En el segundo (trabajo conjunto con Bernardo Llano) estudiamos una caracterización estructural análoga en grupos cíclicos de orden primo, con respecto a soluciones de la ecuación lineal en tres variables x+y=cz+d. Finalmente, presentaremos algunos avances con respecto al estudio de soluciones multicolor en  Z_p de ecuaciones lineales con cuatro variables.

We shall discuss results in additive combinatorics known as arithmetic removal-lemmas, in particular the version for the circle group, and we shall describe some applications related to solving linear equations in subsets of abelian groups.

We will discuss how graph theory can be used to bound the size of sumsets. Let  A and B be finite sets in a commutative group. A central question in the theory of set addition is bounding the size of the sumset

A+hB = {a+b_1+....+b_h : a in A ,  b_1,....,b_h in B}.

One needs information on |A| and |A+B| in order to be able to extract meaningful bounds. To keep the notation simple we assume that |A+B| \leq \alpha |A|. Imre Ruzsa has obtained a very good upper bound in terms of these two quantities. Applying a graph-theoretic method of Helmut Pl\"unnecke he showed that

|A+hB|\leq \alpha^h |A|^{2-1/h}.

Ruzsa's elegant approach,which we will present it in some detail, yields the best possible dependence on |A| and \alpha. The upper bound can nevertheless be improved as it does not have the correct dependence on the third parameter h. A refinement of Ruzsa's method gives

|A+hB|\leq \frac{\alpha^h}{h^2} |A|^{2-1/h}

We will explain the significance of this improved bound and time permitting sketch how it is obtained.

Given a class of graphs A closed under taking minors, we study the maximum degree Delta_n of random graphs from A with n vertices. We prove lower and upper bounds that hold with high probability, depending on the nature of the excluded minors. In particular, we find orders of magnitude for Delta_n not observed before, such us logn / log log logn and logn / log log log logn.

Our main tool is a counting argument introduced recently by McDiarmid and Reed for analyzing the maximum degree of random planar graphs.

Joint work with Omer Giménez and Dieter Mitsche.

Let A and B be finite subsets of a torsion-free group G. We prove that for every positive integer k there is a f(k) such that if |B|>f(k) then the inequality |AB|>|A|+|B|+k holds unless a left translate of A is contained in a cyclic subgroup. We obtain f(k) < c k^6 for arbitrary torsion-free groups, and f(k) < c k^3 for groups with the unique product property, where c is an absolute constant. We give examples to show that f(k) is at least quadratic in k.

For a graph G and a positive integer k, the rainbow k-connection number rc_k(G) is the minimum integer t such that, there exists an edge-colouring of G with t colours, where any two vertices of G are connected by k internally vertex-disjoint paths, with each path  "rainbow" (i.e., using distinct colours). The function rc_k(G) was introduced by Chartrand et al in 2008, and has since attracted considerable interest (Caro et al, Krivelevich and Yuster, Li and Sun, Schiermeyer, among others).

In this talk, we shall prove many new results concerning rc_k(G). We consider the cases when G has fixed vertex-connectivity, when G = K_{n,n}, and when G is some random graph model. We shall also present many related open problems.

Joint work with Shinya Fujita (Gunma National College of Technology, Japan) and Colton Magnant (Georgia Southern University, GA, USA).

The unimodality conjecture is proved for cyclic polytopes. A general method, based on Stanley's construction of a Pascal's type triangle, is considered to conclude about log-concavity of the face vectors of certain polytopes. A well-known necessary condition for an arbitrary (d+2)-tuple of integers to be the face vector of some d-polytope is Euler's relation. According to Euler's relation any polytope P has as many faces of even dimension as it has faces of odd dimension. As a generalization of this fact one can compare the number of faces whose dimension is congruent to i modulo m with the number of all faces of P for some positive integer m and for some 0 < i < m+1. The powers of certain doubly stochastic matrices are discussed to show that for pyramids, bipyramids, prisms and for simple polytopes the above proportion is asymptotically equal to 1/m.

Abstract:

We provide upper bounds for the determining number and the metric dimension of tournaments. A set of vertices S of  V (T ) is a /determining set/ for a tournament T if every nontrivial automorphism of T moves at least one vertex of S, while S is a /resolving set/ for T if every two distinct vertices in T have different distances to some vertex in S. We show that the minimum size of a determining set for an order n tournament (its determining number) is bounded by n/3, while the minimum size of a resolving set for an order n strong tournament (its metric dimension) is bounded by n/2. Both bounds are optimal.