Courses and seminars

ALBCOM Seminar on Algorithms and Theory of Computation COMBGRAPH Seminar on Combinatorics, Graph Theory and Applications

LIMDA Joint Seminar Announcements 2017-2018

ALBCOM Seminar on Algorithms and Theory of Computation COMBGRAPH Seminar on Combinatorics, Graph Theory and Applications GAPCOMB Geometric, Algebraic and Probabilistic Combinatorics

Forthcoming sessions and activities

Date: Wednesday  January 17, 2018


Time: 12h


Where:  Room C3-005, Campus Nord UPC

Speaker: Mattew Tointoin (Université de Neuchâtel, Switzerland.)

Title:  TBA

 

Previous sessions and activities

Date: Wednesday December 13, 2017

Time: 12h

Where:  Room C3-005, Campus Nord UPC

Speaker: Simon Griffiths (Pontifical Catholic University of Rio de Janeiro)

Title:  Title: Moderate deviations of subgraph counts

Abstract: We study the probability of deviations of subgraph counts in the Erd\H os-R\'enyi random graph $G(n,m)$.  In particular, for a particular range of moderately large deviations we determine the associated rate asymptotically.  We also discuss the relation between subgraph count deviations.

Based on joint work with Christina Goldschmidt and Alex Scott.

 

 

 

Date: Tuesday November  28, 2017

Time: 14h

Where:  Room C3-005, Campus Nord UPC

Speaker: Pablo Candela (UAM-ICMAT)

Title:  On sets with small sumset in the circle

Abstract:  It is known by a theorem of Raikov that for any measurable subset A of the circle group, if the sumset A+A has Haar measure |A+A| <1, then this measure must be at least 2|A|. We shall discuss recent joint work with Anne de Roton concerning subsets A of the circle with |A+A| < (2+c) |A|. The results include partial progress towards an analogue in this setting of a conjecture of Freiman known as the 3k-4 conjecture. We shall also discuss applications of these results to the problem of estimating how large can the measure of a subset of the circle be if the set avoids solutions to an equation of the form x+y=kz, for k>2 an integer.

 

 

 

Date: Wednesday November  22, 2017

Time: 12h

Where:  Room C3-005, Campus Nord UPC

Speaker: M. Ángeles Serrano (ICREA-UB)

Title: Multiscale unfolding of real networks by geometric renormalization

Abstract: Renormalization has proven to be a very powerful method for a rigorous investigation of systems as viewed at different distance scales. When implemented as a renormalization group to explore critical phenomena and universal properties, it is based on geometric concepts like self-similarity and scale-invariance. In complex networks multiple scales coexist but, due to the small world property, are so entangled that a proper definition of these symmetries remained elusive. However, complex networks display a hidden metric structure that can be exploited to define a geometric renormalization group.

We find that real scale-free networks embedded in a hidden metric space show geometric scaling under this renormalization group transformation. This feature enables us to unfold real networks in a self-similar multilayer shell which reveals the coexisting scales and their interplay. The multiscale unfolding brings about immediate practical applications. Among many possibilities, it yields a natural way of building high-fidelity smaller-scale replicas of large real networks, and sustains the design of a new multiscale navigation protocol in hyperbolic space which boosts the success of single-scale versions.

 

 

 

Date: Wednesday November  15, 2017

Time: 12h

Where:  Room C3-005, Campus Nord UPC

Speaker: Anna de Mier (UPC)

Title:  Approximating and decomposing clutters with matroids

Abstract: There are several clutters (aka antichains of sets) that can be associated with a matroid, as the clutter of circuits, the clutter of bases or the clutter of hyperplanes. This talk is about the following question: given an arbitrary clutter L, which are the matroidal clutters that are closest to L? To answer it we must first decide on the meaning of closest, and select one of the different matroidal clutters.
We show that for almost all reasonable choices above there is a finite set of matroidal clutters that approximate L and, moreover, that L can be recovered from them. We speak in this case of a decomposition of L. In addition to proving the existence of the decompositions
theoretically, we also give an algorithmic procedure to compute them.
The same framework also allows us to decompose matroidal clutters of non-representable matroids into representable ones, or into other classes of matroids. More generally, we prove that under mild conditions one can decompose the the clutter L with members of a favourite family of clutters, not necessarily a matroidal one.

This is joint work with Jaume Martí-Farré.

 

 

Date: Wednesday November 8, 2017

Time: 12h

Where:  Room C3-005, Campus Nord UPC

Speaker: Maximilian Wötzel (UPC-BGSMath)

Title:  On Testing Minor-Freeness in Bounded Degree Graphs with One-Sided Error

Abstract: We present a one-sided error property testing algorithm for H-minor freeness in bounded-degree
graphs for any minor H that is a minor of the (k \times 2)-grid (for any positive integer k). This
includes, for example, testing whether a graph is a cactus graph and testing minor-freeness for minors
which are cycles with parallel chords. The query complexity of our algorithm in terms of the number of
vertices in the graph, n,  is \tilde{O}(n^{2/3} / \eps^5).

Czumaj et~al. showed that C_k-minor freeness can be tested with query complexity \tilde{O}(\sqrt{n}). In
contrast to these results, we analyze the structure of the graph and show that either we can find a
subgraph of sublinear size that includes the forbidden minor, H, or we can find a pair of disjoint
subsets of vertices whose edge-cut is large, and such that the induced subgraph of each subset is
connected. We then prove a combinatorial lemma which shows that the latter structure includes H as a
minor.

 

 

 

 

Date: Wednesday October 25, 2017

Time: 12h

Where:  Room C3-005, Campus Nord UPC

Speaker: Christoph Spiegel (UPC)

Title:  Sparse Supersaturation and Extremal Results for Linear Homogeneous SystemsAbstract: We study the thresholds for the property of containing a solution to a linear homogeneous system in random sets. We expand a previous sparse Szémeredi-type result of Schacht to the broadest class of matrices possible. We also provide a shorter proof of a sparse Rado result of Friedgut, Rödl, Ruciński and Schacht based on a hypergraph container approach due to Nenadov and Steger. Lastly we further extend these results to include some solutions with repeated entries using a notion of non-trivial solutions due to Rúzsa as well as Rué et al.

 

 

Date: Wednesday October 18

Time: 12h

Where:  Room C3-005, Campus Nord UPC

Speaker: Gonzalo Fiz (UPC-BGSMath)

Title: The triangle-free process and R(3,k)

Abstract: Consider the following random graph process (G_m)_{m\in \N} on the vertex set [n] . Let G_0 be the empty graph and, for each m \in \N, let G_m be obtained from G_{m−1} by adding a single edge, chosen uniformly from those non-edges of G_{m−1} which do not create a triangle. The process ends when we reach a maximal triangle-free graph; we denote by G_{n,\triangle} this (random) final graph. This "triangle-free process" was suggested by Bollob\'as and Erd\H{o}s in 1990 as a possible method of producing good Ramsey graphs, but until Bohman's breakthrough paper in 2009, which determined the order of magnitude of e(G_{n,\triangle}), very little was known about the random triangle-free graph G_{n,\triangle} it produces.

A technique which has proved extremely useful in the study of random graph processes is the so-called ‘differential equations method’, which was introduced by Wormald in the late 1990s. In this method, the idea is to ‘track’ a collection of graph parameters, by showing that (with high probability) they closely follow the solution of a corresponding family of differential equations.

The aim of this talk is to give an overview of this method and to discuss a recent refinement of Bohman's result, which determines asymptotically the number of edges in G_{n,\triangle}, and moreover shows that it shares many properties with the Erd\H{o}s-R\'enyi random graph G(n,m) of the same density. As an application, we improve Kim's lower bound on the Ramsey number R(3,k), obtaining a bound within a factor of four of Shearer's upper bound.

This is joint work with Simon Griffiths and Rob Morris. Similar results were obtained independently by Tom Bohman and Peter Keevash.



LIMDA Joint Seminar Announcements 2016-17

ALBCOM Seminar on Algorithms and Theory of Computation COMBGRAPH Seminar on Combinatorics, Graph Theory and Applications

Forthcoming sessions and activitie

 

Previous sessions and activities

Date: Thursday July 6, 2017

Time:
12h

Where: 
Room C3-005, Campus Nord UPC

Speaker:
Miquel Angel Fiol, UPC Barcelona

Title:
The spectra of liffted digraphs

Abstract:
We present a method to derive the complete spectrum of the lift $\Gamma^\alpha$ of a base digraph $\Gamma$, with voltage assignment $\alpha$ on a (finite) group $G$.
The method is based on assigning to $\Gamma$  a quotient-like matrix whose entries are elements of the group algebra $\mathds{C}[G]$, which fully represents $\Gamma^{\alpha}$. This allows us to derive the eigenvectors and eigenvalues of the lift in terms of those of the base digraph and the irreducible characters of $G$.
Thus, our main theorem generalize some previous results of Lovász and Babai concerning the spectra of Cayley digraphs. (joint work with C. Dalfó and J. Sirán)



Date: Thursday June 29, 2017

Time:
12h

Where: 
Room C3-005, Campus Nord UPC

Speaker:
Mohan Prabu, British University, Hanoi (Vietnam)

Title:
Product of digraphs, (super) edge-magic valences and related problems

Abstract:
A (p, q)-graph G is called edge-magic if there is a bijective function f : V(G)∪E(G) → {1,2,...,p+q} such that the sum f(x)+f(xy)+f(y) for any xy in E(G) is constant. Such a function is called an edge-magic labelling of G and the constant is called the valence. An edge-magic labelling with the extra property that f (V (G)) = {1, 2, ..., p} is called super edge-magic. A graph is called perfect (super) edge-magic if all theoretical (super) edge-magic valences are possible.
In this seminar, we will present some results related to:
-the valences of (super) edge-magic labelings of crowns Cm ⊙ Kn, where m = pq, p and q are different odd primes;
-the edge-magic valences of cycles (motivated by the conjecture of Godbold and Slated which states that all cycles, or order n > 7 are perfect edge-magic).
Finally, we will discuss the super edge-magicness of some graphs of equal order and size (motivated by their applications by means of the ⊗h-product).



Date: Thursday, June 15, 2017

Time: 
10:00-11:30

Where: 
Room S05, FME, Campus Sud UPC

Speaker: 
Benny Sudakov, ETH, Zurich

Title: 
Rainbow cycles and trees in properly edge-colored complete graphs

Abstract: 
A rainbow subgraph  of  a  properly  edge-colored  complete  graph  is a
subgraph  all of  whose  edges  have different colors.  One reason to study
such subgraphs arises from the canonical version of Ramsey's theorem,
proved by Erdos and Rado. Another motivation comes from problems in
design theory. In this talk we discuss several old conjectures about
finding spanning rainbow cycles and trees in properly edge-colored complete
graphs and present some recent progress on these problems.

Joint work with A. Pokrovskiy and in part with N. Alon




Date: 
Thursday, June 15, 2017

Time: 
12:00-13:00

Where: 
Room S05, FME, Campus Sud UPC

Speaker: 
Dieter van Melkebeek, University of Wisconsin-Madison, USA

Title: 
Kernelization lower bounds from AP(3)-free sets

Abstract: 
Many hard computational problems contain a parameter k other than the
input size n that has a large impact on the computational complexity but
in practice only takes on small values. A good example is the vertex
cover problem, where one seeks a subset of at most k vertices of a given
n-vertex graph that hit every edge of the graph. The trivial algorithm
runs in time O(n^k), but there exist algorithms that take time
O(f(k)+n^c) where c is a constant and f is an arbitrary function - a
running time that is typically much better than the trivial algorithm.

One way to achieve such running times is through kernelization: Reduce
in time polynomial in n to an equivalent instance of size bounded by
some function g of the parameter k only, and then run a brute-force
algorithm on the reduced instance. In order to obtain good parameterized
algorithms, the functions f and g should not behave too badly, which
motivates the quest for kernels of small size g(k).

For the vertex cover problem, the best known kernelizations yield graphs
with O(k^2) edges. If P=NP there trivially exist kernelizations with
O(1) edges. Under a hypothesis that is considered not much stronger than
P<>NP, we'll show that kernelizations with O(k^{2-epsilon}) edges do not
exist for any positive constant epsilon. The proof hinges on the
existence of AP(3)-free sets of high density, i.e., large subsets of
{1,2,...,N} that do not contain arithmetic progressions of length 3.

Similar results hold for other NP-complete problems. For example, under
the same hypothesis we can show that for any constant d>=3, d-CNF
formulas cannot be sparsified in polynomial time below the trivial bound
of O(n^k) bits while preserving satisfiability.

In fact, the results can be cast more generally as (conditional) lower
bounds on the communication cost in the following two-player
communication protocol to decide certain languages L: Alice holds he
entire input x but is polynomially bounded; Bob is computationally
unbounded but does not know any part of x; their goal is to
cooperatively decide whether x belongs to L at small cost, where the
cost measure is the number of bits of communication from Alice to Bob.
As another application, under the same hypothesis we show the optimality
of the size of the known probabilistically checkable proofs (PCPs) for
the satisfiability problem on d-CNF formulas.




Date: Tuesday June 6, 2017

Time: 10h30-11h15

Where:  Room 103, Facultat de Matematiques i Estadistica, Campus Sud UPC

Speaker: Robert Hancock, Univ. of Birmingham

Title: Independent sets in hypergraphs and Ramsey properties of graphs and the integers

Abstract: Many important problems in combinatorics and other related areas can be phrased in the language of independent sets in hypergraphs. Recently Balogh, Morris and Samotij, and independently Saxton and Thomason developed very general container theorems for independent sets in hypergraphs; both of which have seen numerous applications to a wide range of problems. We use the container method to prove results that correspond to problems concerning tuples of disjoint independent sets in hypergraphs.
We generalise the random Ramsey theorem of Rödl and Rucinski by providing a resilience analogue. This result also implies the random version of Turán’s theorem due to Conlon and Gowers, and Schacht. We prove a general subcase of the asymmetric random Ramsey conjecture of Kohayakawa and Kreuter. Both of these results in fact hold for uniform hypergraphs. We also strengthen the random Rado theorem of Friedgut, Rödl and Schacht by proving a resilience version of the result.

 



Date: Tuesday June 6, 2017

Time: 11h30-12h30

Where:  Room 103, Facultat de Matematiques i Estadistica, Campus Sud UPC

Speaker: David Wood, Monash University

Title: Improper relaxations of Hadwiger’s Conjecture

Abstract: Hadwiger’s Conjecture asserts that every K_t-minor-free graph has a proper (t-1)-colouring. This talk is about improper relaxations of Hadwiger’s Conjecture. We prove that every K_t-minor-free graph is (2t-2)-colourable with monochromatic components of order at most ⌈(t-2)/2⌉. This result has no more colours and much smaller monochromatic components than all previous results in this direction. We then prove that every K_t-minor-free graph is (t-1)-colourable with monochromatic degree at most t-2. This is the best known degree bound for such a result. Both these theorems are based on a simple decomposition result of independent interest.
Improper colourings are interesting for other graph classes. For example, Archdeacon (1987) proved that graphs embeddable on a fixed surface can be 3-coloured with bounded monochromatic degree. We generalise this theorem for graphs excluding a complete bipartite graph, leading to new improper colouring results for graphs with linear crossing number, graphs with given stack- or queue-number, linklessly or knotlessly embeddable graphs, graphs with given Colin de Verdière parameter, and graphs with given thickness (with relevance to the earth-moon problem).

This is joint work with Jan van den Heuvel
(arXiv:1704.06536) and Patrice Ossona de Mendez and Sang-il Oum (arXiv:1611.09060).

 



Date: T
uesday May 30, 2017

Time:
11h-11h50

Where: 
Room 103, Facultat de Matematiques i Estadistica Campus Sud UPC

Speaker:
Gilles Zemor, Univ. Bordeaux

Title:
Unconditionally private communication through error correction
Abstract:
In the model that has become known as "Perfectly Secure Message Transmission"(PSMT), a sender Alice is
connected to a receiver Bob through n parallel two-way channels. A computationally unbounded adversary
Eve controls t of these channels, meaning she can acquire and alter any data that is transmitted over
these channels. The sender Alice wishes to communicate a secret message to Bob privately and reliably,
i.e. in such a way that Eve will not get any information about the message while Bob will be able to
recover it completely.

In this talk, we focus on protocols that work in two transmission rounds for n= 2t+1. We break from
previous work by following a conceptually simpler blueprint for achieving a PSMT protocol. We reduce the
previously best-known communication complexity, i.e. the number of transmitted bits necessary to
communicate a 1-bit secret, from O(n^3 log n) to O(n^2 log n). Our protocol also answers a question
raised by Kurosawa and Suzuki and hitherto left open: their protocol reaches optimal transmission rate
for a secret of size O(n^2 log n) bits, and the authors raised the problem of lowering this threshold.
The present solution does this for a secret of O(n log n) bits. Additionally, we show how our protocol
can be adapted to a Network Coding context.




Date: Tuesday May 30, 2017

Time:
10h-10h45

Where: 
Room 103, Facultat de Matematiques i Estadistica, Campus Sud UPC

Speaker:
Wouter Cames van Batenburg,  Radboud University Nijmegen

Title:
Packing graphs of bounded codegree

Abstract:
Two graphs G1 and G2 of order n are said to pack if there exist injective mappings of their vertex sets
into 1,...,n such that the images of their edge sets are disjoint. A longstanding conjecture due to
Bollobas and Eldridge and, independently, Catlin, asserts that, if (Delta(G1)+1) (Delta(G2)+1) > n, then
G1 and G2 pack. We consider the validity of this assertion under the additional assumption that G1 or G2
has bounded codegree. In particular, we prove for all t>=2 that if G1 does not contain a copy of the
complete bipartite graph K_{2,t} and Delta(G1) > 17 t Delta(G2), then (Delta(G1)+1) (Delta(G2)+1) > n
implies that G1 and G2 pack.



Date: Wednesday May 17, 2017

Time:
12:00

Where:
Room C3-005, Campus Nord UPC

Speaker:
Christoph Spielgel, UPC, Barcelona

Title: Random Strategies are Nearly Optimal for Generalized van der Waerden Games

Abstract: 
We study the biased version of a strong generalization of the van der Waerden games introduced by Beck as
well as the hypergraph generalization of the biased H-games previously studied by Bednarska and Luczak . In particular,we determine the threshold biases of these games up to constant factors by proving
general winning criteria for Maker and Breaker based on their ideas. As in the result of Bednarska
and Luczak,the random strategy for Maker is again the best known strategy.




Date: Wednesday May 10, 2017

Time:
12:00

Where:
Room C3-005, Campus Nord UPC

Speaker:
Piotr Zwiernik, UPF, Barcelona

Title: Cumulants and generalizations

Abstract: Under mild conditions, moments contain all the information about the underlying probability distribution. Cumulants form a convenient alternative to moments with many useful properties. Recently cumulant-like quantities proved to be useful in operator algebra and algebraic geometry. The reasons why it is relevant to talk about cumulants in a combinatorics seminar are threefold. First, the basic theory of cumulants is very combinatorial and it parallels some of the important results for set partition lattices. Second, cumulants have been used to prove asymptotic normality of certain combinatorial quantities. Finally, cumulants were central to the development of Gian-Carlo Rota’s umbral calculus. In this talk I will present some links between combinatorics and cumulants and show how their generalizations can be useful in algebraic geometry.





Date: Wednesday April 26, 2017


Time:
12:00

Where:
Room C3-005, Campus Nord UPC

Speaker:
Clement Requilé, UPC, Barcelona

Title:
Enumeration of 4-regular planar graphs

Abstract:
In this talk, we will show how to derive the exponential generating function counting labeled 4-regular planar graphs via a system of equations. In particular, this will allow us to enumerate this family. As by-product of this method, we can also access the exponential generating functions counting 3-connected simple 4-regular maps, which turns out to be algebraic, and connected 4-regular planar graphs, which is D-finite. This is joint work with Marc Noy and Juanjo Rué.




Date: Wednesday April 5, 2017

Time: 
12:00

Where:
 Room C3-005, Campus Nord UPC

Speaker: 
Shagnik Das, Freie University Berlin

Title: 
Supersaturation for disjoint pairs

Abstract:
Let F be a family of subsets of [n] such that all sets have size k and every pair of sets has non-empty intersection.  The celebrated theorem of Erdos--Ko--Rado from 1961 says that when n \geq 2k, any such family has size at most {n-1 \choose k-1}.  This classic theorem has since inspired a great number of subsequent papers, and by now much is known about intersecting families.

One tantalising line of research, however, is to investigate what lies beyond the EKR threshold.  Once our families are larger than the EKR bound, they must contain disjoint pairs.  The supersaturation problem, first raised by Ahlswede in 1980, is to determine which families of a given size have the fewest disjoint pairs.  In this talk we shall survey the progress made since then and present some new results.  We hope to inspire you to join in on the fun, and will helpfully point out some of the pitfalls that lie in wait.

Joint work with J. Balogh, W. Gan, H. Liu, M. Sharifzadeh, B. Sudakov and T. Tran.




Date: Monday, April 3, 2017

Time: 
10:30

Where: 
Room S210, Omega (floor -2), Campus Nord UPC, Barcelona

Speaker: 
Mozhgan Pourmoradnasseri, University of Tartu, Estonia

Title: 
The (minimum) rank of typical fooling-set matrices

Abstract:

Fooling set is known under different names in computer science and
mathematics. It is usually used to provide lower bounds on some desired
computational factors. In polytope theory and combinatorial
optimization, the fooling set gives a lower bound on the extension
complexity of a polytope and the minimum size of a linear program. In
computational complexity, the logarithm of the size of a fooling set
induces a lower bound on the communication complexity of a function. In
graph theory, considering the matrix as the adjacency matrix of a
bipartite graph, the fooling set corresponds to a cross-free matching,
which provides a lower bound on the size of the biclique covering of a
graph. A fooling-set matrix is a square matrix with nonzero diagonal,
but at least one in every pair of diagonally opposite entries is 0.
Dietzfelbinger et al. ’96 proved that the rank of such a matrix is at
least \sqrt{n}, for a matrix of order n. It is known that the bound is
tight (up to a multiplicative constant). Due to the diverse application
of fooling set type lower bounds in deferent areas, knowing a priori
upper bound on the size of the fooling set can show the usefulness of
the method in advance. In this talk, the typical minimum rank of a
fooling-set matrix will be discussed: For a fooling-set zero-nonzero
pattern chosen at random, is the minimum rank of a matrix with that
zero-nonzero pattern over a field F closer to its lower bound \sqrt{n}
or to its upper bound n? We study random patterns with a given density
p, and prove an \Omega(n) bound for the cases when (a) p tends to 0
quickly enough; (b) p tends to 0 slowly, and |F| = O(1); (c) p \in ]0,1]
is a constant.



Date: Thursday, February 23, 2017


Time: 12:00

Where: Room C3-005, Campus Nord UPC

Speaker: Camino Balbuena

Title: Vertex disjoint 4-cycles in bipartite tournaments.

Abstract: Let k ≥ 2 be an integer. Bermond and Thomassen conjectured that every
digraph with minimum out-degree at least 2k − 1 contains k vertex disjoint cycles.
In this paper we prove that every bipartite tournament with minimum out-degree at
least 2k −2 and minimum in-degree at least 1 contains k disjoint 4-cycles whenever
k ≥ 3. Also we show a bipartite tournament with out-degree 2 and in-degree 1
having no two disjoint C4. Finally, we show that every bipartite tournament with
minimum degree = min{+, −} at least 1.5k − 1 contains k disjoint 4-cycles.




Date: Thursday, February 16, 2017

Time: 12:00

Where: Room C3-005, Campus Nord UPC

Speaker: Miquel Àngel Fiol

Title: Complexity measures of edge-uncolorability in cubic graphs

Abstract: In this talk we survey the different complexity measures of edge-uncolorability in cubic graphs that have been defined in the literature, and also consider some new ones. We discuss their similarities and differences, and related results in the classification of non-edge-colorable graphs, mainly snarks (the case of cubic graphs). We prove that some of such measures are equivalent. Besides colorings,  we comment upon flows  (e.g., Tutte's 5-flow conjecture), factors (e.g., Berge's conjecture, Fulkerson's conjecture) and other structural parameters, and relate them to each other. We end by showing that, besides the objective to gain new insight into the structure of snarks, such complexity measures give partial results with respect to these important conjectures.

(joint work with G. Mazzuoccolo and E. Steffen)
 

 

 


Date: Tuesday, February 14, 2017

Time: 11:00

Where: Room S210 (floor -2), Omega, Campus Nord UPC

Speaker: Dieter van Melkebeek, University of Wisconsin - Madison, USA

Title: Derandomizing Isolation in the Space-Bounded Setting

Abstract: Isolation is the process of singling out a solution to a
problem that may have many solutions. It plays an important role in the
design of efficient parallel algorithms as it ensures that the various
parallel processes all work towards a single global solution rather than
towards individual solutions that may not be compatible with one
another. For example, the best parallel algorithms for finding perfect
matchings in graphs hinge on isolation for this reason. Isolation is
also an ingredient in some efficient sequential algorithms. For example,
the best running times for certain NP-hard problems like finding
hamiltonian paths in graphs are achieved via isolation.

All of these algorithms are randomized, and the only reason is the use
of the Isolation Lemma -- that for any set system over a finite
universe, a random assignment of small integer weights to the elements
of the universe has a high probability of yielding a unique set of
minimum weight in the system. For each of the underlying problems it is
open whether deterministic algorithms of similar efficiency exist.

This talk is about the possibility of deterministic isolation in the
space-bounded setting. The question is: Can one always make the
accepting computation paths of nondeterministic space-bounded machines
unique without changing the underlying language and without blowing up
the space by more than a constant factor? Or equivalently, does there
exist a deterministic logarithmic space mapping reduction from directed
st-connectivity to itself that transforms positive instances into ones
where there is a unique path from s to t?

I will present some recent results towards a resolution of this
question, obtained jointly with Gautam Prakriya. Our approach towards a
positive resolution can be viewed as derandomizing the Isolation Lemma
in the context of space-bounded computation.




Date: Monday, February 6, 2017

Time: 15:00

Where: Room S210 (floor -2), Omega, Campus Nord UPC

Speaker: Ilario Bonacina, Royal Institute of Technology, Stockholm, Sweden

Title: Total space in Resolution is at least width squared

Abstract: In this talk we cover some results on the space complexity of
Resolution and in particular the new recent connection between total
space and width in the title. Given a k-CNF formula F, the width is the
minimal integer W such that there exists a Resolution refutation of F
with clauses of at most W literals. The total space is the minimal size
T of a memory used to write down a Resolution refutation of F, where
the size of the memory is measured as the total number of literals it
can contain. We show that T = \Omega((W-k)^2). This connection between
total space and width relies on some basic properties of another,
perhaps less known, complexity measure in Resolution: the asymmetric
width.

The talk is based on a paper appeared in ICALP’16.

 

 

 

Date: Monday, January 30, 2017

Time: 15:00:00

Where: Room S210 (floor -2), Omega, Campus Nord UPC

Speaker: Jakob Nordström, Royal Institute of Technology, Stockholm, Sweden

Title: How Limited Interaction Hinders Real Communication (and What It
Means for Proof and Circuit Complexi

Abstract: We obtain the first true size-space trade-offs for the cutting planes
proof system, where the upper bounds hold for size and total space for
derivations with constant-size coefficients, and the lower bounds apply
to length and formula space (i.e., number of inequalities in memory)
even for derivations with exponentially large coefficients. These are
also the first trade-offs to hold uniformly for resolution, polynomial
calculus and cutting planes, thus capturing the main methods of
reasoning used in current state-of-the-art SAT solvers.

We prove our results by a reduction to communication lower bounds in a
round-efficient version of the real communication model of [Krajicek
'98], drawing on and extending techniques in [Raz and McKenzie '99] and
[Goos et al. '15]. The communication lower bounds are in turn
established by a reduction to trade-offs between cost and number of
rounds in the game of [Dymond and Tompa '85] played on directed acyclic
graphs.

As a by-product of the techniques developed to show these proof
complexity trade-off results, we also obtain an exponential separation
between monotone-AC^(i-1) and monotone-AC^i, improving exponentially
over the superpolynomial separation in [Raz and McKenzie '99]. That is,
we give an explicit Boolean function that can be computed by monotone
Boolean circuits of depth log^i n and polynomial size, but for which
circuits of depth O(log^(i-1) n) require exponential size.

This is joint work with Susanna F. de Rezende and Marc Vinyals. 

 

 

Date: Wednesday December 7 2016

Time: 12h

Where: Room C3-005, Campus Nord UPC

Speaker:  George Gottlob, University of Oxford

Title: General and Fractional Hypertree Decompositions: Hard and Easy Cases 

Abstract: Hypertree decompositions, the more powerful generalized hypertree decompositions (GHDs), and the yet more general fractional hypertree decompositions (FHD) are hypergraph decomposition methods successfully used for answering conjunctive queries and for solving constraint satisfaction problems. Each hypergraph H has a width relative to each of these methods: its hypertree width hw(H), its generalized hypertree width ghw(H), and its fractional hypertree width fhw(H), respectively. While hw(H)<=k can be checked in polynomial time, the complexity of checking whether fhw(H)<=k holds for a fixed constant k was unknown. We settle this problem by proving that checking whether fhw(H)<=k is NP-complete, even for k=2 and by same construction also the problem deciding whether ghw(H)<=k is NP-complete for k>=2. Hardness was previously known for k>=3, whilst the case k=2 has remained open since 2001.

Given these hardness results, we investigate meaningful restrictions, for which checking for bounded ghw is easy. We study classes of hypergraphs that enjoy the bounded edge-intersection property (BIP) and the more general bounded multi-edge intersection property (BMIP). For such classes, for each constant k, checking whether ghw(H) <=k, and if so, computing a GHD of width k of H is tractable and actually FPT. Finally we derive some approximability results for fhw. We consider classes of hypergraphs whose fhw is bounded by a constant k and which also enjoy the BIP or MIP, or bounded VC-dimension. For each hypergraph in such a class, we are able to compute an FHD of width O(k log k) efficiently. A different restriction on classes of hypergraphs gives a linear approximation in PTIME. Hypergraphs of bounded rank are a simple example of such a class. Joint work with Wolfgang Fischl and Reingard Pichler.

 

 

Date: Thursday 24 November 2016

Time: 13.00 **ATTENTION AT THE TIME**

Where: Room C3-005, Campus Nord UPC

Speaker: Joan Vilaltella

Title: Autograph, a simple and evolving tool for graphs / Autograph, una eina per grafs senzilla i en evolució

Abstract: There are many excellent software packages for the everyday calculation of graph properties, and other packages, also very good, for the creation of diagrams, but finding both functions in the same tool is not that easy. Autograph modestly tries to fill that void, combining the power of the NetworkX software with an edition area where graphs can be drawn as they would be drawn on a blackboard, but fostering greater interactivity, since the values of many properties are automatically updated with each modification. It is also possible to undo and redo changes, graphs can be stored and retrieved, and even different topologies can be used. We will be able to see this graph editor at work, not forgetting its possible competitors, and also to comment on which new features would be interesting for their addition in future versions.

Encara que hi ha molts paquets de programari excel·lents per fer càlculs habituals de la teoria de grafs, i altres, també molt bons, per crear diagrames, no és tan freqüent que totes dues funcions coincideixin en la mateixa eina. Autograph intenta modestament omplir aquest buit, combinant la potència del programari NetworkX amb una àrea d'edició que permet dibuixar els grafs de manera semblant a com els dibuixaríem en una pissarra, però facilitant la interactivitat, ja que els valors de diverses propietats s'actualitzen automàticament amb cada modificació. També és possible desfer i refer canvis, els grafs es poden desar i recuperar, i fins i tot es pot treballar en diferents topologies. Podrem veure aquest editor de grafs en funcionament, sense oblidar els seus possibles competidors, i també comentar quines noves característiques serien interessants per incorporar-les a futures versions.

 

 

Date: Wednesday November 23, 2016

Time: 12h

Where: Room 005, Modul C3, Campus Nord UPC

Speaker: Valentin Féray, Institut für Mathematik, Universität Zürich

Title: Weighted dependency graphs

Abstract:
The theory of dependency graphs is a powerful toolbox to prove asymptotic normality of sums of random variables. I will explain how this works, and then present a more general notion of weighted dependency graphs. Applications to random graphs, random permutations and subwords in a Markov chain will be given.


 

Date: Wednesday November 16, 2016

Time: 12h

Where: Room 005, Modul C3, Campus Nord UPC

Speaker: Michael Albert, University of Otago (New Zealand)

Title: First order logic of permutations

Abstract:
Finite permutations can be thought of as models of the theory of two linear orders. This viewpoint sits well with the study of permutation patterns since, in that context, permutation classes are simply theories with universal axioms. However, it sits much less well with the algebraic view of permutations since we cannot recover the effect of the permutation as a function. We consider some cases where it is possible to reconcile the two views and answer questions such as: in which permutation classes is it possible to recognise the existence of fixed points (or more generally k-cycles) with a formula from the logic of two linear orders?

 

 

Date: 2016-11-15 (TUESDAY)

Time: 12:00:00 

Where: Room S210 (floor -2), Omega Building, Campus Nord 

Speaker: Martin Koutecký, Department of Applied Mathematics, Charles University, Prague 

Title: Voting and Bribing in Single-Exponential Time 

Abstract:

In social choice theory, many combinatorial problems have been addressed from the viewpoint of parameterized complexity. For many of these problems, though, either their fixed-parameter tractability is not known, or the fastest known algorithms have doubly-exponential dependence on the parameters. These shortcomings (among others) led Bredereck et al. to pose their “Nine Research Challenges in Social Choice Theory”.

In this work we provide a general approach to many fundamental voting and bribing problems in social choice theory, when parameterized by the number of candidates. Our approach shows, for the first time, fixed-parameter tractability of those problems, or provides the first algorithms with singly-exponential dependence on the parameter. Thereby, we solve “Challenge #2” by Bredereck et al., and substantially contribute towards resolving their “Challenge #1”.

In particular, we show that R-Swap Bribery is fixed-parameter tractable parameterized by the number of candidates and solvable in single-exponential time, for many voting rules R; this extends an earlier double-exponential time algorithm by Dorn and Schlotter that is restricted to the unit-cost case.

 

 

Date: 2016-11-10

Time: 13:00 **ATTENTION AT THE TIME**

Where: Room 005, Modul C3, Campus Nord UPC 

Speaker: Gabriela Araujo, Universidad Nacional Autónoma de México (UNAM) 

Title: El problema de Moore en gráficas mixtas 

Abstract: En esta charla abordaremos el problema de Moore en Gráficas Mixtas, el cual fue introducido por Bosàk en 1979, a partir de ese momento este problema ha sido abordado por varios autores y se han logrado distintos resultados de los cuales hablaremos en esta charla, además expondremos nuestras recientes aportaciones en este tema. Por otro lado, buscando generalizar este problema, debido a que dicho problema está relacionado de manera natural con el problema de las Jaulas, plantearemos el problema de Jaulas Mixtas y mostraremos los avances que tenemos en dicho problema.

 

 

Date: 2016-11-03 

Time: 13:00 **ATTENTION AT THE TIME**

Where: Room 005, Modul C3, Campus Nord UPC 

Speaker: Adriana Hansberg, Universidad Nacional Autónoma de México (UNAM) 

Title: Subsecuencias de suma acotada en secuencias de -1’s y 1’s con suma acotada 

Abstract: En esta charla, presentaré el siguiente resultado:

Sean $t$, $k$ y $q$ enteros tal $q\geq 0$, $0\leq t < k$ y $t \equiv k \,({\rm mod}\, 2)$ y sea $s\in [0,t+1]$ el único entero que satisface $s \equiv q + \frac{k-t-2}{2} \,({\rm mod} \, (t+2))$. Entonces, para todo entero $n$ tal que

\[n \ge \max\left\{k,\frac{1}{2(t+2)}k^2 + \frac{q-s}{t+2}k - \frac{t}{2} + s\right\}\]

y cualquier función $f:[n]\to \{-1,1\}$ con $|\sum_{i=1}^nf(i)| \le q$, existe un subconjunto $B \subseteq [n]$ de $k$ enteros consecutivos tal que $|\sum_{y\in B}f(y)| \le t$. Este resultado es justo para todos los parámetros implicados. Daremos también una caracterización de las secuencias extremales.

Además de este teorema, presentaremos otros resultados similares involucrando diferentes subsecuencias y descomposiciones de secuencias en ciertas subsecuencias de suma acotada.

Este es un trabajo en colaboración con Yair Caro y Amanda Montejano.


 

Date: 2016-11-02 **WEDNESDAY**

Time: 12:00 

Where: Room 005, Modul C3, Campus Nord UPC 

Speaker: Arnau Padrol, Institut de Mathématiques de Jussieu, Université Pierre et Marie Curie (Paris 6) 

Title: Colorful simplicial depth, Minkowski sums, and generalized Gale transforms 

Abstract: The colorful simplicial depth of a collection of d+1 finite sets of points in Euclidean d-space is the number of choices of a point from each set such that the origin is contained in their convex hull. We use methods from combinatorial topology to prove a tight upper bound on the colorful simplicial depth. This implies a conjecture of Deza et al. (2006). Furthermore, we introduce colorful Gale transforms as a bridge between colorful configurations and Minkowski sums. Our colorful upper bound then yields a tight upper bound on the number of totally mixed facets of certain Minkowski sums of simplices. This resolves a conjecture of Burton (2003) in the theory of normal surfaces.

This is joint work with Adiprasito, Brinkmann, Paták, Patáková and Sanyal.

 

 

Date: WEDNESDAY 14 September 2016

Time: 12.00

Where: Room C3-005, Campus Nord UPC

Speaker: Domenico LABBATE

Title: Characterizations of regular graphs with conditions on their 2-factors

Coauthors: M. Abreu, M.Funk, B.Jackson, J. Sheehan et al.

Abstract: In this talk, we present existence results and partial characterizations of regular graphs having all 2–factors
Hamiltonian, isomorphic or with the same parity of number of circuits. We will present several conjectures and a
counterexample to one of those. Finally, we will investigate relations between some of these classes and the class of
snarks with all 2-factors having circuits of odd length.

 

Acknowledgements

 The activities of this seminar series are partially funded  by European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement ERC-2014-CoG 648276 AUTAR), by AGAUR (grant 2014SGR1147 and 2014SGR1034) and MINECO (projects MTM2014-54745-P, MTM2014-60127-P and TIN2013-48031-C4-1-P (TASSAT2) )

 

                                                   

LIMDA Joint Seminar Announcements 2015-2016

ALBCOM Seminar on Algorithms and Theory of Computation COMBGRAPH Seminar on Combinatorics, Graph Theory and Applications

Date: 2016-06-16


Time: 12:00

Where: Room 005, Building C3, Campus Nord UPC

Speaker: Christian Elsholtz, Graz University of Technology

Title: Hilbert cubes in arithmetic sets

Abstract:
We show upper bounds on the maximal dimension d of Hilbert
cubes H=a_0+{0,a_1}+ ... + {0, a_d} in several
sets S of arithmetic interest such as the squares. 

 

 

Date: 2016-06-02 

Time: 12:00 

Where: Room C3-005, Campus Nord UPC 

Speaker: Víctor Diego, Departament de Matemàtiques, UPC


Title: Distance mean-regular graphs 

Abstract:

We introduce the concept of distance mean-regular graph, which can be seen as a generalization of both vertex-transitive and distance-regular graphs. Let $\G$ be a graph with vertex set $V$, diameter $D$, adjacency matrix $\A$, and adjacency algebra ${\cal A}$. Then, $\G$ is {\em distance mean-regular} when, for a given $u\in V$, the averages of the intersection numbers $p_{ij}^h(u,v)=|\G_i(u)\cap \G_j(v)|$ (number of vertices at distance $i$ from $u$ and distance $j$ from $v$) computed over all vertices $v$ at a given distance $h\in \{0,1,\ldots,D\}$ from$u$, do not depend on $u$. In this work we study some properties and characterizations of these graphs. For instance, it is shown that a distance mean-regular graph is always distance degree-regular, and we give a condition for the converse to be also true. Some algebraic and spectral properties of distance mean-regular graphs are also investigated. We show that, for distance mean regular-graphs, the role of the distance matrices of distance-regular graphs is played for the so-called distance mean-regular matrices. These matrices are computed from a sequence of orthogonal polynomials evaluated at the adjacency matrix of $\G$ and, hence, they generate a subalgebra of ${\cal A}$. Some other algebras associated to distance mean-regular graphs are also characterized.

 

 

Date: 2016-05-26 

Time: 12:00 

Where: Room C3-005, Campus Nord UPC 

Speaker: Jack Koolen, University of Science and Technology of China


Title: Recent progress on 2-walk-regular graphs 

Abstract:

In this talk I will present some recent progress on 2-walk-regular graphs.

This is based on joint work with Zhi Qiao, Jongyook Park and Shao-Fei Du.

 

 

 

Date: 2016-03-17 

Time: 12:00 

Where: Room C3-005, Campus Nord UPC 

Speaker: Christoph Spiegel, Freie Universität Berlin 

Title: Threshold functions for systems of equations in random sets 

Abstract:

We present a unified framework to deal with threshold functions for the existence of solutions to systems of linear equations in random sets. This covers the study of several fundamental combinatorial families such as k-arithmetic progressions, k-sum-free sets, B_h(g)- sequences and Hilbert cubes of dimension k.

We show that there exists a threshold function for the property "A^m contains a non-trivial solution of Mx=0” where A is a random set. This threshold function depends on a parameter maximized over all subsystems, a notion previously introduced by Rödl and Rucinski. The talk will contain a formal definition of trivial solutions for any combinatorial structure, extending a previous definition by Ruzsa.

Joint work with Juanjo Rué Perna and Ana Zumalacárregui.

 

 

 

Thursday, December 10, 2015, 12h

Room C3-005, Campus Nord UPC

Miquel Àngel Fiol, UPC Barcelona

Cospectral digraphs from locally line digraphs

Abstract:

A digraph $G=(V,E)$ is a line digraph when every pair of vertices $u,v\in V$ have either equal or disjoint in-neighborhoods. When this condition only applies for vertices in a given subset, we say that $G$ is a locally line digraph. In this paper we give a new method to obtain a digraph $G'$ cospectral with a given locally line digraph $G$ with diameter $D$, where the diameter $D'$ of $G'$ is in the interval $[D-1,D+1]$.

In particular, when the method is applied to De Bruijn or Kautz digraphs, we can obtain cospectral digraphs with the same algebraic properties that characterize the formers.


Joint work with Cristina Dalfó.

 

 

COMPUTATIONAL GEOMETRY SEMINAR
Friday, December 4, 2015, 12:30-13:30  (15 minutes delayed with respect to the usual schedule)
Room S215 Omega Building, Campus Nord UPC  (equiv.: Room 215 Floor -2)

Clemens Huemer, Universitat Politècnica de Catalunya

The degree/diameter problem in maximal planar bipartite graphs


Abstract:

The $(\Delta,D)$ (degree/diameter) problem consists of finding the largest possible number of vertices $n$ among all the graphs with maximum degree $\Delta$ and diameter $D$. We consider the $(\Delta,D)$ problem for maximal planar bipartite graphs, that is, simple planar graphs in which every face is a quadrangle. We obtain that for the $(\Delta,2)$ problem, the number of vertices is $n=\Delta+2$; and for the $(\Delta,3)$ problem, $n= 3\Delta-1$ if $\Delta$ is odd and $n= 3\Delta-2$ if $\Delta$ is even. Then, we prove that, for the general case of the $(\Delta,D)$ problem, an upper bound on $n$ is approximately $3(2D+1)(\Delta-2)^{\lfloor D/2\rfloor}$, and another one is $C(\Delta-2)^{\lfloor D/2\rfloor}$ if $\Delta\geq D$ and $C$ is a sufficiently large constant. Our upper bounds improve for our kind of graphs the one given by Fellows, Hell and Seyffarth for general planar graphs. We also give a lower bound on $n$ for maximal planar bipartite graphs, which is approximately $(\Delta-2)^{k}$ if $D=2k$, and $3(\Delta-3)^k$ if $D=2k+1$, for $\Delta$ and $D$ sufficiently large in both cases.

This is a joint work with Cristina Dalfó and Julián Salas.

 

 

Wednesday, December 2nd, 2015, 12h
Room C3-005 Mòdul C3, Campus Nord

Szymon Toruńczyk, Department of CS, UPC and University of Warsaw, Poland

CSPs with infinite instances

Abstract:

Constraint Satisfaction Problems (CSP) are a generalization of 3-SAT, consisting of problems of the form: given an instance consisting of a set of variables, and a set of constraints on them (where each constraint is a relation from a fixed vocabulary on a fixed domain), decide whether there exists an assignment of domain values, which satisfies every constraint. Depending on the allowed set of relations, the CSP problem can have various complexities within NP. We consider CSP problems in which the instance is allowed to be infinite, but has a finite description (an interpretation) in a fixed, countable first-order structure with enough decidability properties, e.g. (N,=) or (Q,<). Then, I will specify tight complexity bounds for this problem, showing that the complexity increases exponentially when we allow infinite instances. In the upper bound, we use results from Ramsey theory and topological dynamics. In this talk, I will recall all the notions mentioned above, and sketch a proof of the upper bound.

 

 

 

Barcelona, 25-27 November 2015

Zero-error information, Operators, and Graphs Workshop

http://www.qciao.org/

The scope of the workshop is to bring together researchers from information and quantum information theory, combinatorics, and functional analysis, with the purpose of developing the nascent links between these fields within the recently growing area of zero-error quantum information.


Confirmed invited participants:

Aida Abiad (Maastricht), Antonio Acín (Barcelona), Sabine Burgdorf (Amsterdam), Runyao Duan (Sydney), Miquel Àngel Fiol Mora (Barcelona), Vittorio Giovannetti (Pisa), Janos Körner (Roma), Monique Laurent (Amsterdam/Tilburg), Debbie Leung (Waterloo), Laura Mančinska (Singapore/Bristol), Gláucia Murta Guimarães (Belo Horizonte), Miguel Navascués (Vienna), Carlos Ortiz (Houston), Teresa Piovesan (Amsterdam), David Roberson (Singapore/London), Ana Belén Sainz (Bristol), Florian Speelman (Amsterdam), Ivan Todorov (Belfast), Antonios Varvitsiotis (Singapore), Nik Weaver (St. Louis).


Organizers:

Andreas Winter (Barcelona), Simone Severini (London), Giannicola Scarpa (Barcelona).

 

 

 

Wednesday November 18, 2015, 12h
Room C3-005 Mòdul C3, Campus Nord UPC

Clément Requilé, Freie University, Berlin

Variants of Plane Diameter Completion

 

Abstract:

Given a plane graph G and a positive integer d, the Plane Diameter Completion problem asks whether G is a spanning subgraph of a plane graph H that has diameter at most d. Plane graphs are defined as planar graphs given together with a fixed embedding on the unit-sphere.

 

We are interested in the complexity of this problem, and to this end examine two variants of it where the input comes with another parameter k. In the first variant, k upper bounds the total number of edges to be added and in the second, k upper bounds the number of additional edges per face. Both problems appear to be NP-complete, the first even for 3-connected graphs of face-degree at most 4 and the second even when k = 1 on 3-connected graphs of face-degree at most 5.

 

A traditionnal way to deal with difficult problems is the design of parameterized algorithms, i.e. algorithms for which the complexity is polynomial in the size of the input and at least exponential in some other parameters independent of the size. This talk will be focused on the presentation of such an algorithm, solving a generalisation of both problems, that is parameterized by both k and d and run in time O(n^3) + 2^{ 2^{O((kd)^2*log(d))} }*n.

 

This talk represents joint work with Petr A. Golovach and Dimitrios M. Thilikos.

 

 

 

Thursday, November 5, 2015, 12h

Room C3-005 Mòdul C3, Campus Nord UPC

Guillem Perarnau, University of Birmingham (UK)

Connectivity in bridge-addable graph classes: the McDiarmid-Steger-Welsh conjecture

Abstract:

A class of graphs is bridge-addable if, given a graph G in the class, any graph obtained by adding an edge between two connected components of G is also in the class. We prove a conjecture of McDiarmid, Steger and Welsh, that says that if G_n is taken uniformly at random from a class of bridge-addable graphs on n vertices, then G_n is connected with probability at least exp(-1/2)+o(1), when n tends to infinity. This lower bound is asymptotically best possible and it is reached for the class of forests. Our proof uses a "local double counting" strategy that enables us to compare the size of two sets of combinatorial objects by solving a related multivariate optimization problem.
This is joint work with Guillaume Chapuy.

 

 

Wednesday, November 4, 2015, 12h

Room C3-005 Mòdul C3, Campus Nord UPC

Amanda Montejano, Instituto de Matemáticas, UNAM (Mexico)

A Rainbow Ramsey Analogue of Rado's Theorem

Abstract:

Given a rational matrix A, consider the homogeneous system of linear equations Ax=0. This system or the matrix is called k-regular, if for every k-coloring of the natural numbers the system has a monochromatic solution. A matrix is called regular if it is k-regular for all k. Generalizing both Schur and Van der Waerden's Theorems a celebrated result by Richard Rado characterizes regular matrices. In the context of the arithmetic anti-Ramsey Theory, which concerns the study of the existence of rainbow structures instead of monochromatic ones, we present a rainbow Ramsey version of Rado's Theorem. We also disprove two conjectures proposed in the literature. We use techniques from the Geometry of Numbers.

 

 

Wednesday, October 14, 2015, 12h

Room C3-005 Mòdul C3, Campus Nord UPC

Mordecai Golin, Department of Computer Science, Hong Kong University of Science and Technology

Optimal Binary Comparison Search Trees

Abstract:

Constructing optimal (minimum average search time) binary search trees (BSTs) is one of the canonical early uses of dynamic programming. In 1971, Knuth described how to solve this problem in O(n^2) time, with input specifying the probability of the different successful and unsuccessful searches. While the trees constructed were binary, the comparisons used were ternary. Successful searches terminated at internal nodes and unsuccessful searches at leaves.

By contrast, in binary comparison trees (BCSTs), internal nodes perform binary comparisons; the search branches left or right depending upon the comparison outcome and all searches terminate at leaves. Polynomial algorithms exist for solving the optimal BCST problem in special cases with input restricted to successful searches. Hu and Tucker gave an O(n log n) algorithm when all comparisons are the inequality “<”; Anderson et. al. developed an O(n^4) algorithm when both “<” and “=” comparisons are allowed.

In this talk we present the first polynomial time algorithms for solving the optimal BCST problem when unsuccessful searches are included in the input and any set of comparisons are permitted. Our running times depend upon the comparisons allowed. If equality is not allowed, our algorithm runs in O(n log n) time; if equality is allowed, O(n^4). We also demonstrate O(n) time algorithms that yield almost optimal binary comparison trees, with tree cost within constant additive factor of optimal.

This is joint work with Marek Chrobak, Ian Munro and Neal Young.

 

 

Thursday, October 1, 2015, 12h

Room C3-005 Mòdul C3, Campus Nord UPC

Ilario Bonaccina, Computer Science Department, University of Rome Sapienza, Rome, Italy

Strong Size Lower Bounds in Resolution via Games

Abstract:

The Strong Exponential Time Hypothesis (SETH) says that solving the SATISFIABILITY problem on formulas that are k-CNFs in n variables require running time 2^((1 - c_k) n) where c_k goes to 0 as k goes to infinity. Of course SETH is much stronger than P vs NP hence proving (or disproving) SETH seems to be out of reach at the moment. However one could ask if SETH is consistent with some particular algorithm or some class of algorithms. For example the fact that SETH holds for the DPLL algorithm could be derived from lower bounds on the size of tree-like resolution refutations. Despite the fact that exponential lower bounds on size of resolution proofs are 30 years old [Haken 85], only in 2000 Pudlak and Impagliazzo proved lower bounds for tree-like resolution strong enough to support SETH. Recently Beck and Impagliazzo (2013) proved that SETH is consistent with regular resolution. Informally this tell us that any SAT solver that could be formalised in regular resolution cannot disprove SETH. At the moment is not known whether SETH is consistent with full resolution, that is without constraints. Here we present a different/simpler proof of the lower bound for regular resolution by Beck and Impagliazzo. Our proof pass trough game characterisations of width and size of resolution proofs and a multiplication of strategies in those games. This technique actually works for some proof systems between regular resolution and resolution. In such systems the refutations are allowed to have some (fairly small) amount of irregularity, that is some (fairly small) number of variables is allowed to be resolved multiple times along paths of the refutations.


Joint work with N. Talebanfard (Tokyo Institute of Technology) IPEC 2015.

 

 

Thursday, September 17, 2015, 12h

Room C3-005 Mòdul C3, Campus Nord UPC

Bruce Reed, School of Computer Science, McGill Univ. (Montreal)

Random Models Of 21st Century Networks And Their Connectivity Structure


Abstract:

The traditional Erdos-Renyi model of a random network is of little use in modeling the type of complex networks which modern researchers study. It postulates that each node has the same likelihood of being attached to every other node. However, in, e.g. the web, certain authoritative pages will have many more links entering them. A 1995 paper of Molloy and Reed, cited over 1500 times, sets out some conditions guaranteeing the existence of a giant component in a network with a specified degree sequence. This work has attracted such a great deal of attention because it can be applied to random models of a wide range of complicated 21st century networks such as the web or biological networks operating at a sub-molecular level. A heuristic argument suggests that a giant component will exist provided the sum of the squares of the degrees of the nodes of the network is at least twice the sum of the degrees. Molloy and Reed proved that this is indeed true subject to certain technical conditions. Many authors, have obtained related results by specifying different technical conditions, or by tying down the size of the giant component.

Since the interest in this result is its wide applicability, it is natural to try and prove it under as few assumptions as possible. Recently, Joos, Perarnau-­Llobet, Rautenbach, and Reed proved the result under essentially no conditions.

I will present, in an accessible way, a variety of complex networks and their random models to which the Molloy-Reed result has been applied. I will then sketch the proof of our result and how it differs from the proof of the Molloy-Reed result.

 

Acknowledgements

 The activities of this seminar series are partially funded  by European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme (grant agreement ERC-2014-CoG 648276 AUTAR), by AGAUR AGAUR (grant 2014SGR1147 and 2014SGR1034) and MINECO (projects MTM2014-54745-P, MTM2014-60127-P and TIN2013-48031-C4-1-P (TASSAT2) ) 

                                                   

Seminar 2014-2015

(If you are using the Firefox web browser, you may need to reload the page to obtain its most recent version instead of the cache version.)


Sessions and activities



Thursday July 16, 2015, 12h
C3-Room 005, Campus Nord UPC

Edita Máčajová, Comenius University, Bratislava, Slovakia

Large cycles and matchings in cubic graphs

The Cycle Double Cover Conjecture claims that every bridgeless graph contains a family of cycles that together cover each edge exactly twice. This conjecture is equivalent to its restriction to the family of cubic graphs. The Fulkerson Conjecture asserts that any bridgeless cubic graphs contains a family of six perfect matchings that together cover every edge exactly twice.

We discuss old and new results and research directions on the way towards these long-standing conjectures. Our talk will include results concerning extensions, bipartizing matchings, Fano colourings, and others.

 




22nd International Colloquium on Structural Information and Communication Complexity
SIROCCO 2015

July 15-17, 2015
Montserrat, Spain

On Wednesday July 15, 14:30 - 15:20 Memorial Talk

Miquel Àngel Fiol

On the works of José Gómez. In memoriam.






Tuesday July 14, 2015, 12h
Sala d'Actes FME

 

Joan Vilaltella

Phd Defense: "Contributions to the theory of graph edge-coloring: snarks and multipoles"
Advisor: Miquel Àngel Fiol.





Monday July 6, 2015, 16h
Sala d'Actes FME

Elisabet Burjons

Master Thesis: "On-line Graph Coloring With Random Adversary"
Director: Xavier Muñoz




ADVANCED COURSE ON COMBINATORIAL MATRIX THEORY

June 29 to July 3, 2015, CRM

http://www.crm.cat/en/Activities/Curs_2014-2015/Pages/Combinatorial-Matrix-Theory.aspx

Speakers:

Richard A. Brualdi, University of Wisconsin-Madison
Angeles Carmona Mejías, Universitat Politècnica de Catalunya-BarcelonaTech
Stephen J. Kirkland, University of Manitoba
Dragan Stevanovic, Serbian Academy of Sciences and Arts (SANU)
Pauline van den Driessche, University of Victoria

Workshop on Algebraic Combinatorics

18 June 2015 at Tilburg University, The Netherlands.

Invited speakers:

Aart Blokhuis http://www.win.tue.nl/~aartb/ - Technische Universiteit Eindhoven
Sebastian Cioaba http://www.math.udel.edu/~cioaba/ - University of Delaware
Miquel Àngel Fiol http://www-ma4.upc.edu/~fiol/ - Universitat Politècnica de Catalunya
Monique Laurent http://homepages.cwi.nl/~monique/ - Centrum Wiskunde & Informatica Amsterdam/Tilburg University
Oriol Serra http://www-ma4.upc.edu/~oserra/ - Universitat Politècnica de Catalunya

http://workshoponalgebraiccombinatorics2015.weebly.com/



Wednesday June 17, 15h30
Facultat de Filosofia (UB), 4th floor
Montalegre 6, Barcelona

SET THEORY SEMINAR

Jordi López Abad, ICMAT-CSIC
Ramsey properties of finite dimensional normed spaces



WORKSHOP ON STRATEGIC BEHAVIOR AND PHASE TRANSITIONS IN RANDOM AND COMPLEX COMBINATORIAL STRUCTURES

June 8 to 12, 2015, CRM Barcelona

http://www.crm.cat/en/Activities/Curs_2014-2015/Pages/Strategic-Behaviour.aspx

 

 

 

COMPUTATIONAL GEOMETRY SEMINAR

Thursday, June 11, 2015, 15:00-16:00

Room S215 Omega Building, Campus Nord UPC
(equiv.: Room 215 Floor -2)

 

Déborah Oliveros, Universidad Nacional Autónoma de México

Helly-type theorems and beyond

 

Prof. Déborah Oliveros is visiting the CRM and UPC in the “Lluís Santaló visiting program”, a program sponsored by the Institut d’Estudis Catalans: http://www.iec.cat/

Abstract:

 

The classical Helly’s Theorem 1913 is perhaps one of the most cited theorems in Discrete Geometry and has given rise to many generalizations and interesting problems. In the past ten years, there has been a significant increase in research activity and productivity in the area. In this talk we will give a survey on this topic and present some nice applications.

 

 


COMPUTATIONAL GEOMETRY SEMINAR
Tuesday, June 9, 2015, 15:00-16:00

Room S215 Omega Building, Campus Nord UPC
(equiv.: Room 215 Floor -2)

Birgit Vogtenhuber, Technische Universität Graz, Austria

Enumerating All Good Drawings of Small Complete Graphs

Abstract:

 

Good drawings (also known as simple topological graphs) are drawings of graphs such that any two edges intersect at most once. Such drawings have attracted attention as generalizations of geometric graphs, in connection with the crossing number, and as data structures in their own right. We are in particular interested in good drawings of the complete graph. In this work, we describe our techniques for generating all different weak isomorphism classes of good drawings of the complete graph for up to nine vertices. In addition, all isomorphism classes were enumerated. As an application of the obtained data, we present several existential and extremal properties of these drawings.

 



Wednesday, June 3, 2015
Seminar at CRM (Centre de Recerca Matemàtica)

Christos Papadimitriou, University of California, Berkeley
Complexity in Game Theory

How hard is it to find an equilibrium in a game or an economy? And how relevant can this question be to Game Theory and Economics?

I shall recount and reexamine a decade of progress and debate on these questions.
Wednesday May 27
Seminar at CRM

Paul Goldberg, Oxford University
Learning game-theoretic equilibria via query protocols

In the traditional model of algorithmically solving a game, the entire game is the "input data", which is presented in its entirety to an algorithm that is supposed to compute a solution, for example an exact/approximate Nash/correlated equilibrium. In some situations it may be preferable to regard the game as a "black box" which the algorithm can find out about via queries. For example, a complete description of a multi-player game may be infeasibly large. In this talk, we give an overview of recent work on algorithms that find game-theoretic equilibria via a sequence of queries that specify pure-strategy profiles, and answer with the associated payoffs. The main research issue is "query complexity", which refers to how many queries are needed in order to find a given kind of solution.



Thursday May 21, 12h
C3-Room 005, Campus Nord, UPC

Dieter Mitsche, Univ. Nice
On the bondage number of random graphs

A dominating set of a graph is a subset D of its vertices such that every vertex not in D is adjacent to at least one member of D. The domination number of a graph G is the number of vertices in a smallest dominating set of G. The bondage number of a nonempty graph G is the size of a smallest set of edges whose removal from G results in a graph with domination number greater than the domination number of G. We study the bondage number of binomial random graph G(n,p). We obtain a lower bound that matches the order of the trivial upper bound. As a side product, we give a one-point concentration result for the domination number of G(n,p) under certain restrictions.

Joint work with X. Pérez-Giménez and P. Pralat.



Thursday May 7, 12h
C3-Room 005, Campus Nord, UPC

Ignasi Sau, CNRS-LIRMM Montpellier
The List Allocation problem and some of its applications in parameterized algorithms

In this talk we will sketch the main ideas of a Fixed-Parameter Tractable (FPT) algorithm for a quite general cut problem on general graphs, which we call List Allocation. Our algorithm strongly uses the "edge contraction" technique introduced by Chitnis et al. [2012]. Besides being a natural cut problem by itself, the relevance of List Allocation is best demonstrated by the following algorithms, which we obtain by reducing in FPT time each corresponding problem to particular cases of List Allocation:

(1) An FPT algorithm for a generalization of Digraph Homomorphism, which we call Arc-Bounded List Digraph Homomorphism.
(2) An FPT algorithm for a graph partitioning problem, called Min-Max Graph Partitioning.
(3) An FPT 2-approximation algorithm for computing the "tree-cut width" of a graph, a graph invariant recently introduced by Wollan [2013] and that has proved of fundamental importance in the structure of graphs not admitting a fixed graph as an immersion.

If time permits, we will partially discuss the above applications of our main algorithm. No previous knowledge of Paramerized Complexity will be assumed in the talk.

This is joint work with EunJung Kim, Sang-Il Oum, Christophe Paul, and Dimitrios M. Thilikos.



Thursday April 30, 12h
C3-Room 005, Campus Nord, UPC

Joaquim Bruna, UAB-CRM Barcelona

Un exemple de transferència en matemàtiques: què tenen a veure els encoders òptics amb els conjunts de Sidon, els Golomb rulers i l'autocorrelació discreta?

S'explicarà com la solució a un problema de tipus industrial proposat per una empresa al Servei de Consultoria del CRM es relaciona i serveix de nexe entre diferents camps de les matemàtiques, alguns d'ells molt treballats a nivell teòric. Això passa sovint en transferència, però en aquest cas- i això és més rar- s'explicarà com determinats teoremes de la teoria additiva de nombres mostren que la solució aportada pel CRM és òptima.



Thursday April 23, 12h

C3-Room 005, Campus Nord, UPC

 

Juraj Hromkovic, ETH Zurich

Towards a better understanding of the hardness of NP-hard optimization problems

 

We present the concept of the stability of approximation. The basic idea is to partition the set of the instances of a given hard optimization problem into infinitely many infinite classes with respect to the quality of efficiently achievable approximation. This approach enables to recognize classes of easy instances as well as to fix which kind of instances is really hard and whether the hard instances are more or few exotic or typical. In this way one revise the classification of the hardness of discrete optimization problems.

 

 

 

Thursday March 19, 12h
C3-Room 005, Campus Nord, UPC

Juanjo Rué, Freie Universitat Berlin
Arithmetic Removal Lemmas and Independent sets in hypergraphs

In the last years, several authors have studied sparse and random analogues of a wide variety of results in extremal combinatorics. Very recently, due to the work of Balogh, Morris, and Samotij, and the work of Saxton and Thomasson on the structure of independent sets on hypergraphs, several of these questions have been addressed in a new framework by using the so-called containers in hypergraphs.

In this talk I will present how to use this technology together with arithmetic removal lemmas due to Serra, Vena and Kral in the context of arithmetic combinatorics. We will show how to get sparse (and random) analogues of well-known additive combinatorial results even in the non-abelian situation.

This talk is based on a work in progress joint with Oriol Serra and Lluís Vena.



Thursday March 5, 12h
C3-Room 005, Campus Nord, UPC

Elisabet Burjons, UPC Barcelona
On-line graph coloring with random adversary

We introduce the concept of on-line algorithms under different models and assumptions, and in particular we consider the problem of on-line graph coloring. We show a new model consisting of infinite advice and random adversary and show upper and lower bounds for the expected competitive ratio in terms of the number of random bits the adversary accesses.

This is joint work with Juraj Hromkovič, Xavier Muñoz and Walter Unger.

 

 

 

Wednesday February 25, 12h
Sala d'Actes de l'FME

Lectura de la tesi doctoral d'Aaron Dall
Matroids: h-vectors, zonotopes, and Lawrence polytopes

El principal objeto de estudio de la presente tesis son las matroides, que generalizan propiedades de matrices a un contexto más combinatorio. Nos interesaremos principalmente por tres clases particulares: matroides regulares, matroides aritméticas, y matroides internamente perfectas. De estas famílias, las matroides regulares son las mejor estudiadas. En cambio, las matroides aritméticas son estructuras relativamente nuevas que capturan simultáneamente invariantes combinatorias y geométricas de configuraciones racionales de vectores. Introducimos en esta tesis la clase de matroides internamente perfectas, que nos permiten usar la estructura del orden interno de dichas matroides para probar, en este caso y suponiendo la veracidad de una afirmación, la conjetura de Stanley que cualquier h-vector de una matroide es una O-secuencia pura. Esta tesis está estructurada de la siguiente forma. En el Capítulo 1 damos los antecedentes relevantes. En el Capítulo 2 ofrecemos una nueva demostración de una generalización del teorema de Kirchhoff. Después reestructuramos el problema en el mundo de la geometría poliédrica a través de dos zonotopos determinados por una matroide regular, demostrando que los volúmenes de estos zonotopos son iguales, y construyendo una biyección explícita entre ellos (fuera de un conjunto de medida cero). Generalizamos entonces al caso de una matroide con pesos. Concluimos mostrando que nuestra técnica pude ser usada para volver a demostrar el teorema clásico de Kirchhoff, puliendo los detalles cuando las matrices tienen corrango igual a uno. Este capítulo es fruto de trabajo conjunto con Julian Pfeifle. En el Capítulo 3 sacamos provecho de una conexión entre el zonotopo y el politopo de Lawrence generado por una representación íntegra (con coeficientes enteros) de una matroide racional para probar relaciones entre varios polinomios asociados con ellos. Primero demostramos una relación entre el polinomio de Ehrhart del zonotopo y el numerador de la serie de Ehrhart del politopo de Lawrence. Al nivel de matroides aritméticas esta relación nos permite ver el numerador de la serie de Ehrhart del politopo de Lawrence como el análogo, para matroides aritméticas, del usual h-vector de la matroide. Después de demostrar el resultado mencionado, lo usamos para ofrecer una nueva interpretación de los coeficientes de una evaluación particular del polinomio aritmético de Tutte. Finalmente mostramos que el h-vector de la matroide y la serie de Ehrhart del politopo de Lawrence coinciden cuando la representación es unimodular. En el Capítulo 4 consideramos una nueva clase de matroides, cuyo orden interno las vuelve especialmente dispuestas para demostrar la conjetura de Stanley. Esta conjetura dice que para cualquier matroide existe un ideal de orden puro cuya O-secuencia coincide con el h-vector de la matroide. Damos un breve repaso de los resultados conocidos en la Sección 4.1 antes de enfocarnos en las matroides ordenadas y el orden interno en la Sección 4.2, donde también definimos las bases y matroides internamente perfectas. En la Sección 4.3 probamos resultados preliminares sobre bases internamente perfectas culminando en el Teorema 4.11, dónde mostramos que, suponiendo la veracidad de cierta afirmación, cualquier matroide perfecta satisface la conjetura de Stanley. Por otra parte, conjeturamos que esta afirmación, en efecto, es válida para todas las matroides internamente perfectas.



Joint ALBCOM/COMBGRAPH Seminar

Thursday February 19, 2015, 17h15
C3-Room 005, Campus Nord, UPC

Jaroslav Nešetřil, IUUK MFF, Charles University Prague
Sparsity and fast algorithms for combinatorial problems

Combinatorial problems model many important situations from both theoretical and applied computer science. To find broad classes of problems which can be effectively solved is of prime importance which leads to several popular dichotomies.

In the lecture we survey the recent actual development from the point of view sparse vs dense dichotomy.

(Joint work with P. Ossona de Mendez -Paris and Prague.)

 



Thursday February 19, 12h
C3-Room 005, Campus Nord, UPC

Jarek Grytczuk, Jagiellonian University in Krakow
Fanciful variations on non-repetitiveness

 

A repetition is a finite sequence whose first half looks exactly the same as the second half. For instance, aa, abab, abcabc, abacabac are repetitions. A sequence is nonrepetitive if it does not contain any repetitions (as subsequences of consecutive terms). In 1906 Thue proved that there exist arbitrarily long nonrepetitive sequences built of only three symbols. This result initiated lots of research leading to deep results, important applications, and interesting generalizations in different areas of mathematics and computer science. In the talk I will present some problems inspired by the theorem of Thue for various combinatorial structures. Here is a new one for example: suppose that we are given a finite set of lines in the plane and we want to color all intersection points of these lines so that there is no repetition on any line. How many colors are needed? It can be proved that 405 colors suffice, but it does not seem optimal.

 



Thursday February 19, 11h
C3-Room 005, Campus Nord, UPC

Aida Abiad, Tilburg University, The Netherlands
Switched symplectic graphs and their 2-ranks

We apply Godsil-McKay switching to the symplectic graphs over F_2 with at least 63 vertices and prove that the 2-rank of (the adjacency matrix of) the graph increases after switching. This shows that the switched graph is a new strongly regular graph with the same parameters as the symplectic graph over F_2 but different 2-rank.

For the symplectic graph on 63 vertices we investigate repeated switching by computer and find many new strongly regular graphs with the same parameters but different 2-ranks.

By using these results and a recursive construction method for the symplectic graph from Hadamard matrices, we also obtain several graphs with the same parameters as the symplectic graphs over F_2, but different 2-ranks.

This is joint work with Willem Haemers.


 

Thursday November 20, 2014, 12h
C3-Room 005, Campus Nord, UPC

Simeon Ball, UPC Barcelona
Applications of the polynomial method in combinatorial geometry to Kakeya and Bourgain sets

In recent years significant advances have been made in the application of algebraic methods to finite geometrical objects, see the recent survey by Tao [1]. Whether these objects are in real, finite or complex space, the finiteness of the object allows for some combinatorial methods to be used. Combining these with algebraic methods, most notably from algebraic geometry, one can hope to obtain theorems concerning the geometrical object under consideration.

In this talk I will consider Kakeya sets and Bourgain sets.

Let F be a field and let AG_k(F) denote the k-dimensional affine space over F. Let F_q denote the finite field with q elements.

A Kakeya set in AG_n(F) is a set L of lines with the property that L contains no two lines with the same direction. I will explain an iterative geometric construction of Kakeya sets in AG_n(F) starting from a Kakeya set in AG_2(F). I will say something about Dvir's proof (from [2]) that if L is a Kakeya set in AG_n(F) which contains a line in every direction then there is a constant c=c(n) such that if S is the set of points incident with some line of L then |S|>cq^n.

A Bourgain set in AG_n(F) is a set L of lines with the property that a plane contains few lines of L. Amongst other things I will sketch Guth and Katz's proof [3] that if L is a set of N^2 lines in AG_3(R), with at most N contained in any plane, and S is a set of points with the property that every line of L is incident with at least N points of S then there is a constant c such that |S|>cN^3.

Furthermore, I will talk about Ellenberg and Hablicsek's article [2] on the finite analogue of this in which L is a set of aq^2 lines in AG_3(F_q) with at most bq lines in a plane, for some constant b. They prove that if q is prime then there is a constant c=c(a,b) such that if S is the set of points incident with some line of L then |S|>cq^3. This does not hold true over non-prime finite fields and we shall also consider this finite non-prime case. I will also detail some results about Bourgain sets in higher dimensions.

[1] Zeev Dvir, On the size of Kakeya sets in finite fields, arXiv:0803.2336v3.
[2] Jordan S. Ellenberg and Márton Hablicsek, An incidence conjecture of Bourgain over fields of positive characteristic, arXiv:1311.1479v1.
[3] Larry Guth and Nets Hawk Katz, Algebraic methods in discrete analogs of the Kakeya problem, Adv. Math., 225 (2010), 2828--2839.
[4] Terence Tao, Algebraic combinatorial geometry: the polynomial method in arithmetic combinatorics, incidence combinatorics, and number theory, arXiv:1310.6482v5.



Thursday October 30, 2014, 12h
C3-Room 005, Campus Nord, UPC

Klara Stokes, University of Skövde
Pentagonal maps of Moore graphs and geometric pentagonal geometries

A map is a drawing of a graph on a Riemann surface such that the complement of the drawing is the disjoint union of finitely many topological discs called faces. It will be explained how to construct geometric point-circle configurations embedded on Riemann surfaces from uniform maps. In particular, geometric realizations of all pentagonal geometries with k lines through each point and either k or k-1 points on each line can be obtained in this way. All these pentagonal geometries come from Moore graphs. Therefore this work involves a study of maps of Moore graphs. In particular we give the minimum genus of the Hoffman-Singleton graph.

 

 

 

Thursday October 23, 2014, 12h

C3-Room 005, Campus Nord, UPC

Francesc Aguiló, UPC Barcelona
Some Structural Properties of optimal diameter 2-Cayley digraphs on finite abelian groups

Given a Cayley digraph G of degree two on a finite Abelian group, we study optimal structural properties related with the diameter. We call such a digraphs 2-Cayley digraphs. An expansion of G is a 2-Cayley digraph G' with the same generating set, that contains an isomorphic copy of G. A contraction of G is a 2-Cayley digraph G'' contained in G. Optimal digraphs that attain the diameter lower bound are called tight digraphs.

In this work we define two processes for obtaining contractions and expansions of 2-Cayley digraphs. These definitions are well suited from the metrical point of view. In particular, a contraction of an optimal diameter digraph has also optimal diameter. This is not true for expansions. Tight expansions from tight digraphs are characterized. Tight 2-Cayley digraphs having infinite tight expansions are also analized.

Joint work with A. Miralles and M. Zaragozá.

 

 


Thursday October 16, 2014, 12h
C3-Room 005, Campus Nord, UPC

Miquel Àngel Fiol, UPC Barcelona
Distance-regular graphs where the distance-d graph has fewer distinct eigenvalues

Let the Kneser graph K of a distance-regular graph Γ be the graph on the same vertex set as Γ, where two vertices are adjacent when they have maximal distance in Γ. We study the situation where the Bose-Mesner algebra of Γ is not generated by the adjacency matrix of K. In particular, we obtain strong results in the so-called 'half-antipodal' case.

(joint work with A.E. Brouwer)

 

 

 

Thursday October 9, 2014, 12h

C3-Room 005, Campus Nord, UPC

Felix Lazebnik, University of Delaware
On Graphs Defined by Some Systems of Equations

In this talk I will present a simple method for constructing infinite families of graphs defined by a class of systems of equations over commutative rings. The graphs in all such families possess some general properties including regularity or bi-regularity, existence of special vertex colorings, and existence of covering maps between every two members of the same family (hence, embedded spectra). Another general property is that nearly every graph constructed in this manner edge-decomposes either the complete, or complete bipartite, graph which it spans.

In many instances, specializations of these constructions have proved useful in various graph theory problems, but especially in many extremal problems which deal with cycles in graphs. I will explain motivations for these constructions, survey both old and new related results, applications, and state open questions.

 

 

 

Thursday October 2, 2014, 12h
C3-Room 005, Campus Nord, UPC


José Aliste-Prieto, Universidad Andrés Bello, Santiago de Chile

Recognizing caterpillars by U-polynomials

En este trabajo con J. Zamora, estudiamos como reconocer grafos tipo orugas a partir de los U-polinomios. Usando su estructura lineal, relacionamos una versión restringida del U-polinomio con una función de Schur naturalmente asociada con composiciones de enteros. Luego usamos la clasificación de equivalencias de dichas funciones de Schur para mostrar que dos orugas tendrán el mismo U-polinomio si y solo si son isomorfas.

Seminar 2013-2014

Sessions and Abstracts

Seminar sessions and other activities



Thursday July 17, 2014, 12h

C3-Room 005, Campus Nord, UPC

Mirka Miller and Joe Ryan (University of Newcastle, Australia)

Some Developments in Sum Graph Labelling

 

Abstract:

Sum graph labelling was defined by Harary in 1989. It is a labelling of vertices by unique positive integers in such a way that there is an edge between vertices labeled u and v if and only if u+v is a label of another vertex in the graph.

In this talk we will give an overview of the known results in sum graph labelling as well as the more recent developments in the so-called exclusive sum graph labelling.

The talk will finish with several open problems.

 

 

 

 

Joint ALAMA - GAMM/ANLA'2014

Facultat de Matemàtiques i Estadística (FME), July 14-16, 2014

www.cimne.com/websasp/ALAMA-GAMM/es/frontal/default.asp

 

 

 

 

JMDA 2014


IX Jornadas de Matemática Discreta y Algorítmica
Tarragona, July 7-9, 2014.

http://deim.urv.cat/~discrete-math/JMDA2014/

 

 



Thursday July 3, 2014, 12h

C3-Room 005, Campus Nord, UPC

José Ignacio Royo (Universitat del País Vasc)
Abelian and nonabelian numbers via 3D origami

Abstract:

It is well known that the description of the origami folding operations via the Huzita-Justin axioms leads to the set of points constructible with origami, which is the smallest subfield O of the complex plane which is closed under square roots, cubic roots and complex conjugation.

Those axioms form a complete set of axioms in some sense, but if we assume more moves axiomatically, the scope of the constructible points can be extended. For example, if alignments involving arbitrarily many simultaneous folds at the same time are permitted, it has been shown by Alperin and Lang that Lill’s method allows one to construct any real algebraic number.

In this talk we intend to push forward the arithmetic limits of O by introducing some manoeuvres which involve the use of the third dimension, that is, allowing the paper not to remain flat after being folded, but in such a way that actually determines new points. The moves we propose are easy to perform physically, and consist in a simple usage of a flat surface, say the table, and the rigidity properties of polyhedra. With those moves, we show that it is easy to obtain all the Abelian numbers, that is, the algebraic numbers whose Galois group is Abelian, and some other non-Abelian numbers, too. We discuss the formalization and axiomatization of those 3D manoeuvres and explore the limits of what can be achieved with those constructions, posing some open questions for further research.

Joint work with Eulàlia Tramuns.

 

 



Thursday June 26, 2014, 12h
C3-Room 005, Campus Nord, UPC

Iñaki Pelayo (UPC Barcelona)
Quasiperfect Dominations in Graphs

Abstract:

Given a graph G, a set D of vertices is a dominating set of G if every vertex not in D is adjacent to at least one vertex of D. The domination number \gamma(G) is the minimum cardinality of a dominating set of G.

If moreover, every vertex not in D is adjacent to exactly one vertex of D, then D is called a perfect dominating set of G. The perfect domination number $\gamma_ {\stackrel{}{11}}(G)$ is the minimum cardinality of a perfect dominating set of G. For every integer k>0, a dominating set D is called a k-quasiperfect dominating set if every  vertex not in D is adjacent to at most k vertices of D. The k-quasiperfect domination number $\gamma_ {\stackrel{}{1k}}(G)$ is the minimum cardinality of a k-quasiperfect dominating set of G.

Certainly, 1-quasiperfect dominating sets and \Delta-quasiperfect dominating sets are precisely the perfect dominating sets and dominating sets, respectively, where \Delta stands for the maximum degree of the graph. It is also clear that, if G is a graph of order n and maximum degree \Delta, then: $n  \ge \gamma_ {\stackrel{}{11}}(G) \ge \gamma_ {\stackrel{}{12}}(G)\ge \ldots \ge \gamma_ {\stackrel{}{1\Delta}}(G)=\ gamma(G)$.

In this talk, we present both the state of the art and our main contributions  to the study of this decreasing chain when restricting ourselves to the following graph families: graphs with maximum degree either \Delta >= n-3 or \Delta <= 3, cographs, claw-free graphs, trees, Cartesian product graphs and strong product graphs.

(Joint work with José Cáceres, Carmen Hernando, Mercè Mora and Mari Luz Puertas.)

 

 

 

 

Thursday June 19, 2014, 11h

Sala d'Actes FME

PhD defense
El problema invers en xarxes finites
Cristina Arauz

Advisors: Ángeles Carmona and Andrés Encinas

 

 

 

 

Wednesday June 18, 2014, 12h

C3-Room 005, Campus Nord, UPC

Rinovia Simantujak (ITB Bandung)
How to uniquely determine your location in a graph?
A metric dimension problem

Abstract:

The metric dimension problem was first introduced in 1975 by Slater [4], and independently by Harary and Melter [3] in 1976; however the problem for hypercube was studied (and solved asymptotically) much earlier in 1963 by Erdös and Rényi [2]. A set of vertices S resolves a graph G if every vertex is uniquely determined by its vector of distances to the vertices in S. The metric dimension of G is the minimum cardinality of a resolving set of G. An analog problem for directed graphs was then considered by Chartrand, Raines and Zhang [1] in 2000.

In this talk I will present a short historical account, known techniques, recent results, and open problems in the area of metric dimension for undirected and directed graphs.

References:

[1] G. Chartrand, M. Raines, P. Zhang, The Directed Distance Dimension of Oriented Graphs, Math. Bohemica 125 (2000) 155-168.
[2] P. Erdös and A. Rényi, On two problems of information theory, Magyar Tud. Akad. Mat. Kutat Int. Kzl 8 (1963), 229-243.
[3] F. Harary, and R.A. Melter, On the metric dimension of a graph, Ars Combin. 2 (1976), 191-195.
[4] P.J. Slater, Leaves of trees, Congr. Numer. 14 (1975) 549-559.

Click here to see or download the abstract in PDF.




Thursday May 15, 2014, 12h
C3-Room 005, Campus Nord, UPC
Miquel Àngel Fiol (UPC Barcelona)
On the Spectral Excess Theorem

 

 



Tuesday May 13, 2014, 12h
C3-Room 005, Campus Nord, UPC

Willem Haemers (Tilburg Univ.)
An Interlacing Approach for Bounding the Sum of Laplacian Eigenvalues of Graphs


 

 

Thursday May 8, 2014, 12h

C3-Room 005, Campus Nord, UPC

Willem Haemers (Tilburg Univ.)
Graphs with maximal energy
Click here to see or download the presentation slides.

 




Wednesday May 7, 2014, 12h
C3-Room 005, Campus Nord, UPC

Nuno B. Freitas (Bayreuth University)
An asymptotic Fermat Last Theorem for totally real fields

Abstract:

Jarvis and Meekin showed that the strategy leading to the proof of Fermat's last theorem generalizes to proving that the classical Fermat equation x^p + y^p = z^p has no non-trivial solutions over Q(\sqrt{2}). Two of the major obstacles to extending this result to other number fields are the modularity of the Frey curves and the existence of newforms in the spaces obtained after level lowering.

In this talk, we will discuss how recent modularity theorems, along with applying level lowering twice, allow us to circumvent the aforementioned obstacles. In particular, we will describe conditions on a totally real field K that, when satisfied, the asymptotic FLT holds. That is, there is a constant B_K (depending only on K) such that, for primes p > B_K, the equation x^p + y^p = z^p only admits solutions (a,b,c) satisfying abc=0. Moreover, we will also see that the conditions are satisfied for most real quadratic fields.




****Special talk****

Thursday April 10, 2014, 15h30
Department of Information and Communication Technologies
Universitat Pompeu Fabra
C/ Roc Boronat, 138
08018 Barcelona, Spain
Room 52.321

Mehdi Molkaraie (University of  Waterloo)
Partition Function of the Ising Model via Factor Graph Duality

Abstract:

The partition function of a factor graph and the partition function of the dual factor graph are related to each other by the normal factor graph duality theorem. We apply this result to the classical problem of computing the partition function of the Ising model to show that, at low temperature, Monte Carlo methods are more efficient on the dual graph than on the original graph.

We will also discuss applications to the q-state Potts model.

http://arxiv.org/abs/1307.3645
http://arxiv.org/abs/1401.4912

 

 

 

 

Thursday April 10, 2014, 12h
C3-Room 005, Campus Nord, UPC
Sonja Riedel (Universität Bremen)
Combinatorial models of toric arrangements

Abstract:

A toric arrangement is a finite family A of level sets of characters on the torus (C^*)^n or S_1^n. Recent work of De Concini and Procesi generated new interest in combinatorial invariants of the topology of the complement of A.

In the case of so-called 'complexified' toric arrangements, the induced stratification of the compact torus S_1^n determines the homotopy type of the complement. To establish in greater generality the link between the combinatorics of these face structures and the topology of A we will use the techniques of matroid theory. Starting from the theory of semimatroids and oriented matroids, we develop a toric oriented matroid with the goal to characterize the face structure of the stratification.

The talk will include an introduction to toric arrangements and the necessary background in matroid theory.

 




**Special talk
Friday April 4, 2014, 12h
C1-001, Campus Nord UPC

Charles Johnson (William and Mary College, Virginia)
Hollow Symmetric Nonnegative Matrices

Abstract:

An n-by-n matrix is "hollow" if all its diagonal entries are 0. We study the eigenvalue distribution of hollow symmetric nonnegative (HSN) matrices. In the process, some very unusual combinatorial structure is uncovered. Examples of HSN matrices include adjacency matrices of graphs and distance matrices in various metrics.

 

 

 

 

Thursday April 3, 2014, 12h

C3-Room 005, Campus Nord, UPC

Martyn Mulder (Erasmus Univ. Rotterdam)
What do trees and hypercubes have in common?

Abstract:

At first sight trees and hypercubes are very different classes of graphs (except for the trivial cases K_1 and K_2, of course). Non-trivial trees are cycle-free, highly irregular and have very few automorphisms. Hypercubes are regular, contain many cycles (for dimension at least 2), and have many automorphims. But there is a nice common property of trees and hypercubes. We explore this property and develop a rich structure theory based on it.




Thursday March 27, 2014, 12h
C3-Room 005, Campus Nord, UPC

Martin Golumbic (Univ. of Haifa)
The Elusive Nature of Intersecting Paths on a Grid

Abstract:

In this lecture, we will survey the mathematical and algorithmic results on the edge intersection graphs of paths in a grid (EPG) together with several restrictions on the representations such as allowing just a single bend in any path.

Let P be a collection of nontrivial simple paths on a host graph H. The edge intersection graph of P, denoted by EP_H(P), has vertex set that corresponds to the members of P, where two vertices are joined by an edge if and only if the corresponding members of P share at least one common edge in H. An undirected graph G is called an edge intersection graph of paths in a grid (EPG) if G = EP_{\Gamma}(P) for some P and grid  \Gamma.

Similarly, G is called an edge intersection graph of paths in a tree (EPT) if G = EP_T(P) for some P and tree T. The EPT and EPG graphs can be useful in network and circuit applications, where scheduling and layout problems are often equivalent to coloring an EPT or EPG graph.

The class of EPT graphs was first investigated by Golumbic and Jamison in two papers appearing in 1985, and subsequently, further research has been carried out by a number of algorithmic graph theorists. In a series of papers during the past 5 years, Golumbic, Lipshteyn and Stern studied the hierarchy of related EPT graph classes giving some structure theorems.

More recently, Golumbic, Lipshteyn and Stern introduced EPG graphs, proving that every graph is an EPG graph, and then turning their attention to the subclass of graphs that admit an EPG representation in which every path has at most a single bend, called B_1-EPG graphs. They proved that any tree is a B_1-EPG graph and gave a structural property that enables generating non B_1-EPG graphs. A characterization of the representation of cliques and chordless 4-cycles in B_1-EPG graphs was given, and also prove that single bend paths on a grid have Strong Helly number 4, and when the paths satisfy the usual Helly property, they have Strong Helly number 3.

We will survey these and other recent results by our colleagues Andrei Asinowski, Andrew Suk and Bernard Ries on edge intersection graphs of systems of paths on a grid with a bounded number of bends, and mention some further research by a team in Germany. We will conclude with some new algorithmic results, open problems and future work.

 

 

 

 

Thursday March 20, 2014, 12h

C3-Room 005, Campus Nord, UPC

Bill Kantor (U. Oregon)
Mutually Unbiased Bases

Abstract:

Two orthonormal bases of an n-dimensional complex vector space are called "mutually unbiased" if all inner products of members of different bases have the same absolute value. The maximal possible number of bases pairwise behaving in this manner is n+1. Finding such large sets of bases arose independently in research in electrical engineering, quantum physics, Euclidean configurations and coding theory.

This talk will assume nothing about any of those subjects, and focus instead on the relationships between such sets of bases and affine planes.




Thursday March 13, 2014, 12h
C3-Room 005, Campus Nord, UPC

Juanjo Rué (Freie Univ. Berlin)
Applications of Tutte's tree decomposition in enriched families of graphs

Abstract:

We adapt the grammar introduced by Chapuy, Fusy, Kang and Shoilekova to study enriched graph families which are defined by their 3-connected components.

More precisely, we will discuss two different problems:

1.- The counting formulas for bipartite series-parallel graphs (and more generally of the Ising model over this family of graphs), as well as asymptotic estimates for the number of such graphs with a fixed size.

2.- The expected number of spanning trees in a random series-parallel graph of size n choosen uniformly at random.

This talk is based in different works in progress joint with Kerstin Weller (point 1, ETH Zürich & Oxford) and Julia Ehrenmüller (point 2, TU Hamburg).

 




Thursday March 6, 2014, 12h
C3-Room 005, Campus Nord, UPC

Cristina Araúz (UPC Barcelona)
Discrete Serrin's Problem

Abstract:

We consider here the discrete analogue of Serrin’s problem: if the equilibrium measure of a network with boundary satisfies that its normal derivative is constant, what can be said about the structure of the network and the symmetry of the equilibrium measure? In the original Serrin’s problem, the conclusion is that the domain is a ball and the solution is radial. To study the discrete Serrin’s problem, we first introduce the notion of radial function and then prove a generalization of the minimum principle, which is one of the main tools in the continuous case. Moreover, we obtain similar results to those of the continuous case for some families of networks with a ball-like structure, which include spider networks with radial conductances, distance-regular graphs or, more generally, regular layered networks.

 

 

 

 

Friday February 21

2nd Graph-TA Workshop 2014

http://www.dama.upc.edu/seminars/2nd-graph-ta

 




Thursday February 20, 2014, 12h

C3-Room 005, Campus Nord, UPC

Anna de Mier (UPC Barcelona)
Transversal extensions of transversal matroids

Abstract:

Given a matroid M, one can wonder in how many ways a new element x can be added to obtain another matroid N. The answer to this question is well understood since H. Crapo developed the theory of single-element extensions in 1965. Our goal is to explore the same question if we require that both M and N are transversal matroids. In this case we say that N is a transversal extension of M.

Recall that a matroid is transversal if its independendent sets are the partial transversals of a collection of sets (A_1,..., A_r). Thus, adding the new element x to some of these sets would give another transversal matroid. The problem is that a given transversal matroid can be presented by many different collections of sets, so it is not obvious how to obtain all transversal extensions efficiently.

In this talk we will present two results in this direction: we show that all extensions obtained from a minimal presentation are different, and that every extension can be obtained by extending some minimal presentation.

Naturally we will review all necessary facts about matroids and transversal matroids.

(Joint work with J. Bonin.)

Click here to see or download the presentation slides.



Thursday February 13, 2014, 12h
C3-Room 005, Campus Nord, UPC

Angeles Carmona (UPC Barcelona)
Generalized Linear Polyominoes, Green functions and Green matrices

Abstract:

A Polyomino is an edge-conected union of cells in the planar square lattice. Because the chemical constitution of a molecule is conventionally represented by a molecular graph or network, the polyominoes have deserved the attention of the Organic Chemistry community. So, several molecular structure descriptors based in network structural descriptors, have been introduced. In particular, in the last decade a great amount of works devoted to calculate the Kirchhoff Index of linear polyominoes-like networks, have been published.  In this work we deal with this class of polyominoes, that we call  generalized linear polyominoes, that besides the most popular class of linear polyomino chains, also includes cycles, Phenylenes and Hexagonal chains to name only a few. Because the Kirchhoff Index is the trace of the Green function of the network, here we obtain the Green function of such a network. To do this, we understand a polyomino as a perturbation of a path by adding weighted edges  between opposite vertices. Therefore, unlike the techniques used previously that are based on the decomposition of the combinatorial Laplacian in structured blocks, here we obtain the Green function of a linear polyomino from a perturbation of the combinatorial Laplacian.  We end with an extension of the above work to  general connected networks.

Joint work with Andrés M. Encinas and Margarida Mitjana.

Click here to see or download the presentation slides.


Thursday February 6, 2014, 12h
C3-Room 005, Campus Nord, UPC

Francesc Aguiló (UPC Barcelona)
Some metric results on weighted Cayley digraphs

Abstract:

Let G_c=<a,b> be a finite (additive) 2-generated Abelian group of order c. Let us consider the weighted Cayley digraph Cay(G_c,{a,b},{W_a,W_b}), where W_a and W_b are the weighs of the arcs (g,g+a) and (g,g+b) respectively, for any g in G_c. When W_a=W_b=1, also known as the non-weighted case, there are many known metric results of the cyclic case G_c=Z_c: diameter's sharp lower bound, optimal diameter families of digraphs, efficent algorithms for computing the distance between any pair of vertices, algorithms for computing the diameter, etc. Most of these items can be studied using the well-known minimum distance diagrams. These diagrams can also be used for the weighted and non-cyclic cases. We introduce here the minimum path diagrams that can be used to count the number of minimum paths between two vertices in a weighted (cyclic or non-cyclic) 2-Cayley digraph when the weighs are W_a=a and W_b=b; they can be used for studying some properties of numerical 3-semigroups <a,b,c> with $1<a<b<c$ (and gcd(a,b,c)=1).

In this session two main results will be introduced on numerical 3-semigroups. First, some properties of the semigroup will be derived from the minimum distance diagram of the related digraph. This fact can be useful for computer filtered search on 3-semigroups. The second main result is a closed expression for

G(N)=max{g(a,b,c): 1<a<b<c leq N, gcd(a,b,c)=1}

where g(a,b,c) is the genus of the semigroup <a,b,c>.

Joint work with Alicia Miralles and Marisa Zaragozá.

Click here to see or download the presentation slides.

 




Thursday January 30, 2014, 12h
C3-Room 005, Campus Nord, UPC

Mercè Mora (UPC Barcelona)
Location and domination in graphs

Abstract:

Many problems related to location and domination in graphs give raise to consider some special subsets of vertices and parameters. The main goal is to determine the existence or the location of some facility, object or item by placing the minimum number of detection devices or watchers in some vertices of the graph. The different parameters are defined by considering restrictions of the detection devices. In this talk I will give the definitions and basic properties of some of the parameters, including bounds and values on some families. I will also show some recent results in this subject, concretely the relation of these parameters in a graph and its complement.

Click here to see or download the presentation slides.



Thursday January 23, 2014, 12h
C3-Room 005, Campus Nord, UPC

Camino Balbuena (UPC Barcelona)
An overview on {C_3,...,C_s}-free extremal graphs

Abstract:

For integers s>3 and n>s, let ex(n;{C_3,...,C_s}) denote the maximum number of edges in a graph on n vertices and girth at least s+1. We refer to it as the extremal function. By EX(n;{C_3,...,C_s}) we denote the set of all simple graphs of order n, girth at least s+1 and with ex(n;{C_3,...,C_s}) edges. A graph G in EX(n;{C_3,...,C_s}) is called an extremal graph.

Graphs constructed by researchers interested in the Cage Problem provide good constructive lower bounds for the extremal number. In this talk we will see some exact values of the extremal function for s=4,5,6,7,10,11, and also some lower bounds. Moreover, we will review the last results on the lower bounds on the order of a extremal graph guaranteeing that the girth is equal to s+1 and other structural properties.

Click here to see or download the presentation slides.

 

 

 

 

Thursday January 16, 2014, 12h

C3-Room 005, Campus Nord, UPC

Miquel Àngel Fiol (UPC Barcelona)
The Preintersection Numbers and Some of Their Properties

Abstract:

The preintersection numbers are, in fact, some Fourier coefficients which depend only on the spectrum of (the adjacency matrix $A$ of) a graph $G$. They can be seen as a generalization of the so-called intersection numbers of a distance-regular graph, which are parameters of a purely combinatorial nature. (In general, this is not true for the preintersection numbers.)

In this talk we first discuss which well-known properties of the intersection numbers are shared by the preintersection numbers, and which are not.

Then we present some results about the structure of $G$, mainly related with distance-regularity, in terms of the preintersection numbers.

(joint work with A. Abiad, C. Dalfó, E. Garriga, and E.R. van Dam)




Tuesday December 10, 17h, and Thursday December 12, 17h
Facultat de Matemàtiques i Estadística, UPC, Room 005

Special lectures of the Random Structures course

http://www.bgsmath.cat/random-structures-and-the-probabilistic-method

on
Graph coloring and the probabilistic method

http://www.springer.com/new+%26+forthcoming+titles+(default)/book/978-3-540-42139-9

delivered by Bruce Reed.




Thursday December 12, 2013, 12h
C3-Room 005, Campus Nord, UPC
Bruce Reed (McGill Univ., Montreal)
The typical structure of H-free graphs

Abstract:

We show that the vertex set of almost every graph which does not contain a cycle of length six as an induced subgraph can be partitioned into a stable set and a subgraph containing neither a stable set of size three nor an induced matching of size 2. We discuss similar precise characterizations of typical graphs without induced cycles of length k for all k. We present a conjecture about the structure of almost every graph without H as an induced subgraph for arbitrary H. We discuss various pieces of evidence in support of this conjecture.




Thursday December 5, 2013, 12h
C3-Room 005, Campus Nord, UPC

Victor Diego (UPC Barcelona)
On a  problem of Shapozenko

Abstract:

The Johnson graph J(n,m) has the m-subsets of [n] as vertices and two subsets are adjacent in the graph if they share m-1 elements. The isoperimetric function of a graph gives, for each k, the cardinality of the smallest boundary among sets with cardinality k.

The isoperimetric function is known for a small class of graphs, including the n-cube. Shapozenko, and later Leader, asked about the isoperimetric function in Johnson graphs, which, as the n-cube, are distance transitive.

In order to study the isoperimetric function of Johnson graphs we use combinatorial tools. The combinatorial tools are based on compression techniques, which allow us to transform sets of vertices without increasing their boundary. In the compression process we will show that sets of vertices that induce Johnson subgraphs are optimal with respect to the isoperimetric problem. Upper bounds are obtained by displaying nested families of sets which interpolate optimal ones. Finally, the values of the form {t \choose m} can be generalized to any m-binomial expression of any value of $k$, giving the complete isoperimetric function for all the Johnson graphs.




Thursday November 21, 2013, 12h
C3-Room 005, Campus Nord, UPC

Benny Sudakov (ETH Zürich and UCLA Los Angeles)
The minimum number of nonnegative edges in hypergraphs

Abstract:

An r-uniform n-vertex hypergraph H is said to have the Manickam-Miklos-Singhi (MMS) property if for every assignment of weights to its vertices with nonnegative sum, the number of edges whose total weight is nonnegative is at least the minimum degree of H. In this talk I will show that for n>10r^3, every r-uniform n-vertex hypergraph with equal codegrees has the MMS property, and the bound on n is essentially tight. One of the immediate corollaries of this result is the vector space Manickam-Miklos-Singhi conjecture from 1988 which determines the minimum number of nonnegative k-dimensional subspaces in any weighting of the 1-dimensional subspaces of (F_q)^n with nonnegative sum.

Joint work with Hao Huang.

 

 



Thursday November 14, 2013, 12h

C3-Room 005, Campus Nord, UPC

Javier Cilleruelo (UAM and ICMAT, Madrid)
Extremal graphs and extremal sets of integers

Abstract:

The study of sets of integers which do not contain special subsets, like arithmetic progressions, solutions of a given linear equation or some other kind of additive structure, is central in additive combinatorics. In the same vein, the study of graphs which do not contain a given subgraph has a rich history in extremal graph theory. In this talk we will connect these two worlds and we will present new results in each of them.




Thursday November 7, 2013, 12h
C3-Room 005, Campus Nord, UPC

Juraj Hromkovic (ETH Zürich)

Towards measuring the information content of problems

 

Abstract:

Information is a fundamental notion in science but we do not have any reasonable exact definition of this term. Shannon, Kolmogorov and Chaitin tried to define the information content of finite objects and introduced in this way very powerful research instruments. Shannon entropy is measurable but it is definitely not a robust definition of the information content. Kolmogorov complexity is a robust definition of the information content but one cannot use it to measure the information content of concrete finite objects. We think that there is no way to measure the information content of finite objects as well as it is no way to measure the computational complexity of particular problem instances. This is the motivation to introduce the information content of computing problems in online setting as a function of the problem instance size. Using this concept we discover the information content of several fundamental online problems and observe very different kinds of behaviors of the tradeoffs between the amount of information provided and the quality of reachable solutions.




Thursday October 31, 2013, 12h
C3-Room 005, Campus Nord, UPC

Christian Rubio Montiel (Instituto de Matemáticas UNAM)
A new characterization of trivially perfect graphs

Abstract:

A graph G is trivially perfect if for every induced subgraph the cardinality of the largest set of pairwise nonadjacent vertices (the stability number) α(G) equals the number of (maximal) cliques m(G). We characterize the trivially perfect graphs in terms of vertex-coloring, we relate them to some well-known classes of perfect graphs and extend the definitions to infinite graphs.




Thursday October 24, 2013, 12h
C3-Room 005, Campus Nord, UPC

Joan Vilaltella (UPC Barcelona)
Complete and irreducible multipoles

Abstract:

Multipoles are the pieces we obtain by cutting some edges of a cubic graph. As a result of the cut, a multipole M has dangling edges with one free end, which we call semiedges. Then, every 3-edge-coloring of a multipole induces a coloring or state of its semiedges, which must satisfy a parity restriction called the Parity Lemma.

Multipoles have been extensively used in the study of snarks, that is, cubic graphs which are not 3-edge-colorable.

A multipole is complete if it has all states allowed by the Parity Lemma. We give lower and upper linear bounds on the minimum order of a complete multipole, and the exact number of states of any complete multipole as a function of its number of semiedges.

Given two multipoles M1 and M2 with the same number of semiedges, we say that M1 is reducible to M2 if the state set of M2 is a non-empty subset of the state set of M1 and M2 has less vertices than M1. If no multipole M2 fulfills this conditions for a given multipole M1, then we say that M1 is irreducible.

The function v(m) is defined as the maximum number of vertices of an irreducible multipole with m semiedges. The exact values of v(m) are only known for m <= 5. Recently, we obtained the result that tree and cycle multipoles are irreducible and, as a byproduct, that v(m) has a linear lower bound.

This is joint work with Miquel Àngel Fiol (UPC Barcelona).

 




Monday October 14 and Tuesday October 15, 2013
C3-Room 005, Campus Nord, UPC
Journées Combinatoire et Algorithmes du Littoral Méditerranéen, JCALM
Graph Minors

Click here to see the program or visit the JCALM 2013 web page:

http://www.lirmm.fr/~sau/JCALM2013Bcn.html




Thursday October 10, 2013, 12h
C3-Room 005, Campus Nord, UPC

Gabriela Araujo (UNAM, Mexico)
Projective planes and colorings



Thursday October 3, 2013, 12h
C3-Room 005, Campus Nord, UPC

Aline Parreau (Univ. de Lille)
Identifying codes and Vapnik–Chervonenkis dimension

Abstract:

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. Using Vapnik–Chervonenkis dimension, we give a dicothomy result for identifying codes in classes of graphs closed under induced subgraphs: either a class has infinite VC dimension and has arbitrarily large logarithmic identifying codes or it has finite VC dimension and an identifying code will always be of polynomial size. We also prove that in the first case, the problem of determining the smallest size of an identifying code is hard to approximate within a constant factor.

 




Tuesday October 1, 2013

 

PhD defense by Guillem Perarnau

Random Combinatorial Structures with low dependencies: existence and enumeration

Thesis advisor: Oriol Serra.

Sala d'actes FME, 11:30h.

 




Thursday September 26, 2013, 12h

C3-Room 005, Campus Nord, UPC

 

Arnau Padrol (FU Berlin)
A universality theorem for projectively unique polytopes and a conjecture of Shephard

Abstract:

In this talk I will present the following universality theorem for projectively unique polytopes: every polytope described by algebraic coordinates is the face of a projectively unique polytope.

This result can be used to construct a combinatorial type of polytope that is not realizable as a subpolytope of any stacked polytope. This disproves a classical conjecture in polytope theory, first formulated by Shephard in the seventies.

This is joint work with Karim Adiprasito.


Seminar 2012-2013

Sessions and Abstracts

Seminar sessions and other activities



Thursday July 25, 12h
EETAC, C4 building, room 028a, Campus Castelldefels

Ruy Fabila-Monroy (CINVESTAV-IPN, Mexico)
Búsqueda con ordenador de configuraciones extremales en conjuntos de puntos

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.



Tuesday July 16, 12h

Jerrold Griggs (University of South Carolina)
Forbidding Posets in a Family of Subsets

Abstract:

We consider extremal set theory analogues of Turan theory for graphs:

Given a finite poset P, let La(n,P) denote the largest size of a family F of subsets of [n]:=\{1,\ldots,n\} that contains no (weak) subposet P. The extension of Sperner's Theorem due to Erdos determined La(n,P) for all n when P=P_k is a k-element path poset (chain). With Lincoln Lu we conjectured that

\pi(P):=\lim_{n\rightarrow\infty} La(n,P)/{n\choose{\lfloor n/2\rfloor}}

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.



Thursday June 27, 12h

Amanda Montejano (UNAM, Mexico)
Null and non-rainbow colorings of projective plane and sphere triangulations

Abstract:

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.



Thursday June 20, 12h

José Gómez (UPC, Barcelona)
Large vertex symmetric graphs with small diameter

Abstract:

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.



Thursday June 13, 12h

Miquel Àngel Fiol (UPC, Barcelona)
Predistance Polynomials and Applications

Abstract:

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



Thursday June 6, 12h

Andriy Bondarenko (Norwegian University of Science and Technology and National Taras Shevchenko University, Kyiv, Ukraine)
Spherical designs: Proof of the Korevaar-Meyers conjecture and beyond

Abstract:

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.



Thursday May 30, 12h

Joseph Peters (Simon Fraser Univ.)
3-colourable circulant graphs

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.



Thursday May 23, 12h

Karoly Boroczky (Renyi Institute, Budapest)
On sumsets and convex hull

Abstract:


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.



Thursday May 16, 12h

Susana C. López (UPC, Barcelona)
Connectivity and other invariants of generalized products of graphs

Abstract:

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.



Thursday May 9, 12h

Sanming Zhou (Univ. Melbourne)
Frobenius circulant graphs of valency six, Eisenstein-Jacobi networks, and hexagonal meshes

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.



Thursday April 25, 12h

Jan Volec (Warwick Univ., UK)
A problem of Erdös and Sós on 3-graphs

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.



Tuesday April 23, 12h

Roman Glebov (Warwick Univ., UK)
On bounded degree spanning trees in the random graph

Abstract:

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.



Thursday April 18, 12h

Albert Guillén (ICREA/Univ. Pompeu Fabra, Barcelona)
Mismatched Decoding and Bit-Interleaved Coded Modulation

Abstract:

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.



Thursday April 11, 12h

Shmuel Zaks (Technion, Haifa)
Optimization in optical networks

Abstract:

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.



Thursday March 21, 12h

Antonio Guedes (Oporto)
Parking functions and labelled trees

Abstract:

 

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.

 



Thursday March 7, 12h

Reza Naserars (CNRS, LRI-Paris 11)
Homomorphism of signed bipartite graphs

Abstract:

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.



Thursday February 28, 11:30 h

Ignasi Sau (LIRM, Montpeller)
Linear kernels and single-exponential algorithms via protrusion decompositions

Abstract:

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.



Thursday February 21, 12h

Florent Foucaud (UPC, Barcelona)
Identifying codes in graphs: problems from the other side of the Pyrenees

Abstract:


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.



Thursday February 14, 12h

Juanjo Rue (ICMAT, Madrid)
Threshold functions for systems of equations on random sets

Abstract:

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.



Tuesday February 19

1st Workshop on Graph-based Technologies and Applications (Graph-TA),
Barcelona, February 19, 2013

http://www.dama.upc.edu/seminars/graph-ta



*International School on Coding Theory and their Applications* (ISCTA)
Tarragona, February 11-14, 2013

http://crises-deim.urv.cat/iscta/



Thursday February 7, 12h

Arnaud Pecher (LaBri, Univ. Bordeaux I)
On the theta number of powers of cycle graphs

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.



Thursday December 20, 11h
Sala d'Actes FME

PhD Defense

Julián Salas
On the Structure of Graphs without Short Cycles

Advisor: Dr. Camino Balbuena



Thursday December 13, 12h

Dima Volchenkov (Univ. Bielefeld)
Markov Chain Analysis of Complex Networks and Databases

Abstract:

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.



Wednesday December 5, 12h

Tobias Muller (Univ. Utrecht)
First order logic and random graphs

Abstract:

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.

(Joint with S. Haber)



Thursday November 29, 12h

Christopher Thraves (Univ. Rey Juan Carlos, Madrid)
Signed graph embedding, when everybody can sit closer to friends than enemies

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.



Thursday November 15, 12h

Pavel Rytir (Charles Univ., Praha)
Geometric representations of linear codes

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.



Thursday November 8, 12h

Jarek Grytczuk (Jagiellonian Univ. Krakow)
Additive colorings of graphs

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.



Thursday October 18, 12h

Guillem Perarnau (UPC, Barcelona)
A probabilistic approach to consecutive pattern avoiding in permutations

Abstract:

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.



Thursday October 11, 12 h

Mirka Miller (Univ. London)
Moore Graphs and Beyond: Recent Advances in the Degree/Diameter Problem

Abstract:

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.



Thursday October 4, 12h

Joe Ryan (Univ. Newcastle)
The Degree Diameter Maximum Subgraph Problem

Abstract:


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.



Thursday September 27, 12h

Oriol Farràs (URV, Tarragona)
Secret Sharing Schemes for Very Dense Graphs

Abstract:

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



Thursday September 13, 12h

Pedro A. Garcia-Sanchez (Univ. Granada)
Catenariedades en monoides conmutativos

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.

Finalmente, relacionaremos la catenariedad con otros invariantes de factorización.


Seminar 2011-2012

Sessions and Abstracts

Unless otherwise stated, all sessions take place at C3-Room 005, Campus Nord, UPC.

Sessions


Monday July 23, 11h
Conference Room of ETSECCPB (2nd floor, room C2 212)

The Inverse Problem on finite networks
Ph.D. Thesis proposal

Cristina Araúz Lombardía

Thesis advisors: Ángeles Carmona Mejías and Andrés M. Encinas Bachiller



Friday June 22, 12h
On the largest tournament Maker can build
Anita Liebenau (TU Berlin)

Abstract:

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.



Thursday June 21, 11h30
Sala de Graus, Campus de Cappont
Universitat de Lleida (UdL)

Special session in memory of Joan Gimbert


11h30
Welcome

11h45
Les aportacions de Joan Gimbert a la teoria de grafs
Josep Conde i Nacho López (UdL)

12h30
The contribution of Joan Gimbert to the degree/diameter problem
Dominique Buset (Université Libre de Bruxelles)



Thursday June 14, 12h
Polytopes of degree 1
Arnau Padrol (UPC, Barcelona)

Abstract:


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.



Thursday June 7, 12h
An alternative way to generalize the pentagon
Simeon Ball, UPC Barcelona

(joint work with John Bamberg, Alice Devillers and Klara Stokes)

Abstract:

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.



Thursday May 31, 12h
A short proof of the odd-girth theorem
Miquel Àngel Fiol, UPC Barcelona

Abstract:

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)



Thursday May 24, 12h
Polarity graphs and other $C_4$-free graphs of large size
Camino Balbuena, UPC Barcelona

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.



Thursday May 3, 12h
Locally identifying colourings of graphs
Aline Parreau, University Joseph Fourier of Grenoble

Abstract:

We introduce the notion of locally identifying colourings of graphs. A proper colouring of vertices is said to be locally identifying if for any adjacent pair of vertices u and v, the set of colours in their closed neighborhood are distinct.

In this talk, we will present different results on these colorings in different classes of graphs, in particular in subclasses of perfect graphs and in planar graphs. We will also show that a graph with maximum degree D has a locally identifying coloring with O(D^2) colours.



Thursday April 26, 12h
Huge locating dominations of graphs
Iñaki Pelayo, UPC, Barcelona

Abstract:


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.



Thursday March 22, 12h
Strongly regular graphs
Andriy Bondarenko, CRM (Barcelona)

Abstract:

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



Thursday March 15, 12h
Testing function isomorphism
David García, CWI Amsterdam

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.



Thursday March 8, 12h
Moments in graphs
Miquel Àngel Fiol, UPC, Barcelona

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



Thursday February 23, 12h
Many neighborly polytopes
Arnau Padrol, UPC Barcelona

Abstract:

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



Thursday February 16, 12h
Graphs and Matrices with Integral Spectrum in Some Families
Igor Shparlinsky, Department of Computing, Macquarie University, Australia

Abstract:

We give a survey of recent results about counting of graphs and matrices (of various types) with integral eigenvalues. This question leads to several other natural counting problems (for example, counting singular matrices in some families). We also pose several open problems.



Thursday February 9, 12h
Consecutive patterns in permutations: clusters, generating functions and asymptotics
Marc Noy, UPC, Barcelona

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.



Thursday January 26, 12h
On a conjecture of Erdös, Faber and Lovász
David Romero, Instituto de Matemáticas, UNAM, Cuernavaca, México

Abstract:

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.



Thursday January 12, 12h
Algunos resultados en teoría anti-Ramsey aritmética
Amanda Montejano, Centro de Física Aplicada y Tecnología Avanzada, UNAM, Mexico

Abstract:

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.



Thursday December 22, 12h
A removal lemma for linear configurations in subsets of the circle
Pablo Candela (Cambridge University)

Abstract:

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.




Thursday December 15, 12h
Upper Bounds for Higher Sumsets
Giorgis Petridis (Cambridge University)

Abstract:

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.



Thursday December 1 2011, 12h
Maximum degree in minor-closed classes of graphs
Marc Noy (UPC, Barcelona)

Abstract:

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.



Thusday November 24, 12h
On the cardinality of sumsets in torsion free groups
Károly J. Böröczky (Alfred Rényi Institute, Budapest)

Abstract:

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.



Thursday November 17 2011, 12h
Rainbow k-connection in Dense Graphs
Henry Liu, Universidade Nova de Lisboa, Portugal

Abstract:

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



Thursday November 10, 12h
Complete Bipartite Turan numbers
Simeon Ball (UPC,  Barcelona)



Thursday November 3, 12h
On the face vectors of polytopes: unimodality and generalized Euler's relations
Laszlo Major (Tampere Univ., Finland)

Abstract:

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.



Thursday October 27, 12h
Breaking symmetry in tournaments
Antoni Lozano (UPC, Barcelona)

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.



Thursday October 20 2011, 12h
Quantum Correlations and Device-Independent Quantum Information Processing
Antoni Acin (Institut de Ciènces Fotòniques, Barcelona)


Seminar 2010-2011

Sessions and Abstracts

 

 

Unless otherwise stated, all sessions take place in Room 005, Mòdul C3, Campus Nord UPC.
Please browse the left menu for additional activities organized by CombGraph.



Dependent Random Choice
Guillem Perarnau, UPC

Tuesday, June 28 and Thursday June 30, 11h
Biblioteca de Matemàtiques
Mòdul C3, Campus Nord



Edge distance-regularity
Marc Càmara, UPC Barcelona

Thursday, June 2, 2011, 12h



On 3-domination critical graphs
Adriana Hansberg, UPC Barcelona

Thursday, May 26 2011, 12h



Graph Isomorphism, Sherali-Adams Relaxations and Expressibility in Counting Logics
Albert Atserias, UPC Barcelona

Thursday, May 19 2011, 12h



Line-identifying codes
Florent Foucaud, LABRI, Univ. Bordeaux

Thursday, May 12 2011, 12h



Els Treballs i els Dies amb l'Ernest
Miquel Angel Fiol, UPC Barcelona

Thursday, May 5 2011, 12h



Integer lattice points in the plane
Sukumar Adhikari, Harish Chandra Research Institute, Allahabad, India

Thursday, April 28 2011, 12h



Bandidos malvados: ¿cómo luchar contra ellos aleatoriamente?
Gabor Lugosi (ICREA y UPF)

Thursday April 14, 2011, 12h



On a slicing formula for bipartite graphs
Eric Fusy, LIX Ecole Polytechnique, Paris

Thursday April 7, 2011, 12h



Regular Star Complements in strongly regular graphs
Peter Rowlinson, University of Stirling, Scotland

Thursday March 31 2011, 12h



A tribute to Yahya ould Hamidoune
Oriol Serra, UPC, Barcelona

Thursday March 24, 2011, 12h



Dynamic programming in sparse graphs
Ignasi Sau (CNRS, LIRMM, Montpellier, France)

Thursday March 10 2011, 12h



Some stability problems in finite geometry
Jan de Beule, Gent Univ.

Thursday March 3 2011, 12h



Erdös year: Erdös problems on repeated and distinct distances
Marc Noy, UPC Barcelona

Thursday February 17 2011, 12h



Identifying codes for regular graphs
Guillem Perarnau, UPC Barcelona

Thursday February 10 2011, 12h



On the girth of {C_3,...,C_s}-free extremal graphs
Camino Balbuena, UPC Barcelona

Thursday January 27, 2011, 12h



Graph Coverings and the degree-diameter problem
Maria Zdimalova, Slovak University of Technology

Thursday January 20, 2011, 12h



The h-product of digraphs and its applications to labelings
Susana López masip, UPC Barcelona

Thursday January 13 2011, 12h



Permutations and $\beta$-shifts
Sergi Elizalde, Dartmouth College

Thursday December 16, 2010 (12h)



 
   
  Erdös' Year: Sums and Products
Oriol Serra, UPC

Thursday December 2, 2010 (12h)

 
  On graphs representable by words
Sergey Kitaev, Reykjavik University

Thursday November 25, 2010 (12h)

 
  Julián Salas, UPC

Thursday November 18, 2010 (12h)

 
 
On Perturbations of Punctually Walk-Regular Graphs
Miquel A. Fiol, UPC

Thursday November 4, 2010 (12 h)

 
  Interval orders and equinumerous objects
Sergey Kitaev, Reykjavik University

Thursday October 7, 2010 (12h)
 
 
  Difference sets, Fourier analysis, and Delsarte's method
Mate Matolcsi, Alfred Renyi Institute of Mathematics, Budapest

Thursday September 30, 2010 (12h)

 

Abstracts



Tuesday, June 28 and Thursday June 30, 11h
Biblioteca de Matemàtiques, Mòdul C3, Campus Nord

Dependent Random Choice

Guillem Perarnau, UPC


Two informal sessions will be devoted to an exposition of the paper 'Dependent random Choice' by J. Fox and B. Sudakov, addressed to an interested audience. The paper is available at  http://onlinelibrary.wiley.com/doi/10.1002/rsa.20344/pdf.



Thursday, June 2, 2011, 12h
Aula 005, Mòdul C3, Campus Nord

Edge distance-regularity

Marc Càmara, UPC Barcelona

Abstract

Edge-distance-regularity is a concept recently introduced which is similar to that of distance-regularity, but now the graph is seen from each of its edges instead of its vertices.  In this talk, we study this concept, give some of its properties, such as regularity, and derive some characterizations. In particular it is shown that a graph is edge-distance-regular if and only if its k-incidence matrix is a polynomial in the adjacency matrix multiplied by the (standard) incidence matrix. Also an analogue of the spectral excess theorem is proved, so giving a quasi-spectral characterization of edge-distance-regularity. Finally, we show that every non bipartite graph which is both distance-regular and edge-distance-regular is a generalized odd graph.  We also introduce the concept of edge-spectrum-regularity, and characterize the graphs which are both spectrum-regular and edge-spectrum regular as those that are 1-walk-regular.

This is a joint work with C. Dalfó, J. Fàbrega, M.A. Fiol and E. Garriga.



Thursday, May 26 2011, 12h
Aula 005, Mòdul C3, Campus Nord

On 3-domination critical graphs

Adriana Hansberg, UPC Barcelona

Abstract

Given a graph G, a subset D of the vertex set V of G is a dominating set if every vertex in V\D has at lest one neighbor in D. The minimum cardinality among all dominating sets of G is called the domination number of G and is denoted by gamma(G). The graph G is said to be k-domination critical if gamma(G) =k and the addition of any non existing edge makes its domination number decrease by one. The k-domination critical graphs were introduced by Sumner and Blitch in 1983 and have awaken great interest among graph theorists. Specially the 3-domination critical graphs have been intensively studied by many authors. In this talk, we revisit this topic reviewing many known results and presenting new achievements on 3-domination critical graphs. In particular, we give the characterization of some  3-domination critical graphs, among them those with minimum degree one.
(joint work with Camino Balbuena)



Thursday, May 19 2011, 12h
Aula 005, Mòdul C3, Campus Nord

Graph Isomorphism, Sherali-Adams Relaxations and Expressibility
in Counting Logics

Albert Atserias, UPC Barcelona

Abstract

Two graphs with adjacency matrices A and B are isomorphic if there exists a permutation matrix P for which the identity P^T A P = B holds. Multiplying through by P and relaxing the permutation matrix to a doubly stochastic matrix leads to the notion of fractional isomorphism. We show that the levels of the Sherali-Adams hierarchy of linear programming relaxations applied to fractional isomorphism interleave in power with the levels of a well known color-refinement heuristic for graph isomorphism called the Weisfeiler-Lehman algorithm. This tight connection has quite striking consequences. For example, it follows immediately from a deep result of Grohe in the context of logics with counting quantifiers, that a fixed number of levels of SA suffice to determine isomorphism of planar graphs. We also offer applications both in finite model theory and polyhedral combinatorics. First, we show that certain properties of graphs such as that of having a flow-circulation of a prescribed value, are definable in the infinitary logic with counting with a bounded number of variables. Second, we exploit a lower bound construction due to Cai, Fürer and Immerman in the context of counting logics to give simple explicit instances that show that the SA relaxations of the vertex-cover and cut polytopes do not reach their integer hulls for up to \Omega(n) levels, where n is the number of vertices in the graph.



Thursday, May 12 2011, 12h
Aula 005, Mòdul C3, Campus Nord

Line-identifying codes

Florent Foucaud, LABRI, Univ. Bordeaux

Abstract

An identifying code of a graph is a subset of its vertices such that the set of code vertices which dominate each vertex are unique and nonempty. This concept was introduced in 1998 by Karpovsky et al. In this talk we introduce the related concept of line-identifying code, that is, the same concept defined over the edges of $G$. Equivalently, a line-identifying code of $G$ is an identifying code of the line-graph of $G$. The line-identifying code number of $G$ is the minimum size of a line-identifying code in $G$. We derive some lower and upper bounds on this parameter. These bounds imply that identifying codes behave quite differently in the class of line-graphs (with respect to general graphs). We also show that the problem of determining the minimum value of this parameter is NP-hard in a very restricted class of graphs (planar bipartite graphs of maximum degree 3 and arbitrarily large girth).

This is joint work with Sylvain Gravier, Reza Naserasr, Aline Parreau and Petru Valicov.


Thursday, May 5 2011, 12h
Aula 005, Mòdul C3, Campus Nord

Els Treballs i els Dies amb l'Ernest

Miquel Angel Fiol, UPC Barcelona

Abstract

En el diccionari Català-Valencià-Balear d'A.M. Alcover i F. de B. Moll podem llegir la següent definició del verb JUBILAR: "Experimentar una alegria viva, expansiva".

Bé, això és el que l'Ernest Garriga, el nostre company i amic del departament, ha pogut experimentar recentment i el que, com a petit homenatge, justifica aquesta xerrada. Aquesta és la història d'una col·laboració que s'ha perllongat durant una quinzena d'anys i ha donat lloc a una trentena de treballs (articles, conferències, tesis,...).  Vam començar a treballar amb l'Ernest, juntament amb el Luis Yebra i el Jordi Barguilla (malauradament ja traspassat), a mitjans dels anys 90 del segle passat. Des d'aleshores, han passat moltes coses: unes bones i d'altres, no tant. Afortunadament, en tots els casos i circumstàncies, els treballs han tirat endavant i han anat sortint coses com "polinomis alternants","grafs frontera", "pertorbacions de grafs i  equacions diferencials", "espectres locals", "polinomis predistància", "el teorema de l'excés espectral", "pseudo-distància-regularitat" "odd grafs retorçats", "grafs k-camí-regulars", "grafs quasi-distància-regulars",...

En aquesta xerrada farem cinc cèntims d'aquests treballs que hem fet (i dels que encara esperem seguir fent) i dels dies que hem passat (i que encara esperem seguir passant) amb l'Ernest. Parafrasejant un comentari de l'Ernest al "Pròleg i agraïments" de la seva  tesi, no sé si la Ciència li agrairà el que ha fet, però jo (i molts  d'altres) sí.



Thursday, April 28 2011, 12h
Aula 005, Mòdul C3, Campus Nord

Integer lattice points in the plane

Sukumar Adhikari, Harish Chandra Research Institute, Allahabad, India

Abstract

We shall discuss a couple of problems related to integer lattice points in the plane.  The first one involves finite colourings of integer lattice points in the plane. The question may be said to belong to the subject of  Euclidean Ramsey Theory and is related to a conjecture which was suggested by Gurevich which says that for any finite colouring of the Euclidean plane $E2$, there always exists a triangle of unit area with monochromatic vertices. The second problem is on a question of Erd\H{o}s regarding visibility of integer lattice points in the plane. For both the problems, before going into the exact problems involved, we  give necessary introductions to those themes. We also mention results related to these problems in  higher dimensions.



Thursday April 14, 2011, 12h
Aula 005, Mòdul C3, Campus Nord
Bandidos malvados: ¿cómo luchar contra ellos aleatoriamente?

Gabor Lugosi (ICREA y UPF)

Abstract

En esta charla repasamos algunos problemas de aprendizaje "online". En este tipo de problemas uno intenta a predecir una sucesión completamente arbitraria. Vamos a mostrar cómo el uso de predicción aleatorizada puede garantizar un buen rendimiento. Un variante interesante es el "multi-armed bandit problem" donde la información recibida por el predictor se limita a su propia pérdida. Cuando el conjunto de posibles acciones es grande pero estructurada, surgen algunos problemas combinatorios y algorítmicos interesantes. (La charla no requiere ningún conocimiento previo del tema.)



Thursday April 7, 2011, 12h
Aula 005, Mòdul C3, Campus Nord

On a slicing formula for bipartite graphs
Eric Fusy, LIX Ecole Polytechnique, Paris

Abstract

The slicings formula, discovered by Tutte and recovered bijectively by Schaeffer, gives an exact expression for the number of (rooted) bipartite planar maps with a prescribed number n_i of faces in each even degree 2i.  We show bijectively that a very similar exact formula exists for bipartite planar maps without multiple edges. The expression in terms of generating functions can be generalized to higher girth.

Joint work with Olivier Bernardi.


Thursday March 31 2011, 12h
Aula 005, Mòdul C3, Campus Nord
Regular Star Complements in strongly regular graphs

Peter Rowlinson, University of Stirling, Scottland

Abstract

Let G be a graph of order n, with \mu as an eigenvalue of multiplicity k. A star complement for \mu in G is an induced subgraph of order n-k which does not have \mu as an eigenvalue. We discuss the strongly regular graphs that can be constructed from a regular star complement of prescribed degree.



Thursday March 24 2011, 12h
Aula 005, Mòdul C3, Campus Nord

A tribute to Yahya ould Hamidoune
Oriol Serra, UPC, Barcelona

On Friday March 11 Yahya ould Hamidoune passed away. The talk will survey the mathematical work Anna Llado and myself shared with him in the last 15 years.



Thursday March 10 2011, 12h
Aula 005, Mòdul C3, Campus Nord

Dynamic programming in sparse graphs
Ignasi Sau (CNRS, LIRMM, Montpellier, France)

Abstract

A fundamental parameter in the design and analysis of graph algorithms is the branchwidth of a graph, which can be seen as a measure of the topological resemblance of a graph to a tree (similar to treewidth). Its algorithmic importance is justified by Courcelle's theorem, stating that graph problems expressible in Monadic Second Order Logic can be solved in f(bw)n steps (here bw is the branchwidth and n is the number of vertices of the input graph). As the bounds for f(bw) provided by Courcelle's theorem are huge, it is of great interest
the design algorithms so that f(bw) is a simple function.

In this talk we overview a general framework for the design and analysis of dynamic programming algorithms for graphs embedded in arbitrary surfaces where f(bw)=2^{O(bw)}. Our approach combines tools from topological graph theory and analytic combinatorics. In particular, we introduce a new type of branch decomposition called "surface cut decomposition", which generalizes "sphere cut decompositions" introduced by Seymour and Thomas for planar graphs. That way, we unify and improve all previous results in this direction.

If time permits, we will also outline the main ideas in order to extend our framework to deal with families of graphs excluding a fixed
graph as a minor.

This is joint work with Juanjo Rué and Dimitrios M. Thilikos.



Thursday March 3 2011, 12h
Aula 005, Mòdul C3, Campus Nord
Some stability problems in finite geometry
Jan de Beule, Gent Univ.

Abstract

Some stability problems in finite geometry will be introduced anddescribed as problems in vector spaces over finite fields. It will be explained how some of these problems correspond to problems on cliques (or co-cliques) in graphs. Then we will focus on a class of recently studied problems in a particular finite geometry, discuss the methodology used, and end with some open problems.



Thursday February 17 2011, 12h
Aula 005, Mòdul C3, Campus Nord
Erdös Year. Erdös problems on distinct and repeated distances
Marc Noy, UPC Barcelona

Abstract

In 1946 Erdos published a short paper introducing two apparently simple problems on discrete geometry that turned out to be very deep. They are the following:

- Given n points in the plane, at most how many pairs of points are at distance 1?
Call f(n) the maximum over all sets of n points.

- Given n points in the plane, at least how many different distances they determine.
Call g(n) the minimum over all sets of n points.

Erdos proved that  n^(1+c/log log n) < f(n) < n^(3/2)

and that                      n^(1/2) < g(n) < n/sqrt(log n)

Some of these bounds have been improved over the years, for instance the best current upper bound for the unit distances problem is f(n) < n^(4/3). In the talk we will discuss some of these results, as well as the recent breakthrough by Guth and Katz in the distinct distances problem, showing the almost tight lower bound  n/log n < g(n).



Thursday February 10 2011, 12h
Aula 003, Mòdul C3, Campus Nord
Identifying codes for regular graphs.
Guillem Perarnau, UPC Barcelona

Abstract

Given a graph G, an identifying code can be defined as a dominating set that identifies each vertex of G with a unique code. They have applications on detecting and locating a "failure" in some vertex. We are mainly interested in bounding the size of a minimal code in terms of the maximum or minimum degree of G. In particular, we will talk about the regular case, which in some case is easier to solve. The first part is centred in giving a new result that provides an asymptotically better approximation to a conjecture stated by Foucaud et al. (2009) than the previous ones. In the second part we talk about graphs with girth five. We use them to compute the minimal size of a code for random regular graphs with high probability.

This is a joint work with Florent Foucaud.



Thursday January 27  2011, 12h
Aula 003, Mòdul C3, Campus Nord
On the girth of {C_3,...,C_s}-free extremal graphs
Camino Balbuena, UPC Barcelona

Abstract

Let G be a {C_3,...,C_s\}-free graph with as many edges as possible. In this paper we consider a question studied by several authors, the compulsory existence of the cycle C_{s+1} in G. It has been proved that the answer is affirmative for s =3,4,5,6. In this talk we revise the last results on the lower bounds on the order of G guaranteeing that the girth is equal to s+1. Furthermore, we focus on s=7 and characterize all the extremal graphs whose girth is not 8.
 
Joint work with E. Abajo and Ana Diánez, (Univ. Sevilla)



Thursday January 20  2011, 12h
Aula 003, Mòdul C3, Campus Nord
Graph coverings and the degree-diameter problem

Maria Zdimalova
Slovak University of Technology


Abstract

The covering graph construction is a well known method used in algebraic graph theory. We will survey the history of graph coverings, explain the method in terms of voltage aasignment and discuss its application in the degree-diameter problem.



Thursday January 13  2011, 12h
Aula 003, Mòdul C3, Campus Nord
 
The h-product of digraphs and its applications to labelings

Susana López Masip, UPC Barcelona

Abstract

In 2008, Figueroa et al., defined the following product:
let $D$ be a digraph and let $\Gamma =\{F_i\}_{i=1}^m$ be a family of digraphs such that $V(F_i)=V$.
Consider a function $h :E(D)\longrightarrow\Gamma $.
Then the product $D\otimes_{h} \Gamma$ is the digraph with vertex set
$V(D\bigotimes_{h}\Gamma)=V(D)\times V$
and $((a_1,b_1),(a_2,b_2))\in E(D\bigotimes_{h}\Gamma)\Longleftrightarrow (a_1,a_2)\in E(D)\land (b_1,b_2)\in E(h (a_1,a_2))$.

In this talk, after providing structural results related to the product, we will focus on the relation existing among the product and different labelings. We will finish the talk with some labeling enumerating results and related problems.


Thursday December 16, 2010 (12h)
Aula 003, Mòdul C3, Campus Nord
Permutations and $\beta$-shifts
 
Sergi Elizalde, Dartmouth College

Abstract

A permutation $\pi$ is realized by the shift on $N$ letters if there is an infinite word on an $N$-letter alphabet whose successive shifts by one position are lexicographically in the same relative order as $\pi$. Understanding the set of permutations realized by shifts, as well as other one-dimensional dynamical systems, is important because it provides tests to distinguish deterministic sequences from random ones.

In this talk I will give a characterization of permutations realized by shifts, and also by a natural generalization of them, where instead of $N$ we have a real number $\beta$.

 
Thursday December 2, 2010 (12h)
Aula 003, Mòdul C3, Campus Nord

Erdos' Year: Sums and Products
Oriol Serra, UPC

Abstract
 
This is a survey talk on some selected problems posed by Erdos in occasion of the Erdos' year at the FME.

Erdos and Szemeredi conjectured that, for every set A of integers, either the sumset A+A or the product set A.A are large (actually, min{|A+A|,|A.A|}\ge |A|^{2-e} for every e>0). The talk will survey some breakthroughs in the problem, including the beautiful proofs of Elekes for the exponent 5/4 and the improvement of Solimosi to the exponent 4/3.
 
Thursday November 25, 2010 (12h)
Aula 003, Mòdul C3, Campus Nord

On graphs representable by words
Sergey Kitaev, Reykjavik University

Abstract

A simple graph $G=(V,E)$ is representable if there exists a word $W$ over the alphabet $V$ such that any two distinct letters $x$ and $y$ alternate in $W$ if and only if $(x,y)$ is an edge in $E$. If $W$ is $k$-uniform (each letter of $W$ occurs exactly $k$ times in it) then $G$ is called $k$-representable. It is known that a graph is representable if and only if it is $k$-representable for some $k$. Minimum $k$ for which a representable graph $G$ is $k$-representable is called its representation number.

Representable graphs appeared first in algebra, in study of the Perkins semigroup which has played a central role in semigroup theory since 1960, particularly as a source of examples and counterexamples. However, these graphs have connections to robotic scheduling and they are interesting from combinatorial and graph theoretical point of view (for example, representable graphs are a generalization of circle graphs, which are exactly 2-representable graphs). Some of questions one can ask about representable graphs are as follows. Are all graphs representable? How do we characterize those graphs that are (non-)representable? How many representable graphs are there? How large the representation number can be for a graph on $n$ nodes?

In this talk, we will go through these and some other questions stating what progress has been made in answering them. In particular, we will see that a graph is representable if and only if it admits a so called semi-transitive orientation. This allows us to prove a number of results about representable graphs, not the least that 3-colorable graphs are representable. We also prove that the representation number of a graph on $n$ nodes is at most $n$, from which one concludes that the recognition problem for representable graphs is in NP. This bound is tight up to a constant factor, as there are graphs whose representation number is $n/2$.
 

Thursday November 18, 2010 (12h)
Aula 003, Mòdul C3, Campus Nord

Some results on connectivity of cages
Julián Salas, UPC

Abstract


An $(r;g)$-cage is a $r$-regular graph of girth $g$ of minimum order. Most work in this subject has been devoted to their existence and construction, nevertheless their structural properties have also been studied.

Fu, Huang and Rodger conjectured that all $(r,g)$-cages are $r$-connected. In this seminar we present different approaches that support this conjecture.

(Joint research with Camino Balbuena)


Thursday November 4, 2010 (12h)
Aula 003, Mòdul C3, Campus Nord

On Perturbations of Punctually Walk-Regular Graphs
Miquel A. Fiol, UPC

Abstract

In this talk we show that certain almost distance-regular graphs, the so-called $h$-punctually walk-regular graphs, can be characterized though the cospectrality of their perturbed graphs. A graph $G$ with diameter $D$ is $h$-punctually walk-regular if the number of paths of length $\ell$ between a pair of vertices $u,v$ at distance $h$ depends only on $\ell$ and $h$. The graphs perturbations considered are the most common ones. Namely, deletion of one or two vertices, addition of a pendant edge, and addition, deletion or contraction of an edge. Our results are based on the theory of graph perturbations developed by Cvetkovi\'c, Godsil, Rowlinson, and coauthors. As a consequence, some new characterizations of distance-regular graphs are obtained.

(This is joint work with C. Dalfó, E.R. van Dam, E. Garriga and W. Haemers.)


Thursday October 7, 2010 (12h)
Aula 101, Mòdul C3, Campus Nord

Interval orders and equinumerous objects
Sergey Kitaev, Reykjavik University

Abstract

Fishburn proved that intensively studied interval orders are in one-to-one correspondence with (2+2)-free posets. Recently, Bousquet-Melou et al. discovered a way to think on (2+2)-free posets in terms of so called ascent sequences which not only allowed to enumerate the posets in question, but also to connect them to other combinatorial objects, namely to Stoimanow's diagrams, certain upper triangular matrices, and to certain pattern avoiding permutations. Several other papers appeared following the influential work by Bousquet-Melou et al. Among other results, two conjectures were solved while dealing with (2+2)-free posets.

In my talk, I will provide an overview of relevant results and research directions.


Thursday September 30, 2010 (12h)
Aula 101, Mòdul C3, Campus Nord

Difference sets, Fourier analysis, and Delsarte's method
Mate Matolcsi, Alfred Renyi Institute of Mathematics, Budapest

Abstract

We will discuss a general scheme with applications to several problems from strikingly different parts of mathematics. The scheme is as follows: a symmetric subset A of a compact Abelian group G is given (A will be called the "forbidden" set). What is the maximal possible cardinality of a set B in G such that all differences b_1-b_2 do not belong to A? Possible applications range through sphere-packings, Littlewood's conjecture on simultaneous approximation, and mutually unbiased bases.


Seminar 2009-2010

Sessions and Abstracts

Sessions

(Download all abstracts in PDF.)


Semiregular cages with odd girth are edge-superconnected
Julián Salas, UPC

Ascending subgraph decompositions of bipartite graphs
Jordi Moragas, UPC
 
Thursday June 17, 2010, 12h
Aula 005 Modul C3
Campus Nord UPC
On the tree-depth of random graphs
Guillem Perarnau, UPC

Routing in Social Networks
Dieter Mitsche, CRM

Thursday June 3, 2010, 12h
Aula 005 Modul C3
Campus Nord UPC
Almost Distance-Regular Graphs
Cristina Dalfó, UPC

Local spectrum of the subconstituents
and completely pseudo-regular codes

Marc Càmara, UPC
 
Thursday May 27, 2010, 12h
Aula 005 Modul C3
Campus Nord UPC
Tree Automata and the HOM problem
Omer Giménez, UPC

Linear systems over composite moduli
Arkadev Chattopadhyay, University of Toronto
 
Thursday May 20, 2010, 12h
Aula 005 Modul C3
Campus Nord UPC
Asymptotic study of subcritical graph classes
Juanjo Rué, Laboratoire d'Informatique,
Ecole Polytechnique, Palaiseau, France


Graph Operations and Laplacian Eigenpolytopes
Arnau Padrol, UPC

Thursday May 13, 2010, 12h
Aula 005 Modul C3
Campus Nord UPC
Vosperian and superconnected vertex transitive graphs
Susana López-Masip, UPC

Empty monochromatic triangles
Clemens Huemer, UPC
 
Thursday May 6, 2010, 12h
Aula 005 Modul C3
Campus Nord UPC
Determining the maximal subset of a finite vector space
in which every subset of basis size is a basis

Simeon Ball
UPC

 
Thursday April 29, 2010, 12h
Aula 005 Modul C3
Campus Nord UPC
On the Number of Local Configurations on Sturmian words
and Discrete Planes

Laurent Vuillon
LAMA, Université de Savoie, CNRS

 
Thursday April 22, 2010, 12h
Aula 005 Modul C3
Campus Nord UPC
Cyclic Flats, Sticky Matroids, and Intertwines
Joseph E. Bonin
Department of Mathematics, The George Washington University

 
Thursday April 15, 2010, 12h
Aula 005 Modul C3
Campus Nord UPC
On the diameter of random planar graphs
Marc Noy
UPC

 
Thursday March 25, 2010, 12h
Aula 005 Modul C3
Campus Nord UPC
Most groups are hyperbolic... or most groups are trivial?
Enric Ventura
UPC

Thursday March 18, 2010, 12h
Aula 005 Modul C3
Campus Nord UPC
Even and quasi-even triangulations of point sets in the plane
Alberto Márquez
Universidad de Sevilla

Thursday March 11, 2010, 12h
Aula 005 Modul C3
Campus Nord UPC
Recent progress on the Merino-Welsh Conjecture
concerning the Tutte polynomial

Steve Noble
Department of Mathematical Sciences, Brunel University

 
Thursday February 11, 2010, 12h
Aula 005 Modul C3
Campus Nord UPC
Pointing, enumeration, and random generation
in unlabelled combinatorial classes

Éric Fusy
Ecole Polytechnique, Paris

 
Thursday February 4, 2010, 12h
Aula 005 Modul C3
Campus Nord UPC
The Colorful Helly Property for Hypergraphs
Jayme L Swarcfiter
Federal University of Rio de Janeiro

 
Thursday January 28, 2010, 12h
Aula 005 Modul C3
Campus Nord UPC
Extensions of the Scherck-Kemperman Theorem
Yahya O. Hamidoune
Univ. Paris 6

 
Wednesday January 20, 2010, 15h
Aula 101 FME
Campus Sud UPC
Shannon capacity and the perfectness of graphs
Ron Holzman
Technion - Israel Institute of Technology

Thursday December 17, 2009, 12h
Aula 005 Modul C3
Campus Nord UPC
Classification of Construction Techniques of Large Directed Graphs
Slamin
Universitas Jember, Indonesia

Thursday December 10, 2009, 12h
Aula 005 Modul C3
Campus Nord UPC
Random graphs with few disjoint cycles
Colin McDiarmid
Oxford University

 
Thursday December 3, 2009, 12h
Aula 005 Modul C3
Campus Nord UPC
Large sets in Finite Fields are sumsets
Noga Alon
Tel Aviv University

Thursday November 26, 2009, 12h
Aula 005 Modul C3
Campus Nord UPC
Workshop on Mathematical Aspects of Large Networks (WLAN)
 
 
November 18-20, 2009
CRM
Bellaterra
Small vertex-transitive and Cayley graphs of girth 6 and 5
Jozef Siran
Slovak University of Technology in Bratislava and The Open University

 
Thursday November 12, 2009, 12h
Aula 005 Modul C3
Campus Nord UPC
Optimal Graphs and Digraphs
Mirka Miller
The University of Newcastle, Australia
University of West Bohemia, Czech Republic
King's College, London, UK

 
Thursday November 5, 2009, 12h
Aula 005 Modul C3
Campus Nord UPC
Optimization in Graphs under Degree Constraints.
Application to Telecommunication Networks

Ignasi Sau
INRIA, Nice and UPC, Barcelona

 
Thursday October 29, 2009, 12h
Aula 005 Modul C3
Campus Nord UPC
Closed formulae from almost closed formulae
in 3-generated numerical semigroups

Francesc Aguiló
UPC, Barcelona

Thursday October 22, 2009, 12h
Aula 005 Modul C3
Campus Nord UPC
A new addition theorem in Z/pZ via the polynomial method
Éric Balandraud
Univ. Paris 6

Thursday October 22, 2009, 12h
Aula 005 Modul C3
Campus Nord UPC
Enumeration of indecomposable permutations and of topological maps
on orientable surfaces

Robert Cori
Univ. Bordeaux I and Ecole Polytechnique, Paris
Tuesday September 22, 2009, 12h
Aula 005 Modul C3
Campus Nord UPC

Abstracts



Thursday June 17, 2010, 12h
Aula 005 Modul C3
Campus Nord UPC
Semiregular cages with odd girth are edge-superconnected
Julián Salas, UPC

Abstract


A graph is said to be edge-superconnected if each minimum edge-cut  consists of all the edges incident with some vertex of minimum degree. A graph G is said to  be a (fd; d + 1; g)-semiregular graph if all its vertices have degree either d or d + 1. A  smallest (fd; d + 1; g)- semiregular graph G with girth g is said to be a (fd; d + 1g; g)-cage.

We show that every (fd; d + 1g; g)-cage with odd girth g is edge-superconnected.


Thursday June 17, 2010, 12h
Aula 005 Modul C3
Campus Nord UPC
Ascending subgraph decompositions of bipartite graphs
Jordi Moragas, UPC

Abstract

Let $G$ be a graph of size ${n+1\choose 2}$ for some integer $n\ge 1$. $G$ is said to have an ascending subgraph decomposition (ASD) if can be decomposed into $n$ subgraphs $H_1,\ldots,H_n$ such that $H_i$ has $i$ edges and is isomorphic to a subgraph of $H_{i+1}$, $i=1,\ldots ,n-1$. In this work we deal with ascending subgraph decompositions of bipartite graphs.
In order to do so, we consider ascending subgraph decompositions in which each factor is a forest of stars. We show that every bipartite graph $G$ with ${n+1\choose 2}$ edges such that the degree sequence $d_1\ge\cdots\ge d_k$ of one of the partite sets satisfies $d_1\ge (k-1)(n-k+1)$, and $d_i\ge n-i+2$ for $2\le i<k$, admits an ASD with star forests. We also give a necessary condition on the degree sequence of $G$ to have an ascending subgraph decomposition into star forests that is not far from the above sufficient one. Our results are based on the existence of certain matrices that we call \emph{ascending} and the construction of edge-colorings of some bipartite graphs with parallel edges.

This is joint work with A. Lladó and Slamin.


Thursday June 3, 2010, 12h
Aula 005 Modul C3
Campus Nord UPC
On the tree-depth of random graphs
Guillem Perarnau, UPC

Abstract

The  tree-depth of a graph $G$ is a parameter that plays a crucial role in the theory of bounded expansion classes and has been introduced under numerous names. We describe the asymptotic behaviour of this parameter  in the case of dense and of sparse random graphs. The results also provide analogous descriptions for the treewidth of random graphs.


Thursday June 3, 2010, 12h
Aula 005 Modul C3
Campus Nord UPC
Routing in Social Networks
Dieter Mitsche, CRM

Abstract

Given n+2 vertices with geometric positions on the positive orthant of the sphere, one of them being a source (S), one of them a sink (D), and n vertices that serve as possible hops (we assume n tending to infinity, and asymptotics are with respect to n). We assume that S and D are orthogonal, whereas all other vertices are placed randomly. S wants to send a message M to D, using at most a constant number of hops, and using a constant number of copies of M (always keeping at least one copy). The probability that a vertex v (having 2 or more copies of M) can send M to another vertex w is proportional to the angle between v and w,  i.e., the smaller the angle between v and w, the more likely v sends to w.  More precisely, the probability depends on the intensity of the Poisson point process \lambda_{v,w} between v and w, where \lambda_{v,w}=k*cos(\angle(v,w)) + \delta  (k is some constant > 0, and \delta=\delta(n) accounts for the fact that even two orthogonal points have non-zero intensity. In particular we are interested in the case \delta=o(1) and also \delta=\omega(\log n/n)). We show that a "First Meeting"-routing algorithm (choosing always the first vertex met as recipient of the copy) needs \Omega(\log(1/\delta)) steps, whereas an "Interest-Based" algorithm (choosing the vertex met only if it is "close" to D) needs at most constant time.

Joint work with J. Diaz, A. Marchetti-Spaccamela and P. Santi.


Thursday May 27, 2010, 12h
Aula 005 Modul C3
Campus Nord UPC
Almost Distance-Regular Graphs
Cristina Dalfó, UPC

Abstract

Distance-regular graphs have been a key concept in Algebraic Combinatorics and have given place to several generalizations, such as association schemes. Motivated by spectral and other algebraic characterizations of distance-regular graphs, we study `almost distance-regular graphs'. We use this name informally for graphs that share some regularity properties that are related to distance in the graph. For example, a known characterization of a distance-regular graph is the invariance of the number of walks of given length between vertices at a given distance, while a graph is called walk-regular if the number of closed walks of given length rooted at any given vertex is a constant. One of the concepts studied here is a generalization of both distance-regularity and walk-regularity called m-walk-regularity.
Another studied concept is that of m-partial distance-regularity, or informally, distance-regularity up to distance m. Using eigenvalues of graphs and the predistance polynomials, we discuss and relate these and other concepts of almost distance-regularity, such as their common generalization of (l,m)-walk-regularity. We introduce the concepts of punctual distance-regularity and punctual walk-regularity as a fundament upon which almost distance-regular graphs are built. We provide examples that are mostly taken from the Foster census, a collection of symmetric cubic graphs. Two problems are posed that are related to the question of when almost distance-regular becomes whole distance-regular. We also give several characterizations of punctually distance-regular graphs that are generalizations of the spectral excess theorem.

This is joint work with E.R. van Dam, M.A. Fiol, E. Garriga, B.L. Gorissen.


Thursday May 27, 2010, 12h
Aula 005 Modul C3
Campus Nord UPC
Local spectrum of the subconstituents and completely pseudo-regular codes
Marc Càmara, UPC

Abstract

The local spectrum of a set of vertices in a graph has been proven to be of great utility to study several metric properties of sets of vertices.
It also has applications in the area of pseudo-distance-regularity around a set and can be used to obtain quasi-spectral characterizations of completely  (pseudo-)regular codes. In this work we study the relation between the local spectrum of a set and that of its subconstituents.
Moreover, we obtain a characterization for completely pseudo-regular codes, and consequently for completely regular codes, in terms of the relation between the local spectrum of an extremal set and the local spectrum of its antipodal set.

This is a joint work with J. Fàbrega, M.A. Fiol and E. Garriga.


Thursday May 20, 2010, 12h
Aula 005 Modul C3
Campus Nord UPC
Tree Automata and the HOM problem
Omer Giménez, UPC

Abstract

The HOM problem consists in determining, given a tree homomorphism $H$ and a regular tree language $L$ represented by a tree automaton, whether $H(L)$ is regular. Recently, we have been able to obtain an algorithm deciding the HOM problem, which was a long standing open question. We solve the HOM problem and we obtain several significant intermediate results by means of a new class of tree automata with arbitrary inequality constraints and a particular kind of equality constraints.

This is joint work with Guillem Godoy, Lander Ramos and Carme Alvarez.


Thursday May 20, 2010, 12h
Aula 005 Modul C3
Campus Nord UPC
Linear systems over composite moduli
Arkadev Chattopadhyay, University of Toronto

Abstract

We study solution sets to systems of 'generalized' linear equations of the form: ell_i (x_1, x_2,..., x_n) in A_i (mod m) where ell_1,..., ell_t are linear forms in n Boolean variables, each A_i is an arbitrary subset of Z_m, and m is a composite integer that is a product of two distinct primes, like 6. Our main technical result is that such solution sets have exponentially small correlation, i.e. with the boolean function MOD_q, when m and q are relatively prime. This bound is independent of the number t of equations. This yields progress on limiting the power of constant-depth circuits with modular gates. We derive the first exponential lower bound on the size of depth-three circuits of type having a MAJORITY gate at the top, AND/OR gates at the middle layer and generalized MOD_m gates at the base, computing the function MOD_q.

This settles an open problem of Beigel and Maciel (Complexity'97) for the case of such modulus m. Our technique makes use of the work of Bourgain on estimating exponential sums involving a low-degree polynomial and ideas involving matrix rigidity from the work of Grigoriev and Razborov on arithmetic circuits over finite fields.


Thursday May 13, 2010, 12h
Aula 005 Modul C3
Campus Nord UPC
Asymptotic study of subcritical graph classes
Juanjo Rué, Laboratoire d'Informatique, Ecole Polytechnique, Palaiseau, France

Abstract

We present a unified general method for the asymptotic study of graphs from the so-called "subcritical" graph classes, which include the classes of cacti graphs, outerplanar graphs, and series-parallel graphs. This general method works both in the labelled and unlabelled framework. The main results concern the asymptotic enumeration and the limit laws of properties of random graphs chosen from subcritical classes. We show that the number $g_n/n!$ (resp. $g_n$) of labelled (resp. unlabelled) graphs on $n$ vertices from a subcritical graph class ${\cG}=\cup_n {\cG_n}$ satisfies asymptotically the universal behaviour $$ g_n = c n^{-5/2} \gamma^n\ (1+o(1)) $$ for computable constants $c,\gamma$, e.g. $\gamma\approx 9.38527$ for unlabelled series-parallel graphs, and that the number of vertices of degree $k$ ($k$ fixed) in a graph chosen uniformly at random from $\cG_n$, converges (after rescaling) to a normal law as $n\to\infty$.

This is a joint work with Michael Drmota, Eric Fusy Mihyun Kang and Veronika Kraus.


Thursday May 13, 2010, 12h
Aula 005 Modul C3
Campus Nord UPC
Graph Operations and Laplacian Eigenpolytopes
Arnau Padrol, UPC

Abstract

We introduce the Laplacian eigenpolytopes (``L-polytopes'') associated to a simple undirected graph G, investigate how they change under basic operations such as taking the union, join, complement, line graph and cartesian product of graphs, and show how several ``famous'' polytopes arise as L-polytopes of ``famous'' graphs.

Eigenpolytopes have been previously introduced by Godsil, who studied them in detail in the context of distance-regular graphs. Our focus on the Laplacian matrix, as opposed to the adjacency matrix of G, permits simpler proofs and descriptions of the result of operations on not necessarily distance-regular graphs. Additionally, it motivates the study of new operations on polytopes, such as the Kronecker product.

Thus, we open the door to a detailed study of how combinatorial properties of G are reflected in its L-polytopes. Subsequent papers will use these tools to construct interesting polytopes from interesting graphs, and vice versa.


Thursday May 6, 2010, 12h
Aula 005 Modul C3
Campus Nord UPC
Vosperian and superconnected vertex transitive graphs
Susana López-Masip, UPC

Abstract

We investigate the structure of a digraph  having a transitive automorphism group where every cutset of minimal cardinality consists of all successors or all predecessors of some vertex. We improve most of the existing results in this area.

This is joint work with Yahya Hamidoune and Anna Lladó.


Thursday May 6, 2010, 12h
Aula 005 Modul C3
Campus Nord UPC
Empty monochromatic triangles
Clemens Huemer, UPC

Abstract

We consider a variation of a problem stated by Erd\"os and Guy in 1973 about the number of convex $k$-gons determined by any set $S$ of $n$ points in the plane. In our setting the points of $S$ are colored and we say that a spanned polygon is monochromatic if all its points are colored with the same color. As a main result we show that any bi-colored set of $n$ points in $\mathbb{R}2$ in general position determines a super-linear number of empty monochromatic triangles, namely $\Omega(n^{5/4})$. We also discuss the subsequent improvement of J. Pach and G. Tóth to $\Omega(n^{4/3})$.

This is a joint work with Oswin Aichholzer, Ruy Fabila, David Flores, Thomas Hackl and Jorge Urrutia.


Thursday April 29, 2010, 12h
Aula 005 Modul C3
Campus Nord UPC
Determining the maximal subset of a finite vector space
in which every subset of basis size is a basis
Simeon Ball
UPC


Abstract

In 1947 Bose proved that in a $3 \times (p+2)$ matrix, with entries from ${\mathbb F}_p$, $p \geq 3$, there are 3 columns which are linearly dependent, He knew that the matrix whose columns are $(1,x,x^2)$, for each $x \in {\mathbb F}_p$, and $(0,0,1)$ is a $3 \times (p+1)$ matrix in which no 3 columns are linearly dependent.
In 1955 Segre, proved, up to a change of basis, that for $p \geq 3$, this is the only $3 \times (p+1)$ matrix in which no 3 columns are linearly dependent.

Segre asked if a $k \times (p+2)$ matrix, $k \leq p$, always has $k$ columns that are linearly dependent. For $k \geq p+1$, it is easy to see that this cannot be true.

In 1955 Segre proved that it is indeed the case for $k=4,5,p-3,p-2,p-1,p$ and in 1967 proved his ``conjecture'' for $k < \sqrt{p}/2+c$. In 1990 Voloch proved the conjecture for $k<p/45+c$.

The row space of the $k \times n$ matrix, in which no $k$ columns are linearly dependent, is a linear maximum distance separable code and the conjecture $n \leq p+1$, become known as the main conjecture for maximum distance separable codes (over prime fields). The conjecture is similar over non-prime fields.

In this talk I shall discuss how to prove the conjecture and moreover, how to prove that a $k \times (p+1)$ matrix, $p \geq k$, in which no $k$ columns are linearly dependent, is equivalent, up to a change of basis, to the matrix whose columns are $(1,x,x^2,\ldots,x^{k-1})$, for each $x \in {\mathbb F}_p$, and $(0,\ldots,0,1)$.

Time permitting I shall also discuss the non-prime case.


Thursday April 22, 2010, 12h
Aula 005 Modul C3
Campus Nord UPC
On the Number of Local Configurations on Sturmian words and Discrete Planes
Laurent Vuillon
LAMA, Université de Savoie, CNRS


Abstract

In this talk, we recall the nice enumerative properties of Sturmian words (words given by discretization of lines with non rational slopes). We propose to generalize several results from dimension two to dimension three. That is to count the number of local configurations on discrete planes.

We will see that the problem is very difficult and we have only a solution for the enumeration of the rectangular factors of size 1*n and 2 * n, with n in N , occurring in at least one discrete plane.  This allows us to enumerate the number of planar discrete configurations of size 2 * n and extends to discrete planes several works on discrete lines. The general  enumeration of the rectangular factors of size m*n , with m and n  in N, occurring in at least is still an open problem.


Thursday April 15, 2010, 12h
Aula 005 Modul C3
Campus Nord UPC
Cyclic Flats, Sticky Matroids, and Intertwines
Joseph E. Bonin
Department of Mathematics, The George Washington University


Abstract

There are many perspectives that one can take on matroids. This talk uses recent progress on two problems to illustrate the merits of the approach to matroid theory via cyclic flats and their ranks, which was developed independently by Julie Sims and by J. Bonin and Anna de Mier. (Sufficient background in matroid theory will be provided to make this talk accessible.)

The first problem we consider is the sticky matroid conjecture. Given a matroid, can each pair of extensions by disjoint sets be `glued together'? Matroids with this property are called sticky. It is
conjectured that sticky matroids are precisely modular matroids (which are direct sums of projective geometries). For a wide class of non-modular matroids, we use cyclic flats to construct pairs of extensions that contain incompatible geometric structures and so cannot be glued together, thus showing that these non-modular matroids are not sticky.

The second problem is that of intertwines. An intertwine of a pair of matroids (or graphs) is a matroid (or graph) such that it, but none of its proper minors, has minors that are isomorphic to each matroid (or graph) in the pair. Intertwines arise naturally when considering the unions of minor-closed classes of matroids or graphs. A corollary of Robertson and Seymour's graph minors theorem is that any pair of graphs has only finitely many intertwines. We show that the situation is very different for matroids: we use cyclic flats to construct infinite sets of intertwines for a broad class of pairs of matroids.


Thursday March 25, 2010, 12h
Aula 005 Modul C3
Campus Nord UPC
On the diameter of random planar graphs
Marc Noy
UPC


Abstract

We show that the diameter Diam(G_n) of a random labelled connected planar graph with n vertices is asymptotically almost surely of order n^{1/4} with exponential probability.

More precisely, there exists a constant c > 0 such that

Prob(n^{1/4 - epsilon} < Diam(G_n)< n^{1/4 + epsilon}) > 1-exp(-n^{c*epsilon})

for epsilon small enough and n large enough (depending on epsilon).

This is in contrast with other families of graphs, like trees or series-parallel graphs, where the diameter is a.a.s. of order n^{1/2}.

The starting point of our proof is a similar (but much more precise) result by Chassaing and Schaeffer for planar quadrangulations. We prove the result first for planar maps, and then for 2-connected maps, using the fact that a random map  has a 2-connected component of linear size a.a.s. A similar argument allows us  to extend the result to 3-connected maps, which proves it also for 3-connected  planar graphs, because they have a unique embedding in the sphere. We then reverse  the previous arguments and go first to 2-connected and then connected planar graphs.

Our approach uses generating functions in a fundamental way, together large deviation estimates, saddle-point bounds, and other tools.

We'll keep the talk at a non-technical level showing the main ideas in the proof.

This is joint work with Guillaume Chapuy, Eric Fusy and Omer Giménez.


Thursday March 18, 2010, 12h
Aula 005 Modul C3
Campus Nord UPC
Most groups are hyperbolic... or most groups are trivial?
Enric Ventura
UPC


Abstract

The sentence "Most groups are hyperbolic" was claimed by  Gromov in 1987 without proof.

Later, the statement was made precise and was proved by Ol'shanski.

We adopt a different point of view and introduce a different and equaly natural way of enumerating group presentations. It happens that, with respect to this new enumeration, the result is surprisingly different: "most groups are trivial". The proof uses Stallings graphs, to represent subgroups of the free group, and partial permutations to enumerate such graphs.

(this is joint work with F. Bassino, C. Nicaud, A. Martino and P. Weil)


Thursday March 11, 2010, 12h
Aula 005 Modul C3
Campus Nord UPC
Even and quasi-even triangulations of point sets in the plane
Alberto Márquez
Universidad de Sevilla


Abstract

Given a point set in the plane, we consider to different kind of triangulations, those with all the vertices with even degree (even triangulations or e-triangulations for short) and those with all non-extreme points with even degree (quasi-even triangulations or q-e-triangulations for short). These particular cases of triangulations are interesting by the following reason:

It is known form the four colors theorem that any triangulation of a point set can be colored using at most four colors. It is not difficult to see that q-e-triangulations are exactly those that can be colored with 3 colors. Aditionally, e-triangulations are, of course eulerian.

In this talk, we study e-triangulations for a point set in convex position, and q-e-triangulations for point sets in general position.


Thursday February 11, 2010, 12h
Aula 005 Modul C3
Campus Nord UPC
Recent progress on the Merino-Welsh Conjecture concerning the Tutte polynomial
Steve Noble
Department of Mathematical Sciences, Brunel University


Abstract

Merino and Welsh conjectured that for any 2-connected loopless graph, either the number of acyclic orientations or the number of totally cyclic orientations is at least the number of spanning trees. Equivalently max {T(G;2,0), T(G;0,2)} >=3D T(G;1,1).
Jackson has shown that max {T(G;3,0), T(G;0,3)} >=3D T(G;1,1).

We simplify and extend Jackson's method to give sufficient conditions on G for when max {T(G;x,y), T(G;y,x)} >=3D T(G;z,z).
We also show that max {T(G;4,0), T(G;0,4)} >=3D T(G;2,2) and that for some large classes of graphs max {T(G;2a,0), T(G;0,2a)} >=3D T(G;a,a) providing a>=3D2. Finally we show = that for paving matroids the Tutte polynomial is convex along the portion of any line x+y=3Dc lying in the positive quadrant.

This is joint work with Bill Jackson, Laura Chavez, Criel Merino, Marcelino Ramirez and Dave Wagner.


Thursday February 4, 2010, 12h
Aula 005 Modul C3
Campus Nord UPC
Pointing, enumeration, and random generation in unlabelled combinatorial classes
Éric Fusy
École Polytechnique, Paris


Abstract

Pointing is a very efficient tool to perform enumeration and random generation in a combinatorial class, as it gives a way to start a recursive decomposition. In the labelled case, the approach works fine because all atoms are distinguishable, hence pointing multiplies by $n$ the $n$th counting coefficient and preserves the fixed-size uniform distribution. In contrast, in the unlabelled case, the pointing approach does not adapt straightforwardly because a structure of size n can give rise to less than n pointed structures (rooting at two vertices in symmetric position gives the same rooted object).

In this talk, we present a pointing operator, called ``cycle-pointing'',  such that each unlabelled unrooted structure of size n gives rise to n unlabelled pointed structures. This yields an automatic exact/asymptotic enumeration method for unlabelled combinatorial classes (such as trees and graph families), and it gives rise to  very efficient random generators, which rely on the principles of ``Boltzmann samplers''.


Thursday January 28, 2010, 12h
Aula 005 Modul C3
Campus Nord UPC
The Colorful Helly Property for Hypergraphs
Jayme L Swarcfiter
Federal University of Rio de Janeiro

Abstract

The definition of the Helly property for hypergraphs was motivated by Helly's theorem for convex sets. Similarly, we define the colorful Helly property for a family of hypergraphs, motivated by the colorful Helly theorem for collections of convex sets, by Lov\'asz. We describe some general facts about the colorful Helly property and prove complexity results. In particular, we show that it is Co-NP-complete to decide if a family of $p$ hypergraphs is colorful Helly, even if $p = 2$. However, for any fixed $p$, we describe a polynomial time algorithm to decide if such family is colorful Helly, provided at least $p-1$ of the hypergraphs are $p$-Helly.

Joint work with R. Barbosa, E. Martins and M. Dourado.


Wednesday January 20, 2010, 15h
Aula 101 FME
Campus Sud UPC
Extensions of the  Scherck-Kemperman Theorem
Yahya O. Hamidoune
Univ. Paris 6


Abstract

Let $\Gamma =(V,E)$  be a  directed graph with a transitive automorphisms group. Let $v\in V$ and let $F$ be a finite subset of $V$ with $v\in F.$ As usual we denote by $\Gamma  (F)$ the image of $F.$

We prove that the size of $\Gamma  (F)$ is at least  $$ |F|+ |\Gamma  (v)|-|\Gamma ^- (v)\cap F|.$$

Let  $A,B$ be finite subsets of a group $G.$ Applied to Cayley graphs, our result reduces to the following extension of the Scherk-Kemperman Theorem, proved by Kemperman: $$|AB|\ge |A|+|B|-|A\cap (cB^{-1})|,$$ for every  $c\in AB.$


Thursday December 17, 2009, 12h
Aula 005 Modul C3
Campus Nord UPC
Shannon capacity and the perfectness of graphs
Ron Holzman
Technion - Israel Institute of Technology


Abstract

The Shannon capacity of a graph measures the maximal volume of error-free communication on a noisy channel described by the graph. This is a fundamental notion in information theory, and it has motivated some challenging problems in graph theory. In particular, it prompted the study of perfect graphs, which deals with the relation between the chromatic number and the size of a maximum clique. In the talk I will present these concepts and the connection between them, highlighting some of the remarkable mathematical achievements in this area.


Thursday December 10, 2009, 12h
Aula 005 Modul C3
Campus Nord UPC
Classification of Construction Techniques of Large Directed Graphs
Slamin
Universitas Jember, Indonesia

Abstract

We classify the construction techniques of large directed graphs. We first present the construction techniques that have been established, namely, the generalised de Bruijn digraphs, generalised Kautz digraphs, line digraphs, digon reduction, generalised digraphs on alphabets, partial line digraphs, digraphs constructed by the use of voltage assignments and vertex deletion scheme. Then we classify the construction techniques according to the general method of generating new digraphs; the diregularity of generated digraphs; and the range of orders of the generated digraphs.


Thursday December 3, 2009, 12h
Aula 005 Modul C3
Campus Nord UPC
Random graphs with few disjoint cycles
Colin McDiarmid
Oxford University


Abstract

Fix a positive integer $k$, and consider the class of all graphs which do not have $k+1 vertex-disjoint cycles. A classical result of Erd\H{o}s and P\'{o}sa says that each such graph $G$ contains a blocker of size at most $f(k)$. Here a {\em blocker} is a set $B$ of vertices such that $G-B$ has no cycles.

We give a seemingly minor but useful extension of this result, and deduce that almost all such labelled graphs on vertex set $1,\ldots,n$ have a blocker of size $k$. This yields an asymptotic counting formula for such graphs; and allows us to deduce further properties of a graph $R_n$ taken uniformly at random from the class: we see for example that the probability that $R_n$ is connected tends to a specified limit as $n \to \infty$.

There are corresponding results when we consider unlabelled graphs with few disjoint cycles.
We consider also variants of the problem involving for example disjoint long cycles.

This is recent joint work with Valentas Kurauskas and Mihyun Kang.


Thursday November 26, 2009, 12h
Aula 005 Modul C3
Campus Nord UPC
Large sets in Finite Fields are Sumsets
Noga Alon
Tel Aviv University


Abstract

I will sketch a proof of the fact that for a prime p, every complement of a set of roughly sqrt p elements of the finite field Z_p is a sumset, that is, is of the form A+A, whereas there are complements of sets of size roughly p^{2/3} which are not sumsets. This improves estimates of Green and Gowers, and can also be used to settle a related problem of Nathanson.


Thursday November 12, 2009, 12h
Aula 005 Modul C3
Campus Nord UPC
Small vertex-transitive and Cayley graphs of girth 6 and 5
Jozef Siran
Slovak University of Technology in Bratislava and The Open University


Abstract

We examine constructions of the smallest known vertex-transitive graphs of a given degree and girth 6 and 5. Most of these graphs can be described in terms of regular lifts of suitable smaller graphs, and we determine which of these are Cayley graphs. We also investigate higher level of transitivity of the smallest known vertex-transitive graphs of a given degree and girth $6$ and relate their constructions to near-difference sets.


Thursday November 5 2009, 12h
Aula 005, ModulC3
Campus Nord UPC
Optimal Graphs and Digraphs
Mirka Miller
The University of Newcastle, Australia
University of West Bohemia, Czech Republic
King’s College London, UK

Abstract

We consider three parameters of a graph: the order (number of vertices), maximum degree (or degree in case of a regular graph) and the diameter. Three related problems arise with respect to these parameters by fixing in turn two of the parameter and optimizing the third one. For example, optimizing the order, given the maximum degree and diameter gives the (undirected) degree/diameter problem: find the maximum possible number of vertices in a graph with given diameter and maximum degree. The corresponding problem for directed graphs uses maximum out-degree instead of maximum degree.

In this talk we will give an overview of the progress of the degree/diameter problem for both directed and undirected graphs, and we
consider also the less-studied order/degree and order/diameter problems.

We conclude with  a number of related open problems.


Thursday October 29, 2009, 12h
Aula 005 Modul C3
Campus Nord UPC
Optimization in Graphs under Degree Constraints.
Application to Telecommunication Networks
Ignasi Sau
INRIA, Nice and UPC Barcelona


Abstract

This talk will overview some of the results of my thesis, which has been defended on October 16 in Sophia Antipolis (France). The final version of the manuscript can be found here: http://www-sop.inria.fr/members/Ignasi.Sauvalls/PhD_Ignasi.pdf. The first part is devoted to traffic grooming, which is a central problem in optical networks. It refers to packing low-rate signals into higher-speed streams, in order to improve bandwidth utilization and reduce the network cost. The objective is to minimize the number of Add-Drop Multiplexers (ADMs), which are devices that insert/extract low-rate traffic to/from a high-speed stream. In graph-theoretical terms, the problem can be translated into finding a partition of the edges of a request graph into subgraphs with bounded number of edges, the objective being to minimize the total number of vertices of the partition. We first focus in Chapter 1 on a general request graph when the topology is a ring or a path. We provide the first inapproximability result for traffic grooming for fixed values of the grooming factor C, answering affirmatively to a conjecture in the literature. We also provide a polynomial-time approximation algorithm for traffic grooming in rings and paths, with an approximation ratio independent of C. We introduce in Chapter 2 a new model of traffic grooming in unidirectional rings, in order to design networks being able to support any request graph with bounded maximum degree. We show that the problem is essentially equivalent to finding the least integer M(C,D) such that the edges of any graph with maximum degree at most D can be partitioned into subgraphs with at most C edges and each vertex appears in at most M(C,D) subgraphs, and we establish the value of M(C,D) for almost all values of C and D. In Chapter 3 we focus on traffic grooming in bidirectional rings with symmetric shortest path routing and all-to-all unitary requests, providing general lower bounds and infinite families of optimal solutions for C=1,2,3 and C of the form k(k+1)/2. In Chapter 4 we study traffic grooming for two-period optical networks, a variation of the traffic grooming problem for WDM unidirectional ring networks with two grooming factors C and C' that allows some dynamism on the traffic. Using tools of graph decompositions, we determine the minimum number of ADMs for C=4, and C'=1,2,3. 

The study of the traffic grooming problem leads naturally to the study of a family of graph-theoretical problems dealing with general constraints on the degree. This is the topic of the second part of this thesis. We begin in Chapter 5 by studying the computational complexity of several families of degree-constrained problems, giving hardness results and polynomial-time approximation algorithms. We then study in Chapter 6 the parameterized complexity of finding degree-constrained subgraphs, when the parameter is the size of the subgraphs. We prove hardness results in general graphs and provide explicit fixed-parameter tractable algorithms for minor-free graphs. We obtain in Chapter 7 subexponential parameterized and exact algorithms for several families of degree-constrained subgraph problems on planar graphs, using bidimensionality theory combined with novel dynamic programming techniques. Finally, we provide in Chapter 8 a framework for the design of dynamic programming algorithms for surface-embedded graphs with single exponential dependence on branchwidth. Our approach is based on a new type of branch decomposition called surface cut decomposition, which generalizes sphere cut decompositions for planar graphs. The existence of such algorithms is proved using diverse techniques from topological graph theory and analytic combinatorics.


Thursday October 22, 2009, 12h
Aula 005 Modul C3
Campus Nord UPC
Closed formulae from almost closed formulae in 3-generated numerical semigroups
Francesc Aguiló
UPC, Barcelona


Abstract

Let $S=<a,b,N>$ be a numerical 3-semigroup, that is $a<b<N$, $\gcd(a,b,N)=1$ and the generating set of $\{a,b,N\}$ of $S$ is minimal.
Let us consider the weighted double-loop digraph $G(N;a,b;a,b)$ and a related minimum distance diagram $H=L(l,h,w,y)$. We say that the 2D periodic tessellation by $H$ is related to the semigroup $S$.
From the numerical point of view, it is a known fact that several properties of $S$ can be efficiently derived from $H$: The Frobenius' number, the Apéry set $Ap(N;S)$, the set of gaps (and its cardinal) and the set of factorizations of any $m\in S$
\[
F(S;m)=\{(x,y,z)\in\Nat3~|~xa+yb+zN=m\}
\] and the related denumerant $d(S;m)=|F(S;m)|$.
From the symbolical point of view, we can derive closed formulae from the previous numerical information. Symbolical questions arise from the need of closed formulae for a sequence of semigroups $\{S_n\}_{n\geq n_0}$, usually for sequences of some interest.
This talk focuse the main goal on the sequence $S_n=<n-2,n-1,n>$, for even $n\geq6$, which are the only 3-generated critical semigroups attaining the optimal value for the Frobenius' number. That is, set
\[
G(n)=\max_{1<a<n,\gcd(a,b,n)=1}f(<a,b,n>).
\]
Then Lewin gave the expression of $G(n)$ and all the critical semigroups: $<n/2,n-1,n>$ and $<n-2,n-1,n>$ for even $n$, and $<(n-1)/2,n-1,n>$ when $n$ is odd.
For this sequence of semigroups, we will study the distribution of the denumerants between the pair of maximal gaps of $S_n$. We will give the critical values $m^*$ for the maximal denumerant and the related factorization sets $F(S_n;m^*)$ as well.


Thursday October 1, 12h
Aula 005 Modul C3
Campus Nord UPC
A new addition theorem in Z/pZ via the polynomial method
Éric Balandraud
Univ Paris 6


Abstract

Following the classical addition theorems in Z/pZ: Cauchy-Davenport Theorem, Hamidoune Da Silva Theorem (known as Erdos-Heilbronn Conjecture), we will present a new addition theorem, that express the minimal size of the set of subsums of a set.

The proof is based on the polynomial method and is very similar of Alon Nathanson Rusza's proof of Hamidoune-Da Silva's Theorem. We will expose the ideas of this proof and some consequences of this new addition theorem.


Tuesday September 22, 12h
Aula 005 Modul C3
Campus Nord UPC
Enumeration of indecomposable permutations and of topological  maps
on orientable surfaces
Robert Cori
Uni. Bordeaux I and Ecole Polytechnique, Paris


Abstract

A permutation $a_1a_2\ldots a_n$ is indecomposable if there does not exist $p<n$ such that $a_1a_2\ldots a_p$ is a permutation of $\{ 1,2,\ldots ,p\}$. We give a formula for the number of indecomposable permutations of of ${\mathbb S}_n$  with $m$ cycles and compute  the asymptotic  probability that a permutation is indecomposable as $n$ goes to infinity with $m/n$ fixed. The asymptotic probability is monotone in $m/n$, and there is no threshold  phenomenon: it degrades gracefully from 1 to 0.

When $n=2m$, a slight majority ($51.1\ldots$ percent) of the  permutations are indecomposable. We also consider indecomposable fixed point free  involutions which are in bijection with maps of arbitrary genus on orientable  surfaces, for these involutions with $m$ left-to-right maxima we obtain a lower bound for the probability of being  indecomposable.



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

Abstract

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


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 Barcelona

Abstract

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 Praze

Abstract

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 II

Abstract

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 Berlin

Abstract

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.


Thursday March 26 2009, 15h
Random graphs on surfaces
Marc Noy, UPC Barcelona

Abstract

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.
 
This is joint work with Guillaume Chapuy, Eric Fusy, Omer Giménez, and Bojan Mohar.


Thursday March 12 2009, 15h
Extremal Graph Theory, old and new results
Miklós Simonovits , Alfred Rényi Institute of Mathematics, Budapest

Abstract

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.


Thursday March 5 2009, 15h
Ramsey Theory and Constraint Propagation
Albert Atserias, UPC Barcelona

Abstract

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 Jerusalem

Abstract

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.


Thursday January 29 2009, 15h
Small  regular bipartite graphs of girth 8
Camino Balbuena, UPC Barcelona

Abstract

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

Abstract

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.


Thursday January 15 2009, 15h
Perfect Codes from Cayley Graphs over Lipschitz Integers
Carmen Martí­nez , Univ. Cantabria

Abstract

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


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

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

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.


Thursday November 27, 2008, 15h
Maps on orientable surfaces
Guillaume Chapuy, Ecole Polytechnique, Paris

Abstract

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.


Thursday November 20, 2008
Extremal examples for the Davenport constant in rank two groups
David Grynkiewicz , Graz Universitat, Austria

Abstract

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

Abstract

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.


Thursday November 6, 2008
Structural Properties of Sparse Graphs
Patrice Ossona de Mendez, CNRS, Paris

Abstract

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.


Thursday October 30, 2008
Graph homomorphism numbers and Tutte-Grothendieck invariants.
Andrew Goodall, University of Bristol

Abstract

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.


Thursday October 16, 2008, 15h
Ramsey theory and the Regularity Lemma
Miklos Ruzsinko, Computer and Automation Research Institute, Budapest

Abstract

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


Dijous 9 d'Octubre 2008, 15h
On k-Walk-Regular Graphs
Miquel Angel Fiol, UPC Barcelona

Abstract

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

CIMPA School Combinatorics, Graph Theory and applications

Tentative plan for a CIMPA School on Combinatorics, Graph Theory and applications to be held in Vientiane, Laos, December 2014

Download

Advanced Course: Combinatorial Convexity (May 7-18, 2012)



Combinatorics, Graph Theory and Applications


Doctoral Program on Applied Mathematics


Universitat Politècnica de Catalunya




Advanced Course


Combinatorial Convexity


by Imre Bárány



May 7-18, 2012






Course Description


The course will cover several topics in combinatorial convexity, where  theorems of Caratheodory, Helly, Radon, and Tverberg are the typical and  classical results. We plan to investigate weak epsilons-nets, halving  lines and planes, the (p,q) problem and its solution, extensions to lattice convex sets, and colourful versions of theorems of Helly,  Caratheodory, Radon, Tverberg, and the like. Further possible  topics are transversals, lattice polytopes and random polytopes. The  methods here use tools from linear algebra, combinatorics, topology,  geometry, probability theory, and geometry of numbers.

Some literature:

 

  • the classic survey by Danzer, Grunbaum, Klee "Helly's  theorem and its relatives", Convexity, Proc. Symp. Pure Math., 7, American Mathematical Society, pp. 101–179.
  • some chapters from J. Matousek's excellent  book "Lectures on discrete geometry" Springer GTM Vol. 212, 2002.


Imre Bárány


Imre Bárány is a member of the Alfred Rényi Institute of Mathematics in Budapest and of the University College of London. His main research interests are in combinatorics and discrete geometry. Among his main contributions, he gave a surprisingly simple alternative proof of Lovász theorem on the chromatic number of Kneser graphs, he solved a problem of Sylvester on the probability of random point sets in convex position, he gave colored versions of Caratheodoy and Helly  theorems and proved a central limit theorem on random points in convex bodies. He received the Erdös prize of the Hungarian Academy of Sciences in 1982, was invited speaker in the ICM 2002 held in Beijing and he is in the Editorial Board of several journals, including Combinatorica, Mathematika, and the Online Journal of Analytic Combinatorics.


Registration and further information


Please send an e-mail tagged 'Barany2012Course' to convexitycourse2012@ma4.upc.edu indicating

Name
Affiliation
e-mail address
Short cv (academic degree, current situation, mathematical background)

 

There is no registration fee.

For further information please contact convexitycourse2012@ma4.upc.edu.

Poster announcement of the course.



Schedule


Monday May 7 10h Welcome coffee (room 'R', FME)
11h-13h
Tuesday May 8 11h-13h Tuesday May 15 11h-13h
Wednesday May 9 11h-13h Wednesday May 16 11h-13h
Thursday May 10 11h-13h Thursday May 17 11h-13h
Friday May 11 11h-13h


Preliminary list of participants


Aguiló, Francesc (Ma4, UPC Barcelona)

Balbuena, Camino  (UPC, Barcelona)

Ball, Simeon (Ma4, UPC, Barcelona)

Boroczky, Karoly (Renyi Institute Budapest)

Brunat, Josep M. (Ma2, UPC, Barcelona)

Comellas, Francesc (Ma4, UPC, Barcelona)

Dalfó, Cristina (Ma4, UPC, Barcelona)

Fàbrega, Josep (Ma4, UPC, Barcelona)

Fiol, Miquel Àngel (Ma4, UPC, Barcelona)

Hansberg, Adriana (UPC, Barcelona)

Huemer, Clemens (Ma4, UPC, Barcelona)

Lladó, Anna (Ma4, UPC, Barcelona)
López-Masip, Susana-Clara (Ma4, UPC, Barcelona)

Magazinov, Alexander (Mathematical Institute of RAS, Moscow)

Maureso, Montserrat (Ma2, UPC, Barcelona)

Miralles, Alícia (Ma4, UPC, Barcelona)

Molina, Enrique (UPC, Barcelona)

Mora, Mercè (Ma2, UPC Barcelona)

Padrol, Arnau (Ma2, UPC, Barcelona)
Pelayo, Ignacio (Ma3, UPC Barcelona)
Perarnau, Guillem (Ma4, UPC, Barcelona)
Pérez-Mansilla, Sónia (Ma4, UPC, Barcelona)
Pfeifle, Julian (Ma2, UPC, Barcelona)
Petridis, Giorgis (Cambridge University)
Serra, Oriol (Ma4, UPC, Barcelona)


Lecture room and directions


The lectures will be held in Room 100 in the building of the Facultat de Matemàtiques i Estadística (FME).

 

Please see the map for the location of the building. To get there you can use Metro L3 (Green Line)

and step off at Palau Reial. For further directions ask info.osrm@upc.edu.

 



Updates will be posted concerning lecture room, directions, list of participants and course notes.

Advanced Course Polymatroids etcetera: Algorithms and Pretty Theorems, by Jack Edmonds (January 11-21, 2010)

Advanced Course Large Graphs, by Mirka Miller (June 2-8, 2010)

Recent Developments in Largest Graphs and Digraphs with Given Degree and Diameter by Prof. Mirka Miller, June 2-8, 2010

ICPAM-CIMPA School Combinatorics, Graph Theory and applications

Advanced Course Eigenvalues, Willem Haemers (June 7-18, 2011)

Download View full-size image

Download View full-size image

Download View full-size image

Download View full-size image