14 problems

Let $H_0$ be a tripartite $3$-graph one of whose parts is a singleton. For every $\varepsilon>0$, there exists $\delta>0$ such that, whenever $H$ is a $3$-partite $3$-graph on part…

Let $G$ be an $n$-vertex $r$-graph, let $s(G;m)$ denote the number of values of $f$ for which $G$ contains $m$ vertices spanning exactly $f$ edges, and let $g_r(m)$ be the threshol…

Let $F$ be a fixed graph and let $\delta_F(\varepsilon)$ be such that every induced $F$-free graph on $n$ vertices contains a set of $\delta_F(\varepsilon)n$ vertices whose edge de…

Let $G$ be a graph, let $H$ be a graph, and let $\rho(H,G)=\operatorname{ind}_H(G)/\abs{G}^{\abs H}$. For every $\varepsilon>0$, consider the parameters $\delta$ and $\kappa$ in Ni…

Let $T$ be a tournament. A nebula is a tournament admitting an ordering whose vertices are partitioned into the vertex sets of stars and singleton components, with no restriction o…

Let $H$ be a tournament. A tournament is $H$-free if it does not contain an induced subtournament isomorphic to $H$, and a transitive subtournament is a subtournament containing no…

Erdős–Hajnal conjecture. There are constants $A$ and $k$ such that

Let $D$ and $H$ be simple, loopless, finite digraphs. A digraph $D$ is $H$-free if it has no induced subgraph isomorphic to $H$, and $4\chi(D)4$ denotes the minimum number of acycl…

Positive EH-coefficient conjecture. Every tournament has a positive EH-coefficient.

Tournament Erdős–Hajnal conjecture. For every tournament $S$, there exists a constant $\delta(S)>0$ such that every $S$-free tournament $T$ satisfies

Self-complementary Erdős–Hajnal conjecture. For every graph $H$, there exists a constant $\epsilon(H)>0$ such that every $\{H,H^c\}$-free graph $G$ has either a clique or a stable…

Narrowness conjecture. For every graph $H$, there exists a constant $\alpha(H)\geq 1$ such that every $H$-free graph $G$ is $\alpha(H)$-narrow.

Perfect-subgraph formulation. For every graph $H$, there exists a constant $\psi(H) > 0$, such that every $H$-free graph $G$ has a perfect induced subgraph with at least…

Let $k$ be a positive integer, let $\chi$ be a fixed coloring of the edges of a complete graph using $k$ colors, and consider $k$-colorings of complete graphs that contain no copy…