Erdos 1976 problems results combinatorial analysis

../

conjecture_p15: Erdős's Rome 1973 statement of the Erdős-Gallai conjecture that every graph on n vertices is covered by at most cn edge-disjoint circuits and edges, with his report that they could prove it only with cn log n in place of cn; the question behind Problem 184.

---

P. Erdős, Problems and results in combinatorial analysis, in: Colloquio Internazionale sulle Teorie Combinatorie (Roma, 1973), Tomo II (1976), 3--17; MR 0465878 (the site's reference text for the key). The site's reference key [Er76] for Problem 184 names this paper; the Rényi archive's index lists it as 1976-35.pdf. It is the paper Erdős's 1975 Aberdeen list (recorded at erdos_1976_problems_results_graph_theory_combinatorial_analysis, p. 169) cites as "Problems and results of combinatorial analysis, Symposium held in Rome September 1973 will appear soon".

The copy read for this card is the Rényi archive's OmniPage scan of the typeset proceedings text: fifteen pages, printed pp. 3--17 = PDF pp. 1--15 (printed p. $n$ is PDF p. $n-2$; the page numbers are printed as "--- 15 ---"), with a text layer that locates passages and garbles the displays and the Italian abstract. Provenance: retrieved from https://users.renyi.hu/~p_erdos/1976-35.pdf (HTTP 200, one request); 2,466,239 bytes. No notice is printed in the scan; the hosting archive's site footer speaks for the site, not the paper (https://users.renyi.hu/~p_erdos/, prints "(C) 2005-2007 All rights reserved. All material on this site is for scientifics purposes only."); the proceedings have no publisher page or DOI for this edition, so the publisher's page was not consulted and no Crossref license is recorded; the term is unstated.

Read status: claims checked for the Gallai sentence on p. 15 (PDF p. 13), read clause by clause on the page image together with the rest of that page; the whole paper, pp. 3--17, was read on the page images for the contents below. The paper states problems and reports results without proof; nothing here is independently reviewed.

Contents

• Title page (p. 3), with an Italian summary and the plan: "In the first four sections I discuss some extremal problems on graphs and hypergraphs. At the end of each section I give references, here is a list of my papers on combinatorial problems" (five papers, 1957--1974, among them the survey with Kleitman).
• Section 1 (pp. 3--5), extremal numbers $f(n;G^{(r)}(k;l))$ of $r$-graphs; Section 2 (pp. 5--9), bipartite graphs, $f(n;C_4)$ with Brown, Rényi and V. T. Sós, a block-design-like structure that would settle the general case, and the friendship theorem; Section 3 (pp. 9--10), extremal problems on hypergraphs; Section 4 (pp. 10--11), remarks on the Erdős--Stone theorem; Section 5 (pp. 11--15), "various combinatorial problems on subsets", ending with a problem from the Erdős--Kleitman survey, the conjecture $\max t=\binom{n}{n/2}+1$ for even $n$ for families of $t$ subsets in which no three distinct sets satisfy $A_i\cap A_j=A_k$ or $A_i\cup A_j=A_k$, and the section's references.
• Section 6 (pp. 15--17), "a few miscellaneous problems which my colleagues and I considered recently": the Erdős--Goodman--Pósa covering of the edges of $G(n;l)$ by at most $\lfloor n^2/4\rfloor$ edge-disjoint cliques (edges or triangles), the sentence quoted below, the covering of $G(n;l)$ by edge-disjoint edges and $K(r)$'s (reported as proved by Bollobás), two problems with Sauer (an $r$-graph covering conjecture and regular subgraphs), the coprime labelling of trees credited to Entringer, small non-planar subgraphs, two conjectures with Hajnal (a subgraph of given chromatic number and girth, and the circuit lengths of a $k$-chromatic graph), on pp. 16--17 problems on the intersections of set families, then van der Waerden's theorem, the Graham--Rothschild conjecture proved by Hindman, and the Faber--Lovász--Erdős conjecture.

The p. 15 sentence (PDF p. 13, page image), in Section 6: "Gallai and I conjectured that every $G(n;k)$ can be covered by at most $cn$ edge disjoint circuits and edges. We could only prove this with $cn\log n$ instead of $cn$." ($G(n;k)$ is a graph of $n$ vertices and $k$ edges.)

Compiled scope

The paper is compiled as a problem source. The p. 15 sentence, a conjecture stated without proof, is paged at conjecture_p15. The paper's other problems are not mapped here to the problem list.

Bears on. #184: the site's key [Er76]. The p. 15 sentence is the Erdős--Gallai conjecture in the problem's form (a decomposition into $O(n)$ edge-disjoint cycles and edges), with the $cn\log n$ bound reported as the only proved bound, as in the 1966 and 1971 statements; the paper gives no lower-bound example and no constant, and settles nothing. Paged at conjecture_p15.

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