Erdos 1997 some recent problems results graph theory

../

problem_10: Erdős's item 10, the statement that with Rousseau and Schelp he proved that a two-coloring of the edges of the complete graph on n vertices leaves at most n squared over four edges on no monochromatic triangle for large n; the unpublished result Problem 639 records, printed without proof.

problem_14: Erdős's item 14, the Erdős–Faudree–Ordman question whether every two-coloring of the edges of the complete graph on n vertices has (1+o(1)) n squared over twelve edge-disjoint monochromatic triangles, with the one-color question and the expectation (1+ε) n squared over 24; the origin wording of Problem 76.

problem_9: Erdős's item 9, the question whether a family of finite graphs forcing a monochromatic triangle under every finite number of colors must, for every infinite cardinal, contain the finite subgraphs of a graph forcing one under that many colors; the original wording of Problem 638.

---

Paul Erdős, Some recent problems and results in graph theory, Discrete Mathematics 164 (1997), 81--85, PII S0012-365X(96)00044-1, DOI 10.1016/S0012-365X(96)00044-1; received 21 September 1995; the author at the Hungarian Academy of Sciences, Mathematical Inst., Budapest (head of p. 81). The issue is a conference volume (the paper speaks of "the meeting held last year in Keszthely" and "the trip to our meeting"). Cited as [Er97d] on the problem pages, the site's key. Its one reference (p. 85) is Erdős, Fon-Der-Flaass, Kostochka and Tuza, Small transversals in uniform hypergraphs, Siberian Adv. Math. 2 (1992), 82--88, not filed in the library.

The copy read for this card is the publisher's scan of the printed article: 5 pages, printed pp. 81--85 = PDF pp. 1--5 (printed p. $n$ is PDF p. $n-80$), a 2003 scan (the scan's metadata names an Acrobat 3.0 Capture plug-in and a January 2003 creation date) with an OCR text layer that locates passages and garbles names ("Erd6s", "Lowisz", "Bollob~is"), the $\Delta$ of item 2, subscripts, superscripts, inequality signs and every display. Provenance: the copy was obtained on 2026-09-22 from the publisher's platform through the library's acquisition, free of charge, the DOI https://doi.org/10.1016/S0012-365X(96)00044-1 resolving to the article's PDF; 256,072 bytes. The scan prints "0012-365X/97/$17.00 © 1997 Published by Elsevier Science B.V. All rights reserved" in the footer of its first page, every other right reserved.

Read status: all five pages were read on the page images. Claims checked for items 1 (p. 81), 6, 7 and 8 (p. 83), 9 (pp. 83--84), 10, 11 and 14 (p. 84), each read clause by clause on the page images, and 16 (p. 85), read clause by clause on the page image; items 2--5, 12, 13, 15 were read on the page images for identification. The paper proves nothing: the results it reports (Kahn's, Spencer's, Abbott and Hanson's, Kostochka's, Axenovich, Fon-Der-Flaass and Kostochka's, Flandrin, Jackson, Lesniak and Schelp's, Rousseau and Schelp's, Bollobás, Chen and Erdős's, Füredi's, and the transversal values of [1]) are stated without proof, and only [1] carries a reference. Nothing here is independently reviewed.

Contents

The opening (p. 81) announces two of Erdős's favorite problems on which important progress had recently been made and says that the remaining questions are probably less well known. The items are numbered 1 to 16 without a heading word; the later literature calls them "Problem 10", "Problem 14".

• Item 1 (p. 81, page image): the Erdős--Faber--Lovász conjecture, made with Faber and Lovász more than twenty years earlier, quoted as posed: "if $G_i$, $1\le i\le n$ are $n$ edge disjoint complete graphs of size $n$ then $\bigcup_{i=1}^nG_i$ has chromatic number $n$." Erdős records that the conjecture proved hard, that he had long offered a prize for a proof or disproof, and that about three years earlier Jeff Kahn had shown the chromatic number of $\bigcup_{i=1}^nG_i$ to be at most $n(1+o(1))$, earning a consolation prize and the hope that he would eventually reach $n$. Two variants are asked: how large the chromatic number of $\bigcup_{i=1}^nG_i$ can be when every $G_i\cap G_j$ is triangle-free, or when every $G_i\cap G_j$ has at most one edge.
• Item 2 (pp. 81--82): strong and weak $\Delta$-systems (sunflowers); $g_r^{(s)}(n)$ and $g_r^{(w)}(n)$; Erdős and Rado's $2^n<g_3^{(s)}(n)<2^nn!$; the conjecture $g_r^{(s)}(n)<C_r^n$ (1) with a prize offered for $r=3$; Spencer's $g_3^{(s)}(n)<(1+\varepsilon)^nn!$; Abbott and Hanson's $g_3^{(s)}(n)>10^{n/2}$; Kostochka's $g_3^{(s)}(n)<C_3^nn!/(\log\log n/\log\log\log n)^n$ (2), rewarded with a consolation prize; Axenovich, Fon-Der-Flaass and Kostochka's $g_3^{(w)}(n)<n!^{(1/2)+\varepsilon}$ (3); the infinite $\Delta$-system papers with Rado and Milner.
• Item 3 (p. 82): if every $m$-vertex subgraph of $G(n)$ has an independent set of size at least $\lfloor m/2\rfloor-k$, is $V=V_1\cup V_2\cup V_3$ with $V_1$, $V_2$ independent and $|V_3|<f(k)$? Open even for $k=0$; the chromatic number is bounded; the Erdős--Hajnal graphs of infinite chromatic number with independent sets of size $>(m/2)(1-\varepsilon)$ and $>(m/2)-f(m)$ in every $m$-vertex subgraph.
• Item 4 (p. 82): the Erdős--Hajnal--Szemerédi problem: if $f(n)\to\infty$ arbitrarily slowly, is there a graph of infinite chromatic number in which, for every $n$, the subgraph spanned by any $n$ vertices becomes bipartite after deleting fewer than $f(n)$ of its edges? Unproved even for $f(n)=n^\lambda$ with $\lambda$ small; the analogue for chromatic number $m>\aleph_0$ with $nf(n)$, or perhaps $cn$, deletions; and $o(n)$ deletions are known not to be enough, because chromatic number $\ge\aleph_1$ forces $\aleph_1$ pairwise vertex-disjoint odd cycles sharing a single length $2r+1$.
• Item 5 (pp. 82--83): with Faudree, the number $g(n)$ of sequences $3\le a_1<\cdots<a_k\le n$ (4) of cycle lengths occurring in $n$-vertex graphs: $g(n)<2^{n-2}$, $g(n)>2^{n/2}$, "very likely" $g(n)^{1/n}\to c$ (5), and the unproved $g(n)/2^{n/2}\to\infty$, $g(n)/2^n\to0$ (6); Flandrin, Jackson, Lesniak and Schelp's $n^{1/5}$ even lengths when all odd lengths occur.
• Item 6 (p. 83, page image): a graph is called trivial when it is complete or empty (Erdős attributes the term to Bollobás), so that Ramsey's theorem says every $G(n)$ contains a trivial subgraph of size $c\log n$; the exact $c$ is unknown, the printed bounds being $\frac{\log2}2\le c\le2\log2$. Writing $k(n)$ for the largest $k$ such that every $G(n)$ has a trivial subgraph on $k$ vertices, Erdős asserts that no doubt $\frac{k(n)}{\log n}\to c$ (7), and then, quoted: "I offer 100 dollars for a proof and 250 dollars for the value of $c$. I offer 1000 dollars for a disproof of (7), but this is cheating since (7) clearly holds." Then the question with Fajtlowicz and Stanton: if $H(n)$ is the largest $h$ such that every $n$-vertex graph has a regular induced subgraph on $h$ vertices, is $H(n)/\log n\to\infty$ (8)? Bollobás's $H(n)<c\sqrt n$, $H(5)=3$, and "surely" $H(n)-k(n)\to\infty$ (9). A filing observation, not a review verdict: (7) is the inverse form of the Ramsey limit, since if $R(k)^{1/k}\to C$ then $k(n)/\log n\to1/\log C$, and the known $\sqrt2\le C\le4$ gives $1/(2\log2)\le c\le2/\log2$ with natural logarithms ($1/2\le c\le2$ with base $2$); the printed bounds equal the base-$2$ reading, since $\log2=1$ there, and with natural logarithms they are the reciprocals of the correct bounds; they are recorded as printed.
• Item 7 (p. 83, page image): the conjecture with V.T. Sós and Faudree, quoted as posed: "if $G(n)$ is a graph which contains no trivial subgraph of size $c\log n$ then it contains at least $cn^{5/2}$ induced subgraphs $G_1,G_2,\ldots,G_t$, where any two of our $G$'s differ either in the number of vertices or in the number of edges." Their own proof reaches only $cn^{3/2}$, and Erdős adds that $cn^{5/2}$ could not be improved if the conjecture holds. The second conjecture, quoted: "our $G(n)$ has an induced subgraph of size $c_1n$ where the vertices have $c_2n^{1/2}$ different degrees"; an earlier Erdős--Hajnal result guarantees only that the number of distinct degree values grows to infinity with $n$. Both conjectures grew out of a problem of Alon and Bollobás. The first conjecture is the site's Problem 636.
• Item 8 (p. 83, page image), the conjecture quoted as printed: "Brandon, McKay and I conjectured that if $G(n;cn^2)$ has no trivial subgraph of size $>c\log n$ then for every $t<\varepsilon n^2$ our $G$ has an induced subgraph of exactly $t$ edges." Erdős adds, with some annoyance, that they could prove it only for $t<c(\log n)^2$. The comma after "Brandon" is printed; the 1992 Catania paper writes "Brandon Mc Kay", one person.
• Item 9 (pp. 83--84, page images): the infinite-cardinal triangle question, quoted on problem_9.
• Item 10 (p. 84, page image): the Erdős--Rousseau--Schelp statement on edges in no monochromatic triangle, quoted on problem_10.
• Item 11 (p. 84, page image): every $G(n;\lfloor n^2/4\rfloor+1)$ has at least $2n^2/9$ edges lying in an odd cycle, and $2n^2/9$ is best possible; then the conjecture, quoted: "Perhaps there are at least $2n^2/9$ edges which occur in a pentagon." Erdős notes that this would be implied if every $G(n;(n^2/4)+1)$ had a triangle with $(n/2)-O(1)$ vertices each adjacent to two or more of its three vertices. Erdős and Faudree ("Fandree" is printed) observed that in every $G(2n;n^2+1)$ some triangle has at least $n+2$ vertices joined to it, and that $n+2$ is best possible. The first sentence is stated as a result with no attribution or reference; Grzesik, Hu and Volec (arXiv:1605.09055v3, PDF p. 2) and the site's Problem 608 commentary credit it to Erdős, citing this paper; Problem 608 cites Erdős, Faudree and Rousseau's 1992 paper [EFR92], which was not read here, for the triangle count $2\lfloor n/2\rfloor+1$ and the $C_{2k+1}$ conjecture.
• Item 12 (p. 84): the Erdős--Hajnal questions: is there $f(k)$ such that chromatic number $\ge f(k)$ forces an odd cycle whose vertex set spans a subgraph of chromatic number $\ge k$; and does chromatic number $\ge F(r)$ force $r$ edge-disjoint cycles on the same vertex set ("more difficult (and more interesting)").
• Item 13 (p. 84): Bollobás, Chen and Erdős: every $G(n;c_kn)$ contains $k$ edge-disjoint cycles $C_i$ with $V(C_{i+1})\subseteq V(C_i)$; $f(n)$, the least size forcing two edge-disjoint cycles on the same vertex set, has $f(n)/n\to\infty$; Hamburger and Szegedy's question whether some $G(n;cn)$ always contains a cycle with at least as many diagonals as vertices.
• Item 14 (p. 84, page image): the Erdős--Faudree--Ordman edge-disjoint monochromatic triangles question, quoted on problem_14.
• Item 15 (pp. 84--85): with Katona, $f(n;t)$, the least number of $t$-subsets of an $n$-set forcing $A_1,A_2,A_3,A_4$ with $A_1\cap A_2=A_3\cap A_4=\emptyset$ and $A_1\cup A_2=A_3\cup A_4$ (10); $f(n;2)=(\frac12+o(1))n^{3/2}$ (no $C_4$); Füredi's proof of $f(n;3)<cn^2$ (11) and $f(n,3)>\binom n2$ for infinitely many $n$; the conjecture $f(n;3)<\binom n2+1$ with equality infinitely often; Füredi's $f(n;t)<3.5\binom n{t-1}$ and "perhaps $f(n;t)=(1+o(1))\binom n{t-1}$".
• Item 16 (p. 85): from [1], $f(k,r,s)$, the least size of a transversal of a family of $k$-sets every $r$ of which have a transversal of $s$ elements: $f(k,3,2)=2k$, $f(k,4,2)=\lceil3k/2\rceil$, $f(k,5,2)=\lceil5k/4\rceil$ (printed with square brackets, $[3k/2]$ and $[5k/4]$, which the site reads as floors; read here as ceilings because floors fail at $k=3$: all 3-subsets of a 7-set satisfy the condition for $r=4$ and need 5 points, and all 3-subsets of a 6-set satisfy it for $r=5$ and need 4), $f(k,6,2)=k$ ("quite tricky for odd $k$"); the expectations $f(k,7,2)=(1+o(1))\frac34k$ and $f(k,r,2)=(1+o(1))c_rk$; the case $s>2$ is left uninvestigated.

Relation to E642

This source bears on Problem 642.

For E642, a cycle's diagonals are edges of the ambient graph joining nonconsecutive vertices of that cycle, so the cycle Hamburger and Szegedy ask for in item 13 (p. 84), one with at least as many diagonals as vertices, is exactly a cycle forbidden by E642. If $F(n)$ denotes E642's maximum number of edges in an $n$-vertex graph in which every cycle has fewer diagonals than vertices, the question there asks whether $F(n)=O(n)$; equivalently, for $n\ge5$, the first edge count forcing such a cycle is $F(n)+1$.

The nested-cycle theorem of Bollobás, Chen and Erdős reported in item 13, that for each fixed $k$ some $c_k$ makes every $G(n;c_kn)$ contain $k$ edge-disjoint cycles with nested vertex sets, does not supply that bound: containment of one cycle's vertex set in another's need not give enough diagonals. Two edge-disjoint cycles on the same vertex set would suffice, since every edge of one cycle is a diagonal of the other, giving at least as many diagonals as vertices; but item 13 says that forcing such a pair requires a threshold whose ratio to $n$ tends to infinity. The paper collects these attributed results and poses the question: it identifies E642's precise linear-threshold question and a sufficient, stronger configuration, but does not answer it.

Compiled scope

The paper is compiled at statement depth for the items the ten citing problem pages consume: items 1, 6, 7, 8, 9, 10, 11, 14 and 16, read clause by clause on the page images and quoted above or on the result pages for items 9, 10 and 14. The other items are summarized from the page images for identification only. The paper proves nothing, and nothing here is independently reviewed.

Bears on. #19, as the site's source Er97d: item 1 (p. 81) states the Erdős--Faber--Lovász conjecture in the edge-disjoint-cliques form, records the prize offer and Kahn's bound $\le n(1+o(1))$ with its consolation prize, and asks the two variants with $G_i\cap G_j$ triangle-free or of at most one edge. #77, as the site's source Er97d: item 6 (p. 83) states the Ramsey limit in the inverse form (7), $k(n)/\log n\to c$ for the largest trivial subgraph every $G(n)$ must contain, with the offers for a proof, for the value of $c$ and for a disproof, "cheating since (7) clearly holds"; the printed bounds on $c$ are recorded above with an observation. #88, as the site's source Er97d: item 8 (p. 83) states the Erdős--McKay conjecture with the hypothesis of $cn^2$ edges and no trivial subgraph of size $>c\log n$, and records the partial result $t<c(\log n)^2$ as their own. #636, as the site's source Er97d: item 7 (p. 83), the first conjecture, made with Sós and Faudree: at least $cn^{5/2}$ induced subgraphs pairwise differing in vertex or edge count when $G(n)$ has no trivial subgraph of size $c\log n$, with the proved $cn^{3/2}$ and the remark that $cn^{5/2}$, if true, is best possible. #637, as the site's source Er97d: item 7 (p. 83), the second conjecture, that a $G(n)$ with no trivial subgraph of size $c\log n$ has an induced subgraph on $c_1n$ vertices taking $c_2n^{1/2}$ distinct degree values, attributed to Sós, Faudree and Erdős, with the Erdős--Hajnal result that the number of distinct degrees tends to infinity. #638, as the site's source Er97d: item 9 (pp. 83--84), the original wording of the problem, with the sentence the site quotes, "If the answer is affirmative many extensions and generalisations will be possible"; paged on problem_9. #639, as the site's source Er97d: item 10 (p. 84), the statement that Erdős, Rousseau and Schelp proved the bound $n^2/4$ "for large $n$", printed without proof or reference, the primary attestation of the unpublished result that page records as [ERS]; paged on problem_10. #608, as the site's source Er97d: item 11 (p. 84), "Perhaps there are at least $2n^2/9$ edges which occur in a pentagon" for every $G(n;\lfloor n^2/4\rfloor+1)$, stated after the odd cycle theorem and with the triangle-neighborhood statement that would imply it; the problem page's status rests on the 2019 construction, which this passage does not affect. #76, as the site's source Er97d: item 14 (p. 84), the Erdős--Faudree--Ordman question $f(n)=(1+o(1))n^2/12$ with the one-color question and the expectation "greater than $(1+\varepsilon)n^2/24$", which the site's commentary paraphrases as "$\ge cn^2$ for some constant $c>1/24$"; paged on problem_14. #644, as the site's source Er97d: item 16 (p. 85) defines the same transversal parameter as $f(k,r,2)$, records the exact cases for $3\le r\le6$, and states both the $r=7$ asymptotic and the general fixed-$r$ asymptotic as expectations. The paper gives no proof and points to its reference [1] for the neighboring exact results.

Results.

• Item 9 (pp. 83--84): the infinite-cardinal monochromatic triangle question, as printed.
• Item 10 (p. 84): at most $n^2/4$ edges of a two-colored $K(n)$ lie in no monochromatic triangle for large $n$, stated as proved with Rousseau and Schelp, without proof.
• Item 14 (p. 84): the edge-disjoint monochromatic triangles question, $f(n)=(1+o(1))n^2/12$?, and the one-color question.

No file of this source is held: no license on record permits its redistribution, and the card cites the edition it names above.