Seminar 2012-2013

Abstract:

Dado un conjunto de n puntos en el plano uno puede preguntarse por el número de ciertas configuraciones geométricas sobre este. Por ejemplo: el número de cruces que aparecen al unir todo par de puntos con un segmento de recta; el número de triángulos vacíos; el número de ángulos obtusos etc. Generalmente se buscan conjuntos de puntos que ya sea maximicen o minimicen estos valores. Recientemente hemos usando el ordenador para hacer búsquedas de estas configuraciones. Hablaré de la experiencia que hemos tenido al respecto.

exists for general posets P, and, moreover, it is an integer. Even for posets as simple as the four-element diamond D_2, where the k-diamond D_k is the poset \{A< B_1,\ldots,B_k < C\}, the existence of \pi remains open.

However, the bounds have improved, and the conjecture has been verified for many posets, including diamonds D_k for most k. We survey the progress, including two new lines of research:

First, what happens if we exclude not just a single poset, but a given family of posets?

Second, what about the supersaturation problem, which asks how many copies of poset P must be contained in a subset family F, when given |F| is larger than La(n,P)?

This is based on studies with Andrew Dove, Ross Kang, Wei-Tian Li, and J.-S. Sereni.

For maximal planar graphs of order n>= 4, we prove that a vertex-coloring containing no rainbow faces uses at most (2n-1)/3 colors, and this is best possible. For maximal graphs embedded on the projective plane, we obtain the analogous best bound (2n+1)/3.

The main ingredients in the proofs are classical homological tools. By considering graphs as topological spaces, we introduce the notion of a null coloring, and prove that for any graph G a maximal null coloring f is such that the quotient graph G/f is a forest.

This is a joint work with Jorge L. Arocha.

We study the problem of finding large vertex symmetric digraphs with given degree Delta and diameter D.

This problem is also called the (Delta,D)-problem or the degree/diameter problem for vertex symmetric digraphs. It consists of finding vertex symmetric digraphs with the order as large as possible for a given degree and diameter.

In this talk I will discuss the paper "Large vertex symmetric digraphs." Networks 50.4 (2007): 241-250.

This paper proposes a new general family of large vertex symmetric digraphs with order:

N=(Delta+(D-1)/2)/(Delta-(D-1)/2)

and provides the best values for asymptotic values of the degree and diameter in general. Furthermore, the new family is used to obtain new large vertex symmetric digraphs by means of known compounding techniques.

The predistance polynomials of a graph $G$ are a sequence of orthogonal polynomials obtained from the spectrum of (the adjacency matrix $A$ of) $G$. When $G$ is distance-regular, they turn to be the distance polynomials which, when applied at $A$, give the distance matrices of $G$. In this talk we recall the main properties of the predistance polynomials and survey some of their (old and new) applications in describing the structure of $G$.

The concept of a spherical design was introduced by Delsarte, Goethals, and Seidel [1]. A set of points x_1,...,x_N in the unit sphere S^d is called a spherical t-design if the average value of any polynomial p of degree at most t on this set equals the average value of p on the whole sphere S^d.

Delsarte, Goethals, and Seidel [1] proved that for each natural d there is a positive constant c(d) such that for each t the minimal number N(d; t) of points in a spherical t-design on S^d is not less than c(d)t^d.

Korevaar and Meyers [2] conjectured that for each d there is a constant C(d) such that N(d; t) < C(d)t^d for all t. Our main result is a proof of the above conjecture.

Various generalizations of our result and related problems will be also discussed.

[1] P. Delsarte, J.M. Goethals, J.J. Seidel, Spherical codes and designs, Geom. Dedicata, 6 (1977), 363-388.
[2] J. Korevaar, J.L. Meyers, Spherical Faraday cage for the case of equal point charges and Chebyshev-type quadrature on the sphere, Integral Transforms Spec. Funct. 1 (1993), 105-117.
[3] A. Bondarenko, D. Radchenko, M. Viazovska, Optimal asymptotic bounds for spherical designs, to appear in Annals of Mathematics.

Abstract:

The circulant graph G(n;S) is a graph on vertex set V={v_0,v_1,...,v_(n-1)} with an edge joining v_i and v_j whenever i =(j + s) mod n for s in {s_1, s_2, ..., s_k}. In this talk, I will present infinite families of circulant graphs for which each graph G(n;S) has chromatic number 3.

First, I will present a family of 3-colourable circulant graphs with k chord lengths. Then I will present a family of 3-colourable circulant graphs with 2 chord lengths. I will also show that recursive circulant graphs and a class of optimal double loop graphs are 3-colourable.

This is joint work with Nenad Obradovic and Goran Ruzic.

One classical result of Freimann gives the optimal lower bound for |A+A| if A is a d-dimensional finite set in R^d.

Matolcsi and Ruzsa have recently generalized this lower bound to |A+kB| if B is a d-dimensional finite set, and A is contained in the convex hull of B. We characterize the equality case of the Matolcsi-Ruzsa bound. The argument is based partially on understanding triangulations of polytopes.

The undirected version of the x_h-product, introduced for digraphs by Figueroa-Centeno et al., is considered. It gives a generalization of the classical direct product of graphs and, motivated by it, we also recover a generalization of the classical lexicographic product of graphs that was introduced by Sabidussi in 1961. We study connectivity properties and other invariants in terms of the factors. We also present a new intersection graph that emerges when we characterize the connectivity of x_h-product of graphs.

Abstract:

A finite Frobenius group is a permutation group that is transitive but not regular such that only the identity element can fix two points. Such a group can be expressed as a semidirect product $G = K \rtimes H$, where $K$ is a nilpotent normal subgroup. A first-kind $G$-Frobenius graph is a Cayley graph on $K$ whose connection set is an $H$-orbit $S$ on $K$ that generates $K$, where $H$ is of even order or $S$ consists of involutions.

In this talk we will focus on the family of 6-valent first-kind Frobenius circulant graphs such that the underlying kernel $K$ is cyclic. We gave a classification of such circulants and showed that they are very efficient in some sense in terms of routing, gossiping and broadcasting. We proved that all 6-valent first-kind Frobenius circulants with cyclic kernels are Eisenstein-Jacobi graphs, the latter being Cayley graphs on quotient rings of the ring of Eisenstein-Jacobi integers. On the other hand, we showed that any Eisenstein-Jacobi graph with order congruent to 1 modulo 6 and underlying Eisenstein-Jacobi integer not an associate of a real integer is a cover of a 6-valent first-kind Frobenius circulant. We noticed that a distributed real-time computing architecture known as HARTS or hexagonal mesh is a special 6-valent first-kind Frobenius circulant, and is in fact the 'geometric' 6-valent circulant with a given diameter and maximum order studied by Yebra, Fiol, Morillo and Alegre in 1985.

This talk is based on joint work with Alison Thomson.

Abstract:

We show that for every epsilon > 0 there exist delta > 0 and natural number n_0 such that every 3-uniform hypergraph on n >= n_0 vertices with the property that every k-vertex subset, where k is at least delta*n, induces at least (1/4 + epsilon)*(k choose 3) edges, contains K4- as a subgraph, where K4- is the 3-uniform hypergraph on 4 vertices with 3 edges.

This question was originally raised by Erdös and Sós. The constant 1/4 is the best possible.

This is a joint work with Roman Glebov and Dan Kral.

The appearence of certain spanning subraphs in the random graph is a well-studied phenomenon in probabilistic graph theory. In this talk, we present results on the threshold for the appearence of bounded-degree spanning trees in G(n,p) as well as for the corresponding universality statements. In particular, we show hitting time thresholds for some classes of bounded degree spanning trees.

Joint work with Daniel Johannsen and Michael Krivelevich.

This talk will discuss the mismatched decoding problem. We will review the fundamental limits of mismatched channel-decoder pairs in a point-to-point setup with particular focus on random coding ensembles, achievable information rates and corresponding error exponents.

In the talk I overview some recent results for optimization problems that originate in optical networks. They deal with optimizing the utilization of regenerators (switching components that regenerate a signal after a certain distance) and ADMs (Add-Drop Multiplexers). The results include design and analysis of algorithms, complexity, approximability and on-line algorithms. Many of the results are derived for a network whose topology is a line, and they can be viewed as scheduling problems. Among the results discussed are (1) an on-line algorithm that minimizes the use of ADMs with a cost of at most 75% more than the optimum (which is best possible), (2) an inapproximability result (that is, no existence of PTAS) for the problem of using smallest number of regenerators so as to satisfy each of a given set of inputs, and (3) an approximation algorithm (with performance between 3 and 4 times the optimum) for the scheduling problem of minimizing total busy time where a machine can process a bounded number of jobs at the same time.

The talk will be self-contained, thus no a-priori knowledge is assumed for optical networks or approximation and on-line algorithms.

Suppose that $n$ drivers enter a one-way street with $n$ parking spaces, and driver $i$ drives directly to his/her favorite space, $f(i)$, parks if it is still empty or "probes" the next space, parks if it is still empty or "probes" the next space, and so on. If all of them can park without leaving the street, then $f$ is a parking function. It can be proved that the number of such functions is $(n+1)^{n-1}$, which is also the number of labeled trees with $n+1$ vertices, by a famous result of Cayley. In fact, in 1980 Kreweras defined (recursively) a bijection between the two sets such that the image of a parking function with $p$ probes is a tree with $p$ inversions, that is, with $p$ pairs of integers $(a,b)$ such that $a<b$ but vertex $a$ is on the path from vertex $b$ to vertex $n+1$.

 

Building on work of Heesung Shin, we find a (non-recursive) bijection with the same property, thus solving a problem recently posed by Stanley.

 

This is joint work with Michel Las Vergnas.

A signature on a graph is an assignment of signs (+ or -) to the edges. Resigning at a vertex $x$ is to change the signs of all the edges incident $x$. Let $\Sigma$ be the set of negative edges. Two signatures $\Sigma_1$ and $\Sigma_2$ on a same graph are said to be equivalent if one can be obtained from the other by a sequence of resigning. A signed graph, denoted $(G, \Sigma)$ is a graph together with a set of equivalent signatures.

A signed minor of $(G,\Sigma)$ is a signed graph obtained from $(G,\Sigma)$ by a sequence of (i) deleting edges or vertices, (ii) contracting positive edges and (iii) resigning. A homomorphism of $(G,\Sigma)$ to $(H, \Sigma_1)$ is homomorphism of $G$ to $H$ which preserves signs of edges with respect to some signatures $\Sigma'$ and $\Sigma_1'$ equivalent to $\Sigma$ and $\Sigma_1$ respectively.

In this talk we show that homomorphism of signed bipartite graphs captures the notion of graph homomorphisms. Thus many coloring theories on graphs can be extend to this set of signed graphs. In particular we consider possible extensions of Hadwiger's conjecture. We also show some results on the complexity of homomorphism problem for this set of signed graphs.

A t-treewidth-modulator of a graph G is a subset X of V(G) such that the treewidth of G-X is at most some constant t. In this talk, we will present an algorithm to compute a decomposition scheme for graphs G that come equipped with a t-treewidth-modulator. This decomposition, called a "protrusion decomposition", is the cornerstone in obtaining the following two main results.

We will first show that any parameterized graph problem (with parameter k) that has "finite integer index" and is "treewidth-bounding" admits a linear kernel on H-topological-minor-free graphs, where H is some arbitrary but fixed graph. A parameterized graph problem is called treewidth-bounding if all positive instances have a t-treewidth-modulator of size O(k), for some constant t. This result partially extends previous meta-theorems on the existence of linear kernels on graphs of bounded genus [Bodlaender et al., FOCS 2009] and H-minor-free graphs [Fomin et al., SODA 2010].

Our second application concerns the Planar-F-Deletion problem. Let F be a fixed finite family of graphs containing at least one planar graph. Given an n-vertex graph G and a non-negative integer k, Planar-F-Deletion asks whether G has a subset X of V(G) such that |X| < k+1 and G-X is H-minor-free for every graph H in F. Very recently, an algorithm for Planar-F-Deletion with running time 2^O(k) n^O(1) (such an algorithm is called "single-exponential") has been presented in [Fomin et al., FOCS 2012] under the condition that every graph in the family F is connected. Using our algorithm to construct protrusion decompositions as a building block, we will explain how to get rid of this connectivity constraint and present an (optimal) single-exponential algorithm for the general Planar-F-Deletion problem.

This is joint work with Eun Jung Kim, Alexander Langer, Christophe Paul, Felix Reidl, Peter Rossmanith, and Somnath Sikdar.

An identifying code is a subset of vertices of a graph such that each vertex is uniquely determined by its closed neighbourhood within the identifying code. Identifying codes are related to other identification problems such as test covers or the metric dimension. In this talk, after introducing the topic, I will present several problems on identifying codes that I have studied during my thesis, especially related to lower and upper bounds on the minimum size of an identifying code in a given graph. I will try to focus on open problems that could be the starting point of future collaborations within the group.

We present a unified framework to deal with threshold functions for the existence of certain combinatorial structures in random sets. More precisely, let Mx = 0 be a linear system of r equations and m variables, and A a random set on [n] where each element is chosen independently with the same probability. We show that, under certain conditions, there exists a threshold function for the property " A^m contains a non-trivial solution of Mx = 0 ", depending only on r and m and, furthermore, we study the behavior of the limiting probability in the threshold scale in terms of volumes of certain convex polytopes arising from the linear system under study.

Our results cover several combinatorial families, namely sets without arithmetic progressions of given length, k-sum-free sets, B_h[g] sequences and sets without Hilbert cubes of dimension k, among others.

Joint work with Ana Zumalacárregui.

Abstract:

A main result of combinatorial optimization is that clique and chromatic number of a perfect graph are computable in polynomial time (Grötschel, Lovász and Schrijver 1981).

We give a closed formula for Lovász's theta number of the powers of cycle graphs $C_k^{d-1}$ and of their complements, the circular complete graphs $K_{k/d}$. As a consequence, we establish that the circular-chromatic number of a circular-perfect graph is computable in polynomial time, which extends the above result from the chromatic number to the circular-chromatic number, and from perfect graphs to the superclass of circular-perfect graphs.

This is a joint work with Christine Bachoc and Alain Thiery.

Most of the networks and databases humans have deal with contain large albeit finite number of units. Their structure maintaining functional consistency of the components is essentially not random and calls for a precise quantitative description of relations between nodes or data units and all network parts, as having important implications for the network robustness. A network can be seen as a discrete time dynamical system possessing a finite number of states. The behavior of such a dynamical system can be studied by means of transfer operators which describe the time evolution of distributions in phase space. The transfer operator can be represented by a stochastic matrix determining a discrete time random walk on the graph in which a walker picks at each node between the various available edges with equal probability. The Laplace operator associated to random walks possesses a group generalized inverse that can be used in order to define a probabilistic Riemannian manifold with a random metric on any finite connected undirected graph, or a database. In contrast to classical graph theory paying attention to the shortest paths of least cost, in the developed probabilistic approach all possible paths between a pair of vertices in a connected graph or a pair of units in a database are taken into account, although some paths shall be more probable than others. In such a formulation of graph theory, the distance is nothing else as a "path integral". The probabilistic geometrization of data enables us to attack applied problems which could not even be started otherwise. In particular, we report on the applications of the probabilistic approach for the analysis of urban structures, evolution of languages and musical compositions.

We say that a graph property is first order expressible if it can be written as a logic sentence using universal and existential quantifiers with variables ranging over the nodes of the graph, the usual connectives AND, OR, NOT, parentheses and the relations = and ~, where x ~ y means that x and y share an edge. For example, the property that G contains a triangle can be written as

Exists x,y,z : (x ~ y) AND (x ~ z) AND (y ~ z).

Starting from the sixties, first order expressible properties have been studied extensively on the most commonly studied model of random graphs, the Erdos-Renyi model.

I will briefly discuss a number of attractive and surprising results for this model and some links to other branches of math, before describing some of my work on a different model of random graphs, the Gilbert model. The Gilbert model of random graphs is obtained as follows. We take n points uniformly at random from the d-dimensional unit torus, and join two points by an edge if and only their distance is at most r.

I will discuss joint work with S. Haber which tells a nearly complete story on first order expressible properties of the Gilbert random graph model. In particular we settle several conjectures of McColm and of Agarwal-Spencer.

Abstract:

Signed graphs are graphs with signed edges. They are commonly used to represent positive and negative relationships in social networks. While balance theory and clusterizable graphs deal with signed graphs, recent empirical studies have proved that they fail to reflect some current practices in real social networks. In this presentation we address the issue of drawing signed graphs and capturing such social interactions. We relax the previous assumptions to define an embedding as a model in which every vertex has to be placed closer to its neighbors connected via a positive edge than its neighbors connected via a negative edge in the resulting space. Based on this definition, we address the problem of deciding whether a given signed graph has a drawing in the 1-dimensional Euclidean space. We provide a polynomial time algorithm that decides if a given complete signed graph has a drawing, and provides it when applicable. When the input signed graph is not complete the recognition problem has been proved to be NP-complete. We provide a greedy heuristic that shows interesting recognition capabilities when the input is not complete.

Abstract:

We say that a linear code C is triangular representable if there exists a two dimensional simplicial complex $\Delta$ such that C is a punctured code of the kernel of the incidence matrix of $\Delta$ and there is a bijection between C and the kernel of $\Delta$ which maps minimal codewords to minimal codewords. We show that the linear codes over rationals and over GF(p), where p is a prime, are triangular representable. In the case of finite fields, we show that this representation determines the weight enumerator of C. On the other hand, we show that there exist linear codes over any field different from rationals and GF(p), p is a prime, that are not triangular representable. We show that every construction of triangular representation fails on a very weak condition that a linear code and its triangular representation have to have the same dimension.

Abstract:

I will present a collection of problems and results concerning graph colorings obtained as an effect of some local operations around vertices. A typical problem looks as follows. Suppose we are given a simple graph G, an abelian (additive) group H, and a mapping f : V (G)->H. Let s(v) denote the sum of elements of H assigned to the neighbors of vertex v by the mapping f. We say that G is H-colorable if there is a mapping f such that s(u) is different from s(v) for each pair of adjacent vertices u and v. The minimum order of a group H for which G is H-colorable is called the additive chromatic number of G, denoted by \chi+(G). Is it true that \chi+(G) stays bounded for graphs of bounded chromatic number (G)? The answer is not known even for bipartite graphs. Nevertheless, we conjecture that \chi+(G) <=\chi (G)+1 for every graph G. So far we only know that \chi+(G) is bounded for graphs of bounded coloring number col(G). For instance, every planar graph G satisfies \chi+(G) <= 1296. A natural variation of the above problem leads to the following conjecture. For a given integer k > 1, consider a graph B_k on the set of positive integers in which ab forms an edge whenever a/b = i/j for some i, j \in { 1,2,...,k}. This graph describes a kind of arithmetic proximity, where two numbers are close to each other if their common part is so large that remainders are small. We conjecture that every graph B_k satisfies \chi(B_k) = k. This looks innocent, but notice that a weaker property that the clique number \omega (B_k) is at most k, is equivalent to the famous Graham's greatest common divisor problem (which is solved, but the full proof is rather hard). It is not hard to prove the conjecture for k = p-1, where p is a prime. We know also that it holds for k up to 194.

In this talk I will present a new approach to consecutive pattern avoiding in permutations introduced by Elizalde and Noy in 2003. This method gives a simple proof of the CMP conjecture, which was presented in this seminar some months ago by Marc Noy and has been recently proved by Elizalde. It also allows us to give general upper and lower bounds for the number of permutations of length n that avoid a pattern of length m. Finally I will discuss about the distribution of the number of permutations avoiding a pattern and show some directions where the new method could be useful, such as the avoidance of a set of patterns or the study of the correlation among different patterns.

The degree/diameter problem is to determine the largest graphs or digraphs of given maximum degree and given diameter. General upper bounds --called Moore bounds-- for the order of such graphs and digraphs are attainable only for certain special graphs and digraphs. Finding better (tighter) upper bounds for the maximum possible number of vertices, given the other two parameters, and thus attacking the degree/diameter problem `from above', remains a largely unexplored area. Constructions producing large graphs and digraphs of given degree and diameter represent a way of attacking the degree/diameter problem `from below'.

In this talk we present an overview of the problem area, some of the most recent new results, and several open problems.

Click here for the slides of the talk.

The Degree Diameter Problem is the classic problem of finding the largest graph (in terms of the number of vertices) subject to constraints of maximum degree and diameter. A variation is to consider the problem as an embedding in a given host graph. Of particular interest is when the host graph corresponds to some common parallel architecture. We will consider the problem first posed by Perez-Roses in [1] for the case of the rectangular mesh and later work on the hexagonal network.

[1] A. Dekker, H. Perez-Roses, G. Pineda-Villavicencio, and P. Watters, The Maximum Degree/Diameter-Bounded Subgraph and its Applications, Journal of Mathematical Modelling and Algorithms (2012), accepted on 25 Jan 2012, doi:10.1007/s10852-012-9182-8.

A secret-sharing scheme realizes a graph if every two vertices connected by an edge can reconstruct the secret while every independent set in the graph does not get any information on the secret. Similar to secret-sharing schemes for general access structures, there are gaps between the known lower bounds and upper bounds on the share size for graphs. Motivated by the question of what makes a graph “hard” for secret-sharing schemes, we study very dense graphs, that is, graphs whose complement contains few edges. We show that if a graph with n vertices contains n^2/2-n^{1+\beta} edges for some constant 0&#8201;&#8804;&#8201;&#946;&#8201;<&#8201;1, then there is a scheme realizing the graph with total share size of O(n^{5/4+3\beta/4}). This should be compared to O(n^2/log n) –the best upper bound known for general graphs. Thus, if a graph is “hard”, then the graph and its complement should have many edges. We generalize these results to nearly complete k-homogeneous access structures for a constant k. To complement our results, we prove lower bounds for secret-sharing schemes realizing very dense graphs, e.g., for linear secret-sharing schemes we prove a lower bound of &#937;(n^{1&#8201;+&#8201;&#946;/2}).

Abstract:

Revisaremos los ditintos grados de catenariedad definidos para monoides atómicos y las relaciones entre ellos: catenariedad, catenariedad monótona, adyacente y homogénea. Veremos cómo la catenariedad clásica se puede calcular utilizando grafos asociados a los elementos Betti. También mostraremos que, en el caso afín, la catenariedad homogénea se puede calcular mirando los grados de los polinomios de un sistema minimal de generadores del ideal asociado al monoide.