Kneser graphs, chromatic numbers, and topological combinatorics
Let $n,k$ be natural numbers such that $n\geq 2k$. The Kneser graph $KG(n,k)$ is the graph whose vertices are the $k$-element subsets of $\{1,\dots,n\}$, and where two such sets $S,T$ are connected by an edge if, and only if, $S\cap T=\emptyset$. The assumption that $n\geq 2k$ tells us that at least some sets are connected by an edge, so this graph is not empty. But it also contains quite a few edges, since for any $m:=\lfloor n/k\rfloor +1$ vertices $S_1,\dots,S_m$, there must at least be one edge between some sets $S_i, S_j$. A "famous" example of such a graph is the so-called Petersen graph, which is $KG(5,2)$.
A proper coloring of a graph $G$ with $r$ colors is a function $\chi$ from $V(G)$ to $\{1,\dots,r\}$ such that if $v,w\in V(G)$ are connected by an edge, then $\chi(v)\neq\chi(w)$. The chromatic number of a graph is the smallest $r$ for which there exists a proper coloring and is denoted by $\chi(G)$. Proving that $\chi(G)\leq r$ is in general easy: it suffices to give one proper coloring that uses at most $r$ colors. However, proving an inequality of the form $\chi(G)\geq r$ is in general quite hard: one must show that no coloring with $r-1$ colors exist. Apart from particularly simple examples such as complete graphs and cycles, it is in general hard to provide such proofs.
It was conjectured by Kneser that the chromatic number of $KG(n,k)$ is exactly $n-2k+2$, and here again the hard part of this conjecture is to prove that it is $\geq n-2k+2$. This conjecture was proven by Lovász using tools from topology and in particular simplicial complexes, homotopy/homology, and the Borsuk-Ulam theorem, giving birth to the field of topological combinatorics.
For this project, the Bachelor thesis should give a self-contained treatment of the proof of Kneser's conjecture using the topological approach. Other examples of applications of the topological approach can also be given for some other classical classes of graphs.
Colorings of cycles and the mathematics of Fourier and Lovász
If $G$ and $H$ are two graphs, a function $f\colon V(G)\to V(H)$ is called a homomorphism if for every edge $\{v,w\}$ in $G$, we have that $\{f(v),f(w)\}$ is an edge in $H$. Many interesting properties in graph theory can be formulated using homomorphisms. For example, proper colorings of $G$ with $r$ colors correspond exactly to homomorphisms from $G$ to $K_r$, the complete graph on $r$ vertices. Thus, the chromatic number of a graph $G$ is the smallest $r$ such that there exists a homomorphism $G\to K_r$.
For some applications in computer science, one is interested in understanding all the homomorphisms $(C_{n})^k \to K_r$, i.e., all proper colorings of $(C_n)^k$ with $r$ colors. Here, $C_{n}$ denotes a cycle with $n$ vertices, and $(C_n)^k$ is the direct $k$th power of $C_n$, whose vertices are tuples $(v_1,\dots,v_k)$ of vertices of $C_n$, and where $\{(v_1,\dots,v_k),(w_1,\dots,w_k)\}$ is an edge in $(C_n)^k$ if for all $i\in\{1,\dots,k\}$, $\{v_i,w_i\}$ is an edge in $C_n$. Such homomorphisms $(C_{n})^k \to K_r$ are called polymorphisms of the pair $(C_n,K_r)$.
For this Bachelor project, the goal is to understand such polymorphisms for small values of $n, k,$ and $r$. The study of such homomorphisms can be done using the topological approach mentioned above, or also using a Fourier-theoretic approach that allows for a more analytic approach to the problem. In both cases, the idea is to associate with each polymorphism $f\colon (C_n)^k\to K_r$ a different map $\hat f$ which can be studied by some more ``classical'' mathematical tools:- In the case of the Fourier approach, $\hat f$ is a map $\mathbb Z^k\to\mathbb C^r$, called the Fourier transform of $f$.
- In the case of the Lovász approach, $\hat f$ is a certain continuous map from the torus $(S^1)^n$ to the sphere $S^{r-2}$.
Chromatic number of graphs and minor conditions
A minor condition is a conjunction of formulas of the form \[ f(x_{i_1},\dots,x_{i_n}) = g(x_{j_1},\dots,x_{j_m})\] in a signature $\tau$ where $f,g$ are operation symbols of some arity $n,m$ and the $x$'s are variables. For example, \[ f(x_1,x_2,x_2) = f(x_2,x_1,x_2) \land f(x_2,x_1,x_2) = f(x_2,x_2,x_1)\] is a minor condition in the signature $\tau=\{f^3\}$ and with two variables. A minor condition is called trivial if there exists a function $\xi\colon\tau\to\mathbb N$ such that $\xi(f)\in\{1,\dots,n\}$ whenever $f$ has arity $n$ and such that, for every equation as the one above, one has $i_{\xi(f)} = j_{\xi(g)}$.
Given a graph $G$ and a minor condition $\Sigma$, there exists a natural construction ("natural" in the sense from category theory) of a new graph $\Sigma(G)$ that has the property that $\Sigma$ is trivial if, and only if, there exists a homomorphism $\Sigma(G)\to G$. In particular, if $\Sigma$ is trivial, then the chromatic number of $\Sigma(G)$ is smaller or equal to the chromatic number of $G$.
The goal of this project is to determine what happens to the chromatic number of the graphs in the sequence $G,\Sigma(G),\Sigma(\Sigma(G)),\dots$ for minor conditions $\Sigma$ that are non-trivial. The conjecture is that this sequence is increasing, or at least unbounded. As a start, one can focus on particular minor conditions from the literature and gain intuition from there. Apart from graph-theoretic methods, the students will have the opportunity to learn and employ methods from topological combinatorics or Ramsey theory.
Constraint satisfaction problems over finite structures
Constraint satisfaction problems are decision problems of the form "Given a set of variables, a set, and constraints over the variables, does there exist a map from the variables to the domain that satisfies all the constraints?"
Such problems are parameterized by the set of constraints that are allowed in the input, called the constraint language.
For constraint languages consisting of relations on a finite set, the complexity of problems has been completely characterized by a celebrated recent result by Bulatov and Zhuk: every CSP is either in P or NP-complete, and the border between the two cases can be characterized algebraically using tools from the theory of universal algebra.
The following contains possible topics for a bachelor or a master thesis on the topic of constraint satisfaction problems and their generalizations.
Goals
The goal of the internship is to develop the existing methods and prove complexity dichotomies for larger classes of constraint languages, in particular in the 3-element case. The tools that will be employed are mathematical in nature, leveraging the theory of universal algebras.- Bachelor: read and write a report on [1] and [2]; compute an example of a structure with 3 elements that is not covered by the result in [2] and investigate the complexity of its CSP.
- Master: read [1] and [2], investigate a complexity dichotomy for the CSPs of all 3-element structures.
References
- Constraint Satisfaction Problems over Finite Structures.
Libor Barto, William DeMeo, Antoine Mottet. - Finite Algebras with Hom-Sets of Polynomial Size.
Libor Barto, Antoine Mottet.
Promise Constraint Satisfaction
A promise CSP is parameterized by two structures $\mathbb A$ and $\mathbb B$ such that there exists a homomorphism from $\mathbb A$ to $\mathbb B$.
The PCSP of the pair $(\mathbb A,\mathbb B)$ takes as input a structure $\mathbb X$ and asks to distinguish between two cases:
- Yes: there exists a homomorphism $\mathbb X\to\mathbb A$
- No: there does not exist a homomorphism $\mathbb X\to\mathbb B$
Note that it cannot be the case that $\mathbb X$ satisfies both Yes and No; and we are promised that it satisfies at least one of them, hence the name. For example the PCSP of the pair $(\mathbb K_3,\mathbb K_{17})$ asks to determine whether a given graph is $3$-colorable, or not even $17$-colorable. The complexity of this problem is unknown! Therefore, no dichotomy like the Bulatov-Zhuk dichotomy is known for PCSPs.
The same algebraic tools used for traditional CSPs can be used for PCSPs, in particular a notion of polymorphism exists that characterize the complexity of the problems.
Goals
Depending on the level of the student, the goal can be one of the following:
- Read some recent articles and write a thesis about the state-of-the-art,
- Study the polymorphisms of templates of the form $(\mathbb C_{2n+1},\mathbb K_4)$ where $n\geq 1$ (the case $(\mathbb C_{2n+1},\mathbb K_3)$ is done in Reference [2]). For this, computer experiments can be performed and methods from machine learning can be used.
References
- An invitation to promise constraint satisfaction.
Andrei Krokhin, Jakub Opršal. - The complexity of 3-coloring $H$-colorable graphs.
Andrei Krokhin, Jakub Opršal. - Algebraic and algorithmic synergies between promise and infinite-domain constraint satisfaction
Antoine Mottet.
Oligomorphic matroids
A matroid is a combinatorial structure that captures two essential notions in mathematics: the concept of linear independence in vector spaces, and the concept of spanning forests in graphs. They enjoy many properties (for example, there exists a duality notion for matroids that allows to define a concept of dual for graphs that are not planar) and have found uses in several different areas of mathematics. Matroids were recently in the news, as June Huh received the Fields medal in 2022 for solving one of the long standing open problems in matroid theory. Most of the time, the matroids are considered to be finite, but it is possible to consider infinite matroids as well (see Reference [1]).
Goals
For this topic, we consider oligomorphic matroids: these are infinite matroids on which a permutation group acts and making the matroid behave essentially like a finite matroid. These matroids have never been studied in the literature, and the task is to start exploring the properties of these matroids and establish their basic theory.
References
- Axioms for infinite matroids.
Henning Bruhn, Reinhard Diestel, Matthias Kriesell, Rudi Pendavingh, Paul Wollan.
Circuit complexity of constraint satisfaction problems
In the references, the circuit complexity of boolean CSPs is considered. The size and depth of (monotone or non-monotone) circuits solving a given CSP is investigated.
Goals
Generalize some of the results to CSPs over domains with more elements.
References
- The Complexity of Satisfiability Problems: Refining Schaefer’s Theorem
Eric Allender, Michael Bauland, Neil Immerman, Henning Schnoor, Heribert Vollmer. - Constant-depth circuits vs. monotone circuits
Bruno Cavalar, Igor Oliveira.
A topological version of Schaefer's theorem (solved)
Reference [1] looks at the topological complexity of the possible solution sets for instances of CSP($\mathbb A$), where $\mathbb A$ is a two-element structures.
With every solution set of an instance $I$, one can associate a cubical complex (like a simplicial complex but where faces are generalizations of squares and cubes).
A semi-algebraic set is a subset of $\mathbb R^d$ that is a union of sets defined by polynomial equalities and inequalities.
The authors prove that Pol($\mathbb A$) is the clone of projections iff for every compact semi-algebraic set $S$, there exists an instance of CSP($\mathbb A$) whose associated cubical complex is homeomorphic to $S$.
Goal
- Bachelor: read [1] and write a report on it with full proofs and prerequisites.
- Master: Generalize the methods from [1] to pp-interpretations, pp-constructions and show that similar results can be obtained for CSPs with more elements.
References
- A topological version of Schaefer's theorem.
Patrick Schnider, Simon Weber.
A minion of graphs (solved)
An $n$-marked graph is a graph $G=(V,E)$ such that $n$ of its vertices are labelled by the numbers $1$ to $n$. Given two $n$-marked graphs $G$ and $H$, one defines $G\oplus H$ to be the graph obtained by taking the disjoint union of the graphs and gluing the vertices according to their labels. If $G$ is $n$-marked and $\sigma\colon\{1,\dots,n\}\to\{1,\dots,m\}$, one can define $G^\sigma$ to be the $m$-marked graph obtained by gluing the vertices of $G$ according to $\sigma$; if some $i\in\{1,\dots,m\}$ is not in the image of $\sigma$, we simply introduce in $G^\sigma$ a vertex labelled $i$ that is not connected to any other vertex. This way, the set of finite marked graphs forms a minion (something behaving similarly to Pol($\mathbb A$)), whose elements of "arity" $n$ are the $n$-marked graphs.
A tree decomposition of a graph $G$ is a tree whose vertices are bags of vertices from $G$ and satisfying certain conditions. The width of the tree decomposition is the maximal size of a bag minus 1, and the treewidth of $G$, denoted by $tw(G)$, is the smallest width of a tree decomposition of $G$. The treewidth of $G$ measures how "tree-like" $G$ is: trees have treewidth 1, while the clique on $n$ vertices has treewidth $n-1$.
Fix a number $k$. For every $n\geq 1$, define an equivalence relation $\sim_n$ on $n$-marked graphs as follows: $\mathbb G\sim_n\mathbb G'$ iff for every $n$-marked graph $\mathbb H$, we have that $tw(G\oplus H)\leq k \Longleftrightarrow tw(G'\oplus H)\leq k$. The relation $\sim_n$ has finitely many equivalence classes, for all $n$.
Goals
Investigate the following questions:
- Is it true that if $G\sim_n H$, and $\sigma\colon\{1,\dots,n\}\to\{1,\dots,m\}$ is an arbitrary function, then $G^\sigma\sim_m H^\sigma$?
- If so, then one can define a minion whose elements of arity $n$ are the equivalence classes of $\sim_n$. Since $\sim_n$ has finitely many equivalence classes, this is a locally finite minion. Investigate the relationship between this minion and other minions known in the theory of PCSPs.