Search

We prove that the maximum number of triangles in a C 5 -free graph on n vertices is at most 1 2 2 ( 1 + o ( 1 ) ) n 3 / 2 , improving an estimate of Alon and Shikhelman [Alon, N. and C. Shikhelman, Many T copies in H-free graphs . Journal of Combinatorial Theory, Series B 121 (2016) 146-172]. [ABSTRACT FROM AUTHOR]

We continue the work of Gyárfás, Győri and Simonovits [Gyárfás, A., E. Győri and M. Simonovits, On 3 -uniform hypergraphs without linear cycles . Journal of Combinatorics 7 (2016), 205–216], who proved that if a 3-uniform hypergraph H with n vertices has no linear cycles, then its independence number α ≥ 2 n 5 . The hypergraph consisting of vertex disjoint copies of complete hypergraphs K 5 3 shows that equality can hold. They asked whether α can be improved if we exclude K 5 3 as a subhypergraph and whether such a hypergraph is 2-colorable. We answer these questions affirmatively. Namely, we prove that if a 3-uniform linear-cycle-free hypergraph H , doesn't contain K 5 3 as a subhypergraph, then it is 2-colorable. This result clearly implies that α ≥ ⌈ n 2 ⌉ . We show that this bound is sharp. Gyárfás, Győri and Simonovits also proved that a linear-cycle-free 3-uniform hypergraph contains a vertex of strong degree at most 2. In this context, we show that a linear-cycle-free 3-uniform hypergraph has a vertex of degree at most n − 2 when n ≥ 10 . [ABSTRACT FROM AUTHOR]

We prove the quarter of a century old conjecture of Erdős that every K 4 -free graph with n vertices and ⌊ n 2 / 4 ⌋ + m edges contains m pairwise edge disjoint triangles. [ABSTRACT FROM AUTHOR]

Abstract: Given a sequence of simple graphs over uniquely labeled vertices from a set V, the periodic subgraph mining problem consists in discovering maximal subgraphs that recur at regular intervals in . For a periodic subgraph to be maximal, it is intended here that it cannot be enriched by adding edges nor can its temporal span be expanded in any direction. We give algorithms that improve the theoretical complexity of solutions previously available for this problem. In particular, we show an optimal solution based on an implicit description of the output subgraphs that takes time —where is the average number of edges over the entire sequence —to publish all maximal periodic subgraphs that meet or exceed a minimum occurrence threshold σ. [Copyright &y& Elsevier]

Abstract: The Erdős-Gallai Theorem gives the maximum number of edges in a graph without a path of length k. We extend this result for Berge paths in r-uniform hypergraphs. We also find the extremal hypergraphs avoiding t-tight paths of a given length and consider this extremal problem for other definitions of paths in hypergraphs. [ABSTRACT FROM AUTHOR]

Abstract: We give upper bounds for the size of 3-uniform hypergraphs avoiding a given odd cycle using the definition of a cycle due to Berge. In particular, we show that a 3-uniform hypergraph containing no cycle of length has less than edges. Constructions show that these bounds are best possible (up to constant factor) for . [Copyright &y& Elsevier]

Abstract: We are presenting in this volume the collection of extended abstracts that were selected for presentation at EUROCOMBʼ11 in Budapest. EUROCOMB conferences are organized biannually, the series was started in Barcelona 2001, and continued with Prague 2003, Berlin 2005, Seville 2007 and Bordeaux 2009. Since Prague EUROCOMBʼ03 the European Prize is awarded at the meeting. The prize is established to recognize excellent contributions in Combinatorics, Discrete Mathematics and their Applications by young European researchers (eligibility of EU) not older than 35. It is supported by DIMATIA and by private sources. The role of combinatorics is growing in the contemporary research in mathematics, computer science, engineering, also in physics, life and social sciences. This is reflected in the growing interest in EUROCOMB conferences, which became an established forum of the frontier research in these fields. This year a total of 188 contributions were submitted and the Program Committee selected 135 extended abstracts to be presented at the conference. As a comparison, there were 142 contributions for EUROCOMBʼ07 in Seville and 92 of those were selected for presentation. We thank all members of the Program Committee for their work. We also thank to allmembers of the Organizing Committee of EUROCOMBʼ11 for all their work in preparing the meeting in lovely Budapest. [Copyright &y& Elsevier]