Turan, Paul


Turán's problem for hypergraphs ★★

Author(s): Turan

\begin{conjecture} Every simple $3$-uniform hypergraph on $3n$ vertices which contains no complete $3$-uniform hypergraph on four vertices has at most $\frac12 n^2(5n-3)$ hyperedges. \end{conjecture}

\begin{conjecture} Every simple $3$-uniform hypergraph on $2n$ vertices which contains no complete $3$-uniform hypergraph on five vertices has at most $n^2(n-1)$ hyperedges. \end{conjecture}

Keywords:

The Erdos-Turan conjecture on additive bases ★★★★

Author(s): Erdos; Turan

Let $B \subseteq {\mathbb N}$. The \emph{representation function} $r_B : {\mathbb N} \rightarrow {\mathbb N}$ for $B$ is given by the rule $r_B(k) = \#\{ (i,j) \in B \times B : i + j = k \}$. We call $B$ an \emph{additive basis} if $r_B$ is never $0$.

\begin{conjecture} If $B$ is an additive basis, then $r_B$ is unbounded. \end{conjecture}

Keywords: additive basis; representation function

The Crossing Number of the Complete Bipartite Graph ★★★

Author(s): Turan

The crossing number $cr(G)$ of $G$ is the minimum number of crossings in all drawings of $G$ in the plane.

\begin{conjecture} $\displaystyle cr(K_{m,n}) = \floor{\frac m2} \floor{\frac {m-1}2} \floor{\frac n2} \floor{\frac {n-1}2} $ \end{conjecture}

Keywords: complete bipartite graph; crossing number

Syndicate content