---
OA_place: publisher
OA_type: hybrid
PlanS_conform: '1'
_id: '23001'
abstract:
- lang: eng
  text: "A famous conjecture by Itai and Zehavi states that, for every \U0001D451\r\n-vertex-connected
    graph \U0001D43A\r\n and every vertex \U0001D45F\r\n in \U0001D43A\r\n, there
    are \U0001D451\r\n spanning trees of \U0001D43A\r\n such that, for every vertex
    \U0001D463\r\n in \U0001D43A ∖{\U0001D45F}\r\n, the paths between \U0001D45F\r\n
    and \U0001D463\r\n in different trees are internally vertex-disjoint. We show
    that with high probability the Itai–Zehavi conjecture holds asymptotically for
    the Erdős–Rényi random graph \U0001D43A⁡(\U0001D45B,\U0001D45D)\r\n when \U0001D45B⁢\U0001D45D
    =\U0001D714⁡(log⁡\U0001D45B)\r\n and for random regular graphs \U0001D43A⁡(\U0001D45B,\U0001D451)\r\n
    when \U0001D451 =\U0001D714⁡(log⁡\U0001D45B)\r\n. Moreover, we essentially confirm
    the conjecture up to a constant factor for sparser random regular graphs. This
    answers a question of Draganić and Krivelevich positively. Our proof makes use
    of recent developments on sprinkling techniques in random regular graphs."
acknowledgement: "Hollom was supported by the Internal Graduate Studentship of Trinity
  College, Cambridge. Mond was supported by UK Research and Innovation grant MR/W007320/2.
  Wang was supported by the ERC Starting Grant “RANDSTRUCT” No. 101076777. Lichev
  was supported by the Austrian Science Fund (FWF) [10.55776/ESP624]. For open access
  purposes, the authors have applied a CC BY public copyright license to any author-accepted
  manuscript version arising from this submission. Open Access funding provided by
  Technische Universitat Wien.\r\n\r\nPart of this research was done during a visit
  of the fourth author to IST Austria. We thank IST Austria for its hospitality. We
  also thank the anonymous referees for their comments and suggestions. Open Access
  funding provided by Technische Universitat Wien. This work was supported by the
  European Research Council, UK Research and Innovation, the Austrian Science Fund,
  and Trinity College."
article_number: e70095
article_processing_charge: Yes (via OA deal)
article_type: original
arxiv: 1
author:
- first_name: Lawrence
  full_name: Hollom, Lawrence
  last_name: Hollom
- first_name: Lyuben
  full_name: Lichev, Lyuben
  id: 9aa8388e-d003-11ee-8458-c4c1d7447977
  last_name: Lichev
- first_name: Adva
  full_name: Mond, Adva
  last_name: Mond
- first_name: Julien
  full_name: Portier, Julien
  last_name: Portier
- first_name: Yiting
  full_name: Wang, Yiting
  id: 1917d194-076e-11ed-97cd-837255f88785
  last_name: Wang
citation:
  ama: Hollom L, Lichev L, Mond A, Portier J, Wang Y. Approximate Itai–Zehavi conjecture
    for random graphs. <i>Random Structures and Algorithms</i>. 2026;69(2). doi:<a
    href="https://doi.org/10.1002/rsa.70095">10.1002/rsa.70095</a>
  apa: Hollom, L., Lichev, L., Mond, A., Portier, J., &#38; Wang, Y. (2026). Approximate
    Itai–Zehavi conjecture for random graphs. <i>Random Structures and Algorithms</i>.
    Wiley. <a href="https://doi.org/10.1002/rsa.70095">https://doi.org/10.1002/rsa.70095</a>
  chicago: Hollom, Lawrence, Lyuben Lichev, Adva Mond, Julien Portier, and Yiting
    Wang. “Approximate Itai–Zehavi Conjecture for Random Graphs.” <i>Random Structures
    and Algorithms</i>. Wiley, 2026. <a href="https://doi.org/10.1002/rsa.70095">https://doi.org/10.1002/rsa.70095</a>.
  ieee: L. Hollom, L. Lichev, A. Mond, J. Portier, and Y. Wang, “Approximate Itai–Zehavi
    conjecture for random graphs,” <i>Random Structures and Algorithms</i>, vol. 69,
    no. 2. Wiley, 2026.
  ista: Hollom L, Lichev L, Mond A, Portier J, Wang Y. 2026. Approximate Itai–Zehavi
    conjecture for random graphs. Random Structures and Algorithms. 69(2), e70095.
  mla: Hollom, Lawrence, et al. “Approximate Itai–Zehavi Conjecture for Random Graphs.”
    <i>Random Structures and Algorithms</i>, vol. 69, no. 2, e70095, Wiley, 2026,
    doi:<a href="https://doi.org/10.1002/rsa.70095">10.1002/rsa.70095</a>.
  short: L. Hollom, L. Lichev, A. Mond, J. Portier, Y. Wang, Random Structures and
    Algorithms 69 (2026).
das_tickbox: '0'
date_created: 2026-09-27T22:01:52Z
date_published: 2026-09-01T00:00:00Z
date_updated: 2026-10-07T07:13:30Z
day: '01'
ddc:
- '500'
department:
- _id: MaKw
- _id: GradSch
doi: 10.1002/rsa.70095
external_id:
  arxiv:
  - '2506.23970'
file:
- access_level: open_access
  checksum: 9a786460a47542f24576e947987e558a
  content_type: application/pdf
  creator: dernst
  date_created: 2026-10-07T07:10:43Z
  date_updated: 2026-10-07T07:10:43Z
  file_id: '23068'
  file_name: 2026_RandomStructAlgorithms_Hollom.pdf
  file_size: 457581
  relation: main_file
  success: 1
file_date_updated: 2026-10-07T07:10:43Z
fulldoi: https://doi.org/10.1002/rsa.70095
has_accepted_license: '1'
intvolume: '        69'
issue: '2'
language:
- iso: eng
month: '09'
oa: 1
oa_version: Published Version
project:
- _id: bd95085b-d553-11ed-ba76-e55d3349be45
  grant_number: '101076777'
  name: Randomness and structure in combinatorics
publication: Random Structures and Algorithms
publication_identifier:
  eissn:
  - 1098-2418
  issn:
  - 1042-9832
publication_status: published
publisher: Wiley
quality_controlled: '1'
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: yes
title: Approximate Itai–Zehavi conjecture for random graphs
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: 69
year: '2026'
...