Hypergraph complexity

There are occasional, serendipitous events that make one suspect that there may be some benevolent animating power behind the universe. (This only lasts until the next annoying thing happens.) In August 2017, I was leaving San Francisco for Calgary after attending a workshop at AIM. On the flight, across the aisle from me, I saw someone editing what was clearly some mathematical papers. I introduced myself, and the other party turned out to be none other than Jacob Fox, on his way to a meeting in Banff. After parting ways, I started to look at some of his papers, and one immediately caught my eye, namely A relative Szemerédi theorem (with Conlon and Zhao). I had a problem that I’ve been working (and been stuck) on for a while, and this paper gave me a crucial theorem I needed to continue.

This paper also introduced me to the idea of hypergraph complexity, which I don’t yet understand, hence this post. We’ll start with some basic definitions and concepts.

Definition 1. Let $J$ be a set and for $H \subseteq J$ , let $\binom {J}{r}$ denote the set of all $r$ -element subsets of $J$ . An $r$ –uniform hypergraph on $J$ is any subset of $H$ .

It should be clear that this just generalises the notion of an edge as a choice or two elements, to a choice of an arbitrary (but constant) number of elements. Hypergraphs give us some nice generalisations of Ramsey-type results, for example,

Theorem 1. [2] An infinite $m$ -regular hypergraph contains an infinite clique or an infinite anticlique.

The nonstandard proof of this (which can be found in [2]) involves a beautiful use of iterated nonstandard extensions, a somewhat tricky (but very useful) subject I will probably address in a later post.

In what follows, we restrict our attention to finite hypergraphs. We firstly need to define a hypergraph system:

Definition 2. [1] A hypergraph system is a quadruple $V = (J, (V_j )_{j\in J}, r, H)$ where $J$ is a finite set, $(V_j )_{j\in J}$ is a collection of non-empty sets, $r\geq 1$ is a positive integer, and $H \subseteq \binom{J}{r}$ is an $r$ -uniform hypergraph. For any $e\subseteq J$ , set $V_e := \prod_{j\in e} V_j$ .

What would be a reasonable hypergraph system, and what would it be good for? Since the concept occurs in a paper concern a Szemerédi-type theorem, it seems reasonable that they have something to do with arithmetic progressions. To make this clear, we’ll need the notion of a weighted hypergraph, which we’ll illustrate by means of an example. Set $J = \{ 1,2,3\}$ , $r=2$ , and $V_j = \mathbb{Z}_N$ . The weights on $V$ are functions $g_e : V_e \to \mathbb{R}^{\geq 0}$ . For instance, for the edge $(1,2)$ we have a function $g_{(1,2)}: \mathbb{Z}_N \times \mathbb{Z}_N \to \mathbb{R}^{\geq 0}$ . Suppose that $A \subseteq \mathbb{Z}_N$ , and let $\chi_A$ denote its indicator function. We define the functions

$g_{1,2}(x,y) = \chi_A (x-y)$

$g_{2,3}(x,y) = \chi_A (x+y)$

$g_{1,3}(x,y) = \chi_A (x).$

The product $g_{1,2}(x,y) g_{2,3}(x,y) g_{1,3}(x,y)$ will only be greater than $0$ if there are some $x,y \in \mathbb{Z}_N$ such that $x-y, x, x+y$ are in $A$ . Equivalently, if

$\mathbb{E}_{x,y \in \mathbb{Z}_N} g_{1,2}(x,y) g_{2,3}(x,y) g_{1,3}(x,y) >0,$

$A$ will contain a 3-arithmetic progression.

This is a simplistic example, and not nearly sufficient to characterise the existence of 3APs. For instance, we make no mention of the issue of wrap-around progressions in the cyclic group $\mathbb{Z}_N$ . What is more, one would ideally like to have a result which takes into account values of $N$ of arbitrary size. For appropriate linear forms conditions that work for any size of AP, the paper [1] should be consulted. For now, we continue with trying to get a handle on the complexity.

Suppose we are given a hypergraph system as above.

Definition 3. [1] For any set $e$ of size $r$ and any $E_e \subseteq V_e = \prod_{j\in e} V_j$ , define the complexity of $E_e$ to be the smallest integer $T$ such that there is a partition of $E_e$ into $T$ sets $E_{e,1}, \dots ,E_{e,T}$ such that each $E_{e,i}$ is the set of $r$ -cliques of some $(r-1)$ -uniform hypergraph.

Thus, in the above example we would let $E_e$ be a subset of $\mathbb{Z}_N \times \mathbb{Z}_N$ for some $e \in H$ . Certainly, an $(r-1)$ -uniform hypergraph for $r=2$ is not the most scintillating mathematical object, but let us persist with this simple case.

To make sense of the latter part of the Definition 3, let us first discuss what the required cliques are (following [1]). If $x = (x_j)_{j\in J} \in V_j$ and $J' \subseteq J$ , write $x_{J'} = (x_j)_{j\in J'} \in V_{J'}$ for the obvious projection of $x$ onto the coordinates $J'$ . For any $e\subseteq J$ , define

$\partial e = \{ f\subseteq e: |f| = |e|-1.\}$

In a 2-uniform hypergraph as above, for $e = (1,2)$ , $\partial e = \{1,2\}$ . Simply put, the boundary is seen as the set of edges of one dimension less that together uniquely determine the edge we are looking at.

If we now say that $E_{e,i}$ is the set of $(r-1)$ -cliques of some $r$ -uniform hypergraph, we mean that there is some $B_{f,i} \subseteq V_f$ for each $f\in \partial e$ so that

$\chi_{E_{e,i}} (x_e) = \prod_{f\in \partial e} \chi_{B_{f,i}}(x_f)$

for all $x_e \in V_e$ .

To be fair, this does not make anything very clear, so let’s unpack this notion further with our very simple example of a (complete) 2-uniform hypergraph, by trying to understand what a satisfying notion of complexity should be. Taking the edge $\{ 1,2\}$ as before, and $V_1 = V_2 = \mathbb{N}\times \mathbb{N}$ . Let the set $V_e = \{1,2,\dots ,20 \} \times \{1,3,5, \dots ,19\}$ . We want sets $E_{e,i}$ and $B_{1,i} , B_{2,i} \subseteq \mathbb{N}$ so that

$\chi_{E_{e,i}} (x_e) = \chi_{B_{1,i}}(x_1) \times \chi_{B_{2,i}}(x_2)$

for all $x_e \in V_{\{ 1,2\} }$ . The triviality of this example now becomes obvious – setting $B_{1,1} = \{1,2,\dots ,20\}$ and $B_{2,1} = \{1,3,\dots ,19\}$ gives us a complexity of 1. We could see this example as an instance of a complete bipartite graph between the components making up $V_e$ , which is fully described by the Cartesian product of the two sets.

Let’s see if the same reasoning applies to 3-uniform hypergraphs. Let $e = \{ 1,2,3\}$ be an edge in some 3-uniform hypergraph, with the associated set $V_e = \mathbb{N}\times \mathbb{N} \times \mathbb{N}$ . Let the subset $E_e$ be $\{1,2,\dots ,10\} \times \{1,3,5,7 ,9\} \times \{2,4,6,8\}.$ Now we need sets $E_{e ,1}, \dots , E_{e, T}$ and subsets $B_{f_1 ,i}, B_{f_2, i}, B_{f_3, i}$ of $V_{f_1 }, V_{f_2 }, V_{f_3 } = \mathbb{N}\times \mathbb{N}$ such that

$\chi_{E_{e,i}} (x_e) = \chi_{B_{f_1,i}}(x_1) \times \chi_{B_{2,i}}(x_2)\times \chi_{B_{f_3,i}}(x_3).$

A little consideration will show that the same trick employed above works here as well, because our set $V_e$ can be considered to be a complete 3-uniform tripartite graph on the parts $V_1, V_2, V_3$ . It seems clear that we will need to be slightly more creative in order to get higher complexity.

Consider now the following subset of the above set $V_e$ :

$E_e =\{ (1,3,2), (1,3,4), (2,5,7), (2, 5, 9), (4,7,6), (3,7,6), (3,7,5), (4, 7,5), (10, 9, 8), (10,9,1)\}.$

This set can’t be written as a single Cartesian product of subsets of the sets we are considering, and seems slightly more random in character, so there is a hope that the complexity should be higher. Setting $f_1 = (1,2)$ , $f_2 = (2,3)$ and $f_3 = (1,2)$ , we take

$B_{1,1} = \{(1,3)\}, B_{2,1} = \{ (3,2), (3,4) \} , B_{3,1} = \{(1,2), (1,4)\}$

$B_{1,2} = \{(2,5)\}, B_{2,2} = \{ (5,7), (5,9) \} , B_{3,2} = \{(2,7), (2,9)\}$

$B_{1,3} = \{(3,7), (4,7)\}, B_{2,3} = \{ (7,5), (7,6) \} , B_{3,3} = \{(3,5), (3,6), (4,5),(4,6)\}$

$B_{1,4} = \{(10,9)\}, B_{2,4} = \{ (9,1), (9,8) \} , B_{3,4} = \{(10,1), (10,8)\}$

(where the notation has been shortened in an obvious way). To avoid confusion, we note that there are elements $x,y,z \in B_{1,i}, B_{2,i}, B_{3,i}$ such that $\chi_{B_{1,i}}(x)\chi_{B_{2,i}}(y)\chi_{B_{3,i}}(z) = 1$ , but which do not correspond to projections of an edge in $V_e$ , and can therefore be ignored. We thus see that our set $E_e$ has a complexity of at most 4.

Of course, the case of a 3-uniform hypergraph is quite easy to analyse this way, because two of the edges determine the third, and the difficulty of generating such examples will increase rapidly for higher $r$ .

Intuitively, the example at least makes clear that the complexity of the hypergraph is somehow determined by how easily the set $V_e$ can be described in terms of parts of a smaller “dimension”, and that highly random sets will have higher complexity (without specifying exactly what we mean by “random” here). The real application of this complexity is in hypergraph removal lemmas, which we’ll (possibly) discuss in another post.

Shameless self-promotion: If you enjoy Fourier series and Martin-Löf randomness (or Kolmogorov-Chaitin-Solomonoff randomness – take your pick), see my paper in APAL. For something similar, involving Carleson’s theorem and Schnorr randomness, see the paper by Franklin, McNicholl and Rute at https://arxiv.org/abs/1603.01778.

References:

A relative Szemerédi theorem, David Conlon, Jacob Fox and Yufei Zhao
Nonstandard Methods in Ramsey Theory and Combinatorial Number Theory, M Di Nasso, I Goldbring and M Lupini

Trying to be a mathematician

Mathematics, optimisation and such

Hypergraph complexity

Leave a Reply Cancel reply

Share this:

Like this:

Related

Leave a Reply Cancel reply