Erdős Problems

Tags Prizes

1 solved out of 3 shown (show only solved or open)

OPEN - $100

We say $H$ is a unique subgraph of $G$ if there is exactly one way to find $H$ as a subgraph (not necessarily induced) of $G$. Is there a graph on $n$ vertices with \[\gg \frac{2^{\binom{n}{2}}}{n!}\] many distinct unique subgraphs?

#426: [Er76b]

graph theory

A problem of Erdős and Entringer [EnEr72], who constructed a graph with \[\gg 2^{\binom{n}{2}-O(n^{3/2+o(1)})}\] many unique subgraphs. This was improved by Harary and Schwenk [HaSc73] and then by Brouwer [Br75], who constructed a graph with \[\gg \frac{2^{\binom{n}{2}-O(n)}}{n!}\] many unique subgraphs.

Note that there are $\sim 2^{\binom{n}{2}}/n!$ many non-isomorphic graphs on $n$ vertices (folklore, often attributed to Pólya), and hence the bound in the problem statement is trivially best possible.

Erdős believed Brouwer's construction was essentially best possible, but Spencer suggested that $\gg \frac{2^{\binom{n}{2}}}{n!}$ may be possible. Erdős offered \$100 for a construction and \$25 for a proof that no such construction is possible.

OPEN

What is the maximum number of edges that a graph on $n$ vertices can have if it does not contain two edge-disjoint cycles with the same vertex set?

#585: [Er76b]

graph theory, cycles

Pyber, Rödl, and Szemerédi [PRS95] constructed such a graph with $\gg n\log\log n$ edges.

Chakraborti, Janzer, Methuku, and Montgomery [CJMM24] have shown that such a graph can have at most $n(\log n)^{O(1)}$ many edges. Indeed, they prove that there exists a constant $C>0$ such that for any $k\geq 2$ there is a $c_k$ such that if a graph has $n$ vertices and at least $c_kn(\log n)^{C}$ many edges then it contains $k$ pairwise edge-disjoint cycles with the same vertex set.

SOLVED - $250

Let $r\geq 1$ and define $T(n,r)$ to be maximal such that there exists a family $\mathcal{F}$ of subsets of $\{1,\ldots,n\}$ of size $T(n,r)$ such that $\lvert A\cap B\rvert\neq r$ for all $A,B\in \mathcal{F}$.

Estimate $T(n,r)$ for $r\geq 2$. In particular, is it true that for every $\epsilon>0$ there exists $\delta>0$ such that for all $\epsilon n<r<(1/2-\epsilon) n$ we have \[T(n,r)<(2-\delta)^n?\]

#703: [Er76b][Er81]

combinatorics

It is trivial that $T(n,0)=2^{n-1}$. Frankl and Füredi [FrFu84] proved that, for fixed $r$ and $n$ sufficiently large in terms of $r$, the maximal $T(n,r)$ is achieved by taking \[\mathcal{F} = \left\{ A\subseteq \{1,\ldots,n\} : \lvert A\rvert> \frac{n+r}{2}\textrm{ or }\lvert A\rvert < r\right\}\] when $n+r$ is odd, and \[\mathcal{F} = \left\{ A\subseteq \{1,\ldots,n\} : \lvert A\backslash \{1\}\rvert\geq \frac{n+r}{2}\textrm{ or }\lvert A\rvert < r\right\}\] when $n+r$ is even. (Frankl [Fr77b] had earlier proved this for $r=1$ and all $n$.)

An affirmative answer to the second question implies that the chromatic number of the unit distance graph in $\mathbb{R}^n$ (with two points joined by an edge if the distance between them is $1$) grows exponentially in $n$, which was proved by alternative methods by Frankl and Wilson [FrWi81] - see [704].

The answer to the second question is yes, proved by Frankl and Rödl [FrRo87].