2016-17 LIMDA Seminar
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 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.
____________________________
- 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).
____________________________
Joint work with A. Pokrovskiy and in part with N. Alon
____________________________
Date: Thursday, June 15th 2017
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.
____________________________
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: June 6th 2017
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).
____________________________
Title: Unconditionally private communication through error correction
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: May 30th 2017
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.
____________________________
Speaker: Christoph Spiegel, 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.
____________________________
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.
____________________________
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.
____________________________
____________________________
Speaker: Miquel Àngel Fiol
Title: Complexity measures of edge-uncolorability in cubic graphs
Joint work with G. Mazzuoccolo and E. Steffen.
____________________________
Date: February 14th 2017
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.
____________________________
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 theminimal integer W such that there exists a Resolution refutation of F with clauses of at most W literals. The total space is the minimal sizeT 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.
____________________________
Title: How Limited Interaction Hinders Real Communication (and What It Means for Proof and Circuit Complexity
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.
____________________________
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.
____________________________
Date: November 24th 2016
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.
____________________________
____________________________
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”.
____________________________
Date: November 10th 2016
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: November 3rd 2016
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
Este es un trabajo en colaboración con Yair Caro y Amanda Montejano.
____________________________
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.
____________________________
Title: Characterizations of regular graphs with conditions on their 2-factors
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.
Share: