# LIMDA Joint Seminar Announcements 2016-17

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

### Forthcoming sessions and activitie

### Previous sessions and activities

**Date: **Thursday July 6, 2017

**12h**

**Time:****Room C3-005, Campus Nord UPC**

**Where:****Miquel Angel Fiol, UPC Barcelona**

**Speaker:****The spectra of liffted digraphs**

**Title:****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$.**

**Abstract:**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

**12h**

**Time:****Room C3-005, Campus Nord UPC**

**Where:****Mohan Prabu, British University, Hanoi (Vietnam)**

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

**Title**:**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.**

**Abstract:**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

**10:00-11:30**

**Time:****Room S05,**

**Where:****FME**, Campus Sud UPC

**Benny Sudakov, ETH, Zurich**

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

**Title:****A rainbow subgraph of a properly edge-colored complete graph is a**

**Abstract:**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

**Thursday, June 15, 2017**

**Date:****12:00-13:00**

**Time:****Room S05,**

**Where:****FME**, Campus Sud UPC

**Dieter van Melkebeek, University of Wisconsin-Madison, USA**

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

**Title:****Many hard computational problems contain a parameter k other than the**

**Abstract:**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).

uesday May 30, 2017

Date: T

**11h-11h50**

**Time:****Room 103,**

**Where:****Facultat de Matematiques i Estadistica**Campus Sud UPC

**Gilles Zemor, Univ. Bordeaux**

**Speaker:****Unconditionally private communication through error correction**

**Title:****In the model that has become known as "Perfectly Secure Message Transmission"(PSMT), a sender Alice is**

**Abstract:**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

**10h-10h45**

**Time:****Room 103,**

**Where:****Facultat de Matematiques i Estadistica**, Campus Sud UPC

**Wouter Cames van Batenburg, Radboud University Nijmegen**

**Speaker:****Packing graphs of bounded codegree**

**Title:****Two graphs G1 and G2 of order n are said to pack if there exist injective mappings of their vertex sets**

**Abstract:**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

**12:00**

**Time:****Room C3-005, Campus Nord UPC**

**Where:****Christoph Spielgel, UPC, Barcelona**

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

**We study the biased version of a strong generalization of the van der Waerden games introduced by Beck as**

Abstract:Abstract:

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

**12:00**

**Time:****Room C3-005, Campus Nord UPC**

**Where:****Piotr Zwiernik, UPF, Barcelona**

**Speaker:****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

** **12:00

Time:

**Room C3-005, Campus Nord UPC**

**Where:****Clement Requilé, UPC, Barcelona**

Speaker:Speaker:

**Enumeration of 4-regular planar graphs**

Title:Title:

**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é.**

Abstract:Abstract:

**Date: **Wednesday April 5, 2017

**12:00**

**Time:****Room C3-005, Campus Nord UPC**

**Where:****Shagnik Das, Freie University Berlin**

Speaker:Speaker:

**Supersaturation for disjoint pairs**

Title:Title:

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

Abstract:

Abstract:

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

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

Where:

Where:

**Mozhgan Pourmoradnasseri, University of Tartu, Estonia**

Speaker:

Speaker:

**The (minimum) rank of typical fooling-set matrices**

Title:

Title:

**Fooling set is known under different names in computer science and**

Abstract:

Abstract:

mathematics. It is usually used to provide lower bounds on some desired

computational factors. In polytope theory and combinatorial

optimization, the fooling set gives a lower bound on the extension

complexity of a polytope and the minimum size of a linear program. In

computational complexity, the logarithm of the size of a fooling set

induces a lower bound on the communication complexity of a function. In

graph theory, considering the matrix as the adjacency matrix of a

bipartite graph, the fooling set corresponds to a cross-free matching,

which provides a lower bound on the size of the biclique covering of a

graph. A fooling-set matrix is a square matrix with nonzero diagonal,

but at least one in every pair of diagonally opposite entries is 0.

Dietzfelbinger et al. ’96 proved that the rank of such a matrix is at

least \sqrt{n}, for a matrix of order n. It is known that the bound is

tight (up to a multiplicative constant). Due to the diverse application

of fooling set type lower bounds in deferent areas, knowing a priori

upper bound on the size of the fooling set can show the usefulness of

the method in advance. In this talk, the typical minimum rank of a

fooling-set matrix will be discussed: For a fooling-set zero-nonzero

pattern chosen at random, is the minimum rank of a matrix with that

zero-nonzero pattern over a field F closer to its lower bound \sqrt{n}

or to its upper bound n? We study random patterns with a given density

p, and prove an \Omega(n) bound for the cases when (a) p tends to 0

quickly enough; (b) p tends to 0 slowly, and |F| = O(1); (c) p \in ]0,1]

is a constant.

**Date:** Thursday, February 23, 2017

**Time:** 12:00

**Where:** Room C3-005, Campus Nord UPC

**Speaker:** Camino Balbuena

**Title:** Vertex disjoint 4-cycles in bipartite tournaments.

**Abstract****:** Let k ≥ 2 be an integer. Bermond and Thomassen conjectured that every

digraph with minimum out-degree at least 2k − 1 contains k vertex disjoint cycles.

In this paper we prove that every bipartite tournament with minimum out-degree at

least 2k −2 and minimum in-degree at least 1 contains k disjoint 4-cycles whenever

k ≥ 3. Also we show a bipartite tournament with out-degree 2 and in-degree 1

having no two disjoint C4. Finally, we show that every bipartite tournament with

minimum degree = min{+, −} at least 1.5k − 1 contains k disjoint 4-cycles.

**Date:** Thursday, February 16, 2017

**Time:** 12:00

**Where:** Room C3-005, Campus Nord UPC

**Speaker:** Miquel Àngel Fiol

**Title:** Complexity measures of edge-uncolorability in cubic graphs

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

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

** Date:** Tuesday, February 14, 2017

**Time:** 11:00

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

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

**Title:** Derandomizing Isolation in the Space-Bounded Setting

**Abstract:** Isolation is the process of singling out a solution to a

problem that may have many solutions. It plays an important role in the

design of efficient parallel algorithms as it ensures that the various

parallel processes all work towards a single global solution rather than

towards individual solutions that may not be compatible with one

another. For example, the best parallel algorithms for finding perfect

matchings in graphs hinge on isolation for this reason. Isolation is

also an ingredient in some efficient sequential algorithms. For example,

the best running times for certain NP-hard problems like finding

hamiltonian paths in graphs are achieved via isolation.

All of these algorithms are randomized, and the only reason is the use

of the Isolation Lemma -- that for any set system over a finite

universe, a random assignment of small integer weights to the elements

of the universe has a high probability of yielding a unique set of

minimum weight in the system. For each of the underlying problems it is

open whether deterministic algorithms of similar efficiency exist.

This talk is about the possibility of deterministic isolation in the

space-bounded setting. The question is: Can one always make the

accepting computation paths of nondeterministic space-bounded machines

unique without changing the underlying language and without blowing up

the space by more than a constant factor? Or equivalently, does there

exist a deterministic logarithmic space mapping reduction from directed

st-connectivity to itself that transforms positive instances into ones

where there is a unique path from s to t?

I will present some recent results towards a resolution of this

question, obtained jointly with Gautam Prakriya. Our approach towards a

positive resolution can be viewed as derandomizing the Isolation Lemma

in the context of space-bounded computation.

**Date:** Monday, February 6, 2017

**Time:** 15:00

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

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

**Title:** Total space in Resolution is at least width squared

**Abstract:** In this talk we cover some results on the space complexity of

Resolution and in particular the new recent connection between total

space and width in the title. Given a k-CNF formula F, the width is the

minimal integer W such that there exists a Resolution refutation of F

with clauses of at most W literals. The total space is the minimal size

T of a memory used to write down a Resolution refutation of F, where

the size of the memory is measured as the total number of literals it

can contain. We show that T = \Omega((W-k)^2). This connection between

total space and width relies on some basic properties of another,

perhaps less known, complexity measure in Resolution: the asymmetric

width.

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

**Date:** Monday, January 30, 2017

**Time:** 15:00:00

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

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

**Title:** How Limited Interaction Hinders Real Communication (and What It

Means for Proof and Circuit Complexi

**Abstract: **We obtain the first true size-space trade-offs for the cutting planes

proof system, where the upper bounds hold for size and total space for

derivations with constant-size coefficients, and the lower bounds apply

to length and formula space (i.e., number of inequalities in memory)

even for derivations with exponentially large coefficients. These are

also the first trade-offs to hold uniformly for resolution, polynomial

calculus and cutting planes, thus capturing the main methods of

reasoning used in current state-of-the-art SAT solvers.

We prove our results by a reduction to communication lower bounds in a

round-efficient version of the real communication model of [Krajicek

'98], drawing on and extending techniques in [Raz and McKenzie '99] and

[Goos et al. '15]. The communication lower bounds are in turn

established by a reduction to trade-offs between cost and number of

rounds in the game of [Dymond and Tompa '85] played on directed acyclic

graphs.

As a by-product of the techniques developed to show these proof

complexity trade-off results, we also obtain an exponential separation

between monotone-AC^(i-1) and monotone-AC^i, improving exponentially

over the superpolynomial separation in [Raz and McKenzie '99]. That is,

we give an explicit Boolean function that can be computed by monotone

Boolean circuits of depth log^i n and polynomial size, but for which

circuits of depth O(log^(i-1) n) require exponential size.

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

**Date:** Wednesday December 7 2016

**Time:**12h

**Where:**Room C3-005, Campus Nord UPC

**Speaker:**George Gottlob, University of Oxford

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

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

**Date:** Thursday 24 November 2016**Time:** 13.00 **ATTENTION AT THE TIME****Where:** Room C3-005, Campus Nord UPC**Speaker:** Joan Vilaltella**Title:** Autograph, a simple and evolving tool for graphs / Autograph, una eina per grafs senzilla i en evolució**Abstract: **There are many excellent software packages for the everyday calculation of graph properties, and other packages, also very good, for the creation of diagrams, but finding both functions in the same tool is not that easy. Autograph modestly tries to fill that void, combining the power of the NetworkX software with an edition area where graphs can be drawn as they would be drawn on a blackboard, but fostering greater interactivity, since the values of many properties are automatically updated with each modification. It is also possible to undo and redo changes, graphs can be stored and retrieved, and even different topologies can be used. We will be able to see this graph editor at work, not forgetting its possible competitors, and also to comment on which new features would be interesting for their addition in future versions.Encara que hi ha molts paquets de programari excel·lents per fer càlculs habituals de la teoria de grafs, i altres, també molt bons, per crear diagrames, no és tan freqüent que totes dues funcions coincideixin en la mateixa eina. Autograph intenta modestament omplir aquest buit, combinant la potència del programari NetworkX amb una àrea d'edició que permet dibuixar els grafs de manera semblant a com els dibuixaríem en una pissarra, però facilitant la interactivitat, ja que els valors de diverses propietats s'actualitzen automàticament amb cada modificació. També és possible desfer i refer canvis, els grafs es poden desar i recuperar, i fins i tot es pot treballar en diferents topologies. Podrem veure aquest editor de grafs en funcionament, sense oblidar els seus possibles competidors, i també comentar quines noves característiques serien interessants per incorporar-les a futures versions.

**Date**: Wednesday November 23, 2016

**Time**: 12h

**Where**: Room 005, Modul C3, Campus Nord UPC

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

**Title**: Weighted dependency graphs

**Abstract**:

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

**Date**: Wednesday November 16, 2016

**Time**: 12h

**Where**: Room 005, Modul C3, Campus Nord UPC

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

**Title**: First order logic of permutations

**Abstract**:

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

**Date:** 2016-11-15 (TUESDAY)**Time:** 12:00:00 **Where:** Room S210 (floor -2), Omega Building, Campus Nord **Speaker**: Martin Koutecký, Department of Applied Mathematics, Charles University, Prague **Title:** Voting and Bribing in Single-Exponential Time **Abstract:**

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

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

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

**Date:** 2016-11-10**Time:** 13:00 **ATTENTION AT THE TIME****Where**: Room 005, Modul C3, Campus Nord UPC **Speaker:** Gabriela Araujo, Universidad Nacional Autónoma de México (UNAM) **Title:** El problema de Moore en gráficas mixtas **Abstract: **En esta charla abordaremos el problema de Moore en Gráficas Mixtas, el cual fue introducido por Bosàk en 1979, a partir de ese momento este problema ha sido abordado por varios autores y se han logrado distintos resultados de los cuales hablaremos en esta charla, además expondremos nuestras recientes aportaciones en este tema. Por otro lado, buscando generalizar este problema, debido a que dicho problema está relacionado de manera natural con el problema de las Jaulas, plantearemos el problema de Jaulas Mixtas y mostraremos los avances que tenemos en dicho problema.

**Date:** 2016-11-03 **Time:** 13:00 **ATTENTION AT THE TIME****Where**: Room 005, Modul C3, Campus Nord UPC **Speaker:** Adriana Hansberg, Universidad Nacional Autónoma de México (UNAM) **Title:** Subsecuencias de suma acotada en secuencias de -1’s y 1’s con suma acotada **Abstract: **En esta charla, presentaré el siguiente resultado:

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

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

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

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

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

**Date:** 2016-11-02 **WEDNESDAY****Time:** 12:00 **Where**: Room 005, Modul C3, Campus Nord UPC **Speaker:** Arnau Padrol, Institut de Mathématiques de Jussieu, Université Pierre et Marie Curie (Paris 6) **Title:** Colorful simplicial depth, Minkowski sums, and generalized Gale transforms **Abstract: **The colorful simplicial depth of a collection of d+1 finite sets of points in Euclidean d-space is the number of choices of a point from each set such that the origin is contained in their convex hull. We use methods from combinatorial topology to prove a tight upper bound on the colorful simplicial depth. This implies a conjecture of Deza et al. (2006). Furthermore, we introduce colorful Gale transforms as a bridge between colorful configurations and Minkowski sums. Our colorful upper bound then yields a tight upper bound on the number of totally mixed facets of certain Minkowski sums of simplices. This resolves a conjecture of Burton (2003) in the theory of normal surfaces.

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

**Date:** WEDNESDAY 14 September 2016**Time:** 12.00**Where:** Room C3-005, Campus Nord UPC**Speaker:** Domenico LABBATE**Title:** Characterizations of regular graphs with conditions on their 2-factors**Coauthors:** M. Abreu, M.Funk, B.Jackson, J. Sheehan et al.**Abstract:** In this talk, we present existence results and partial characterizations of regular graphs having all 2–factors

Hamiltonian, isomorphic or with the same parity of number of circuits. We will present several conjectures and a

counterexample to one of those. Finally, we will investigate relations between some of these classes and the class of

snarks with all 2-factors having circuits of odd length.

### Acknowledgements

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

Share: