Longest Paths in Random Hypergraphs

Oliver Cooley, Frederik Garbe, Eng Keat Hng, Mihyun Kang, Nicolás Sanhueza‐Matamala, Julian Zalla

Type: Article

Publication Date: 2021-01-01

Citations: 2

DOI: https://doi.org/10.1137/20m1345712

Abstract

Related DatabasesWeb of Science You must be logged in with an active subscription to view this.Article DataHistorySubmitted: 15 June 2020Accepted: 15 August 2021Published online: 18 October 2021Keywordsrandom hypergraphs, paths, phase transition, search algorithmAMS Subject Headings05C80, 05C65, 05C38Publication DataISSN (print): 0895-4801ISSN (online): 1095-7146Publisher: Society for Industrial and Applied MathematicsCODEN: sjdmec

Locations

SIAM Journal on Discrete Mathematics - View
arXiv (Cornell University) - View - PDF
London School of Economics and Political Science Research Online (London School of Economics and Political Science) - View - PDF

Similar Works

Action	Title	Year	Authors
+ PDF Chat	Subcritical Random Hypergraphs, High-Order Components, and Hypertrees	2020	Oliver Cooley Wenjie Fang Nicola Del Giudice Mihyun Kang
+	Relative Turán Problems for Uniform Hypergraphs	2021	Sam Spiro Jacques Verstraëte
+	Nearly Perfect Matchings in Uniform Hypergraphs	2021	Hongliang Lu Xingxing Yu Xiaofan Yuan
+ PDF Chat	Sprinkling a Few Random Edges Doubles the Power	2021	Rajko Nenadov Miloš Trujić
+	Ramsey Goodness of Clique Versus Paths in Random Graphs	2021	Luiz Moreira
+ PDF Chat	Random Walks on Dense Graphs and Graphons	2021	Julien Petit Renaud Lambiotte Timotéo Carletti
+	Random graphs	2008	Alain Barrat Marc Barthélemy Alessandro Vespignani
+ PDF Chat	Derandomization beyond Connectivity: Undirected Laplacian Systems in Nearly Logarithmic Space	2021	Jack Murtagh Omer Reingold Aaron Sidford Salil Vadhan
+ PDF Chat	Large Induced Matchings in Random Graphs	2021	Oliver Cooley Nemanja Draganić Mihyun Kang Benny Sudakov
+	The longest path in a random graph	1981	Miklós Ajtai János Komlós Endre Szemerédi
+	F$F$‐factors in Quasi‐random Hypergraphs	2022	Laihao Ding Jie Han Shumin Sun Guanghui Wang Wenling Zhou
+ PDF Chat	The Average-Case Complexity of Counting Cliques in Erdös--Rényi Hypergraphs	2021	Enric Boix-Adserà Matthew Brennan Guy Bresler
+ PDF Chat	Percolation on Random Graphs with a Fixed Degree Sequence	2022	Nikolaos Fountoulakis Felix Joos Guillem Perarnau
+ PDF Chat	On Ordered Ramsey Numbers of Tripartite 3-Uniform Hypergraphs	2022	Martin Balko Máté Vizer
+	Cycles in random graphs and hypergraphs	1992	V. F. Kolchin
+	From unbiased to maximal entropy random walks on hypergraphs	2023	Pietro Traversa Guilherme Ferraz de Arruda Yamir Moreno
+	Hypercycles in a random hypergraph	1992	Геннадий Васильевич Балакин V. F. Kolchin V. I. Khokhlov
+ PDF Chat	From unbiased to maximal-entropy random walks on hypergraphs	2024	Pietro Traversa Guilherme Ferraz de Arruda Yamir Moreno
+ PDF Chat	Repeated Patterns in Proper Colorings	2021	David Conlon Mykhaylo Tyomkyn
+ PDF Chat	An Optimal Algorithm for Strict Circular Seriation	2021	Santiago Armstrong Cristóbal Guzmán Carlos Sing‐Long

Works That Cite This (1)

Action	Title	Year	Authors
+ PDF Chat	Loose Cores and Cycles in Random Hypergraphs	2022	Oliver Cooley Mihyun Kang Julian Zalla

Works Cited by This (14)

Action	Title	Year	Authors
+	Component structure in the evolution of random hypergraphs	1985	Jeanette Schmidt‐Pruzan Eli Shamir
+	The longest path in a random graph	1981	Miklós Ajtai János Komlós Endre Szemerédi
+ PDF Chat	A random graph with a subcritical number of edges	1988	Boris Pittel
+ PDF Chat	Tight Hamilton cycles in random uniform hypergraphs	2012	Andrzej Dudek Alan Frieze
+ PDF Chat	The phase transition in random graphs: A simple proof	2012	Michael Krivelevich Benny Sudakov
+	Cycles in a random graph near the critical point	1991	Tomasz Łuczak
+	Hypergraph extensions of the Erdős-Gallai Theorem	2016	Ervin Győri Gyula Y. Katona Nathan Lemons
+ PDF Chat	The size of the giant high‐order component in random hypergraphs	2018	Oliver Cooley Mihyun Kang Christof Koch
+ PDF Chat	Loose Hamilton Cycles in Random Uniform Hypergraphs	2011	Andrzej Dudek Alan Frieze
+ PDF Chat	An Improved Upper Bound on the Length of the Longest Cycle of a Supercritical Random Graph	2013	Graeme Kemkes Nicholas Wormald