18 problems

Let a graph or digraph property be monotone if it is preserved under deletion of edges or arcs, and let a property be non-trivial if it is neither always true nor always false. A p…

Yao–Karp conjecture. The same lower bound holds for randomized decision tree complexity:

Universal property conjecture. There exists a natural number $\ell$ such that every maximal triangle-free graph satisfying $\mathcal{D}_\ell$ has property $\mathcal{D}_k$ for every…

Separation conjecture for $\mathcal{D}_3$ and $\mathcal{D}_4$. There is a finite maximal triangle-free graph $G$ satisfying $\mathcal{D}_3$ but not $\mathcal{D}_4$.

A graph property is called global when its behavior is governed by the graph as a whole, and local when it is governed by bounded or otherwise localized substructures. A $d$-depend…

Let $G_{n,p,d}$ denote the class of $d$-dependent random graph distributions on graphs with $n$ vertices and marginal edge probability $p$. Let $\mathcal{P}$ be a monotone graph pr…

Let $G_{n,p,d}$ denote the class of $d$-dependent random graph distributions on graphs with $n$ vertices and marginal edge probability $p$. Let $d4ab$ be a monotone graph property,…

Let $R$ be a non-trivial graph property on a finite vertex set $V$. In the associated query game, a seeker asks whether individual edges belong to the graph, and the game ends when…

Let $R$ be a graph property and let $V$ be a finite vertex set. The property $R$ is monotone if it remains true when edges are added, and it is elusive on $V$ if the hider has a st…

Finite-forbidden-subgraph conjecture. The class $X_M$ is at most factorial if and only if $M$ contains a forest and the bipartite complement of a forest.

Forest boundary conjecture. For any tree $T$, the class of $\{T,\overline{T^b}\}$-free bipartite graphs is at most factorial.

Factorial characterization conjecture. A hereditary graph property $X$ is factorial if and only if the fastest of these three subclasses is factorial.

A hereditary graph property $X$ is a class of graphs closed under taking induced subgraphs. A graph property is factorial when the number of labelled graphs in the property on $n$…

Let $([n],A)$ be a digraph, and let $c(\mathcal{F})$ denote the argument complexity of a digraph property $\mathcal{F}$ on $n$ vertices. A property is non-trivial when it is neithe…

Let $f$ be a monotone graph property on graphs with $n$ vertices, and consider its bounded-error quantum query complexity, the minimum number of quantum oracle queries required by…

Let $f$ be a monotone graph property on graphs with $n$ vertices, and let $R(f)$ denote its randomized decision-tree complexity: the minimum, over randomized algorithms, of the max…

Let $f$ be a monotone graph property on graphs with $n$ vertices, and let $D(f)$ denote its deterministic decision-tree complexity, namely the minimum worst-case number of edge que…

Let ${\mathcal P}$ be a natural graph property, and consider the random graph model $G(n,p)$ with $p$ sufficiently large. A graph property has unbounded local resilience if the amo…