Anti-Ramsey Numbers of Paths and Cycles in Hypergraphs

DOI10.1137/19M1244950zbMath1431.05145arXiv1901.06092MaRDI QIDQ5212951

Ran Gu, Jiaao Li, Yongtang Shi

Publication date: 31 January 2020

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: The anti-Ramsey problem was introduced by ErdH{o}s, Simonovits and S'{o}s in 1970s. The anti-Ramsey number of a hypergraph $mathcalH$, $ar(n,s,mathcalH)$, is the smallest integer $c$ such that in any coloring of the edges of the $s$-uniform complete hypergraph on $n$ vertices with exactly $c$ colors, there is a copy of $mathcalH$ whose edges have distinct colors. In this paper, we determine the anti-Ramsey numbers of linear paths and loose paths in hypergraphs for sufficiently large $n$, and give bounds for the anti-Ramsey numbers of Berge paths. Similar exact anti-Ramsey numbers are obtained for linear/loose cycles, and bounds are obtained for Berge cycles. Our main tools are path extension technique and stability results on hypergraph Tur'{a}n problems of paths and cycles.

Full work available at URL: https://arxiv.org/abs/1901.06092

zbMATH Keywords

rainbowpathscycleshypergraphsTurán numberanti-Ramsey

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Hypergraphs (05C65) Paths and cycles (05C38) Coloring of graphs and hypergraphs (05C15) Ramsey theory (05D10)

Cites Work

• Unnamed Item
• Unnamed Item
• Turán numbers for 3-uniform linear paths of length 3
• Anti-Ramsey number of matchings in hypergraphs
• On the Turán number of forests
• Exact solution of the hypergraph Turán problem for \(k\)-uniform linear paths
• 3-uniform hypergraphs avoiding a given odd cycle
• Turán problems and shadows. I: Paths and cycles
• On 3-uniform hypergraphs without a cycle of a given length
• Rainbow generalizations of Ramsey theory: A survey
• Hypergraph extensions of the Erdős-Gallai theorem
• On restricted colourings of \(K_ n\)
• Complete solution for the rainbow numbers of matchings
• A rainbow \(k\)-matching in the complete graph with \(r\) colors
• Exact solution of some Turán-type problems
• A homological approach to two problems on finite sets
• An Erdős-Gallai type theorem for uniform hypergraphs
• On families of sets without \(k\) pairwise disjoint members
• New inequalities for families without \(k\) pairwise disjoint members
• Cycles of given lengths in hypergraphs
• Anti-Ramsey numbers of subdivided graphs
• Rainbow numbers for matchings and complete graphs
• General lemmas for Berge-Turán hypergraph problems
• Asymptotics for the Turán number of Berge-\(K_{2,t}\)
• Two problems on matchings in set families -- in the footsteps of Erdős and Kleitman
• Proof of a conjecture of Erdős on triangles in set-systems
• Minimal paths and cycles in set systems
• The Turán number of disjoint copies of paths
• Hypergraph Turán numbers of linear cycles
• An anti-Ramsey theorem on cycles
• Hypergraphs with No Cycle of a Given Length
• The Size of a Hypergraph and its Matching Number
• Turán Numbers of Multiple Paths and Equibipartite Forests
• Turán Numbers for Forests of Paths in Hypergraphs
• On maximal paths and circuits of graphs
• An Extremal Set-Intersection Theorem
• SETS OF INDEPENDENT EDGES OF A HYPERGRAPH
• On families of finite sets no two of which intersect in a singleton
• A Bound on the Number of Edges in Graphs Without an Even Cycle
• Set Systems with No Singleton Intersection
• An anti-Ramsey theorem

Related Items (18)

Anti-Ramsey numbers for cycles in the generalized Petersen graphs ⋮ Exact rainbow numbers for matchings in plane triangulations ⋮ Anti‐Ramsey number of expansions of paths and cycles in uniform hypergraphs ⋮ Extremal \(P_8\)-free/\(P_9\)-free planar graphs ⋮ Constrained Ramsey numbers for the loose path, cycle and star ⋮ Anti-Ramsey Number of Edge-Disjoint Rainbow Spanning Trees in All Graphs ⋮ Anti-Ramsey number of matchings in outerplanar graphs ⋮ Anti-Ramsey number of disjoint union of star-like hypergraphs ⋮ Anti-Ramsey number of matchings in a hypergraph ⋮ The anti-Ramsey numbers of \(C_3\) and \(C_4\) in complete \(r\)-partite graphs ⋮ Rainbow numbers for paths in planar graphs ⋮ Anti-Ramsey numbers in complete \(k\)-partite graphs ⋮ Unnamed Item ⋮ Rainbow numbers for small graphs in planar graphs ⋮ The rainbow numbers of cycles in maximal bipartite planar graph ⋮ \((k-2)\)-linear connected components in hypergraphs of rank \(k\) ⋮ Anti-Ramsey number of matchings in \(r\)-partite \(r\)-uniform hypergraphs ⋮ Anti-Ramsey numbers for cycles in \(n\)-prisms

This page was built for publication: Anti-Ramsey Numbers of Paths and Cycles in Hypergraphs