LIMDA Joint Seminar Announcements 2016-17

Forthcoming sessions and activitie

 

Previous sessions and activities

Date: Thursday July 6, 2017

Time: 12h

Where:  Room C3-005, Campus Nord UPC

Speaker: Miquel Angel Fiol, UPC Barcelona

Title: The spectra of liffted digraphs

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

Date: Thursday June 29, 2017

Time: 12h

Where:  Room C3-005, Campus Nord UPC

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

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

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

Date: Thursday, June 15, 2017

Time: 10:00-11:30

Where: Room S05, FME, Campus Sud UPC

Speaker: Benny Sudakov, ETH, Zurich

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

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

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




Date: Thursday, June 15, 2017

Time: 12:00-13:00

Where: Room S05, FME, Campus Sud UPC

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

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

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

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

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

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

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

Date: Tuesday June 6, 2017

Time: 10h30-11h15

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

Speaker: Robert Hancock, Univ. of Birmingham

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

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

 

Date: Tuesday June 6, 2017

Time: 11h30-12h30

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

Speaker: David Wood, Monash University

Title: Improper relaxations of Hadwiger’s Conjecture

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

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

 

Date: Tuesday May 30, 2017

Time: 11h-11h50

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

Speaker: Gilles Zemor, Univ. Bordeaux

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

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

Date: Tuesday May 30, 2017

Time: 10h-10h45

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

Speaker: Wouter Cames van Batenburg,  Radboud University Nijmegen

Title: Packing graphs of bounded codegree

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

Date: Wednesday May 17, 2017

Time: 12:00

Where: Room C3-005, Campus Nord UPC

Speaker: Christoph Spielgel, UPC, Barcelona

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

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

Date: Wednesday May 10, 2017

Time: 12:00

Where: Room C3-005, Campus Nord UPC

Speaker: Piotr Zwiernik, UPF, Barcelona

Title: Cumulants and generalizations

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

Date: Wednesday April 26, 2017

Time: 12:00

Where: Room C3-005, Campus Nord UPC

Speaker: Clement Requilé, UPC, Barcelona

Title: Enumeration of 4-regular planar graphs

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

Date: Wednesday April 5, 2017

Time: 12:00

Where: Room C3-005, Campus Nord UPC

Speaker: Shagnik Das, Freie University Berlin

Title: Supersaturation for disjoint pairs

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

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

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

Date: Monday, April 3, 2017

Time: 10:30

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

Speaker: Mozhgan Pourmoradnasseri, University of Tartu, Estonia

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

Abstract:

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

Date: Thursday, February 23, 2017

Time: 12:00

Where: Room C3-005, Campus Nord UPC

Speaker: Camino Balbuena

Title: Vertex disjoint 4-cycles in bipartite tournaments.

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

Date: Thursday, February 16, 2017

Time: 12:00

Where: Room C3-005, Campus Nord UPC

Speaker: Miquel Àngel Fiol

Title: Complexity measures of edge-uncolorability in cubic graphs

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

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

 

 

Date: Tuesday, February 14, 2017

Time: 11:00

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

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

Title: Derandomizing Isolation in the Space-Bounded Setting

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

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

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

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

Date: Monday, February 6, 2017

Time: 15:00

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

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

Title: Total space in Resolution is at least width squared

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

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

 

 

 

Date: Monday, January 30, 2017

Time: 15:00:00

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

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

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

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

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

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

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

 

 

Date: Wednesday December 7 2016

 

Date: Thursday 24 November 2016

Time: 13.00 **ATTENTION AT THE TIME**

Where: Room C3-005, Campus Nord UPC

Speaker: Joan Vilaltella

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

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

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

 

 

Date: Wednesday November 23, 2016

Time: 12h

Where: Room 005, Modul C3, Campus Nord UPC

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

Title: Weighted dependency graphs

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

 

Date: Wednesday November 16, 2016

Time: 12h

Where: Room 005, Modul C3, Campus Nord UPC

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

Title: First order logic of permutations

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

 

 

Date: 2016-11-15 (TUESDAY)

Time: 12:00:00 

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

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

Title: Voting and Bribing in Single-Exponential Time 

Abstract:

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

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

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

 

 

Date: 2016-11-10

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

Where: Room 005, Modul C3, Campus Nord UPC 

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

Title: El problema de Moore en gráficas mixtas 

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

 

 

Date: 2016-11-03 

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

Where: Room 005, Modul C3, Campus Nord UPC 

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

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

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

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

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

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

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

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

 

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

Time: 12:00 

Where: Room 005, Modul C3, Campus Nord UPC 

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

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

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

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

 

 

Date: WEDNESDAY 14 September 2016

Time: 12.00

Where: Room C3-005, Campus Nord UPC

Speaker: Domenico LABBATE

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

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

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

 

Acknowledgements

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