Workshop B2 - Graph Theory and Combinatorics

Organizers: Marc Noy (Universitat Politècnica de Catalunya, Spain) - Jaroslav Nesetril (Charles University, Czech Republic) - Angelika Steger (ETH Zürich, Switzerland)

View workshop abstracts PDF



July 13, 14:30 ~ 15:20 - Room B7

Stability and Exactness Results from Flag Algebra Calculations

Oleg Pikhurko

University of Warwick, United Kingdom   -

Flag algebras provide a powerful framework for proving asymptotic inequalities between the possible densities of fixed subgraphs in a large graph. We develop general methods for establishing more refined results (namely, stability as well as exact inequalities) from flag algebra calculations and apply them to concrete examples (Turan function, inducibility problem, etc). In fact, some of our sufficient conditions are stated in a way that allows automatic verification by a computer. This gives a unifying way to obtain computer-assisted proofs of some known and new results.

Joint work with Jakub Sliacan (The Open University, UK) Kostas Tyros (Koç University, Turkey).

View abstract PDF

July 13, 15:30 ~ 15:55 - Room B7

Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs

Sergio Cabello

University of Ljubljana, Slovenia   -

We show how to compute for $n$-vertex planar graphs in roughly $O(n^{11/6})$ expected time the diameter and the sum of the pairwise distances. These are the first algorithms for these problems using time $O(n^c)$ for some constant $c<2$, even when restricted to undirected, unweighted planar graphs.

View abstract PDF

July 13, 16:00 ~ 16:25 - Room B7

Critical percolation on random regular graphs

Guillem Perarnau

University of Birmingham, United Kingdom   -

We show that for all $d\in \{3,\ldots,n-1\}$ the size of the largest component of a random $d$-regular graph on $n$ vertices at the percolation threshold $p=1/(d-1)$ is $\Theta(n^{2/3})$, with high probability. This extends known results for fixed $d\geq 3$ and for $d=n-1$, confirming a prediction of Nachmias and Peres on a question of Benjamini. In contrast to previous approaches, our proof is based on an application of the switching method.

Joint work with Felix Joos (University of Birmingham).

View abstract PDF

July 13, 17:00 ~ 17:50 - Room B7

Modeling limits

Patrice Ossona de Mendez

Centre d’analyse et de mathématique sociales (CAMS) and CNRS, France   -

A sequence of graphs is FO-convergent if the probability of satisfaction of every first-order formula converges. A graph modeling is a graph, whose domain is a standard probability space, with the property that every definable set is Borel. It was known that FO-convergent sequences of graphs do not always admit a modeling limit, and it was conjectured that this is the case if the graphs in the sequence are sufficiently sparse. Precisely, two conjectures were proposed:

1) If a FO-convergent sequence of graphs is residual, that is, if for every integer $d$ the maximum relative size of a ball of radius $d$ in the graphs of the sequence tends to zero, then the sequence has a modeling limit.

2) A monotone class of graphs $\mathcal C$ has the property that every FO-convergent sequence of graphs from $\mathcal C$ has a modeling limit if and only if $\mathcal C$ is nowhere dense, that is, if and only if for each integer $p$ there is $N(p)$ such that the $p$th subdivision of the complete graph on $N(p)$ vertices does not belong to $\mathcal C$.

In this talk we present the proof of both conjectures. This solves some of the main problems in the area and among others provides an analytic characterization of the nowhere dense--somewhere dense dichotomy.

View abstract PDF

July 13, 18:00 ~ 18:25 - Room B7

On the computation of numerical semigroups

Maria Bras

Universitat Rovira i Virgili, Spain   -

A numerical semigroup is a subset of the positive integers (${\mathbb N}$) together with $0$, closed under addition, and with a finite complement in ${\mathbb N}\cup\{0\}$. The number of gaps is its {\it genus}. Numerical semigroups arise in algebraic geometry, coding theory, privacy models, and in musical analysis. It has been shown that the sequence counting the number of semigroups of each given genus $g$, denoted $(n_g)_{g\geq 0}$, has a Fibonacci-like asymptotic behavior. It is still not proved that, for each $g$, %it holds $n_{g+2}\geq n_{g+1}+n_{g}$ or, even more simple, $n_{g+1}\geq n_g$.

All algorithms used to compute $n_g$ explore by brute force approach the tree that contains at each depth the semigroups of genus equal to that depth, and in which the parent of a semigroup is the semigroup obtained when adjoining to the child its largest gap. We present a new algorithm for descending the tree using the new notion of seed of a numerical semigroup.

Joint work with Julio Fernández-González (Universitat Politècnica de Catalunya).

View abstract PDF

July 13, 18:30 ~ 18:55 - Room B7

Bijections for planar maps with boundaries

Eric Fusy

École Polytechnique and CNRS, France   -

I will present a general bijective method for planar maps based on certain orientations. This method allows us to count planar maps with prescribed face-degrees and girth. I will then explain how the method and (partial) girth control can be adapted to the setting of planar maps with boundaries (i.e., planar maps where some faces are distinguished, so that these face-contours are vertex-disjoint simple cycles).

Joint work with Olivier Bernardi (Brandeis University).

View abstract PDF

July 14, 14:30 ~ 15:20 - Room B7

Gaps Between Classical Satisfiability Problems and their Quantum Relaxations

Albert Atserias

Universitat Politècnica de Catalunya, Spain   -

An instance of the constraint satisfaction problem asks for an assignment of values to variables in such a way that a given set of local constraints are satisfied. One can think of such problems operationally in the form of a game: Alice provides value-assignments that satisfy given constraints on request, Bob provides value-assignments to the variables also on request, and a referee checks if Alice's and Bob's assignments are consistent with one another. Many problems of graph theory, combinatorics, logic and computer science fall within this abstract framework. Since the problem of deciding if Alice and Bob have a winning strategy is NP-hard to solve in general, a common approach to provide structure to the problem is to consider relaxations of it where the variables range over larger but more structured domains. We study a relaxation that is actually motivated by a modeling issue: the universe appears to be quantum mechanical, so Alice and Bob could use strategies that are correlated through quantum entanglement. In this relaxation, which is well-studied in quantum information theory, the constraints are represented by polynomials through their Fourier transform, and the variables range over bounded linear operators over a Hilbert space. Among other results we obtain a complete understanding of which types of Boolean constraints show a discrepancy between quantum and classical strategies.

View abstract PDF

July 14, 15:30 ~ 15:55 - Room B7

An application of Hoffman graphs for spectral characterizations of graphs

Aida Abiad

Maastricht University, The Netherlands   -

In this paper, we present the first application of Hoffman graphs for spectral characterizations of graphs. In particular, we show that the $2$-clique extension of the $(t+1)\times(t+1)$-grid is determined by its spectrum when $t$ is large enough. This result will help to show that the Grassmann graph $J_2(2D,D)$ is determined by its intersection numbers as a distance regular graph, if $D$ is large enough.

Joint work with Qianqian Yang (University of Science and Technology of China) and Jack H. Koolen (University of Science and Technology of China and Wen-Tsun Wu Key Laboratory of CAS).

View abstract PDF

July 14, 16:00 ~ 16:25 - Room B7

Colorful simplicial depth, Minkowski sums, and generalized Gale transforms

Arnau Padrol

Université Pierre et Marie Curie, France   -

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.

Joint work with Karim Adiprasito (Hebrew University of Jerusalem), Philip Brinkmann (Freie Universität Berlin), Pavel Paták (Hebrew University of Jerusalem), Zuzana Patáková (Hebrew University of Jerusalem), Raman Sanyal (Goethe Universität Frankfurt).

View abstract PDF

July 14, 17:00 ~ 17:50 - Room B7

Approximation of MIN CSPs

Víctor Dalmau

Universitat Pompeu Fabra, Spain   -

An instance of the constraint satisfaction problem (CSP) is given by a family of constraints on overlapping sets of variables, and the goal is to assign values from a fixed domain to the variables so that all constraints are satisfied. In the optimization version, the goal is to maximize the number of satisfied constraints (MAX CSP) or, alternatively, to minimize the number of unsatisfied constraints (MIN CSP). This problem is usually parameterized by the set, Gamma, of relations allowed in the constraints, usually called constraint language. It turns out that MAX CSP/MIN CSP is computationally hard for most constraint languages, which motivates the study of approximation algorithms. In this talk we will focus on the approximation of MIN CSPs. We shall start addressing the following question: which constraint languages give rise to a MIN CSPs that is constant-factor approximable? We shall also study some other weaker approximation notions such polynomial loss and robust approximation.

View abstract PDF

July 14, 18:00 ~ 18:25 - Room B7

Enumeration of labelled 4-regular planar graphs

Juanjo Rué

Universitat Politècnica de Catalunya, Spain   -

The enumeration of planar graphs and related classes of graphs is currently an active area of research. For the case of 4-regular planar graphs there are known schemes for exhaustive generation starting from some basic graphs, such as the graph of the octahedron, but no counting results up to now. We present here a complete solution to the enumeration of 4-regular planar graphs.

To obtain our results we follow the classical technique introduced by Tutte: take a graph rooted at a directed edge and classify the possible configurations arising from the removal of the root edge. This produces several combinatorial classes that are further decomposed, typically in a recursive way. The decomposition translates into a system of polynomial equations for the associated generating functions. Along the way, we have to deal with the enumeration of quadrangulations and other classes of planar maps.

Joint work with Marc Noy (Universitat Politècnica de Catalunya and BGSMath) and Clément Requilé (Freie Universität Berlin and Berlin Mathematical School).

View abstract PDF

July 14, 18:30 ~ 18:55 - Room B7

A Tutte polynomial for graphs embedded on surfaces

Lluís Vena

University of Amsterdam, The Netherlands   -

In this talk, we present a graph polynomial for maps (graphs embedded in orientable surfaces) that contains the Las Vergnas polynomial, Bollob\'as-Riordan polynomial and Kruskhal polynomial as specialisations.

The new polynomial invariant of maps is built following Tutte's construction of the dichromate of a graph (that is, the Tutte polynomial) as a unification of the chromatic polynomial and the flow polynomial. In our case, we consider the analogues for maps of the chromatic polynomial (local tensions) and of the flow polynomial (local flows). Hence, by construction, the new polynomial includes among its evaluations the number of local tensions and local flows taking values in any given finite group. Other evaluations include the number of quasi-forests. An extension of the polynomial to graphs embedded on non-orientable surfaces is also discussed.

Joint work with Andrew Goodall (Charles University Prague), Thomas Krajewski (Aix-Marseille Université), Bart Litjens (University of Amsterdam), and Guus Regts (University of Amsterdam)..

View abstract PDF

July 15, 14:30 ~ 15:20 - Room B7

Geometric Representations of Graphs: Partial Extensions versus Simltaneous Embeddings

Jan Kratochvil

Charles University, Prague, Czech Republic   -

Extending partial solutions is often provably more difficult than constructing a solution from scratch. Somewhat surprisingly for geometric representations of graphs, this does not seem to be the case. In most of the cases when the computational complexity of the extension problem is known, the complexity is the same as of the plain recognition problem. Another closely related problem are simultaneous representations of graphs. Closely related, but not always known to be of the same computational complexity. We will survey the known results, compare them, and comment on open problems. The classes of graphs we will be interested in are interval graphs, circle graphs, comparability graphs, and also several graph drawing types.

View abstract PDF

July 15, 15:30 ~ 16:20 - Room B7

Planar arcs

Simeon Ball

Universitat Politècnica de Catalunya, Spain   -

Let $\mathrm{PG}_{2}({\mathbb F}_q)$ denote the projective plane over ${\mathbb F}_q$. An arc (or planar arc) of $\mathrm{PG}_{2}({\mathbb F}_q)$ is a set of points in which any $3$ points span the whole plane. An arc is complete if it cannot be extended to a larger arc.

In 1967 Beniamino Segre proved that the set of tangents to a planar arc of size $q+2-t$, when viewed as a set of points in the dual plane, is contained in an algebraic curve of small degree $d$. Specifically, if $q$ is even then $d=t$ and if $q$ is odd then $d=2t$.

The main result to be presented here is the following theorem.

Theorem 1: Let $S$ be a planar arc of size $q+2-t$ not contained in a conic. If $q$ is odd then $S$ is contained in the intersection of two curves, sharing no common component, each of degree at most $t+p^{\lfloor \log_p t \rfloor}$.

This leads directly to the following theorem.

Theorem 2: If $q$ is odd then an arc of size at least $q-\sqrt{q}+3+\max \{ \sqrt{q}/p,\frac{1}{2} \}$ is contained in a conic.

There are examples of complete arcs of size $q+1-\sqrt{q}$ in $\mathrm{PG}_2({\mathbb F}_q)$ when $q$ is square, first discovered by Kestenband in 1981. These arcs are the intersection of two curves of degree $t$.It has long been conjectured that if $q \neq 9$ is an odd square then any larger arc is contained in a conic.

Joint work with Michel Lavrauw (Sabanci University).

View abstract PDF

July 15, 17:00 ~ 17:50 - Room B7

Some topological algorithms for graphs on surfaces

Éric Colin de Verdière

Université Paris-Est Marne-la-Vallée and CNRS, France   -

The aim of this talk is to survey various recent results for solving computational problems for graphs on surfaces, at the interface of topological graph theory and graph algorithms.

Given a topologically non-trivial surface (up to homeomorphism, a sphere with handles), how can we compute a shortest non-contractible closed curve (which cannot be continuously deformed to a point)? How can we cut the surface economically to to make it planar (homeomorphic to a disk)? These are basic topological questions, which we revisit them from an algorithmic perspective.

Conversely, we will illustrate how topology can help devising more efficient graph algorithms in the case of graphs embeddable on a fixed surface, in the case of the minimum multicut problem.

View abstract PDF



Scaffolding skeletons using spherical Voronoi diagrams

Alvaro Javier Fuentes Suárez

Inria Sophia Antipolis, France   -

Skeletons are used in 3D graphics for modeling and animating articulated shapes. The user can design a complex shape by sketching a simple and intuitive geometric object that is the input to a surface generating algorithm.

In this work, a skeleton is a finite set of line segments in space that do not intersect except at the endpoints. It can be seen as a graph with geometrical constraints (length of the edges, position of vertices). We study the problem of generating a mesh around a skeleton. The mesh we want to obtain should be as "coarse" as possible (in the sense of number of patches around each line segment), with mostly quad patches and must enclose the skeleton. Following [Panotopoulou] we call this mesh a scaffold.

This problem has been studied before in [Ji2010] and [Bærentzen2012]. The main limitation in Ji et al. was the presence of irregularities in the final mesh. Furthermore the method proposed by Bærentzen et al. cannot handle closed skeletons, i.e. skeletons with cycles when seen as a graph. The following problems were also left as open : under what conditions the construction can be done; whether there is an optimal solution on the number of patches; or whether the mesh can be constructed such that each segment piece is enclosed by the same number of patches.

We present a method for constructing a scaffold for a skeleton using spherical Voronoi diagrams at the branch points. We prove that such a mesh can always be computed, even in the presence of cycles. We can compute a solution with minimal total number of patches, or, alternatively, a mesh with the same number of patches around each line segment. The main tools we use are: spherical Voronoi diagrams, Delaunay triangulations, Integer Linear Programming and a numerical characterization of inscribable graphs due to [Rivin1996].

Our method has been implemented and is currently being used for developing a meshing algorithm for implicit surfaces defined around a skeleton [Zanni2013]. We point out also that the problem is closely related to a perfect matching for graphs.


[Panotopoulou] Panotopoulou, A., K. Welker, E. Ross and E. Hubert, "Scaffolding a Skeleton", (in preparation).

[Ji2010] Ji, Z., L. Liu and Y. Wang, "B-Mesh: A modeling system for base meshes of 3D articulated shapes", Computer Graphics Forum 29 (2010).

[Bærentzen2012] Bærentzen, J. A., M. K. Misztal and K. We?nicka, "Converting skeletal structures to quad dominant meshes", Computers and Graphics 36 (2012).

[Rivin1996] Rivin, I., "A Characterization of Ideal Polyhedra in Hyperbolic 3-Space", Annals of Mathematics 143 (1996).

[Zanni2013] Zanni, C., "Skeleton-based Implicit Modeling & Applications" Phd thesis, Universitè de Grenoble (2013).

Joint work with Evelyne Hubert (Inria Sophia Antipolis).

View abstract PDF

Counting arithmetical structures

Luis David Garcia Puente

Sam Houston State University, USA   -

Let $G$ be a finite, simple, connected graph. An arithmetical structure on $G$ is a pair of positive integer vectors $d,r$ such that $(\mathrm{diag}(d)-A)r=0$, where $A$ is the adjacency matrix of $G$. Arithmetical graphs were introduced in the context of arithmetical geometry by Lorenzini in 1989 to model intersections of curves. We investigate the combinatorics of arithmetical structures on path and cycle graphs, as well as the associated critical groups (the cokernels of the matrices $(\mathrm{diag}(d)-A))$. For paths, we prove that arithmetical structures are enumerated by the Catalan numbers, and we obtain refined enumeration results related to ballot sequences. For cycles, we prove that arithmetical structures are enumerated by the binomial coefficients $\binom{2n-1}{ n-1}$, and we obtain refined enumeration results related to multisets. In addition, we determine the critical groups for all arithmetical structures on paths and cycles.

Joint work with Benjamin Braun (University of Kentucky), Hugo Corrales (CINVESTAV), Scott Corry (Lawrence University), Darren Glass (Gettysburg College), Nathan Kaplan (University of California, Irvine), Jeremy L. Martin (University of Kansas), Gregg Musiker (University of Minnesota) and Carlos E. Valencia (CINVESTAV).

View abstract PDF

Null decomposition of trees and its concecuences

Daniel Alejandro Jaume

Universidad Nacional de San Luis, Argentina   -

The purpose of this study is to determine which information about a tree could be obtained from the support of the null space its adjacency matrices. In order to do that, we introduce a new family of trees, the S-trees, which are based on the non-zero entries of vectors in null space. We show that every tree can be decomposed into a forest of S-trees and a forest of non-singular trees.

The support of a tree \(T\) is the set \[ Supp(T):=\{u \in V(T): \exists x \in \mathcal{N}(T) \text{ such that } x_{u}\neq 0\} \] Where \(\mathcal{N}(T)\) is the null space of \(A(T)\), the adjacency matrix of \(T\). The cardinality of the support is denoted \(supp(T)\).

Definition: A tree \(T\) is an S-tree if \(N\left[ Supp(T) \right]=V(T) \), where \(N[Supp(T)]\) is the closed neighborhood of \(Supp(T)\).

Definition: Let \(T\) be an S-tree. The core of \(T\), denoted by \(Core(T)\), is defined to be the set of all non-supported vertices of \(T\). We will denote by \(core(T)\) the cardinality of \(Core(T)\).

A tree \(T\) is non-singular tree, N-tree for short, if its adjacency matrix \(A(T)\) is invertible. Thus \(T\) is a N-tree if and only if \(T\) has a perfect matching.

Definition: Let \(T\) be a tree. The S-forest of T, denoted by \(\mathcal{F}_{S}(T)\), is defined to be the forest induced by the closed neighbor of \(Supp(T)\) in \(T\): \( \mathcal{F}_{S}(T):=T\left\langle N\left[ Supp(T) \right] \right\rangle \). The N-forest of T, denoted by \(\mathcal{F}_{N}(T)\), is defined to be the remain forest: \( \mathcal{F}_{N}(T):=T \backslash \mathcal{F}_{S}(T) \). The pair of forests \((\mathcal{F}_{S}(T),\mathcal{F}_{N}(T))\) is called the Null Decomposition of \(T\).

Theorem: Let \(T\) be a tree. The S-forest \(\mathcal{F}_{S}(T)\) of \(T\) is a forest of S-trees, and the N-forest \(\mathcal{F}_{N}(T)\) of \(T\) is a forest of N-trees. Futhermore:

1) \(\nu(T) = core(T)+\frac{|V(\mathcal{F}_{N}(T))|}{2}\), where \(\nu(T)\) is the matching number of \(T\),

2) \(\alpha(T)= supp(T)+\frac{|V(\mathcal{F}_{N}(T))|}{2} \), where \(\alpha(T)\) is the independence number of \(T\),

3) \( rk(T) = core(T)+|V(\mathcal{F}_{N}(T))| \), where \(rk(T)\) is the rank of the adjacency matrix of \(T\),

4) \( null(T) = supp(T)-core(T) \), where \(null(T)\) is the nullity of the adjacency matrix of \(T\),

5) \( m(T)=\prod_{S \in\mathcal{F}_{S}(T)} m(S) \), where \(m(T)\) is the number of maximum matching of \(T\), and

6) \( a(T)=\prod_{N \in\mathcal{F}_{N}(T)} a(N) \), where \(a(T)\) is the number of maximum independent sets of \(T\).

Corollary: Let \(T\) be a tree. Then \(\nu(T)=\alpha(T)-null(T)\).

Joint work with Gonzalo Molina (Universidad Nacional de San Luis).

View abstract PDF

Bounds on the letter frequencies in Kolakoski sequences via Chvatal's sequence of graphs

Bernd Sing

The University of the West Indies, Barbados   -

An infinite sequence $z$ over the alphabet $\{1,2\}$ that equals its own run-length sequence, is called a Kolakoski-sequence (also see [1,2]): \[% \begin{array}{ccccccccccccccc}% z\!& \!=\! & \underbrace{22} & \underbrace{11} & \underbrace{2} & \underbrace{1} & \underbrace{22} & \underbrace{1} & \underbrace{22} & \underbrace{11} & \underbrace{2} & \underbrace{11} & \ldots && \\ && 2 & 2 & 1 & 1 & 2 & 1 & 2 & 2 & 1 & 2 & \ldots &\! =\!&\! z. \end{array}% \] Prepending a 1 to this sequence gives the other Kolakoski sequence over this alphabet. Although it is conjectured that the letter frequencies are equal in the infinite sequence (i.e., half the letters are 1s and half of them 2s), it is not even know if the frequencies actually exist.

Seeking to understand this mysterious sequences better, one can consider sequences that equal their own run-length sequence over other alphabets with two letters, see [3]: For alphabets consisting of two even numbers, one can easily establish that the limiting frequencies are $1/2$; in the case of two odd numbers, the limiting frequencies are unequal (they are given by cubic irrationals); while in the case that of one even and one odd number, one arrives at the same conjecture about the letter frequencies as for the alphabet $\{1,2\}$.

In order to find bounds on the letter frequencies of the Kolakoski sequence, Vasek Chvatal [4] considered a certain recursively defined sequence of digraphs. Using the 22nd term in this sequence, he showed that the letter frequencies of the Kolakoski sequence are confined to $[0.499162,0.500838]$; however, the number of vertices grows by a factor of $2$ in each step (so the 22nd graph has $2^{22}$ vertices).

In this paper we look at the structure of the digraphs one gets for different alphabets: One can again recursively define such a sequence of digraphs for any two letter alphabet. While the number of vertices always grows by a factor of $2$, other properties like connectedness differ for different alphabets.


[1] W. Kolakoski, ``Self generating runs, Problem 5304'', Amer. Math. Monthly 72: 674 (1965).

[2] R. Oldenburger, ``Exponent trajectories in symbolic dynamics''. Trans. AMS 46: 453–466 (1939).

[3] B. Sing, ``More Kolakoski sequences'', Integers 11B (2011), A14.

[4] V. Chvatal, ``Notes on the Kolakoski sequence'', DIMACS Technical Report 93-84 (1994).

View abstract PDF

The Dehn-Sommerville Relations and the Catalan Matroid

Nicole Yamzon

San Francisco State University, United States   -

The $f$-vector of a $d$-dimensional polytope $P$ stores the number of faces of each dimension. When $P$ is simplicial the Dehn--Sommerville relations imply that to determine the $f$-vector of $P$, we only need to know approximately half of its entries. This raises the question: Which $(\lceil{\frac{d+1}{2}}\rceil)$-subsets of the $f$-vector of a general simplicial polytope are sufficient to determine the whole $f$-vector? We prove that the answer is given by the bases of the Catalan matroid.

Joint work with Anastasia Chavez (University of California Berkeley).

View abstract PDF

FoCM 2017, based on a nodethirtythree design.