Courses and seminars
ALBCOM Seminar on Algorithms and Theory of Computation COMBGRAPH Seminar on Combinatorics, Graph Theory and Applications
LIMDA Joint Seminar Announcements 20172018
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 C3005, 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 C3005, 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 osR\'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 C3005, Campus Nord UPC
Speaker: Pablo Candela (UAMICMAT)
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 2A. 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 3k4 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 C3005, Campus Nord UPC
Speaker: M. Ángeles Serrano (ICREAUB)
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 selfsimilarity and scaleinvariance. 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 scalefree 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 selfsimilar 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 highfidelity smallerscale replicas of large real networks, and sustains the design of a new multiscale navigation protocol in hyperbolic space which boosts the success of singlescale versions.
Date: Wednesday November 15, 2017
Time: 12h
Where: Room C3005, 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 nonrepresentable 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 C3005, Campus Nord UPC
Speaker: Maximilian Wötzel (UPCBGSMath)
Title: On Testing MinorFreeness in Bounded Degree Graphs with OneSided Error
Abstract: We present a onesided error property testing algorithm for Hminor freeness in boundeddegree
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 minorfreeness 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_kminor 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 edgecut 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 C3005, 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émereditype 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 nontrivial solutions due to Rúzsa as well as Rué et al.
Date: Wednesday October 18
Time: 12h
Where: Room C3005, Campus Nord UPC
Speaker: Gonzalo Fiz (UPCBGSMath)
Title: The trianglefree 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 nonedges of G_{m−1} which do not create a triangle. The process ends when we reach a maximal trianglefree graph; we denote by G_{n,\triangle} this (random) final graph. This "trianglefree 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 trianglefree graph G_{n,\triangle} it produces.
A technique which has proved extremely useful in the study of random graph processes is the socalled ‘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}sR\'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 201617
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 C3005, 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 quotientlike 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 C3005, Campus Nord UPC
Speaker: Mohan Prabu, British University, Hanoi (Vietnam)
Title: Product of digraphs, (super) edgemagic valences and related problems
Abstract: A (p, q)graph G is called edgemagic 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 edgemagic labelling of G and the constant is called the valence. An edgemagic labelling with the extra property that f (V (G)) = {1, 2, ..., p} is called super edgemagic. A graph is called perfect (super) edgemagic if all theoretical (super) edgemagic valences are possible.
In this seminar, we will present some results related to:
the valences of (super) edgemagic labelings of crowns Cm ⊙ Kn, where m = pq, p and q are different odd primes;
the edgemagic valences of cycles (motivated by the conjecture of Godbold and Slated which states that all cycles, or order n > 7 are perfect edgemagic).
Finally, we will discuss the super edgemagicness of some graphs of equal order and size (motivated by their applications by means of the ⊗hproduct).
Date: Thursday, June 15, 2017
Time: 10:0011:30
Where: Room S05, FME, Campus Sud UPC
Speaker: Benny Sudakov, ETH, Zurich
Title: Rainbow cycles and trees in properly edgecolored complete graphs
Abstract: A rainbow subgraph of a properly edgecolored 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 edgecolored 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:0013:00
Where: Room S05, FME, Campus Sud UPC
Speaker: Dieter van Melkebeek, University of WisconsinMadison, 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
nvertex 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 bruteforce
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^{2epsilon}) 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 NPcomplete problems. For example, under
the same hypothesis we can show that for any constant d>=3, dCNF
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 twoplayer
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 dCNF formulas.
Date: Tuesday June 6, 2017
Time: 10h3011h15
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: 11h3012h30
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_tminorfree graph has a proper (t1)colouring. This talk is about improper relaxations of Hadwiger’s Conjecture. We prove that every K_tminorfree graph is (2t2)colourable with monochromatic components of order at most ⌈(t2)/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_tminorfree graph is (t1)colourable with monochromatic degree at most t2. 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 3coloured 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 queuenumber, linklessly or knotlessly embeddable graphs, graphs with given Colin de Verdière parameter, and graphs with given thickness (with relevance to the earthmoon problem).
This is joint work with Jan van den Heuvel
(arXiv:1704.06536) and Patrice Ossona de Mendez and Sangil Oum (arXiv:1611.09060).
Date: Tuesday May 30, 2017
Time: 11h11h50
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 twoway 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 bestknown communication complexity, i.e. the number of transmitted bits necessary to
communicate a 1bit 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: 10h10h45
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 C3005, 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 Hgames 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 C3005, 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 cumulantlike 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 GianCarlo 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 C3005, Campus Nord UPC
Speaker: Clement Requilé, UPC, Barcelona
Title: Enumeration of 4regular planar graphs
Abstract: In this talk, we will show how to derive the exponential generating function counting labeled 4regular planar graphs via a system of equations. In particular, this will allow us to enumerate this family. As byproduct of this method, we can also access the exponential generating functions counting 3connected simple 4regular maps, which turns out to be algebraic, and connected 4regular planar graphs, which is Dfinite. This is joint work with Marc Noy and Juanjo Rué.
Date: Wednesday April 5, 2017
Time: 12:00
Where: Room C3005, 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 nonempty intersection. The celebrated theorem of ErdosKoRado from 1961 says that when n \geq 2k, any such family has size at most {n1 \choose k1}. 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 foolingset 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 crossfree matching,
which provides a lower bound on the size of the biclique covering of a
graph. A foolingset 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
foolingset matrix will be discussed: For a foolingset zerononzero
pattern chosen at random, is the minimum rank of a matrix with that
zerononzero 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 C3005, Campus Nord UPC
Speaker: Camino Balbuena
Title: Vertex disjoint 4cycles in bipartite tournaments.
Abstract: Let k ≥ 2 be an integer. Bermond and Thomassen conjectured that every
digraph with minimum outdegree at least 2k − 1 contains k vertex disjoint cycles.
In this paper we prove that every bipartite tournament with minimum outdegree at
least 2k −2 and minimum indegree at least 1 contains k disjoint 4cycles whenever
k ≥ 3. Also we show a bipartite tournament with outdegree 2 and indegree 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 4cycles.
Date: Thursday, February 16, 2017
Time: 12:00
Where: Room C3005, Campus Nord UPC
Speaker: Miquel Àngel Fiol
Title: Complexity measures of edgeuncolorability in cubic graphs
Abstract: In this talk we survey the different complexity measures of edgeuncolorability 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 nonedgecolorable 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 5flow 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 SpaceBounded 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 NPhard 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
spacebounded setting. The question is: Can one always make the
accepting computation paths of nondeterministic spacebounded 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
stconnectivity 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 spacebounded 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 kCNF 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((Wk)^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 sizespace tradeoffs for the cutting planes
proof system, where the upper bounds hold for size and total space for
derivations with constantsize 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 tradeoffs to hold uniformly for resolution, polynomial
calculus and cutting planes, thus capturing the main methods of
reasoning used in current stateoftheart SAT solvers.
We prove our results by a reduction to communication lower bounds in a
roundefficient 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 tradeoffs between cost and number of
rounds in the game of [Dymond and Tompa '85] played on directed acyclic
graphs.
As a byproduct of the techniques developed to show these proof
complexity tradeoff results, we also obtain an exponential separation
between monotoneAC^(i1) and monotoneAC^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^(i1) n) require exponential size.
This is joint work with Susanna F. de Rezende and Marc Vinyals.
Date: Wednesday December 7 2016
Where: Room C3005, 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 NPcomplete, even for k=2 and by same construction also the problem deciding whether ghw(H)<=k is NPcomplete 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 edgeintersection property (BIP) and the more general bounded multiedge 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 VCdimension. 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 C3005, 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 incorporarles 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 kcycles) with a formula from the logic of two linear orders?
Date: 20161115 (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 SingleExponential 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 fixedparameter tractability is not known, or the fastest known algorithms have doublyexponential 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, fixedparameter tractability of those problems, or provides the first algorithms with singlyexponential 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 RSwap Bribery is fixedparameter tractable parameterized by the number of candidates and solvable in singleexponential time, for many voting rules R; this extends an earlier doubleexponential time algorithm by Dorn and Schlotter that is restricted to the unitcost case.
Date: 20161110
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: 20161103
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{kt2}{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{qs}{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: 20161102 **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 dspace 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 C3005, Campus Nord UPC
Speaker: Domenico LABBATE
Title: Characterizations of regular graphs with conditions on their 2factors
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 2factors 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 ERC2014CoG 648276 AUTAR), by AGAUR (grant 2014SGR1147 and 2014SGR1034) and MINECO (projects MTM201454745P, MTM201460127P and TIN201348031C41P (TASSAT2) )
LIMDA Joint Seminar Announcements 20152016
ALBCOM Seminar on Algorithms and Theory of Computation COMBGRAPH Seminar on Combinatorics, Graph Theory and Applications
Date: 20160616
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: 20160602
Time: 12:00
Where: Room C3005, Campus Nord UPC
Speaker: Víctor Diego, Departament de Matemàtiques, UPC
Title: Distance meanregular graphs
Abstract:
We introduce the concept of distance meanregular graph, which can be seen as a generalization of both vertextransitive and distanceregular 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 meanregular} 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 meanregular graph is always distance degreeregular, and we give a condition for the converse to be also true. Some algebraic and spectral properties of distance meanregular graphs are also investigated. We show that, for distance mean regulargraphs, the role of the distance matrices of distanceregular graphs is played for the socalled distance meanregular 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 meanregular graphs are also characterized.
Date: 20160526
Time: 12:00
Where: Room C3005, Campus Nord UPC
Speaker: Jack Koolen, University of Science and Technology of China
Title: Recent progress on 2walkregular graphs
Abstract:
In this talk I will present some recent progress on 2walkregular graphs.
This is based on joint work with Zhi Qiao, Jongyook Park and ShaoFei Du.
Date: 20160317
Time: 12:00
Where: Room C3005, 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 karithmetic progressions, ksumfree 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 nontrivial 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 C3005, Campus Nord UPC
Miquel Àngel Fiol, UPC Barcelona
Cospectral digraphs from locally line digraphs
Abstract:
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, Room S215 Omega Building, Campus Nord UPC (equiv.: Room 215 Floor 2)
Clemens Huemer,
Wednesday, December 2nd, 2015, 12h
Room C3005 Mòdul C3, Campus Nord
Szymon Toruńczyk, Department of CS, UPC and University of Warsaw, Poland
CSPs with infinite instances
Abstract:
Barcelona, 2527 November 2015
Zeroerror 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 C3005 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 C3005 Mòdul C3, Campus Nord UPC
Guillem Perarnau, University of Birmingham (UK)
Connectivity in bridgeaddable graph classes: the McDiarmidStegerWelsh conjecture
Abstract:
Wednesday, November 4, 2015, 12h
Room C3005 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 C3005 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:
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 C3005 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 C3005 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 ErdosRenyi 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 submolecular 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, PerarnauLlobet, 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 MolloyReed result has been applied. I will then sketch the proof of our result and how it differs from the proof of the MolloyReed 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 ERC2014CoG 648276 AUTAR), by AGAUR AGAUR (grant 2014SGR1147 and 2014SGR1034) and MINECO (projects MTM201454745P, MTM201460127P and TIN201348031C41P (TASSAT2) )
Seminar 20142015
(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
C3Room 005, Campus Nord UPC
Edita Máčajová, Comenius University, Bratislava, Slovakia
We discuss old and new results and research directions on the way towards these longstanding 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 1517, 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.
Joan Vilaltella
ADVANCED COURSE ON COMBINATORIAL MATRIX THEORY
June 29 to July 3, 2015, CRM
http://www.crm.cat/en/Activities/Curs_20142015/Pages/CombinatorialMatrixTheory.aspx
Speakers:
Richard A. Brualdi, University of WisconsinMadison
Angeles Carmona Mejías, Universitat Politècnica de CatalunyaBarcelonaTech
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://wwwma4.upc.edu/~fiol/  Universitat Politècnica de Catalunya
Monique Laurent http://homepages.cwi.nl/~monique/  Centrum Wiskunde & Informatica Amsterdam/Tilburg University
Oriol Serra http://wwwma4.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, ICMATCSIC
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_20142015/Pages/StrategicBehaviour.aspx
COMPUTATIONAL GEOMETRY SEMINAR
Thursday, June 11, 2015, 15:0016:00
Room S215 Omega Building, Campus Nord UPC
(equiv.: Room 215 Floor 2)
Déborah Oliveros, Universidad Nacional Autónoma de México
Hellytype theorems and beyond
Abstract:
COMPUTATIONAL GEOMETRY SEMINAR
Tuesday, June 9, 2015, 15:0016: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:
Wednesday, June 3, 2015
Seminar at CRM (Centre de Recerca Matemàtica)
Christos Papadimitriou, University of California, Berkeley
Complexity in Game Theory
I shall recount and reexamine a decade of progress and debate on these questions.
Seminar at CRM
Paul Goldberg, Oxford University
Learning gametheoretic equilibria via query protocols
Thursday May 21, 12h
C3Room 005, Campus Nord, UPC
Dieter Mitsche, Univ. Nice
On the bondage number of random graphs
Joint work with X. PérezGiménez and P. Pralat.
Thursday May 7, 12h
C3Room 005, Campus Nord, UPC
Ignasi Sau, CNRSLIRMM Montpellier
The List Allocation problem and some of its applications in parameterized algorithms
(1) An FPT algorithm for a generalization of Digraph Homomorphism, which we call ArcBounded List Digraph Homomorphism.
(2) An FPT algorithm for a graph partitioning problem, called MinMax Graph Partitioning.
(3) An FPT 2approximation algorithm for computing the "treecut 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, SangIl Oum, Christophe Paul, and Dimitrios M. Thilikos.
Thursday April 30, 12h
C3Room 005, Campus Nord, UPC
Joaquim Bruna, UABCRM Barcelona
Thursday April 23, 12h
C3Room 005, Campus Nord, UPC
Juraj Hromkovic, ETH Zurich
Towards a better understanding of the hardness of NPhard 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
C3Room 005, Campus Nord, UPC
Juanjo Rué, Freie Universitat Berlin
Arithmetic Removal Lemmas and Independent sets 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 wellknown additive combinatorial results even in the nonabelian situation.
This talk is based on a work in progress joint with Oriol Serra and Lluís Vena.
Thursday March 5, 12h
C3Room 005, Campus Nord, UPC
Elisabet Burjons, UPC Barcelona
Online graph coloring with random adversary
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: hvectors, 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 hvector de una matroide es una Osecuencia 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 hvector 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 hvector 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 Osecuencia coincide con el hvector 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
C3Room 005, Campus Nord, UPC
Jaroslav Nešetřil, IUUK MFF, Charles University Prague
Sparsity and fast algorithms for combinatorial problems
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
C3Room 005, Campus Nord, UPC
Jarek Grytczuk, Jagiellonian University in Krakow
Fanciful variations on nonrepetitiveness
Thursday February 19, 11h
C3Room 005, Campus Nord, UPC
Aida Abiad, Tilburg University, The Netherlands
Switched symplectic graphs and their 2ranks
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 2ranks.
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 2ranks.
This is joint work with Willem Haemers.
Thursday November 20, 2014, 12h
C3Room 005, Campus Nord, UPC
Simeon Ball, UPC Barcelona
Applications of the polynomial method in combinatorial geometry to Kakeya and Bourgain sets
In this talk I will consider Kakeya sets and Bourgain sets.
Let F be a field and let AG_k(F) denote the kdimensional 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 nonprime finite fields and we shall also consider this finite nonprime 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), 28282839.
[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
C3Room 005, Campus Nord, UPC
Klara Stokes, University of Skövde
Pentagonal maps of Moore graphs and geometric pentagonal geometries
Thursday October 23, 2014, 12h
C3Room 005, Campus Nord, UPCFrancesc Aguiló, UPC Barcelona
Some Structural Properties of optimal diameter 2Cayley digraphs on finite abelian groups
Joint work with A. Miralles and M. Zaragozá.
Thursday October 16, 2014, 12h
C3Room 005, Campus Nord, UPC
Miquel Àngel Fiol, UPC Barcelona
Distanceregular graphs where the distanced graph has fewer distinct eigenvalues
(joint work with A.E. Brouwer)
Thursday October 9, 2014, 12h
C3Room 005, Campus Nord, UPCFelix Lazebnik, University of Delaware
On Graphs Defined by Some Systems of Equations
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
C3Room 005, Campus Nord, UPC
José AlistePrieto, Universidad Andrés Bello, Santiago de Chile
Recognizing caterpillars by Upolynomials
Seminar 20132014
Sessions and Abstracts
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
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 socalled 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 1416, 2014
www.cimne.com/websasp/ALAMAGAMM/es/frontal/default.asp
JMDA 2014
IX Jornadas de Matemática Discreta y Algorítmica
Tarragona, July 79, 2014.
http://deim.urv.cat/~discretemath/JMDA2014/
Thursday July 3, 2014, 12h
José Ignacio Royo (Universitat del País Vasc)
Abelian and nonabelian numbers via 3D origami
It is well known that the description of the origami folding operations via the HuzitaJustin 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 nonAbelian 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
C3Room 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 kquasiperfect dominating set if every vertex not in D is adjacent to at most k vertices of D. The kquasiperfect domination number $\gamma_ {\stackrel{}{1k}}(G)$ is the minimum cardinality of a kquasiperfect dominating set of G.
Certainly, 1quasiperfect dominating sets and \Deltaquasiperfect 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 >= n3 or \Delta <= 3, cographs, clawfree 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
PhD defense
El problema invers en xarxes finites
Cristina ArauzAdvisors: Ángeles Carmona and Andrés Encinas
Wednesday June 18, 2014, 12h
C3Room 005, Campus Nord, UPCRinovia Simantujak (ITB Bandung)
How to uniquely determine your location in a graph?
A metric dimension problem
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) 155168.
[2] P. Erdös and A. Rényi, On two problems of information theory, Magyar Tud. Akad. Mat. Kutat Int. Kzl 8 (1963), 229243.
[3] F. Harary, and R.A. Melter, On the metric dimension of a graph, Ars Combin. 2 (1976), 191195.
[4] P.J. Slater, Leaves of trees, Congr. Numer. 14 (1975) 549559.
Click here to see or download the abstract in PDF.
Thursday May 15, 2014, 12h
On the Spectral Excess Theorem
Tuesday May 13, 2014, 12h
C3Room 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
C3Room 005, Campus Nord, UPCWillem Haemers (Tilburg Univ.)
Graphs with maximal energy
Click here to see or download the presentation slides.
Wednesday May 7, 2014, 12h
Nuno B. Freitas (Bayreuth University)
An asymptotic Fermat Last Theorem for totally real fields
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 nontrivial 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 qstate Potts model.
http://arxiv.org/abs/1307.3645
http://arxiv.org/abs/1401.4912
Thursday April 10, 2014, 12h
Combinatorial models of toric arrangements
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 socalled '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
C1001, Campus Nord UPC
Charles Johnson (William and Mary College, Virginia)
Hollow Symmetric Nonnegative Matrices
An nbyn 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
C3Room 005, Campus Nord, UPCMartyn Mulder (Erasmus Univ. Rotterdam)
What do trees and hypercubes have in common?
At first sight trees and hypercubes are very different classes of graphs (except for the trivial cases K_1 and K_2, of course). Nontrivial trees are cyclefree, 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
C3Room 005, Campus Nord, UPC
Martin Golumbic (Univ. of Haifa)
The Elusive Nature of Intersecting Paths on a Grid
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_1EPG graphs. They proved that any tree is a B_1EPG graph and gave a structural property that enables generating non B_1EPG graphs. A characterization of the representation of cliques and chordless 4cycles in B_1EPG 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
C3Room 005, Campus Nord, UPCBill Kantor (U. Oregon)
Mutually Unbiased Bases
Two orthonormal bases of an ndimensional 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
C3Room 005, Campus Nord, UPC
Juanjo Rué (Freie Univ. Berlin)
Applications of Tutte's tree decomposition in enriched families of graphs
We adapt the grammar introduced by Chapuy, Fusy, Kang and Shoilekova to study enriched graph families which are defined by their 3connected components.
More precisely, we will discuss two different problems:
1. The counting formulas for bipartite seriesparallel 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 seriesparallel 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
C3Room 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 balllike structure, which include spider networks with radial conductances, distanceregular graphs or, more generally, regular layered networks.
Friday February 21
2nd GraphTA Workshop 2014
http://www.dama.upc.edu/seminars/2ndgraphta
Thursday February 20, 2014, 12h
C3Room 005, Campus Nord, UPCAnna de Mier (UPC Barcelona)
Transversal extensions of transversal matroids
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 singleelement 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
C3Room 005, Campus Nord, UPC
Angeles Carmona (UPC Barcelona)
Generalized Linear Polyominoes, Green functions and Green matrices
Abstract:
A Polyomino is an edgeconected 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 polyominoeslike 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
C3Room 005, Campus Nord, UPC
Francesc Aguiló (UPC Barcelona)
Some metric results on weighted Cayley digraphs
Let G_c=<a,b> be a finite (additive) 2generated 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 nonweighted 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 wellknown minimum distance diagrams. These diagrams can also be used for the weighted and noncyclic 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 noncyclic) 2Cayley digraph when the weighs are W_a=a and W_b=b; they can be used for studying some properties of numerical 3semigroups <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 3semigroups. 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 3semigroups. 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
C3Room 005, Campus Nord, UPC
Mercè Mora (UPC Barcelona)
Location and domination in graphs
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
C3Room 005, Campus Nord, UPC
Camino Balbuena (UPC Barcelona)
An overview on {C_3,...,C_s}free extremal graphs
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
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 socalled intersection numbers of a distanceregular 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 wellknown 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 distanceregularity, 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/randomstructuresandtheprobabilisticmethod
on Graph coloring and the probabilistic method
http://www.springer.com/new+%26+forthcoming+titles+(default)/book/9783540421399
delivered by Bruce Reed.
Thursday December 12, 2013, 12h
The typical structure of Hfree graphs
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
Victor Diego (UPC Barcelona)
On a problem of Shapozenko
Abstract:
The isoperimetric function is known for a small class of graphs, including the ncube. Shapozenko, and later Leader, asked about the isoperimetric function in Johnson graphs, which, as the ncube, 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 mbinomial expression of any value of $k$, giving the complete isoperimetric function for all the Johnson graphs.
Thursday November 21, 2013, 12h
C3Room 005, Campus Nord, UPC
Benny Sudakov (ETH Zürich and UCLA Los Angeles)
The minimum number of nonnegative edges in hypergraphs
Abstract:
Joint work with Hao Huang.
Thursday November 14, 2013, 12h
C3Room 005, Campus Nord, UPCJavier Cilleruelo (UAM and ICMAT, Madrid)
Extremal graphs and extremal sets of integers
Abstract:
Thursday November 7, 2013, 12h
C3Room 005, Campus Nord, UPC
Juraj Hromkovic (ETH Zürich)
Towards measuring the information content of problems
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
C3Room 005, Campus Nord, UPC
Christian Rubio Montiel (Instituto de Matemáticas UNAM)
A new characterization of trivially perfect graphs
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 vertexcoloring, we relate them to some wellknown classes of perfect graphs and extend the definitions to infinite graphs.
Thursday October 24, 2013, 12h
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 3edgecoloring 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 3edgecolorable.
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 nonempty 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
Journées Combinatoire et Algorithmes du Littoral Méditerranéen, JCALM
Graph MinorsClick here to see the program or visit the JCALM 2013 web page:
http://www.lirmm.fr/~sau/JCALM2013Bcn.html
Thursday October 10, 2013, 12h
C3Room 005, Campus Nord, UPC
Gabriela Araujo (UNAM, Mexico)
Projective planes and colorings
Thursday October 3, 2013, 12h
Identifying codes and Vapnik–Chervonenkis dimension
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
C3Room 005, Campus Nord, UPC
Arnau Padrol (FU Berlin)
A universality theorem for projectively unique polytopes and a conjecture of Shephard
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 20122013
Sessions and Abstracts
Seminar sessions and other activities
Thursday July 25, 12h
EETAC, C4 building, room 028a, Campus Castelldefels
Ruy FabilaMonroy (CINVESTAVIPN, Mexico)
Búsqueda con ordenador de configuraciones extremales en conjuntos de puntos
Abstract:
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 kelement 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 fourelement diamond D_2, where the kdiamond 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, WeiTian Li, and J.S. Sereni.
Thursday June 27, 12h
Amanda Montejano (UNAM, Mexico)
Null and nonrainbow colorings of projective plane and sphere triangulations
Abstract:
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:
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): 241250.
This paper proposes a new general family of large vertex symmetric digraphs with order:
N=(Delta+(D1)/2)/(Delta(D1)/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:
Thursday June 6, 12h
Andriy Bondarenko (Norwegian University of Science and Technology and National Taras Shevchenko University, Kyiv, Ukraine)
Spherical designs: Proof of the KorevaarMeyers conjecture and beyond
Abstract:
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 tdesign 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), 363388.
[2] J. Korevaar, J.L. Meyers, Spherical Faraday cage for the case of equal point charges and Chebyshevtype quadrature on the sphere, Integral Transforms Spec. Funct. 1 (1993), 105117.
[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.)
3colourable circulant graphs
The circulant graph G(n;S) is a graph on vertex set V={v_0,v_1,...,v_(n1)} 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 3colourable circulant graphs with k chord lengths. Then I will present a family of 3colourable circulant graphs with 2 chord lengths. I will also show that recursive circulant graphs and a class of optimal double loop graphs are 3colourable.
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:
Matolcsi and Ruzsa have recently generalized this lower bound to A+kB if B is a ddimensional finite set, and A is contained in the convex hull of B. We characterize the equality case of the MatolcsiRuzsa 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:
Thursday May 9, 12h
Sanming Zhou (Univ. Melbourne)
Frobenius circulant graphs of valency six, EisensteinJacobi networks, and hexagonal meshes
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 firstkind $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 6valent firstkind 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 6valent firstkind Frobenius circulants with cyclic kernels are EisensteinJacobi graphs, the latter being Cayley graphs on quotient rings of the ring of EisensteinJacobi integers. On the other hand, we showed that any EisensteinJacobi graph with order congruent to 1 modulo 6 and underlying EisensteinJacobi integer not an associate of a real integer is a cover of a 6valent firstkind Frobenius circulant. We noticed that a distributed realtime computing architecture known as HARTS or hexagonal mesh is a special 6valent firstkind Frobenius circulant, and is in fact the 'geometric' 6valent 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 3graphs
We show that for every epsilon > 0 there exist delta > 0 and natural number n_0 such that every 3uniform hypergraph on n >= n_0 vertices with the property that every kvertex 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 3uniform 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:
Joint work with Daniel Johannsen and Michael Krivelevich.
Thursday April 18, 12h
Albert Guillén (ICREA/Univ. Pompeu Fabra, Barcelona)
Mismatched Decoding and BitInterleaved Coded Modulation
Abstract:
Thursday April 11, 12h
Shmuel Zaks (Technion, Haifa)
Optimization in optical networks
Abstract:
The talk will be selfcontained, thus no apriori knowledge is assumed for optical networks or approximation and online algorithms.
Thursday March 21, 12h
Antonio Guedes (Oporto)
Parking functions and labelled trees
Abstract:
Building on work of Heesung Shin, we find a (nonrecursive) 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, LRIParis 11)
Homomorphism of signed bipartite graphs
Abstract:
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 singleexponential algorithms via protrusion decompositions
Abstract:
We will first show that any parameterized graph problem (with parameter k) that has "finite integer index" and is "treewidthbounding" admits a linear kernel on Htopologicalminorfree graphs, where H is some arbitrary but fixed graph. A parameterized graph problem is called treewidthbounding if all positive instances have a ttreewidthmodulator of size O(k), for some constant t. This result partially extends previous metatheorems on the existence of linear kernels on graphs of bounded genus [Bodlaender et al., FOCS 2009] and Hminorfree graphs [Fomin et al., SODA 2010].
Our second application concerns the PlanarFDeletion problem. Let F be a fixed finite family of graphs containing at least one planar graph. Given an nvertex graph G and a nonnegative integer k, PlanarFDeletion asks whether G has a subset X of V(G) such that X < k+1 and GX is Hminorfree for every graph H in F. Very recently, an algorithm for PlanarFDeletion with running time 2^O(k) n^O(1) (such an algorithm is called "singleexponential") 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) singleexponential algorithm for the general PlanarFDeletion 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:
Thursday February 14, 12h
Juanjo Rue (ICMAT, Madrid)
Threshold functions for systems of equations on random sets
Abstract:
Our results cover several combinatorial families, namely sets without arithmetic progressions of given length, ksumfree 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 Graphbased Technologies and Applications (GraphTA),
Barcelona, February 19, 2013
http://www.dama.upc.edu/seminars/graphta
*International School on Coding Theory and their Applications* (ISCTA)
Tarragona, February 1114, 2013
http://crisesdeim.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^{d1}$ and of their complements, the circular complete graphs $K_{k/d}$. As a consequence, we establish that the circularchromatic number of a circularperfect graph is computable in polynomial time, which extends the above result from the chromatic number to the circularchromatic number, and from perfect graphs to the superclass of circularperfect 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:
Wednesday December 5, 12h
Tobias Muller (Univ. Utrecht)
First order logic and random graphs
Abstract:
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 ErdosRenyi 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 ddimensional 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 AgarwalSpencer.
(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
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 1dimensional 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 NPcomplete. 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
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
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 Hcolorable 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 Hcolorable 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 = p1, 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:
Thursday October 11, 12 h
Mirka Miller (Univ. London)
Moore Graphs and Beyond: Recent Advances in the Degree/Diameter Problem
Abstract:
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:
[1] A. Dekker, H. PerezRoses, G. PinedaVillavicencio, and P. Watters, The Maximum Degree/DiameterBounded Subgraph and its Applications, Journal of Mathematical Modelling and Algorithms (2012), accepted on 25 Jan 2012, doi:10.1007/s1085201291828.
Thursday September 27, 12h
Oriol Farràs (URV, Tarragona)
Secret Sharing Schemes for Very Dense Graphs
Abstract:
Thursday September 13, 12h
Pedro A. GarciaSanchez (Univ. Granada)
Catenariedades en monoides conmutativos
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 20112012
Sessions and Abstracts
Sessions
Monday July 23, 11h
Conference Room of ETSECCPB (2nd floor, room C2 212)
The Inverse Problem on finite networks
Ph.D. Thesis proposalCristina 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 2008, Beck showed that the largest undirected clique Maker can build is of order k_c = (2o(1)) log n. Based on a "random graph intuition" he conjectured that the largest k_t such that Maker wins the k_ttournament game is of order k_t = (1o(1)) log n.
Given n large enough, we show that Maker wins the ktournament game for k = (2o(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:
We will use Gale duality to prove that the only polytopes of combinatorial degree 1 are kfold pyramids over polygons and kfold 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:
In the talk we will see some constructions of pentagonal geometries, obtain some nonexistence 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 oddgirth theorem
Miquel Àngel Fiol, UPC BarcelonaAbstract:
(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 BarcelonaWe 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^21)\frac{1}{2}\sqrt{q} (q1)$ 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 GrenobleAbstract:
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, BarcelonaAbstract:
A dominating set is called locatingdominating (resp. distinguishingdominating 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 locatingtotal dominating (resp. distinguishingtotal 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 NordhausGaddum type result for the locatingdominating number, which is the minimum cardinality of a locatingdominating set.
Joint research work with Carmen Hernando and Mercè Mora.
Thursday March 22, 12h
Strongly regular graphs
Andriy Bondarenko, CRM (Barcelona)Abstract:
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 AmsterdamWe 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 blackbox access to f. We present a series of recent results establishing nearly tight worstcase querycomplexity 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, BarcelonaLet $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 wellknown 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 BarcelonaAbstract:
Thursday February 16, 12h
Graphs and Matrices with Integral Spectrum in Some Families
Igor Shparlinsky, Department of Computing, Macquarie University, AustraliaAbstract:
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, BarcelonaAbstract:
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+m1}) = \sigma for some i in {1,...,nm+1}. Two permutations \sigma and \tau of the same length are called Wilfequivalent 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...(s1)(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 Wilfequivalence of several patterns. Finally we prove that the monotone pattern dominates asymptotically all nonoverlapping 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éxicoAbstract:
Thursday January 12, 12h
Algunos resultados en teoría antiRamsey aritmética
Amanda Montejano, Centro de Física Aplicada y Tecnología Avanzada, UNAM, MexicoAbstract:
En términos generales nos interesa estudiar la ``forma'' de aquellas coloraciones que no contengan estructuras multicolor (llamaremos a estas coloraciones libresmulticolor (rainbowfree). 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 libresmulticolor. 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 libremulticolor 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:
Thursday December 15, 12h
Upper Bounds for Higher Sumsets
Giorgis Petridis (Cambridge University)Abstract:
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 graphtheoretic method of Helmut Pl\"unnecke he showed that
A+hB\leq \alpha^h A^{21/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^{21/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 minorclosed classes of graphs
Marc Noy (UPC, Barcelona)Abstract:
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:
Thursday November 17 2011, 12h
Rainbow kconnection in Dense Graphs
Henry Liu, Universidade Nova de Lisboa, PortugalAbstract:
In this talk, we shall prove many new results concerning rc_k(G). We consider the cases when G has fixed vertexconnectivity, 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:
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 DeviceIndependent Quantum Information Processing
Antoni Acin (Institut de Ciènces Fotòniques, Barcelona)Seminar 20102011
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 distanceregularity Marc Càmara, UPC Barcelona Thursday, June 2, 2011, 12h On 3domination critical graphs Adriana Hansberg, UPC Barcelona Thursday, May 26 2011, 12h Graph Isomorphism, SheraliAdams Relaxations and Expressibility in Counting Logics Albert Atserias, UPC Barcelona Thursday, May 19 2011, 12h Lineidentifying 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 degreediameter problem Maria Zdimalova, Slovak University of Technology Thursday January 20, 2011, 12h The hproduct 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 WalkRegular 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 distanceregularity
Marc Càmara, UPC Barcelona
Abstract
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 3domination critical graphs
Adriana Hansberg, UPC Barcelona
Abstract
(joint work with Camino Balbuena)
Thursday, May 19 2011, 12h
Aula 005, Mòdul C3, Campus Nord
Graph Isomorphism, SheraliAdams Relaxations and Expressibility
in Counting Logics
Albert Atserias, UPC Barcelona
Abstract
Thursday, May 12 2011, 12h
Aula 005, Mòdul C3, Campus Nord
Lineidentifying codes
Florent Foucaud, LABRI, Univ. Bordeaux
Abstract
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
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", "pseudodistànciaregularitat" "odd grafs retorçats", "grafs kcamíregulars", "grafs quasidistànciaregulars",...
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
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
Thursday April 7, 2011, 12h
Aula 005, Mòdul C3, Campus Nord
On a slicing formula for bipartite graphs
Eric Fusy, LIX Ecole Polytechnique, ParisAbstract
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
Thursday March 24 2011, 12h
Aula 005, Mòdul C3, Campus Nord
A tribute to Yahya ould Hamidoune
Oriol Serra, UPC, BarcelonaThursday March 10 2011, 12h
Aula 005, Mòdul C3, Campus Nord
Dynamic programming in sparse graphs
Ignasi Sau (CNRS, LIRMM, Montpellier, France)Abstract
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
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 BarcelonaAbstract
 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 BarcelonaAbstract
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 BarcelonaAbstract
Thursday January 20 2011, 12h
Aula 003, Mòdul C3, Campus Nord
Graph coverings and the degreediameter problem
Maria Zdimalova
Slovak University of Technology
Abstract
Thursday January 13 2011, 12h
Aula 003, Mòdul C3, Campus Nord
The hproduct of digraphs and its applications to labelings
Susana López Masip, UPC Barcelona
Abstract
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
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 onedimensional 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, UPCAbstract
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^{2e} 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.
Aula 003, Mòdul C3, Campus Nord
On graphs representable by words
Sergey Kitaev, Reykjavik UniversityAbstract
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 2representable 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 semitransitive orientation. This allows us to prove a number of results about representable graphs, not the least that 3colorable 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$.
Aula 003, Mòdul C3, Campus Nord
Some results on connectivity of cages
Julián Salas, UPCAbstract
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 WalkRegular Graphs
Miquel A. Fiol, UPCAbstract
In this talk we show that certain almost distanceregular graphs, the socalled $h$punctually walkregular graphs, can be characterized though the cospectrality of their perturbed graphs. A graph $G$ with diameter $D$ is $h$punctually walkregular 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 distanceregular 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 UniversityAbstract
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, BudapestAbstract
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_1b_2 do not belong to A? Possible applications range through spherepackings, Littlewood's conjecture on simultaneous approximation, and mutually unbiased bases.
Seminar 20092010
Sessions and Abstracts
Sessions
(Download all abstracts in PDF.)Semiregular cages with odd girth are edgesuperconnected 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 treedepth 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 DistanceRegular Graphs Cristina Dalfó, UPC Local spectrum of the subconstituents and completely pseudoregular 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ópezMasip, 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 quasieven 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 MerinoWelsh 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 
Thursday January 28, 2010, 12h Aula 005 Modul C3 Campus Nord UPC  
Extensions of the ScherckKemperman 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 1820, 2009 CRM Bellaterra 
Small vertextransitive 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 3generated 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
Aula 005 Modul C3
Campus Nord UPC
Semiregular cages with odd girth are edgesuperconnected
Julián Salas, UPCAbstract
A graph is said to be edgesuperconnected if each minimum edgecut 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 edgesuperconnected.
Aula 005 Modul C3
Campus Nord UPC
Ascending subgraph decompositions of bipartite graphs
Jordi Moragas, UPCAbstract
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 ,n1$. 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 (k1)(nk+1)$, and $d_i\ge ni+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 edgecolorings of some bipartite graphs with parallel edges.
This is joint work with A. Lladó and Slamin.
Aula 005 Modul C3
Campus Nord UPC
On the treedepth of random graphs
Guillem Perarnau, UPCAbstract
Aula 005 Modul C3
Campus Nord UPC
Routing in Social Networks
Dieter Mitsche, CRMAbstract
Joint work with J. Diaz, A. MarchettiSpaccamela and P. Santi.
Aula 005 Modul C3
Campus Nord UPC
Almost DistanceRegular Graphs
Cristina Dalfó, UPCAbstract
Another studied concept is that of mpartial distanceregularity, or informally, distanceregularity up to distance m. Using eigenvalues of graphs and the predistance polynomials, we discuss and relate these and other concepts of almost distanceregularity, such as their common generalization of (l,m)walkregularity. We introduce the concepts of punctual distanceregularity and punctual walkregularity as a fundament upon which almost distanceregular 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 distanceregular becomes whole distanceregular. We also give several characterizations of punctually distanceregular 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.
Aula 005 Modul C3
Campus Nord UPC
Local spectrum of the subconstituents and completely pseudoregular codes
Marc Càmara, UPCAbstract
It also has applications in the area of pseudodistanceregularity around a set and can be used to obtain quasispectral 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 pseudoregular 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.
Aula 005 Modul C3
Campus Nord UPC
Tree Automata and the HOM problem
Omer Giménez, UPCAbstract
This is joint work with Guillem Godoy, Lander Ramos and Carme Alvarez.
Aula 005 Modul C3
Campus Nord UPC
Linear systems over composite moduli
Arkadev Chattopadhyay, University of TorontoAbstract
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 lowdegree polynomial and ideas involving matrix rigidity from the work of Grigoriev and Razborov on arithmetic circuits over finite fields.
Aula 005 Modul C3
Campus Nord UPC
Asymptotic study of subcritical graph classes
Juanjo Rué, Laboratoire d'Informatique, Ecole Polytechnique, Palaiseau, FranceAbstract
This is a joint work with Michael Drmota, Eric Fusy Mihyun Kang and Veronika Kraus.
Aula 005 Modul C3
Campus Nord UPC
Graph Operations and Laplacian Eigenpolytopes
Arnau Padrol, UPCAbstract
Eigenpolytopes have been previously introduced by Godsil, who studied them in detail in the context of distanceregular 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 distanceregular 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 Lpolytopes. Subsequent papers will use these tools to construct interesting polytopes from interesting graphs, and vice versa.
Aula 005 Modul C3
Campus Nord UPC
Vosperian and superconnected vertex transitive graphs
Susana LópezMasip, UPCAbstract
This is joint work with Yahya Hamidoune and Anna Lladó.
Aula 005 Modul C3
Campus Nord UPC
Empty monochromatic triangles
Clemens Huemer, UPCAbstract
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 BallUPC
Abstract
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,p3,p2,p1,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 nonprime 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^{k1})$, for each $x \in {\mathbb F}_p$, and $(0,\ldots,0,1)$.
Time permitting I shall also discuss the nonprime 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 VuillonLAMA, Université de Savoie, CNRS
Abstract
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. BoninDepartment of Mathematics, The George Washington University
Abstract
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 nonmodular 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 nonmodular 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 minorclosed 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 NoyUPC
Abstract
More precisely, there exists a constant c > 0 such that
Prob(n^{1/4  epsilon} < Diam(G_n)< n^{1/4 + epsilon}) > 1exp(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 seriesparallel 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 2connected maps, using the fact that a random map has a 2connected component of linear size a.a.s. A similar argument allows us to extend the result to 3connected maps, which proves it also for 3connected planar graphs, because they have a unique embedding in the sphere. We then reverse the previous arguments and go first to 2connected and then connected planar graphs.
Our approach uses generating functions in a fundamental way, together large deviation estimates, saddlepoint bounds, and other tools.
We'll keep the talk at a nontechnical 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 VenturaUPC
Abstract
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 quasieven triangulations of point sets in the plane
Alberto MárquezUniversidad de Sevilla
Abstract
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 qetriangulations are exactly those that can be colored with 3 colors. Aditionally, etriangulations are, of course eulerian.
In this talk, we study etriangulations for a point set in convex position, and qetriangulations for point sets in general position.
Thursday February 11, 2010, 12h
Aula 005 Modul C3
Campus Nord UPC
Recent progress on the MerinoWelsh Conjecture concerning the Tutte polynomial
Steve NobleDepartment of Mathematical Sciences, Brunel University
Abstract
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
In this talk, we present a pointing operator, called ``cyclepointing'', 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 SwarcfiterFederal University of Rio de Janeiro
Abstract
Joint work with R. Barbosa, E. Martins and M. Dourado.
Wednesday January 20, 2010, 15h
Aula 101 FME
Campus Sud UPC
Extensions of the ScherckKemperman Theorem
Yahya O. HamidouneUniv. Paris 6
Abstract
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 ScherkKemperman Theorem, proved by Kemperman: $$AB\ge A+BA\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 HolzmanTechnion  Israel Institute of Technology
Abstract
Thursday December 10, 2009, 12h
Aula 005 Modul C3
Campus Nord UPC
Classification of Construction Techniques of Large Directed Graphs
SlaminUniversitas Jember, Indonesia
Abstract
Thursday December 3, 2009, 12h
Aula 005 Modul C3
Campus Nord UPC
Random graphs with few disjoint cycles
Colin McDiarmidOxford University
Abstract
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 AlonTel Aviv University
Abstract
Thursday November 12, 2009, 12h
Aula 005 Modul C3
Campus Nord UPC
Small vertextransitive and Cayley graphs of girth 6 and 5
Jozef SiranSlovak University of Technology in Bratislava and The Open University
Abstract
Thursday November 5 2009, 12h
Aula 005, ModulC3
Campus Nord UPC
Optimal Graphs and Digraphs
Mirka MillerThe University of Newcastle, Australia
University of West Bohemia, Czech Republic
King’s College London, UK
Abstract
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 lessstudied 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 SauINRIA, Nice and UPC Barcelona
Abstract
The study of the traffic grooming problem leads naturally to the study of a family of graphtheoretical 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 degreeconstrained problems, giving hardness results and polynomialtime approximation algorithms. We then study in Chapter 6 the parameterized complexity of finding degreeconstrained subgraphs, when the parameter is the size of the subgraphs. We prove hardness results in general graphs and provide explicit fixedparameter tractable algorithms for minorfree graphs. We obtain in Chapter 7 subexponential parameterized and exact algorithms for several families of degreeconstrained 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 surfaceembedded 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 3generated numerical semigroups
Francesc AguilóUPC, Barcelona
Abstract
Let us consider the weighted doubleloop 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=<n2,n1,n>$, for even $n\geq6$, which are the only 3generated 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,n1,n>$ and $<n2,n1,n>$ for even $n$, and $<(n1)/2,n1,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 BalandraudUniv Paris 6
Abstract
The proof is based on the polynomial method and is very similar of Alon Nathanson Rusza's proof of HamidouneDa 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 CoriUni. Bordeaux I and Ecole Polytechnique, Paris
Abstract
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$ lefttoright maxima we obtain a lower bound for the probability of being indecomposable.
Seminar 20082009
Sessions and Abstracts
Sessions
(Download all abstracts in PDF.) Realvalued 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 
Sumfree 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 PerezRoses, The University of Newcastle, Australia  Thursday December 11 2008 
SylvesterFrobenius 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 
kdominació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 TutteGrothendieck 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 kWalkRegular Graphs Miquel Angel Fiol, UPC Barcelona  Thursday October 09 2008 
Abstracts
Thursday June 11, 2009
Realvalued flows in cubic graphs
Martin Skoviera, Comenius University, Bratislava, SlovakiaAbstract
Thursday May 28, 2009
Permutaciones alternantes y gráficas completas
Abstract
In this talk we will discuss these two known results to show that the number of alternating permutations can be obtained as the evaluation of Tutte's polynomial in two distinct points, namely T(K_n,2,1)=T(K_{n+2}; 1, 1). By using the same technique we will show that (K_{n,m},2,1)=T(K_{n+1,m+1}; 1, 1).
The sum of digits of primes
Abstract
It is relatively easy to show that the average number of nonzero binary digits of primes < x is almost the same as the average number of nonzero 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 nonzero binary digits for k close to (1/2) \log_2 x.
The proof is based on a thorough analysis of exponential sums involving the sumofdigits function (that is related to a recent solution of problem of Gelfond) and a refined central limit theorem for the sumofdigits function of primes. Interestingly this result answers a question of Ben Green whether for every given k there exists a prime with k nonzero binary digits. There is also a very nice relation to the ThueMorse 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 BarcelonaAbstract
Thursday May 07 2009, 15h
Algorithmic relations of the Tutte polynomial
Martin Loebl, Univerzita Karlova v PrazeAbstract
Thursday April 30 2009, 15h
Graphs with many edges containing no complete bipartite graphs
Valentina Pepe, Universita di Napoli, Federico IIAbstract
Thursday April 02 2009, 15h
Extension Diameter of Boolean Lattices
Mareike Massow, TU BerlinAbstract
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 BarcelonaAbstract
Improving on previous results by McDiarmid we prove the following precise asymptotic estimate:
A_n(g) ~ c(g)*n^{5(g1)/21}*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 facewidth parameter (Robertson, Vitray). Similar results hold for graphs embeddable in nonorientable surfaces.
Thursday March 12 2009, 15h
Extremal Graph Theory, old and new results
Miklós Simonovits , Alfred Rényi Institute of Mathematics, BudapestAbstract
(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 selfimproving 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}sKleitmanRothschild type (Erd\H{o}sFranklR\"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 BarcelonaAbstract
Thursday February 26 2009, 15h
Noise Sensitivity, Noise Stability, Percolation and some connections to TCS
Gil Kalai, Hebrew University of JerusalemAbstract
1) The definition of noise sensitivity, and how it is described in terms of the Fourier transform.
2) Noise sensitivity of the crossing event in Percolation (BKS 99, Schramm and Steiff 2005, and finally Garban, Pete, Schramm 2008  http://front.math.ucdavis.edu/0803.3750 ), the scaling limit for the Spectral distribution (Schramm and Smirnov, 2007, GPS 2008), and dynamic percolation. (ScSt (2005), GPS (2008)). Other cases of noise sensitivity.
3) Noise stability of the majority function, of weighted majority. A conjecture regarding the situation for functions described by monotone depth monotone threshold circuits.
4) The "majority is stablest theorem" (Mossel, O'Donnell, Oleszkiewicz 05 http://front.math.ucdavis.edu/0503.5503) and the connection to hardness of approximation.
Small regular bipartite graphs of girth 8
Camino Balbuena, UPC BarcelonaAbstract
Thursday January 22 2009, 15h
The exterior algebra method in additive combinatorics
Gyula Karolyi, Eötvös University, BudapestAbstract
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. CantabriaAbstract
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
Sumfree sets, sets with small sumset and the clique number of random Cayley graphs.
Gyan Prakash, Univ. Bordeaux IAbstract
A subset $A$ of an abelian group is said to be sumfree 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 sumfree 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 sumfree subsets in an arbitrary finite abelian groups, due to Green and Ruzsa.
Thursday December 11, 2008
Construcción de grandes grafos de determinadas clases
Herbert PerezRoses , The University of Newcastle, AustraliaAbstract
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
SylvesterFrobenius change problem for vectors
Zdzislaw Skupien , AGH University, Krakow, PolandAbstract
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 qfully 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 pseudoconductor, such that each vector v in h(q) + C is qfully 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 qfully 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, ParisAbstract
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, AustriaAbstract
Abstracto
Thursday November 13, 2008
kdominación en grafos
Adriana Hansberg, Univ. AachenAbstract
Es conocido que el problema de establecer la existencia de un conjunto kdominante con cardinalidad menor a un entero q dado es NPcompleto. Por esta razón, es natural o bien proceder a buscar cotas para el número de kdominació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 kdominació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, ParisAbstract
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 TutteGrothendieck invariants.
Andrew Goodall, University of BristolAbstract
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 qstate 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 qstate 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 qstate Potts model graphs H, is the graph G uniquely determined?
This not only includes the longstanding 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 qstate Potts model.
Thursday October 16, 2008, 15h
Ramsey theory and the Regularity Lemma
Miklos Ruzsinko, Computer and Automation Research Institute, BudapestAbstract
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 3colored Ramsey numbers for triples of odd cycles, and Gyarfas, Sarkozy, Szemeredi and myself determined the exact 3colored 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 kWalkRegular Graphs
Miquel Angel Fiol, UPC BarcelonaAbstract
In this talk we show some algebraic characterizations of kwalkregularity, which are based on the socalled 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 walkregular 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
Advanced Course: Combinatorial Convexity (May 718, 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 718, 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 email tagged 'Barany2012Course' to convexitycourse2012@ma4.upc.edu indicating
Name
Affiliation
email 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) 11h13h 

Tuesday May 8  11h13h  Tuesday May 15  11h13h 
Wednesday May 9  11h13h  Wednesday May 16  11h13h 
Thursday May 10  11h13h  Thursday May 17  11h13h 
Friday May 11  11h13h 
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ópezMasip, SusanaClara (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érezMansilla, 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 Large Graphs, by Mirka Miller (June 28, 2010)
Recent Developments in Largest Graphs and Digraphs with Given Degree and Diameter by Prof. Mirka Miller, June 28, 2010
Share: