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.

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: Tuesday 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

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

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:

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:

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:

Barcelona, 25-27 November 2015

Zero-error information, Operators, and Graphs Workshop

http://www.qciao.org/

Confirmed invited participants:

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:

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:

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:

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:

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:

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:

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 sessions and other activities

Thursday July 17, 2014, 12h

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

Some Developments in Sum Graph Labelling

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.

Sessions

The Inverse Problem on finite networks

On the largest tournament Maker can build

Special session in memory of Joan Gimbert

Welcome

Les aportacions de Joan Gimbert a la teoria de grafs

The contribution of Joan Gimbert to the degree/diameter problem

Polytopes of degree 1

An alternative way to generalize the pentagon

A short proof of the odd-girth theorem

Polarity graphs and other $C_4$-free graphs of large size

Locally identifying colourings of graphs

Huge locating dominations of graphs

Strongly regular graphs

Testing function isomorphism

Moments in graphs

Many neighborly polytopes

Graphs and Matrices with Integral Spectrum in Some Families

Consecutive patterns in permutations: clusters, generating functions and asymptotics

On a conjecture of Erdös, Faber and Lovász

Algunos resultados en teoría anti-Ramsey aritmética

A removal lemma for linear configurations in subsets of the circle

Upper Bounds for Higher Sumsets

Maximum degree in minor-closed classes of graphs

On the cardinality of sumsets in torsion free groups

Rainbow k-connection in Dense Graphs

Complete Bipartite Turan numbers

On the face vectors of polytopes: unimodality and generalized Euler's relations

Breaking symmetry in tournaments

Quantum Correlations and Device-Independent Quantum Information Processing

Abstracts

Dependent Random Choice

Edge distance-regularity

On 3-domination critical graphs

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

Line-identifying codes

Els Treballs i els Dies amb l'Ernest

Integer lattice points in the plane

Bandidos malvados: ¿cómo luchar contra ellos aleatoriamente?

On a slicing formula for bipartite graphs

Regular Star Complements in strongly regular graphs

A tribute to Yahya ould Hamidoune

Dynamic programming in sparse graphs

Some stability problems in finite geometry

Erdös Year. Erdös problems on distinct and repeated distances

Identifying codes for regular graphs.

On the girth of {C_3,...,C_s}-free extremal graphs

Graph coverings and the degree-diameter problem

The h-product of digraphs and its applications to labelings

Permutations and $\beta$-shifts
 

Erdos' Year: Sums and Products

Some results on connectivity of cages

On Perturbations of Punctually Walk-Regular Graphs

Interval orders and equinumerous objects

Difference sets, Fourier analysis, and Delsarte's method

Sessions

Abstracts

Semiregular cages with odd girth are edge-superconnected

Ascending subgraph decompositions of bipartite graphs

On the tree-depth of random graphs

Routing in Social Networks

Almost Distance-Regular Graphs

Local spectrum of the subconstituents and completely pseudo-regular codes

Tree Automata and the HOM problem

Linear systems over composite moduli

Asymptotic study of subcritical graph classes

Graph Operations and Laplacian Eigenpolytopes

Vosperian and superconnected vertex transitive graphs

Empty monochromatic triangles

Determining the maximal subset of a finite vector space
in which every subset of basis size is a basis

On the Number of Local Configurations on Sturmian words and Discrete Planes

Cyclic Flats, Sticky Matroids, and Intertwines

On the diameter of random planar graphs

Most groups are hyperbolic... or most groups are trivial?

Even and quasi-even triangulations of point sets in the plane

Recent progress on the Merino-Welsh Conjecture concerning the Tutte polynomial

Pointing, enumeration, and random generation in unlabelled combinatorial classes

The Colorful Helly Property for Hypergraphs

Extensions of the  Scherck-Kemperman Theorem

Shannon capacity and the perfectness of graphs

Classification of Construction Techniques of Large Directed Graphs

Random graphs with few disjoint cycles

Large sets in Finite Fields are Sumsets

Small vertex-transitive and Cayley graphs of girth 6 and 5

Optimal Graphs and Digraphs

Optimization in Graphs under Degree Constraints.
Application to Telecommunication Networks

Closed formulae from almost closed formulae in 3-generated numerical semigroups

A new addition theorem in Z/pZ via the polynomial method

Enumeration of indecomposable permutations and of topological  maps
on orientable surfaces

Sessions

The sum of digits of primes

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.

Bounds for complex roots of combinatorial polynomials

Algorithmic relations of the Tutte polynomial

Graphs with many edges containing no complete bipartite graphs

Extension Diameter of Boolean Lattices

Random graphs on surfaces

Extremal Graph Theory, old and new results

Ramsey Theory and Constraint Propagation

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

Small  regular bipartite graphs of girth 8

The exterior algebra method in additive combinatorics

Perfect Codes from Cayley Graphs over Lipschitz Integers

Sum-free sets, sets with small sumset and the clique number of random Cayley graphs.

Construcción de grandes grafos de determinadas clases

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.

Sylvester-Frobenius change problem for vectors

Maps on orientable surfaces

Extremal examples for the Davenport constant in rank two groups

k-dominación en grafos

Structural Properties of Sparse Graphs

Graph homomorphism numbers and Tutte-Grothendieck invariants.

Ramsey theory and the Regularity Lemma

On k-Walk-Regular Graphs

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

• Imre Bárány

• Registration and further information

• Schedule

• Preliminary list of participants

• Lecture room and directions

Course Description

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

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.

Schedule

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)

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.