← All problems

Pach–Tardos conjecture for ordered uniform forests

8 years old · documented by

An ordered rr-uniform forest is an rr-uniform hypergraph whose vertex set is linearly ordered and whose edges admit an ordering e1,e2,…,ete_1,e_2,\ldots,e_t such that, for every i∈{2,3,…,t}i\in\{2,3,\ldots,t\}, there is an h<ih<i with

ei∩⋃j<iej⊆eh.e_i\cap\bigcup_{j<i}e_j\subseteq e_h.

The interval chromatic number of an ordered hypergraph is the least number of consecutive intervals in the vertex ordering whose union gives a proper coloring. Let ex→(n,F){\rm ex}_{\rightarrow}(n,F) denote the maximum number of edges in an nn-vertex ordered rr-uniform hypergraph containing no ordered copy of FF.

Pach–Tardos conjecture for ordered forests. Let r≥2r\geq 2. Then for any ordered rr-uniform forest FF with interval chromatic number rr,

ex→(n,F)=O(nr−1⋅polylog⁡n).{\rm ex}_{\rightarrow}(n,F)=O\bigl(n^{r-1}\cdot\operatorname{polylog} n\bigr).

This extends the graph conjecture of Pach and Tardos to uniform hypergraphs. The source notes that the corresponding polynomial bound without the polylogarithmic factor is elementary for rr-uniform forests, but gives no resolution of the strengthened conjecture.

References

3 papers in this index state this conjecture (2017–2019). The statement above is taken from the most recent of them; the others are arXiv:1807.05104, arXiv:1711.07723.

Source: Zoltán Füredi, Tao Jiang, Alexandr Kostochka, Dhruv Mubayi and Jacques Verstraëte, “Extremal problems for convex geometric hypergraphs and ordered hypergraphs”, arXiv:1906.04575 (2019).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.