Login (DCU Staff Only)
Login (DCU Staff Only)

DORAS | DCU Research Repository

Explore open access research and scholarly works from DCU

Advanced Search

Creating Subgraphs in Semi-Random Hypergraph Games

Natalie, Behague orcid logoORCID: 0000-0001-6616-1606 (2026) Creating Subgraphs in Semi-Random Hypergraph Games. Electronic Journal of Combinatorics, 33 (1). pp. 1-41. ISSN 1077-8926

Abstract
The semi-random hypergraph process is a natural generalisation of the semirandom graph process, which can be thought of as a one player game. For fixed r < s, starting with an empty hypergraph on n vertices, in each round a set of r vertices U is presented to the player independently and uniformly at random. The player then selects a set of s − r vertices V and adds the hyperedge U ∪ V to the suniform hypergraph. For a fixed (monotone) increasing graph property, the player’s objective is to force the graph to satisfy this property with high probability in as few rounds as possible. We focus on the case where the player’s objective is to construct a subgraph isomorphic to an arbitrary, fixed hypergraph H. In the case r = 1 the threshold for the number of rounds required was already known in terms of the degeneracy of H. In the case 2 6 r < s, we give upper and lower bounds on this threshold for general H, and find further improved upper bounds for cliques in particular. We identify cases where the upper and lower bounds match. We also demonstrate that the lower bounds are not always tight by finding exact thresholds for various paths and cycles.
Metadata
Item Type:Article (Published)
Refereed:Yes
Subjects:Mathematics
Mathematics > Mathematical analysis
DCU Faculties and Centres:DCU Faculties and Schools > Faculty of Science and Health
DCU Faculties and Schools > Faculty of Science and Health > School of Mathematical Sciences
Publisher:Electronic Journal of Combinatorics
Official URL:https://www.combinatorics.org/ojs/index.php/eljc/a...
Copyright Information:Author
ID Code:32433
Deposited On:20 Mar 2026 12:04 by Vidatum Academic . Last Modified 20 Mar 2026 12:04
Documents

Full text available as:

[thumbnail of 13447-PDFfile-58660-2-10-20260117.pdf]
Preview
PDF - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
Creative Commons: Attribution-Noncommercial-No Derivative Works 4.0
818kB
Metrics

Altmetric Badge

Dimensions Badge

Downloads

Downloads

Downloads per month over past year

Archive Staff Only: edit this record