. Problems and memories ...... András Gyárfás Alfréd Rényi Institute of Mathematics 2013 July 5, Budapest . . . . . . Gyárfás (MTARÉNYI) Problemsandmemories 2013July5,Budapest 1/25 First encounter - Mátraháza, 1962 My first encounter with Paul Erdős took place in 1962 at the Mátraháza Guest House of the Hungarian Academy of Sciences. I was a high school student and was rather embarrassed by the solemn formalities, especially at the dinner tables. I was pleased to hear the signs of some unaccepted behavior from a neighboring table, where an „old” man about fifty was regulated by his mother: „Pali you should keep your fork properly!” . . . . . . Gyárfás (MTARÉNYI) Problemsandmemories 2013July5,Budapest 2/25 Pingpong I soon learned that the unruled boy is a famous mathematician who travels around the world with his mother. Next day I had opportunity to play ping pong against „Pali” I was very angry upon being beaten by such an old man playing in a ridiculous style. As a consolation he told me what a graph is and what does Turán theorem say about the number of edges in a graph that does not contain K . „Adding any edge to the Turán graph we get a K k+1 k+1 but... ...what is the smallest graph with this property?” - asked during the revenge game which I lost again. . . . . . . Gyárfás (MTARÉNYI) Problemsandmemories 2013July5,Budapest 3/25 Budapest, 1963 The problem I have heard from Erdős in Mátraháza kept me busy and about a year later, after a lecture he gave in Budapest, I handed him my typewritten solution for the case when n, the number of vertices, is large in terms of k. It was disappointing to learn that his question was not an unsolved problem, but his result with Hajnal and Moon! . Theorem .. (Erdős, Hajnal, Moon, 1964) The minim(um) number of edges in a K -saturated graph with n vertices is k +k(n−k). ...... k+2 2 . . . . . . Gyárfás (MTARÉNYI) Problemsandmemories 2013July5,Budapest 4/25 Eötvös University, 1965 Two years later, at Eötvös University, I listened to Béla Bollobás’ talk at the Hajós seminar about extending the Erdős - Hajnal - Moon result to hypergraphs. I remember Béla’s comment: „this is trivial”... Trivial or not, certainly important and rediscovered several times (Jaeger - Payan 1971, Katona 1974). The underlying idea, cross-intersecting sets, developed further and have many applications. . . . . . . Gyárfás (MTARÉNYI) Problemsandmemories 2013July5,Budapest 5/25 Memphis, Tennessee, 1980 - 1992 Long distance information, give me Memphis Tennessee, Help me find the party trying to get in touch with me, She could not leave her number, but I know who placed the call, ’Cause my uncle took the message and he wrote it on the wall... ... and beside Elvis Presley, Chuck Berry and Fedex, I learned that Memphis Tennessee is also known as a hub during the movements of Paul Erdős in the US. Indeed, I have had much more chance to meet (and think on math) with him there than in Budapest. The University of Memphis (with Faudree, Ordman, Rousseau and Schelp as permanent faculty and me as permanent visitor) provided many opportunities to pursue theorems, problems and conjectures. From the early 90-s the department was fortified by Béla Bollobás, who leads a Chair of Excellence in Combinatorics since then. . . . . . . Gyárfás (MTARÉNYI) Problemsandmemories 2013July5,Budapest 6/25 Problems from Memphis 1. Cyles in graphs without proper subgraphs of minimum degree 3. Graphs with n vertices and 2n−1 edges must contain proper subgraphs of minimum degree 3 but this fails for graphs with n vertices and 2n−2 edges, for example the wheel is such a graph (Erdős, Faudree, Rousseau and Schelp, 1990). Let G(n) be the family of graphs with n vertices, 2n−2 edges and without proper subgraphs of minimum degree 3. . Conjecture .. 1. (Erdős, Faudree, Gy., Schelp, 1988) Every G ∈ G(n) contains cycles ......of length i for every integer 3 ≤ i ≤ k where k tends to infinity with n. . . . . . . Gyárfás (MTARÉNYI) Problemsandmemories 2013July5,Budapest 7/25 Problems from Memphis 2. Large chordal subgraphs. Any graph with n vertices and at least n2/3 edges contains a chordal subgraph with at least 2n−3 edges. The complete tripartite graph shows that this is sharp . Conjecture .. 2. (Erdős , Gy., Ordman, Zalcstein 1989) Any graph with n vertices and more than n2/3 edges contains a chordal subgraph with at least 8n/3−4 edges. The complete tripartite graph with one additional edge s......hows that this would be sharp. We could prove a weaker result, that graphs with n vertices and more than n2/3 edges contain chordal subgraphs with at least 7n/3−6 edges. . . . . . . Gyárfás (MTARÉNYI) Problemsandmemories 2013July5,Budapest 8/25 Problems from Memphis 3. Monochromatic domination. In an edge colored complete graph K a subset S of vertices dominate in color i those vertices in V(K)−S that send at least one edge of color i to S. If the edges of K are 3-colored then in one of the colors at most 22 n vertices dominate at least 2n/3 vertices of K . n However, there are 3-colorings such that no color can dominate more than 2n/3 vertices of K with any fixed number of vertices. n The random 3-coloring shows that no two vertices dominate much more than 5n/8 vertices in any color. . Problem .. 3. (Erdős, Faudree, Gould, Gy., Rousseau, Schelp, 1990) If the edges of K are 3-colored then in one of the colors at most 3 vertices dominate n at least 2n/3 vertices of K . Recently Kral, Liu, Sereni, Whalen and n Yilma applied flag algebra to prove that in one of the colors 4 vertices ......dominate at least 2n/3 vertices of Kn. . . . . . . Gyárfás (MTARÉNYI) Problemsandmemories 2013July5,Budapest 9/25 Problems from Memphis 4. Covering by monochromatic cycles The cycle partition number be the minimum k such that the vertex set of any r- edge-colored complete graph can be covered by at most k vertex disjoint monochromatic cycles. The cycle partition number depends only on r and it is at most cr2logr (Erdős, Gy. - Pyber, 1991) . Conjecture .. 4. (Erdős, Gy., Pyber, 1991) The cycle partition number of any ......r-colored complete graph is at most r. The case r = 2 in Conjecture is due to J. Lehel and was proved for large enough complete graphs by Łuczak, Rödl and Szemerédi and Allen. Then Bessy and Thomassé proved it for all complete graphs. Although Conjecture 4 for r = 3 is asymptotically true, Pokrovskiy found a counterexample in which three monochromatic cycles cannot cover all vertices. . . . . . . Gyárfás (MTARÉNYI) Problemsandmemories 2013July5,Budapest 10/25