---
OA_place: publisher
OA_type: hybrid
_id: '18583'
abstract:
- lang: eng
  text: "There are a number of well-known problems and conjectures about partitioning
    graphs to satisfy local constraints. For example, the majority colouring conjecture
    of Kreutzer, Oum, Seymour, van der Zypen and Wood states that every directed graph
    has a 3-colouring such that for every vertex v, at most half of the out-neighbours
    of v have the same colour as \r\n. As another example, the internal partition
    conjecture, due to DeVos and to Ban and Linial, states that for every d, all but
    finitely many d-regular graphs have a partition into two non-empty parts such
    that for every vertex v, at least half of the neighbours of v lie in the same
    part as v. We prove several results in this spirit: in particular, two of our
    results are that the majority colouring conjecture holds for Erdős–Rényi random
    directed graphs (of any density), and that the internal partition conjecture holds
    if we permit a tiny number of ‘exceptional vertices’. Our proofs involve a variety
    of techniques, including several different methods to analyse random recolouring
    processes. One highlight is a personality-changing scheme: we ‘forget’ certain
    information based on the state of a Markov chain, giving us more independence
    to work with."
acknowledgement: "We are grateful to the anonymous referees for their thorough reading
  of the paper, and for many suggestions which have improved the exposition throughout.\r\n\r\nMichael
  Anastos was supported by the European Union's Horizon 2020 research and innovation
  programme under the Marie Skłodowska-Curie grant agreement No. 101034413. Matthew
  Kwan was supported by ERC Starting Grant ‘RANDSTRUCT’ No. 101076777, also funded
  by the European Union image. Mihyun Kang was supported in part by the Austrian Science
  Fund (FWF) [10.55776/I6502]. For the purpose of open access, the authors have applied
  a CC-BY public copyright licence to any Author Accepted Manuscript version arising
  from this submission."
article_number: e70010
article_processing_charge: Yes (via OA deal)
article_type: original
arxiv: 1
author:
- first_name: Michael
  full_name: Anastos, Michael
  id: 0b2a4358-bb35-11ec-b7b9-e3279b593dbb
  last_name: Anastos
- first_name: Oliver
  full_name: Cooley, Oliver
  id: 43f4ddd0-a46b-11ec-8df6-ef3703bd721d
  last_name: Cooley
- first_name: Mihyun
  full_name: Kang, Mihyun
  last_name: Kang
- first_name: Matthew Alan
  full_name: Kwan, Matthew Alan
  id: 5fca0887-a1db-11eb-95d1-ca9d5e0453b3
  last_name: Kwan
  orcid: 0000-0002-4003-7567
citation:
  ama: Anastos M, Cooley O, Kang M, Kwan MA. Partitioning problems via random processes.
    <i>Journal of the London Mathematical Society</i>. 2024;110(6). doi:<a href="https://doi.org/10.1112/jlms.70010">10.1112/jlms.70010</a>
  apa: Anastos, M., Cooley, O., Kang, M., &#38; Kwan, M. A. (2024). Partitioning problems
    via random processes. <i>Journal of the London Mathematical Society</i>. Wiley.
    <a href="https://doi.org/10.1112/jlms.70010">https://doi.org/10.1112/jlms.70010</a>
  chicago: Anastos, Michael, Oliver Cooley, Mihyun Kang, and Matthew Alan Kwan. “Partitioning
    Problems via Random Processes.” <i>Journal of the London Mathematical Society</i>.
    Wiley, 2024. <a href="https://doi.org/10.1112/jlms.70010">https://doi.org/10.1112/jlms.70010</a>.
  ieee: M. Anastos, O. Cooley, M. Kang, and M. A. Kwan, “Partitioning problems via
    random processes,” <i>Journal of the London Mathematical Society</i>, vol. 110,
    no. 6. Wiley, 2024.
  ista: Anastos M, Cooley O, Kang M, Kwan MA. 2024. Partitioning problems via random
    processes. Journal of the London Mathematical Society. 110(6), e70010.
  mla: Anastos, Michael, et al. “Partitioning Problems via Random Processes.” <i>Journal
    of the London Mathematical Society</i>, vol. 110, no. 6, e70010, Wiley, 2024,
    doi:<a href="https://doi.org/10.1112/jlms.70010">10.1112/jlms.70010</a>.
  short: M. Anastos, O. Cooley, M. Kang, M.A. Kwan, Journal of the London Mathematical
    Society 110 (2024).
corr_author: '1'
date_created: 2024-11-24T23:01:48Z
date_published: 2024-12-01T00:00:00Z
date_updated: 2025-12-02T13:52:26Z
day: '01'
ddc:
- '510'
department:
- _id: MaKw
doi: 10.1112/jlms.70010
ec_funded: 1
external_id:
  arxiv:
  - '2307.06453'
  isi:
  - '001374738100001'
file:
- access_level: open_access
  checksum: 98e301e0565d75e3fb50e10e982a5018
  content_type: application/pdf
  creator: dernst
  date_created: 2024-12-10T08:10:39Z
  date_updated: 2024-12-10T08:10:39Z
  file_id: '18639'
  file_name: 2024_JournLondonMathSoc_Anastos.pdf
  file_size: 539891
  relation: main_file
  success: 1
file_date_updated: 2024-12-10T08:10:39Z
has_accepted_license: '1'
intvolume: '       110'
isi: 1
issue: '6'
language:
- iso: eng
month: '12'
oa: 1
oa_version: Published Version
project:
- _id: fc2ed2f7-9c52-11eb-aca3-c01059dda49c
  call_identifier: H2020
  grant_number: '101034413'
  name: 'IST-BRIDGE: International postdoctoral program'
- _id: bd95085b-d553-11ed-ba76-e55d3349be45
  grant_number: '101076777'
  name: Randomness and structure in combinatorics
publication: Journal of the London Mathematical Society
publication_identifier:
  eissn:
  - 1469-7750
  issn:
  - 0024-6107
publication_status: published
publisher: Wiley
quality_controlled: '1'
scopus_import: '1'
status: public
title: Partitioning problems via random processes
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 110
year: '2024'
...
---
_id: '11740'
abstract:
- lang: eng
  text: "We consider a generalised model of a random simplicial complex, which arises
    from a random hypergraph. Our model is generated by taking the downward-closure
    of a non-uniform binomial random hypergraph, in which for each k, each set of
    k+1 vertices forms an edge with some probability pk independently. As a special
    case, this contains an extensively studied model of a (uniform) random simplicial
    complex, introduced by Meshulam and Wallach [Random Structures & Algorithms 34
    (2009), no. 3, pp. 408–417].\r\nWe consider a higher-dimensional notion of connectedness
    on this new model according to the vanishing of cohomology groups over an arbitrary
    abelian group R. We prove that this notion of connectedness displays a phase transition
    and determine the threshold. We also prove a hitting time result for a natural
    process interpretation, in which simplices and their downward-closure are added
    one by one. In addition, we determine the asymptotic behaviour of cohomology groups
    inside the critical window around the time of the phase transition."
acknowledgement: 'Supported by Austrian Science Fund (FWF): I3747, W1230.'
article_number: P3.27
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Oliver
  full_name: Cooley, Oliver
  id: 43f4ddd0-a46b-11ec-8df6-ef3703bd721d
  last_name: Cooley
- first_name: Nicola
  full_name: Del Giudice, Nicola
  last_name: Del Giudice
- first_name: Mihyun
  full_name: Kang, Mihyun
  last_name: Kang
- first_name: Philipp
  full_name: Sprüssel, Philipp
  last_name: Sprüssel
citation:
  ama: Cooley O, Del Giudice N, Kang M, Sprüssel P. Phase transition in cohomology
    groups of non-uniform random simplicial complexes. <i>Electronic Journal of Combinatorics</i>.
    2022;29(3). doi:<a href="https://doi.org/10.37236/10607">10.37236/10607</a>
  apa: Cooley, O., Del Giudice, N., Kang, M., &#38; Sprüssel, P. (2022). Phase transition
    in cohomology groups of non-uniform random simplicial complexes. <i>Electronic
    Journal of Combinatorics</i>. Electronic Journal of Combinatorics. <a href="https://doi.org/10.37236/10607">https://doi.org/10.37236/10607</a>
  chicago: Cooley, Oliver, Nicola Del Giudice, Mihyun Kang, and Philipp Sprüssel.
    “Phase Transition in Cohomology Groups of Non-Uniform Random Simplicial Complexes.”
    <i>Electronic Journal of Combinatorics</i>. Electronic Journal of Combinatorics,
    2022. <a href="https://doi.org/10.37236/10607">https://doi.org/10.37236/10607</a>.
  ieee: O. Cooley, N. Del Giudice, M. Kang, and P. Sprüssel, “Phase transition in
    cohomology groups of non-uniform random simplicial complexes,” <i>Electronic Journal
    of Combinatorics</i>, vol. 29, no. 3. Electronic Journal of Combinatorics, 2022.
  ista: Cooley O, Del Giudice N, Kang M, Sprüssel P. 2022. Phase transition in cohomology
    groups of non-uniform random simplicial complexes. Electronic Journal of Combinatorics.
    29(3), P3.27.
  mla: Cooley, Oliver, et al. “Phase Transition in Cohomology Groups of Non-Uniform
    Random Simplicial Complexes.” <i>Electronic Journal of Combinatorics</i>, vol.
    29, no. 3, P3.27, Electronic Journal of Combinatorics, 2022, doi:<a href="https://doi.org/10.37236/10607">10.37236/10607</a>.
  short: O. Cooley, N. Del Giudice, M. Kang, P. Sprüssel, Electronic Journal of Combinatorics
    29 (2022).
corr_author: '1'
date_created: 2022-08-07T22:01:59Z
date_published: 2022-07-29T00:00:00Z
date_updated: 2024-10-09T21:03:03Z
day: '29'
ddc:
- '510'
department:
- _id: MaKw
doi: 10.37236/10607
external_id:
  arxiv:
  - '2005.07103'
  isi:
  - '000836200300001'
file:
- access_level: open_access
  checksum: 057c676dcee70236aa234d4ce6138c69
  content_type: application/pdf
  creator: dernst
  date_created: 2022-08-08T06:28:52Z
  date_updated: 2022-08-08T06:28:52Z
  file_id: '11742'
  file_name: 2022_ElecJournCombinatorics_Cooley.pdf
  file_size: 1768663
  relation: main_file
  success: 1
file_date_updated: 2022-08-08T06:28:52Z
has_accepted_license: '1'
intvolume: '        29'
isi: 1
issue: '3'
language:
- iso: eng
license: https://creativecommons.org/licenses/by-nd/4.0/
month: '07'
oa: 1
oa_version: Published Version
publication: Electronic Journal of Combinatorics
publication_identifier:
  eissn:
  - 1077-8926
publication_status: published
publisher: Electronic Journal of Combinatorics
quality_controlled: '1'
scopus_import: '1'
status: public
title: Phase transition in cohomology groups of non-uniform random simplicial complexes
tmp:
  image: /image/cc_by_nd.png
  legal_code_url: https://creativecommons.org/licenses/by-nd/4.0/legalcode
  name: Creative Commons Attribution-NoDerivatives 4.0 International (CC BY-ND 4.0)
  short: CC BY-ND (4.0)
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 29
year: '2022'
...
---
_id: '12151'
abstract:
- lang: eng
  text: The k-sample G(k,W) from a graphon W:[0,1]2→[0,1] is the random graph on {1,…,k},
    where we sample x1,…,xk∈[0,1] uniformly at random and make each pair {i,j}⊆{1,…,k}
    an edge with probability W(xi,xj), with all these choices being mutually independent.
    Let the random variable Xk(W) be the number of edges in  G(k,W). Vera T. Sós asked
    in 2012 whether two graphons U, W are necessarily weakly isomorphic if the random
    variables Xk(U) and Xk(W) have the same distribution for every integer k≥2. This
    question when one of the graphons W is a constant function was answered positively
    by Endre Csóka and independently by Jacob Fox, Tomasz Łuczak and Vera T. Sós.
    Here we investigate the question when W is a 2-step graphon and prove that the
    answer is positive for a 3-dimensional family of such graphons. We also present
    some related results.
acknowledgement: "Supported by Austrian Science Fund (FWF) Grant I3747. Supported
  by ERC Advanced Grant 101020255 and Leverhulme Research Project Grant RPG-2018-424.\r\nAn
  extended abstract of this paper appeared in the Proceedings of the European Conference\r\non
  Combinatorics, Graph Theory and Applications (EuroComb 2021), CRM Research Perspectives,
  Springer."
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Oliver
  full_name: Cooley, Oliver
  id: 43f4ddd0-a46b-11ec-8df6-ef3703bd721d
  last_name: Cooley
- first_name: M.
  full_name: Kang, M.
  last_name: Kang
- first_name: O.
  full_name: Pikhurko, O.
  last_name: Pikhurko
citation:
  ama: Cooley O, Kang M, Pikhurko O. On a question of Vera T. Sós about size forcing
    of graphons. <i>Acta Mathematica Hungarica</i>. 2022;168:1-26. doi:<a href="https://doi.org/10.1007/s10474-022-01265-8">10.1007/s10474-022-01265-8</a>
  apa: Cooley, O., Kang, M., &#38; Pikhurko, O. (2022). On a question of Vera T. Sós
    about size forcing of graphons. <i>Acta Mathematica Hungarica</i>. Springer Nature.
    <a href="https://doi.org/10.1007/s10474-022-01265-8">https://doi.org/10.1007/s10474-022-01265-8</a>
  chicago: Cooley, Oliver, M. Kang, and O. Pikhurko. “On a Question of Vera T. Sós
    about Size Forcing of Graphons.” <i>Acta Mathematica Hungarica</i>. Springer Nature,
    2022. <a href="https://doi.org/10.1007/s10474-022-01265-8">https://doi.org/10.1007/s10474-022-01265-8</a>.
  ieee: O. Cooley, M. Kang, and O. Pikhurko, “On a question of Vera T. Sós about size
    forcing of graphons,” <i>Acta Mathematica Hungarica</i>, vol. 168. Springer Nature,
    pp. 1–26, 2022.
  ista: Cooley O, Kang M, Pikhurko O. 2022. On a question of Vera T. Sós about size
    forcing of graphons. Acta Mathematica Hungarica. 168, 1–26.
  mla: Cooley, Oliver, et al. “On a Question of Vera T. Sós about Size Forcing of
    Graphons.” <i>Acta Mathematica Hungarica</i>, vol. 168, Springer Nature, 2022,
    pp. 1–26, doi:<a href="https://doi.org/10.1007/s10474-022-01265-8">10.1007/s10474-022-01265-8</a>.
  short: O. Cooley, M. Kang, O. Pikhurko, Acta Mathematica Hungarica 168 (2022) 1–26.
corr_author: '1'
date_created: 2023-01-12T12:07:59Z
date_published: 2022-11-23T00:00:00Z
date_updated: 2024-10-09T21:03:37Z
day: '23'
department:
- _id: MaKw
doi: 10.1007/s10474-022-01265-8
external_id:
  arxiv:
  - '2103.09114'
  isi:
  - '000886839900006'
intvolume: '       168'
isi: 1
keyword:
- graphon
- k-sample
- graphon forcing
- graph container
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: ' https://doi.org/10.48550/arXiv.2103.09114'
month: '11'
oa: 1
oa_version: Preprint
page: 1-26
publication: Acta Mathematica Hungarica
publication_identifier:
  eissn:
  - 1588-2632
  issn:
  - 0236-5294
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: On a question of Vera T. Sós about size forcing of graphons
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 168
year: '2022'
...
---
_id: '12286'
abstract:
- lang: eng
  text: "Inspired by the study of loose cycles in hypergraphs, we define the loose
    core in hypergraphs as a structurewhich mirrors the close relationship between
    cycles and $2$-cores in graphs. We prove that in the $r$-uniform binomial random
    hypergraph $H^r(n,p)$, the order of the loose core undergoes a phase transition
    at a certain critical threshold and determine this order, as well as the number
    of edges, asymptotically in the subcritical and supercritical regimes.&#x0D;\r\nOur
    main tool is an algorithm called CoreConstruct, which enables us to analyse a
    peeling process for the loose core. By analysing this algorithm we determine the
    asymptotic degree distribution of vertices in the loose core and in particular
    how many vertices and edges the loose core contains. As a corollary we obtain
    an improved upper bound on the length of the longest loose cycle in $H^r(n,p)$."
acknowledgement: 'Supported by Austrian Science Fund (FWF): I3747, W1230.'
article_number: P4.13
article_processing_charge: No
article_type: original
author:
- first_name: Oliver
  full_name: Cooley, Oliver
  id: 43f4ddd0-a46b-11ec-8df6-ef3703bd721d
  last_name: Cooley
- first_name: Mihyun
  full_name: Kang, Mihyun
  last_name: Kang
- first_name: Julian
  full_name: Zalla, Julian
  last_name: Zalla
citation:
  ama: Cooley O, Kang M, Zalla J. Loose cores and cycles in random hypergraphs. <i>The
    Electronic Journal of Combinatorics</i>. 2022;29(4). doi:<a href="https://doi.org/10.37236/10794">10.37236/10794</a>
  apa: Cooley, O., Kang, M., &#38; Zalla, J. (2022). Loose cores and cycles in random
    hypergraphs. <i>The Electronic Journal of Combinatorics</i>. The Electronic Journal
    of Combinatorics. <a href="https://doi.org/10.37236/10794">https://doi.org/10.37236/10794</a>
  chicago: Cooley, Oliver, Mihyun Kang, and Julian Zalla. “Loose Cores and Cycles
    in Random Hypergraphs.” <i>The Electronic Journal of Combinatorics</i>. The Electronic
    Journal of Combinatorics, 2022. <a href="https://doi.org/10.37236/10794">https://doi.org/10.37236/10794</a>.
  ieee: O. Cooley, M. Kang, and J. Zalla, “Loose cores and cycles in random hypergraphs,”
    <i>The Electronic Journal of Combinatorics</i>, vol. 29, no. 4. The Electronic
    Journal of Combinatorics, 2022.
  ista: Cooley O, Kang M, Zalla J. 2022. Loose cores and cycles in random hypergraphs.
    The Electronic Journal of Combinatorics. 29(4), P4.13.
  mla: Cooley, Oliver, et al. “Loose Cores and Cycles in Random Hypergraphs.” <i>The
    Electronic Journal of Combinatorics</i>, vol. 29, no. 4, P4.13, The Electronic
    Journal of Combinatorics, 2022, doi:<a href="https://doi.org/10.37236/10794">10.37236/10794</a>.
  short: O. Cooley, M. Kang, J. Zalla, The Electronic Journal of Combinatorics 29
    (2022).
date_created: 2023-01-16T10:03:57Z
date_published: 2022-10-21T00:00:00Z
date_updated: 2023-08-04T10:29:18Z
day: '21'
ddc:
- '510'
department:
- _id: MaKw
doi: 10.37236/10794
external_id:
  isi:
  - '000876763300001'
file:
- access_level: open_access
  checksum: 00122b2459f09b5ae43073bfba565e94
  content_type: application/pdf
  creator: dernst
  date_created: 2023-01-30T11:45:13Z
  date_updated: 2023-01-30T11:45:13Z
  file_id: '12462'
  file_name: 2022_ElecJournCombinatorics_Cooley_Kang_Zalla.pdf
  file_size: 626953
  relation: main_file
  success: 1
file_date_updated: 2023-01-30T11:45:13Z
has_accepted_license: '1'
intvolume: '        29'
isi: 1
issue: '4'
keyword:
- Computational Theory and Mathematics
- Geometry and Topology
- Theoretical Computer Science
- Applied Mathematics
- Discrete Mathematics and Combinatorics
language:
- iso: eng
month: '10'
oa: 1
oa_version: Published Version
publication: The Electronic Journal of Combinatorics
publication_identifier:
  eissn:
  - 1077-8926
publication_status: published
publisher: The Electronic Journal of Combinatorics
quality_controlled: '1'
scopus_import: '1'
status: public
title: Loose cores and cycles in random hypergraphs
tmp:
  image: /image/cc_by_nd.png
  legal_code_url: https://creativecommons.org/licenses/by-nd/4.0/legalcode
  name: Creative Commons Attribution-NoDerivatives 4.0 International (CC BY-ND 4.0)
  short: CC BY-ND (4.0)
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 29
year: '2022'
...