Most of my work belongs to discrete mathematics. This area of mathematics deals with mathematical structures and problems that are "discrete" in nature, as opposed to those that exhibit continuous properties. Since information in computer systems is stored as sequences of zeroes and ones, discrete mathematics finds many applications in computer science.
My PhD is in structural and algorithmic graph theory. A graph is a mathematical object that consists of elements called vertices and links between them called edges. For example, the road map in a GPS device in a car is discretized and represented by a graph, i.e. by a list of crossings (vertices) with mutual links (edges). A substantial amount of my work during and after my PhD is related to graph colorings, i.e. decompositions of vertices and edges of graphs subject to certain constraints. My work in structural graph theory includes a solution of Lovász-Plummer Conjecture and a solution of Steinberg’s Conjecture, which both were included in the list of 100 significant open problems in the book Graph Theory by Bondy and Murty (after 15 years since its publication, only 5 of these 100 problems are fully resolved). In relation to computer science applications, I am interested in using graph decompositions and logic methods in algorithm design.
Most of my current research is related to combinatorial limits. The theory of combinatorial limits provides analytic views on large discrete structures and it responds to challenges from computer science where structures such as the graph of internet connections and graphs of social networks (e.g., Facebook, LinkedIn) are enormous. The theory opened new links between analysis, combinatorics, ergodic theory, group theory and probability theory. For example, the recently refuted conjecture of Aldous and Lyons on sparse graph limits is closely related to Gromov's question whether all countable discrete groups are sofic. My work includes applications of analytic methods in extremal combinatorics and it also led to new insights in structural properties of graph limits.
Concerning the theory of graph limits, I have been mostly interested in problems concerning limits of dense graphs. Such graph limits determined by finitely many subgraph densities (finitely forcible graph limits) form extremal points of the graph limit space and are closely related to problems in extremal combinatorics, one of my main research areas in mathematics. Indeed, questions from extremal graph theory can be cast as optimization problems over the graph limit space with optimal solutions corresponding to its extremal points. It was believed that a special structure of finitely forcible graph limits could result in new methods for difficult problems from extremal combinatorics.
Lovász and Szegedy in 2011 made two conjectures that would imply that all finitely forcible graph limits possess a simple structure. In a series of papers coauthored by my postdocs and students, we developed the method of decorated constraints that can be used to construct complex finitely forcible graph limits, and disproved the two conjectures of Lovász and Szegedy. This line of research culminated with a joint result with Cooper and Martins (two students working under my supervision), where we provided a universal framework for constructing very complex finitely forcible graph limits by showing that any graphon can be embedded in a finitely forcible graphon (graphons are analytic objects representing dense graph limits). This dismissed any hope that finitely forcible graph limits possess a simple structure, and is surprising when contrasted with the fact that finitely forcible graph limits form a meager set in the space of all graph limits.
Building on these results, Grzesik, Lovász Jr. and I constructed a counterexample to a conjecture of Lovász on the finite forcibility of optimum solutions in extremal graph theory, which was one of the two most frequently cited open problems on graph limits. This conjecture, which is often referred to as saying that "every extremal graph theory problem has a finitely forcible optimum", reads as follows: every finite feasible set of subgraph density constraints can be extended further by a finite set of density constraints such that the resulting set is satisfied by an asymptotically unique graph. Such a result would match our empirical experience in extremal graph theory where many extremal configurations have a simple (though sometimes recursive) structure. We have constructed a counterexample using a mixture of analytic and flag algebra arguments.
Integer programming is a fundamental problem in mathematical optimization with a vast range of applications. Integer programming is computationally very hard; in fact, its restriction to zero-one variables is one of the 21 original problems shown to be NP-complete by Karp in his 1972 paper. On the other hand, if the constraint matrix of an input instance exhibits a specific block structure, such as in 2-stage IPs and n-fold IPs, integer programming can be efficiently solved. These tractability results are based on the sparsity of the constraint matrix of an instance, which is measured by the primal/dual tree-depth of the matrix.
Matroids have long been a crucial concept in discrete optimization, particularly as a theoretical framework for determining the optimality of greedy algorithms. My recent research has started uncovering a completely new and very different link between matroid theory and discrete optimization. By exploiting the fact that the structure of the column matroid of a matrix is preserved by elementary row operations, my collaborators and I have identified specific structural properties of the column matroid under which a matrix is equivalent to a sparse matrix. Building on our structural results, we have designed efficient algorithms that reveal a hidden Dantzig-Wolfe-like structure of the constraint matrix. For instance, we have shown the smallest dual tree-depth of a matrix equivalent to the given matrix is equal to branch-depth of the column matroid of the matrix, and designed an efficient algorithm that transforms an integer programming instance to an equivalent one with the constraint matrix having the smallest possible dual tree-depth.
Graph coloring is one of the most classical topics in graph theory and it continues to form a large part of my research since my PhD. A major open problem on colorings of planar graphs was Steinberg's Conjecture from 1976, which was widely believed to be true but out of reach of the current proof techniques. The conjecture asserts that every planar graph with no cycles of length four or five is 3-colorable and can be viewed as a variant of the very classical theorem of Grötzsch from 1959 that every triangle-free planar graph is 3-colorable. Steinberg's Conjecture has been attracting a substantial amount of attention among graph theorists and several stronger conjectures, e.g., Novosibirsk 3-Color Conjecture and Strong Bordeaux Conjecture, have been proposed. We disproved the conjecture in 2016. Steinberg's Conjecture is the first and, so far, the only solved problem with a four star (highest) importance rating on the Open Problem Garden, a collection of open problems particularly from combinatorics. Our (quite simple) counterexample attracted a good amount of attention in the graph theory community and was also featured in an article in the popular science magazine Pour la Science.