Current Trends in Combinatorics

The central problem in monochromatic subgraph partitions is the following: given a complete graph on n vertices whose edges are coloured with r colours, the goal is to find a small set of vertex-disjoint monochromatic cycles which together cover all the vertices. There are variants substituting complete graphs with other host graphs, cycles with other classes of graphs, graphs with hypergraphs, and other. The problem goes back to work by Gyarfas from the late 1960’s, but the core problem as well as its variants have attracted much interest during the past decade. In this talk, we will give an overview of the most important results and methods of the area, and then discuss some recent results for hypergraphs, which are joint work with Bustamante and Han, and with Bustamante.

For a given graph $H$, and a $\{-1, 1\}$-weighting function $f$ of the edges of the complete graph $K_n$, we study the existence of a \emph{zero-sum} copy of $H$; that is, a copy of $H$ in $K_n$ with $\sum_{e\in E(H)}f(e)=0$. For example, for all %all sufficiently large $n$ $n\geq 5$, we can guarantee the existence of a zero-sum copy of $K_4$ for every $f:E(K_n)\to \{-1,1\}$ if we are provided with enough edges of both types; however, this phenomenon is not true if $H$ is a complete graph on $m\geq 5$ vertices. So, given a graph $H$, our aim is to determine a function $h(H, n)$, if it exists, such that, for sufficiently large $n$, every $f:E(K_n)\to \{-1,1\}$ with $\min\{e(-1),e(1)\}\geq h(H,n)$ contains a zero-sum copy of $H$, where $e(-1)$ and $e(1)$ denote the number of edges assigned $-1$ and $1$, respectively. In the cases where $H$ is a path, a star or a tree, the exact function $h(H,n)$ is determined and the extremal $\{-1, 1\}$-weighting functions are characterized. Of course, such type of problems can be regarded as edge coloring problems: while Ramsey Theory studies the existence of monochromatic subgraphs in edge colorings on the complete graph, and anti-Ramsey Theory studies the existence of rainbow subgraphs, here we study the existence of \emph{balanced} subgraphs, where balanced means to have the same number of edges of each color.\\ This is a joint work with Yair Caro and Adriana Hansberg.

The method of hypergraph containers, introduced a few years ago by Balogh, Morris and Samotij, and independently by Saxton and Thomason, has proved to be an extremely useful tool in the study of the typical properties of sparse $H$-free graphs. In particular, a fairly straightforward application of this technique allows one to locate the threshold at which the structure of a typical $H$-free graph transitions from being "random-like" to being "structured". For most hereditary graph properties, however, the standard version of this method does not allow one to establish even the existence of such a threshold. In this talk we will discuss a refinement of the container method that takes into account the asymmetry between edges and non-edges in a sparse member of a hereditary graph property. As an application, we will show how to determine the approximate structure of a typical graph with $n$ vertices, $m$ edges, and no induced copy of $C_4$, for all $m \gg n^{4/3} (\log n)^3$. This is based on joint work with Wojciech Samotij and David Saxton.

Given an $n$-set $M$ and a positive integer $k\leq n$, as a $k$-$sequence$ of elements of $M$ we will understand an injective function $G : \{1, \dots, k\} \rightarrow M$. A $k$-sequence $G$ will be also denoted as $(x_1, \dots, x_k)$, with $G(i) = x_i$ for each $i= 1 \dots, k$. A set $T$ of $k$-sequences of $M$ will be called an $(n,k)$-$transversal$ if for each $n$-sequence $S=(x_1, \dots, x_n)$ of elements of $M$, there is $(y_1, \dots, y_k) \in T$ such that $(y_1, \dots, y_k)$ is a subsequence of $S$. An instance of this notion of transversal can be deduce from a result of Erd\"os and Szekeres which states that every sequence of $n$ integers contains a crescent or decrescent subsequence of order $k$ (for $k \leq \lceil \sqrt{n}\hskip 3pt \rceil$). Given an $n$-set $M$ and a digraph $D=(V, A)$, with vertex-set $M=V$, the set of transitive tournaments of order $k$ of $D$ define, in a ``natural way'', a set of $k$-sequences of $M$ (each of those transitive tournaments of $D$ can define two sequences of $k$ elements of $M$). In this talk we present some $(n,k)$-transversals which arise from the set of transitive tournaments of digraphs, some of them closely related with the diagonal Ramsey numbers.

In this talk we consider two decision problems. The first one is the Golumbic, Kaplan and Shamir decision sandwich problem for the property $\Pi$, where two graphs $G^1 = (V,E^1)$ and $G^2 = (V,E^2)$ are given, such that $E^1 \subseteq E^2$, plus the question whether there exists a graph $G=(V,E)$, such that $E^1 \subseteq E \subseteq E^2$, and $G$ satisfies property $\Pi$. The second one is the Feder, Hell, Klein and Motwani decision graph partition problem, where it is given a graph $G$ and the question whether there is a partition for the vertex set $V$ of $G$ into at most $k$ sets $V_1, V_2, \ldots, V_k$, which can have inner properties (like $V_i$ being a clique, or an independent set, or no restriction) and external properties (like $V_iV_j$ being completely adjacent, or completely non-adjacent, or no restriction). We will discuss the complexity of the sandwich problem for properties or classes of graphs arising from partition problems.

In 2006, Barát and Thomassen made the following conjecture: for each tree \(T\), there exists a natural number \(k_T\) such that, if \(G\) is a \(k_T\)-edge-connected graph and \(|E(T)|\) divides \(|E(G)|\), then \(G\) can be edge-decomposed into copies of \(T\). In a series of papers, starting in 2008, Thomassen verified this conjecture for stars, some bistars, paths of length \(3\), and paths whose length is a power of \(2\). In 2014, we verified this conjecture for paths of length \(5\), and subsequently, for paths of any given length. In this talk we address this last result. We note that further results on this conjecture have been obtained in the last two years: Bensmail, Harutyunyan, Le and Thomassé (2015) proved this conjecture for paths, using a different approach and weakening the condition on high edge-connectivity; more recently, these authors, together with M. Merker proved the conjecture. This is joint work with F. Botler, G. O. Mota, and M. T. I. Oshiro, from University of São Paulo, Brazil.

The problem of finding the mean order of the subtrees of a tree was introduced by Jamison in 1983. It is known that paths have the smallest mean subtree order among trees of a fixed order. However, the problem of determining the structure of trees with maximum subtree order remains open. We discuss some progress on the latter for subclasses of trees. We also present some extensions of the mean subtree order of a tree to other classes of graphs and present results for these new invariants. (This is joint work with Lucas Mol and Alexander Stephens.)

For a graph $H$, let $$c_{\infty}(H) = \lim_{n \to \infty} (\max |E(G)|/n),$$ where the maximum is taken over all graphs $G$ on $n$ vertices not containing $H$ as a minor. Thus $c_{\infty}(H)$ is the asymptotic maximum density of graphs not containing an $H$-minor. Employing a structural result of Eppstein, we prove new upper bounds on $c_{\infty}(H)$ for disconnected graphs $H$. The case when $H=sK_r$, that is when $H$ is a disjoint union of $s$ copies of the complete graph on $r$ vertices, is of particular interest. Thomason has shown that $$c_{\infty}(sK_r)=s(r-1)-1$$ for $s = \Omega(r \sqrt{\log r})$. We show that the same conclusion holds for $s = \Omega(\log^{3/2}r)$, which is best possible up to the power of the logarithm. Based on joint work with Yingjie Qian.

A packing $k$-coloring of a graph $G$ is a partition of $V(G)$ into sets $V_1,\ldots,V_k$ such that for each $1\leq i\leq k$, the distance between any two distinct $x,y\in V_i$ is at least $i+1$. The packing chromatic number, $\chi_p(G)$, of a graph $G$ is the minimum $k$ such that $G$ has a packing $k$-coloring. Sloper showed that there are $4$-regular graphs with arbitrarily large packing chromatic number. The question whether the packing chromatic number of subcubic graphs is bounded appears in several papers. We answer this question in the negative. Moreover, we show that for every fixed $k$ and $g\geq 2k+2$, almost every $n$-vertex cubic graph of girth at least $g$ has the packing chromatic number greater than $k$. This is joint work with J. Balogh and X. Liu.

The local crossing number of a drawing of a graph is the largest number of crossings on any edge of the drawing. In a rectilinear drawing of a graph, the vertices are points in the plane in general position and the edges are straight line segments. The rectilinear local crossing number of a graph $G$ is the minimum local crossing number over all rectilinear drawings of $G$. In this talk, we present the latest results on rectilinear local crossing numbers of the complete and the complete bipartite graphs.

The intersection graph of a set $\mathcal A$ of arcs on a circle is a graph having one vertex for each arc in $\mathcal A$ and such that two different vertices are adjacent if and only if the corresponding arcs have nonempty intersection. A graph $G$ is a circular-arc graph if and only if $G$ is the intersection graph of some set $\mathcal A$ of arcs on a circle; if so, the set $\mathcal A$ is called a circular-arc model of $G$. Forbidden structures for the class of circular-arc graphs and its main subclasses (including subclasses of interval graphs), as well as efficient algorithms for finding these forbidden structures, have received a great deal of attention. In this work, we will present some recent results regarding minimal forbidden induced subgraph characterizations and linear-time algorithms for finding an instance of such forbidden subgraphs for some subclasses of circular-arc graphs, including normal Helly circular-arc graphs, concave-round graphs (also known as Tucker circular-arc graphs or $\Gamma$ circular-arc graphs), and Helly circular-arc graphs. Results on normal Helly circular-arc graphs are joint work with Yixin Cao and Luciano N. Grippo.

We consider a hypergraph analogue of the basic fact that every regular bipartite graph has a perfect matching. A theorem of Aharoni implies that every regular tripartite hypergraph $H$ with $n$ vertices in each class has a matching of size at least $n/2$, and moreover this bound is tight. We prove a stability version of this statement, showing that if $H$ has matching number close to $n/2$ then it is correspondingly close in structure to the extremal configuration.

Kasteleyn (1961) showed how to express the dimer partition function for the square lattice on the torus using 4 Pfaffians and stated without proof that the partition function for a graph of genus $g$ requires $2^{2g}$ Pfaffians (a fact rigorously established almost four decades later). Via algebraic considerations, Kasteleyn also showed that for the square lattice, under some mild conditions on the edge weights, one of the 4 Pfaffians vanishes (equals 0). It is not evident if and how a similar situation occurs for square lattices of genus $g>1$. We give a combinatorial proof of Kasteleyn's observation for $g=1$. We also discuss potential extensions of our result for the higher order genus case and briefly elaborate on possible implications concerning the widely believed assumption in theoretical physics that dimer models are discrete analogues of free fermions. Based on joint work with A. Jiménez (U. Valparaíso, Chile) and M. Loebl (Charles U., Czech Republic)

In this talk, I will discuss variants of Szemer\'edi's celebrated graph regularity lemma with much better quantitative bounds, and how they can be used to make progress on problems in discrete and computational geometry. Based on joint work with J\'anos Pach and Andrew Suk.