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 runiform 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:

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

 

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s