Asymptotic Thresholds for ( a: b ) Minimum-Degree Games

Adnane Fouadi, Mourad El Ouali () and Anand Srivastav ()
Additional contact information
Adnane Fouadi: Laboratory of Engineering Science, Faculty of Science, Ibn Zohr University, Agadir 80000, Morocco
Mourad El Ouali: Laboratory of Engineering Science, Faculty of Science, Ibn Zohr University, Agadir 80000, Morocco
Anand Srivastav: Department of Mathematics, Christian-Albrechts-Universität zu Kiel, 24118 Kiel, Germany

Games, 2025, vol. 16, issue 5, 1-21

Abstract: We investigate the ( a : b ) Maker–Breaker subgraph game played on the edge set of the complete graph K n , where n , a , b ∈ N , and Maker’s objective is to construct a member of a prescribed family of graphs H , while Breaker aims to prevent this. In our study, Breaker moves first, and H is taken to be either the family of connected spanning subgraphs or the family of spanning subgraphs with minimum-degree at least k = k ( n ) . For the ( a : b ) minimum-degree- k game, we determine the asymptotically optimal threshold bias across a wide range of values for a . For the ( a : b ) connectivity game, we resolve an open problem posed by Hefetz et al. (2012) by identifying the exact leading term in the asymptotic behavior of the threshold bias when a = c ln n .

Keywords: positional games; Maker–Breaker subgraph game; biased games; minimum-degree- k game; connectivity; asymptotic optimal bias (search for similar items in EconPapers)
JEL-codes: C C7 C70 C71 C72 C73 (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2073-4336/16/5/47/pdf (application/pdf)
https://www.mdpi.com/2073-4336/16/5/47/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jgames:v:16:y:2025:i:5:p:47-:d:1744368

Access Statistics for this article

Games is currently edited by Ms. Susie Huang

More articles in Games from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().