Some Problems

Combinatorics and more 2023-03-28

In the previous post, Two Three Four posts ago I wrote about three recent breakthroughs in combinatorics and here I want to mention some problems that I posed over the years that are loosely related to these advances.

Rank of incidence matrices and q-analogs

The goal of finding q-analogs of combinatorial results where, roughly speaking, sets are replaced by subspaces of vector spaces over a field with $q$ elements, is common both in enumerative combinatorics and in extremal combinatorics. A recent breakthrough we discussed by Keevash, Sah, and Sawhney was about the existence of $q$ -analogs of designs (subspace designs).

I will mention a problem (Question 4) in this direction about incidence matrices, following three questions that were largely solved.

Incidence matrices and weighted incidence matrices for sets

The incidence matrix of $k$ -subsets vs. $m$ -subsets of $[n]$ , is a matrix $I_{k,m}(n)$ whose rows correspond to $k$ -subsets $R$ of $[n]$ , whose columns correspond to $m$ -subsets $S$ of $[n]$ , and the entry $I(S,T)$ equals 1 if $R \subset S$ , and equals 0 if $R \not \subset S$ .

A weighted incidence matrix of $k$ -subsets vs. $m$ -subsets of $[n]$ , is a matrix $J_{k,m}(n)$ whose rows correspond to $k$ -subsets $R$ of $[n]$ , whose columns correspond to $m$ -subsets $S$ of $[n]$ , and $J(R,S) \ne 0$ if $R \subset S$ and $J(R,S)=0$ if $R \not \subset S$ .

Question 1: What is the rank $r_p(n,k,m)$ of the incidence matrix of $k$ -subsets vs. $m$ -subsets of $[n]$ , over a field of characteristic $p$ .

This question was beautifully answered by Richard Wilson in 1990 . The problem was posed by Nati Linial and Bruce Rothschild in 1981 and they settled the case $p=2$ . (The answer for $p=2$ , $m=k-1$ , that motivated the question, was observed earlier by Perles and by Frankl.) It is unforgivable that I did not present the statement of Wilson’s theorem here on the blog.

Question 2: What is the minimum rank, denoted by $s_p(n,k,m)$ , of a weighted incidence matrix of $k$ -subsets vs. $m$ -subsets of $[n]$ over a field of characteristic $p$ .

This question was answered by me in the early 80s (it is related also to various results by others around the same time). The answer is ${n-k+m} \choose {m}$ , and remarkably it is independent from the characteristic $p$ .

Incidence matrices and weighted incidence matrices for subspaces

The incidence matrix $I^q=I^q_{k,m}(n)$ of $k$ -dimensional subspaces vs. $m$ -dimensional subspaces of $F_q^n$ ( $k<m)$ has entries $I_{V,U}=1$ if $V \subset U$ and $I_{V,U}=0$ if $V \not \subset U$ .

A weighted incidence matrix $J^q=J^q_{k,m}(n)$ of $k$ -dimensional subspaces vs. $m$ -dimensional subspaces of $F_q^n$ ( $k<m$ ) has entries $J_{V,U}\ne 0$ if $V \subset U$ and $J_{V,U}=0$ if $V \not \subset U$ .

We pose two additional questions which are the “q-analogs” of Questions 1 and 2.

Question 3: What is the rank $r_q^p(n,k,m)$ of the incidence matrix $I^q_{k,m}(n)$ over a field of characteristic $p$ (you can simply take the field $F_p$ ).

Frumkin and Yakir settled problem 3 when $q$ is not a power of $p$ .

The problem I want to pose (again) here is:

Question 4: What is the minimum rank denoted by $s_q^p(n,k,m)$ of a weighted incidence matrix $J^q_{k,m}(n)$ over a field of characteristic $p$ .

In particular, I would like to know if the answer does not depend on $p$ and if it agrees with some easy lower bounds (obtained from certain identity submatrices) like in the case of a field with one element $p=1$ (namely, subsets).

q-trees

Qoestion 5: What are the q-analogs of trees? (and hypertrees).

The basic idea is first to find weights so that the incidence matrix of 1-subspace vs 2-subspaces has rank $q+q^2+\cdots +q^n$ , and then the $q$ -trees will correspond to collection of $q+q^2+\cdots +q^n$ 2-spaces with linearly independent columns. (I don’t expect uniqueness.) This is a little related to a $q$ -analog of the notion of symmetric matroids that I studied in the late 80s.

A year ago Ferdinand Ihringer, Motaz Mokatren and I made some very preliminary steps in this direction before moving on (separately) to other projects. It will be nice to come back to it.

Remark: There is even greater generalities where problems can be extended from set systems (graphs and hypergraphs) to more general algebraic objects. Those could be related to general primitive permutation groups, to association schemes, and to other objects in algebraic combinatorics.

Unit distances and related problems in discrete geometry.

Let $V$ be a normed space. For a set $S \subset V$ the unit distance graph $G(V)$ is the graph whose vertices are points in $V$ and two vertices are adjacent if their distance is one.

We can consider the following quantities

1) $a(V)$ : The maximum size of a unit distance set in $V$ . (In other words, the maximum clique in $G(V)$ .)

2) $\chi(V)$ : The number of colors needed for $V$ if two points of unit distance are colored with different colors.

3) $b(V)$ : The maximum number of colors needed to color points in a set $S$ of diameter 1 if every color set has diameter smaller than 1. (This is the Borsuk number of $V$ .)

4) $b_f(V)$ The maximum number of colors needed to color points in a finite set $S$ of diameter 1 if two points of unit distance are colored with different colors.

5) $kiss(V)$ The maximum number of points of norm 1 with pairwise distances at least 1.

6) The maximum over all sets $S$ with points of pairwise distance at least one, of the minimum degree in the unit distance graph $G(S)$ .

7) The maximum over all sets $S$ with points of pairwise distance at least one of the chromatic number of the unit distance graph of $S$ .

Estimating these seven quantities for Euclidean spaces and for other normed spaces are well-known problems. (See my survey article on problems around Borsuk’s problem.) Alon, Bucić, and Sauermann made a remarkable breakthrough on the first problem of the largest clique in a unit distance graphs for arbitrary normed spaces.

Jordan Ellenberg asked: “Does the Alon-Bucic-Sauermann result give you upper bounds for the chromatic number of (the unit distance graph of) $R^d$ with a typical norm? (Or is that already easy for some reason?) “. But I know little about Jordan’s question.

There is much to say about them but I will not discuss these problems here. I will mention a single annoying problem.

Question 6: Is there an example of a normed space $V$ such that $b(V) \ne b_f(V)$ ?

(I am not even sure if for the seventh item it makes a difference to consider finite $S$ .)

Intersection patterns of standard boxes

In the post that I mentioned we also discussed Tomon’s remarkable result on intersection patterns of standard boxes. Here is some loosely related problem. In short, we want to find topological analogs for results on intersection patterns of standard boxes.

Topological Helly-type theorems is an important direction in geometric and topological combinatorics. The idea is to prove Helly type theorems about convex sets in a much wider topological contexts.

A primary goal of Topological Helly-type theorems is to extend results for nerves of families of convex sets in $\mathbb R^d$ to the class of $d$ -Leray simplcial complexes. Among the results achieved so far are: The upper bound theorem; Eckhoff’s conjecture; Alon and Kleitman’s (p,q)-theorem; colorful and matroidal Helly’s theorem; topological Amenta’s theorem, and more.

Another goal of Topological Helly-type theorems is to study if results on nerves of standard boxes can be extended to flag $d$ -Leray simplicial complexes?

In this direction the immediate goal is to extend Eckhoff’s upper bound theorem. (Item 3 in this post.)

Question 7. Conjecture: Let $K$ be a $d$ Leray flag complex of dimension $d$ with $n$ vertices. Then the $f$ -vector of $K$ obeys Eckhoff’s upper bound theorem for standard boxes.

A closely related question is

Question 8. Conjecture: Let $K$ be a $d$ -Leray flag complex of dimension $m$ , then the $f$ -vector of $K$ is the $f$ -vector of a completely balanced $m$ -dimensional $d$ -Leray complex.

Studying the equality cases of the conjecture is also of interest and the extremal complexes can also be regarded as some sort of ultra-trees.

roy_meshulam

Roy Meshulam and I worked together on topological Helly type theorems for more than two decades.