27 problems

For integers $r\ge 1$ and real numbers $n\ge 1$, $0<\eta\le 1/2$, define … Here $a_i,b_j\sim n$ denotes the same dyadic range as in the source, and $\lVert\cdot\rVert$ is distance…

Let $\mathcal{M}=(E,\mathcal{I})$ be a matroid whose ground set $E$ can be partitioned into $k$ disjoint bases, and let $S_1,S_2,\ldots,S_\ell$ be pairwise disjoint subsets of $E$.…

Mohr–Pardey–Rautenbach's conjecture. Fix integers $k,n\geq 1$ such that $\binom{n}{2}$ and $(k-1)n/k$ are both even integers. If $\mathbf{c}:E(K_n)\to\{-1,1\}$ is a 0-sum labeling…

Mohr–Pardey–Rautenbach conjecture. There exists a copy $F'$ of $F$ in $K_n$ such that

Far-from-Turán discrepancy conjecture. For every $\varepsilon>0$, there exists $c>0$ such that, if $G$ is an $n$-vertex graph that is $\varepsilon$-far from every Turán graph, incl…

Verstraete's conjecture.

Let $T$ be a tree with $\ell$ leaves, let $\mathcal{T}$ denote the family of trees used in the discrepancy definition, and let $\mathcal{D}^1(T,\mathcal{T})$ denote the one-dimensi…

Let $T$ be a tree with $\ell$ leaves, and let $\mathcal{DT}$ be the set of all directed rooted trees, namely trees with a distinguished root and all edges oriented away from it. Wr…

Let $\mathcal{L}={R(x,y,z)}$ be the language of ternary $3$-graph relations, and let $\text{XOP}_2$ be a proposed definition given by an infinite scheme of existential sentences. X…

Hereditary-discrepancy characterization. A monotone class $\mathscr{C}$ is nowhere dense if and only if, for every partitioned formula $\varphi(\bar{x};\bar{y})$, every…

Let $A$ be drawn from the $(m,n,1/2)$-Bernoulli ensemble, where $C$ is a universal constant and $n\geq C m\log m$. Computational hardness conjecture. With high probability, no effi…

Linear discrepancy conjecture. For every $C>0$, there is an integer $N$ such that, whenever $n\geq N$, every non-diagonal $n\times n$ matrix $M$ with entries in $\{-1,1\}$ and

Let $q\geq 1$, and let $st enmathbb{R}$ and $vtinmathbb{R}^m$ for $tin [w]$ satisfy … for every $x\in\mathbb{R}^m$. Positivity-induced triangle inequality. For all…

Let $\mathbf W^r_{\infty,\alpha}$ be the weighted Sobolev-type function class, and let $\kappa_m(\mathbf W^r_{\infty,\alpha})$ denote the minimal cubature error over formulas with…

Let $\mathbf W^r_{1,\alpha}$ be the weighted Sobolev-type function class, and let $\kappa_m(\mathbf W^r_{1,\alpha})$ denote the minimal cubature error over formulas with $m$ knots.…

For a point set $\xi$ with $m$ points in the $d$-dimensional domain and arbitrary weights, let $\widetilde D^{r,o}_{\mathbf p}(m,d)$ denote the infimum of the smooth…

For a point set $\xi$ with $m$ points in the $d$-dimensional domain and arbitrary weights, let $D^{r,o}_\infty(m,d)$ be the infimum of the $r$-discrepancy over all such point-weigh…

Let $m$ points be chosen in $[0,1)^d$, and let $D(m,d)_\infty$ denote the infimum of their $L_\infty$ discrepancy. Star-discrepancy lower-bound conjecture. For $d\ge 3$, … This is…

Let $D_q^r(\xi,\Lambda)$ be the $r$-discrepancy of a point set $\xi$ with weights $\Lambda$, and define … Here $m$ is the number of points, $d$ is the dimension, and $C(r,d)>0$ dep…

Let $D(m,d)_\infty$ denote the minimal $L_\infty$ discrepancy of an $m$-point set in dimension $d$, and let $C(d)>0$ depend only on $d$. Discrepancy lower-bound conjecture. For…

Linial–Luria's conjecture. There exist arbitrarily large Latin squares $L$ such that, for every box $T=I\times X\times Q$,

Let $D_r^w(m,d)_\infty$ denote the minimal weighted $r$-discrepancy in dimension $d$, where $m$ is the number of nodes. Weighted higher-order discrepancy lower-bound conjecture. Fo…

For a $d$-dimensional permutation $A$, let $\mathcal T\subseteq[n]^{d+1}$ be a box and write $A(\mathcal T)$ for the number of $1$-entries of $A$ in it. An empty box is a box with…

High-dimensional permutation discrepancy conjecture. For every $d\geq2$ there exist arbitrarily large $d$-dimensional permutations $A$ such that, for every box $\mathcal T$,

Discrepancy asymptotic constant conjecture. There is some constant $C$ such that