---
OA_place: publisher
OA_type: hybrid
PlanS_conform: '1'
_id: '22752'
abstract:
- lang: eng
text: "In this note we outline a new and simple approach to proving central limit
theorems for various ‘global’ graph parameters that have robust ‘local’ approximations,
using the Efron–Stein inequality, which relies on a combinatorial analysis of
the stability of these approximations under resampling an edge. As an application,
we give short proofs of a central limit theorem for the order of the giant component
and of the \U0001D458\r\n-core for sparse random graphs."
acknowledgement: This research was funded in whole or in part by the Austrian Science
Fund (FWF) [10.55776/P36131 (Joshua Erde), 10.55776/I6502 (Mihyun Kang), 10.55776/ESP3863424
(Michael Anastos)] and by the Swiss National Science Foundation (SNSF) [P500-2_235474]
(Vincent Pfenninger). For open access purposes, the authors have applied a CC BY
public copyright license to any author accepted manuscript version arising from
this submission. The authors thank the reviewers for helpful comments on the paper,
and for bringing the particular form of Theorem 2.2 to our attention.
article_number: e70464
article_processing_charge: Yes (in subscription journal)
article_type: original
arxiv: 1
author:
- first_name: Michael
full_name: Anastos, Michael
id: 0b2a4358-bb35-11ec-b7b9-e3279b593dbb
last_name: Anastos
- first_name: Joshua
full_name: Erde, Joshua
last_name: Erde
- first_name: Mihyun
full_name: Kang, Mihyun
last_name: Kang
- first_name: Vincent
full_name: Pfenninger, Vincent
last_name: Pfenninger
citation:
ama: Anastos M, Erde J, Kang M, Pfenninger V. A short proof of a central limit theorem
for the order of the giant component and k-core. Bulletin of the London Mathematical
Society. 2026;58(8). doi:10.1112/blms.70464
apa: Anastos, M., Erde, J., Kang, M., & Pfenninger, V. (2026). A short proof
of a central limit theorem for the order of the giant component and k-core. Bulletin
of the London Mathematical Society. Wiley. https://doi.org/10.1112/blms.70464
chicago: Anastos, Michael, Joshua Erde, Mihyun Kang, and Vincent Pfenninger. “A
Short Proof of a Central Limit Theorem for the Order of the Giant Component and
K-Core.” Bulletin of the London Mathematical Society. Wiley, 2026. https://doi.org/10.1112/blms.70464.
ieee: M. Anastos, J. Erde, M. Kang, and V. Pfenninger, “A short proof of a central
limit theorem for the order of the giant component and k-core,” Bulletin of
the London Mathematical Society, vol. 58, no. 8. Wiley, 2026.
ista: Anastos M, Erde J, Kang M, Pfenninger V. 2026. A short proof of a central
limit theorem for the order of the giant component and k-core. Bulletin of the
London Mathematical Society. 58(8), e70464.
mla: Anastos, Michael, et al. “A Short Proof of a Central Limit Theorem for the
Order of the Giant Component and K-Core.” Bulletin of the London Mathematical
Society, vol. 58, no. 8, e70464, Wiley, 2026, doi:10.1112/blms.70464.
short: M. Anastos, J. Erde, M. Kang, V. Pfenninger, Bulletin of the London Mathematical
Society 58 (2026).
das_tickbox: '0'
date_created: 2026-08-23T22:01:47Z
date_published: 2026-08-01T00:00:00Z
date_updated: 2026-09-07T13:56:17Z
day: '01'
ddc:
- '510'
department:
- _id: MaKw
doi: 10.1112/blms.70464
external_id:
arxiv:
- '2506.11651'
file:
- access_level: open_access
checksum: b4b21f05c3fc62fde243a5ddd46cef49
content_type: application/pdf
creator: dernst
date_created: 2026-09-07T13:53:26Z
date_updated: 2026-09-07T13:53:26Z
file_id: '22845'
file_name: 2026_BulletinLondonMathSoc_Anastos.pdf
file_size: 248641
relation: main_file
success: 1
file_date_updated: 2026-09-07T13:53:26Z
fulldoi: https://doi.org/10.1112/blms.70464
has_accepted_license: '1'
intvolume: ' 58'
issue: '8'
language:
- iso: eng
license: https://creativecommons.org/licenses/by/4.0/
mathsc:
- 05C80
- 60F05
month: '08'
oa: 1
oa_version: Published Version
project:
- _id: 8f906bd2-16d5-11f0-9cad-e07be8aa9ac9
grant_number: ESP3863424
name: Combinatorial Optimisation Problems on Sparse Random Graphs
publication: Bulletin of the London Mathematical Society
publication_identifier:
eissn:
- 1469-2120
issn:
- 0024-6093
publication_status: published
publisher: Wiley
quality_controlled: '1'
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: no
title: A short proof of a central limit theorem for the order of the giant component
and k-core
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: 58
year: '2026'
...
---
OA_place: publisher
OA_type: hybrid
_id: '18478'
abstract:
- lang: eng
text: For a given graph G=(V,E), we define its \emph{nth subdivision} as the graph
obtained from G by replacing every edge by a path of length n. We also define
the \emph{mth power} of G as the graph on vertex set V where we connect every
pair of vertices at distance at most m in G. In this paper, we study the chromatic
number of powers of subdivisions of graphs and resolve the case m=n asymptotically.
In particular, our result confirms a conjecture of Mozafari-Nia and Iradmusa in
the case m=n=3 in a strong sense.
acknowledgement: "This work was initiated at the annual workshop of the Combinatorics
and Graph Theory group of Freie Universität Berlin in Wilhelmsaue in September 2023.
The authors would like to thank the institution for enabling this research. Finally,
the fourth author would like to thank Tibor Szabó and the Combinatorics and Graph
Theory group at Freie Universität Berlin for their hospitality during the research
visit. Additionally, we thank Moharram Iradmusa for bringing the papers [5], [7]
to our attention. Finally, we thank the anonymous referees for their suggestions
on the manuscript, which have improved the quality of the document.\r\nM.A.: This
project has received funding from the European Union’s Horizon 2020 research and
innovation programme under the Marie Skłodowska-Curie grant agreement No 101034413
.\r\nS.B.: The research leading to these results was supported by EPSRC, UK, grant
no. EP/V048287/1. There are no additional data beyond that contained within the
main manuscript.\r\nS.R.: Funded by the Deutsche Forschungsgemeinschaft (DFG, German
Research Foundation) under Germany’s Excellence Strategy – The Berlin Mathematics
Research Center MATH+ (EXC-2046/1, project ID: 390685689).\r\nJ.R. acknowledges
the support of the Grant PID2020-113082GB-I00 funded by MICIU/AEI/10.13039/501100011033,
Spain, and the Severo Ochoa and María de Maeztu Program for Centers and Units of
Excellence in R&D, Spain (CEX2020-001084-M)."
article_processing_charge: Yes (in subscription journal)
article_type: original
arxiv: 1
author:
- first_name: Michael
full_name: Anastos, Michael
id: 0b2a4358-bb35-11ec-b7b9-e3279b593dbb
last_name: Anastos
- first_name: Simona
full_name: Boyadzhiyska, Simona
last_name: Boyadzhiyska
- first_name: Silas
full_name: Rathke, Silas
last_name: Rathke
- first_name: Juanjo
full_name: Rué, Juanjo
last_name: Rué
citation:
ama: Anastos M, Boyadzhiyska S, Rathke S, Rué J. On the chromatic number of powers
of subdivisions of graphs. Discrete Applied Mathematics. 2025;360:506-511.
doi:10.1016/j.dam.2024.10.002
apa: Anastos, M., Boyadzhiyska, S., Rathke, S., & Rué, J. (2025). On the chromatic
number of powers of subdivisions of graphs. Discrete Applied Mathematics.
Elsevier. https://doi.org/10.1016/j.dam.2024.10.002
chicago: Anastos, Michael, Simona Boyadzhiyska, Silas Rathke, and Juanjo Rué. “On
the Chromatic Number of Powers of Subdivisions of Graphs.” Discrete Applied
Mathematics. Elsevier, 2025. https://doi.org/10.1016/j.dam.2024.10.002.
ieee: M. Anastos, S. Boyadzhiyska, S. Rathke, and J. Rué, “On the chromatic number
of powers of subdivisions of graphs,” Discrete Applied Mathematics, vol.
360. Elsevier, pp. 506–511, 2025.
ista: Anastos M, Boyadzhiyska S, Rathke S, Rué J. 2025. On the chromatic number
of powers of subdivisions of graphs. Discrete Applied Mathematics. 360, 506–511.
mla: Anastos, Michael, et al. “On the Chromatic Number of Powers of Subdivisions
of Graphs.” Discrete Applied Mathematics, vol. 360, Elsevier, 2025, pp.
506–11, doi:10.1016/j.dam.2024.10.002.
short: M. Anastos, S. Boyadzhiyska, S. Rathke, J. Rué, Discrete Applied Mathematics
360 (2025) 506–511.
corr_author: '1'
date_created: 2024-10-27T23:01:44Z
date_published: 2025-01-15T00:00:00Z
date_updated: 2025-04-14T07:54:56Z
day: '15'
ddc:
- '510'
department:
- _id: MaKw
doi: 10.1016/j.dam.2024.10.002
ec_funded: 1
external_id:
arxiv:
- '2404.05542'
isi:
- '001343647000001'
file:
- access_level: open_access
checksum: bd20a13e56b3ea01daf5e7aca5247c60
content_type: application/pdf
creator: dernst
date_created: 2025-01-13T09:25:59Z
date_updated: 2025-01-13T09:25:59Z
file_id: '18836'
file_name: 2025_DiscreteApplMath_Anastos.pdf
file_size: 441060
relation: main_file
success: 1
file_date_updated: 2025-01-13T09:25:59Z
fulldoi: https://doi.org/10.1016/j.dam.2024.10.002
has_accepted_license: '1'
intvolume: ' 360'
isi: 1
language:
- iso: eng
month: '01'
oa: 1
oa_version: Published Version
page: 506-511
project:
- _id: fc2ed2f7-9c52-11eb-aca3-c01059dda49c
call_identifier: H2020
grant_number: '101034413'
name: 'IST-BRIDGE: International postdoctoral program'
publication: Discrete Applied Mathematics
publication_identifier:
issn:
- 0166-218X
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: On the chromatic number of powers of subdivisions of 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: 360
year: '2025'
...
---
OA_place: publisher
OA_type: gold
_id: '19433'
abstract:
- lang: eng
text: An ordered r-matching is an r-uniform hypergraph matching equipped with an
ordering on its vertices. These objects can be viewed as natural generalisations
of r-dimensional orders. The theory of ordered 2-matchings is well developed and
has connections and applications to extremal and enumerative combinatorics, probability
and geometry. On the other hand, in the case r≥3 much less is known, largely
due to a lack of powerful bijective tools. Recently, Dudek, Grytczuk and Ruciński
made some first steps towards a general theory of ordered r-matchings, and in
this paper we substantially improve several of their results and introduce some
new directions of study. Many intriguing open questions remain.
acknowledgement: We would like to thank Timo Seppäläinen for some illuminating discussion
about random high-dimensional orders and for bringing our attention to [59]. We
would also like to thank the referees for helpful feedback. Michael Anastos is supported
by the European Union’s Horizon 2020 research and innovation programme under the
Marie Skłodowska-Curie grant agreement No. 101034413. Matthew Kwan is supported
by ERC Starting Grant ‘RANDSTRUCT’ No. 101076777, also funded by the European Union.
Zhihan Jin and Benny Sudakov are supported by SNSF grant 200021-228014.
article_number: e55
article_processing_charge: Yes
article_type: original
arxiv: 1
author:
- first_name: Michael
full_name: Anastos, Michael
id: 0b2a4358-bb35-11ec-b7b9-e3279b593dbb
last_name: Anastos
- first_name: Zhihan
full_name: Jin, Zhihan
last_name: Jin
- first_name: Matthew Alan
full_name: Kwan, Matthew Alan
id: 5fca0887-a1db-11eb-95d1-ca9d5e0453b3
last_name: Kwan
orcid: 0000-0002-4003-7567
- first_name: Benny
full_name: Sudakov, Benny
last_name: Sudakov
citation:
ama: Anastos M, Jin Z, Kwan MA, Sudakov B. Extremal, enumerative and probabilistic
results on ordered hypergraph matchings. Forum of Mathematics, Sigma. 2025;13.
doi:10.1017/fms.2024.144
apa: Anastos, M., Jin, Z., Kwan, M. A., & Sudakov, B. (2025). Extremal, enumerative
and probabilistic results on ordered hypergraph matchings. Forum of Mathematics,
Sigma. Cambridge University Press. https://doi.org/10.1017/fms.2024.144
chicago: Anastos, Michael, Zhihan Jin, Matthew Alan Kwan, and Benny Sudakov. “Extremal,
Enumerative and Probabilistic Results on Ordered Hypergraph Matchings.” Forum
of Mathematics, Sigma. Cambridge University Press, 2025. https://doi.org/10.1017/fms.2024.144.
ieee: M. Anastos, Z. Jin, M. A. Kwan, and B. Sudakov, “Extremal, enumerative and
probabilistic results on ordered hypergraph matchings,” Forum of Mathematics,
Sigma, vol. 13. Cambridge University Press, 2025.
ista: Anastos M, Jin Z, Kwan MA, Sudakov B. 2025. Extremal, enumerative and probabilistic
results on ordered hypergraph matchings. Forum of Mathematics, Sigma. 13, e55.
mla: Anastos, Michael, et al. “Extremal, Enumerative and Probabilistic Results on
Ordered Hypergraph Matchings.” Forum of Mathematics, Sigma, vol. 13, e55,
Cambridge University Press, 2025, doi:10.1017/fms.2024.144.
short: M. Anastos, Z. Jin, M.A. Kwan, B. Sudakov, Forum of Mathematics, Sigma 13
(2025).
corr_author: '1'
date_created: 2025-03-20T12:59:14Z
date_published: 2025-03-14T00:00:00Z
date_updated: 2025-09-30T11:18:57Z
day: '14'
ddc:
- '510'
department:
- _id: MaKw
doi: 10.1017/fms.2024.144
ec_funded: 1
external_id:
arxiv:
- '2308.12268'
isi:
- '001444429200001'
file:
- access_level: open_access
checksum: f396270ad78c1ed67095c8e5a66fca26
content_type: application/pdf
creator: dernst
date_created: 2025-04-03T11:24:35Z
date_updated: 2025-04-03T11:24:35Z
file_id: '19468'
file_name: 2025_ForumMathSigma_Anastos.pdf
file_size: 630297
relation: main_file
success: 1
file_date_updated: 2025-04-03T11:24:35Z
fulldoi: https://doi.org/10.1017/fms.2024.144
has_accepted_license: '1'
intvolume: ' 13'
isi: 1
language:
- iso: eng
month: '03'
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: Forum of Mathematics, Sigma
publication_identifier:
issn:
- 2050-5094
publication_status: published
publisher: Cambridge University Press
quality_controlled: '1'
scopus_import: '1'
status: public
title: Extremal, enumerative and probabilistic results on ordered hypergraph matchings
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: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 13
year: '2025'
...
---
OA_place: publisher
OA_type: hybrid
_id: '19440'
abstract:
- lang: eng
text: Let μ(G) denote the minimum number of edges whose addition to G results in
a Hamiltonian graph, and let μ^(G) denote the minimum number of edges whose addition
to G results in a pancyclic graph. We study the distributions of μ(G),μ^(G) in
the context of binomial random graphs. Letting d=d(n):=n⋅p, we prove that there
exists a function f:R+→[0,1] of order f(d)=12de−d+e−d+O(d6e−3d) such that, if
G∼G(n,p) with 20≤d(n)≤0.4logn, then with high probability μ(G)=(1+o(1))⋅f(d)⋅n.
Let ni(G) denote the number of degree i vertices in G. A trivial lower bound on
μ(G) is given by the expression n0(G)+⌈12n1(G)⌉. In the denser regime of random
graphs, we show that if np−13logn−2loglogn→∞ and G∼G(n,p) then, with high probability,
μ(G)=n0(G)+⌈12n1(G)⌉. For completion to pancyclicity, we show that if G∼G(n,p)
and np≥20 then, with high probability, μ^(G)=μ(G). Finally, we present a polynomial
time algorithm such that, if G∼G(n,p) and np≥20, then, with high probability,
the algorithm returns a set of edges of size μ(G) whose addition to G results
in a pancyclic (and therefore also Hamiltonian) graph.
acknowledgement: The authors would like to express their thanks to the referees of
the article for their valuable input towards improving the presentation of our result.
This project has received funding from the European Union's Horizon 2020 research
and innovation programme under the Marie Skłodowska-Curie grant agreement No 101034413.
article_number: e21286
article_processing_charge: Yes (in subscription journal)
article_type: original
arxiv: 1
author:
- first_name: Yahav
full_name: Alon, Yahav
last_name: Alon
- first_name: Michael
full_name: Anastos, Michael
id: 0b2a4358-bb35-11ec-b7b9-e3279b593dbb
last_name: Anastos
citation:
ama: Alon Y, Anastos M. The completion numbers of hamiltonicity and pancyclicity
in random graphs. Random Structures and Algorithms. 2025;66(2). doi:10.1002/rsa.21286
apa: Alon, Y., & Anastos, M. (2025). The completion numbers of hamiltonicity
and pancyclicity in random graphs. Random Structures and Algorithms. Wiley.
https://doi.org/10.1002/rsa.21286
chicago: Alon, Yahav, and Michael Anastos. “The Completion Numbers of Hamiltonicity
and Pancyclicity in Random Graphs.” Random Structures and Algorithms. Wiley,
2025. https://doi.org/10.1002/rsa.21286.
ieee: Y. Alon and M. Anastos, “The completion numbers of hamiltonicity and pancyclicity
in random graphs,” Random Structures and Algorithms, vol. 66, no. 2. Wiley,
2025.
ista: Alon Y, Anastos M. 2025. The completion numbers of hamiltonicity and pancyclicity
in random graphs. Random Structures and Algorithms. 66(2), e21286.
mla: Alon, Yahav, and Michael Anastos. “The Completion Numbers of Hamiltonicity
and Pancyclicity in Random Graphs.” Random Structures and Algorithms, vol.
66, no. 2, e21286, Wiley, 2025, doi:10.1002/rsa.21286.
short: Y. Alon, M. Anastos, Random Structures and Algorithms 66 (2025).
date_created: 2025-03-23T23:01:26Z
date_published: 2025-03-01T00:00:00Z
date_updated: 2025-09-30T11:15:41Z
day: '01'
ddc:
- '510'
department:
- _id: MaKw
doi: 10.1002/rsa.21286
ec_funded: 1
external_id:
arxiv:
- '2304.03710'
isi:
- '001420226800001'
file:
- access_level: open_access
checksum: 6067747e805fa356d560dc45f2a89918
content_type: application/pdf
creator: dernst
date_created: 2025-03-25T11:46:27Z
date_updated: 2025-03-25T11:46:27Z
file_id: '19459'
file_name: 2025_RandomStruc_Alon.pdf
file_size: 549236
relation: main_file
success: 1
file_date_updated: 2025-03-25T11:46:27Z
fulldoi: https://doi.org/10.1002/rsa.21286
has_accepted_license: '1'
intvolume: ' 66'
isi: 1
issue: '2'
language:
- iso: eng
license: https://creativecommons.org/licenses/by-nc/4.0/
month: '03'
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'
publication: Random Structures and Algorithms
publication_identifier:
eissn:
- 1098-2418
issn:
- 1042-9832
publication_status: published
publisher: Wiley
quality_controlled: '1'
scopus_import: '1'
status: public
title: The completion numbers of hamiltonicity and pancyclicity in random graphs
tmp:
image: /images/cc_by_nc.png
legal_code_url: https://creativecommons.org/licenses/by-nc/4.0/legalcode
name: Creative Commons Attribution-NonCommercial 4.0 International (CC BY-NC 4.0)
short: CC BY-NC (4.0)
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 66
year: '2025'
...
---
OA_place: repository
OA_type: green
_id: '19798'
abstract:
- lang: eng
text: In an n×n array filled with symbols, a transversal is a collection of entries
with distinct rows, columns and symbols. In this note we show that if no symbol
appears more than βn times, the array contains a transversal of size (1−β/4−o(1))n
. In particular, if the array is filled with n symbols, each appearing n times
(an equi- n square), we get transversals of size (3/4−o(1))n. Moreover, our
proof gives a deterministic algorithm with polynomial running time, that finds
these transversals.
acknowledgement: "We are very grateful to Matthew Kwan and Alp Müyesser with whom
we had many interesting discussions leading to the results of this note. We also
thank the anonymous reviewers for their suggestions improving the presentation of
this note.\r\n\r\nMA was supported by the Austrian Science Fund (FWF) [10.55776/ESP3863424]
and by the European Union's Horizon 2020 research and innovation programme under
the Marie Skłodowska-Curie grant—project number 101034413. PM was supported by the
European Union's Horizon Europe Marie Skłodowska-Curie grant RAND-COMB-DESIGN—project
number 101106032."
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Michael
full_name: Anastos, Michael
id: 0b2a4358-bb35-11ec-b7b9-e3279b593dbb
last_name: Anastos
- first_name: Patrick
full_name: Morris, Patrick
last_name: Morris
citation:
ama: Anastos M, Morris P. A note on finding large transversals efficiently. Journal
of Combinatorial Designs. 2025;33(9):338-342. doi:10.1002/jcd.21990
apa: Anastos, M., & Morris, P. (2025). A note on finding large transversals
efficiently. Journal of Combinatorial Designs. Wiley. https://doi.org/10.1002/jcd.21990
chicago: Anastos, Michael, and Patrick Morris. “A Note on Finding Large Transversals
Efficiently.” Journal of Combinatorial Designs. Wiley, 2025. https://doi.org/10.1002/jcd.21990.
ieee: M. Anastos and P. Morris, “A note on finding large transversals efficiently,”
Journal of Combinatorial Designs, vol. 33, no. 9. Wiley, pp. 338–342, 2025.
ista: Anastos M, Morris P. 2025. A note on finding large transversals efficiently.
Journal of Combinatorial Designs. 33(9), 338–342.
mla: Anastos, Michael, and Patrick Morris. “A Note on Finding Large Transversals
Efficiently.” Journal of Combinatorial Designs, vol. 33, no. 9, Wiley,
2025, pp. 338–42, doi:10.1002/jcd.21990.
short: M. Anastos, P. Morris, Journal of Combinatorial Designs 33 (2025) 338–342.
date_created: 2025-06-08T22:01:23Z
date_published: 2025-09-01T00:00:00Z
date_updated: 2025-12-30T08:37:37Z
day: '01'
department:
- _id: MaKw
doi: 10.1002/jcd.21990
ec_funded: 1
external_id:
arxiv:
- '2412.05891'
isi:
- '001495472300001'
fulldoi: https://doi.org/10.1002/jcd.21990
intvolume: ' 33'
isi: 1
issue: '9'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2412.05891
month: '09'
oa: 1
oa_version: Preprint
page: 338-342
project:
- _id: 8f906bd2-16d5-11f0-9cad-e07be8aa9ac9
grant_number: ESP3863424
name: Combinatorial Optimisation Problems on Sparse Random Graphs
- _id: fc2ed2f7-9c52-11eb-aca3-c01059dda49c
call_identifier: H2020
grant_number: '101034413'
name: 'IST-BRIDGE: International postdoctoral program'
publication: Journal of Combinatorial Designs
publication_identifier:
eissn:
- 1520-6610
issn:
- 1063-8539
publication_status: published
publisher: Wiley
quality_controlled: '1'
scopus_import: '1'
status: public
title: A note on finding large transversals efficiently
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 33
year: '2025'
...
---
OA_place: publisher
OA_type: hybrid
_id: '20007'
abstract:
- lang: eng
text: 'There is no known polynomial-time algorithm for graph isomorphism testing,
but elementary combinatorial “refinement” algorithms seem to be very efficient
in practice. Some philosophical justification for this phenomenon is provided
by a classical theorem of Babai, Erdős and Selkow: an extremely simple polynomial-time
combinatorial algorithm (variously known as “naïve refinement”, “naïve vertex
classification”, “colour refinement” or the “1-dimensional Weisfeiler–Leman algorithm”)
yields a so-called canonical labelling scheme for “almost all graphs”. More precisely,
for a typical outcome of a random graph G(n,1/2), this simple combinatorial algorithm
assigns labels to vertices in a way that easily permits isomorphism-testing against
any other graph.'
acknowledgement: All authors were supported by ERC Starting Grant “RANDSTRUCT” No.
101076777. Michael Anastos was also supported in part by the Austrian Science Fund
(FWF)[10.55776/ESP3863424] and by the European Union’s Horizon 2020 research and
innovation programme under the Marie Skłodowska-Curie grant agreement No. 101034413.
For Open Access purposes, the authors have applied a CC BY public copyright license
to any author accepted manuscript version arising from this submission.
article_processing_charge: Yes (via OA deal)
arxiv: 1
author:
- first_name: Michael
full_name: Anastos, Michael
id: 0b2a4358-bb35-11ec-b7b9-e3279b593dbb
last_name: Anastos
- first_name: Matthew Alan
full_name: Kwan, Matthew Alan
id: 5fca0887-a1db-11eb-95d1-ca9d5e0453b3
last_name: Kwan
orcid: 0000-0002-4003-7567
- first_name: Benjamin
full_name: Moore, Benjamin
id: 6dc1a1be-bf1c-11ed-8d2b-d044840f49d6
last_name: Moore
citation:
ama: 'Anastos M, Kwan MA, Moore B. Smoothed analysis for graph isomorphism. In:
Proceedings of the 57th Annual ACM Symposium on Theory of Computing. Association
for Computing Machinery; 2025:2098-2106. doi:10.1145/3717823.3718173'
apa: 'Anastos, M., Kwan, M. A., & Moore, B. (2025). Smoothed analysis for graph
isomorphism. In Proceedings of the 57th Annual ACM Symposium on Theory of Computing
(pp. 2098–2106). Prague, Czechia: Association for Computing Machinery. https://doi.org/10.1145/3717823.3718173'
chicago: Anastos, Michael, Matthew Alan Kwan, and Benjamin Moore. “Smoothed Analysis
for Graph Isomorphism.” In Proceedings of the 57th Annual ACM Symposium on
Theory of Computing, 2098–2106. Association for Computing Machinery, 2025.
https://doi.org/10.1145/3717823.3718173.
ieee: M. Anastos, M. A. Kwan, and B. Moore, “Smoothed analysis for graph isomorphism,”
in Proceedings of the 57th Annual ACM Symposium on Theory of Computing,
Prague, Czechia, 2025, pp. 2098–2106.
ista: 'Anastos M, Kwan MA, Moore B. 2025. Smoothed analysis for graph isomorphism.
Proceedings of the 57th Annual ACM Symposium on Theory of Computing. STOC: Symposium
on Theory of Computing, 2098–2106.'
mla: Anastos, Michael, et al. “Smoothed Analysis for Graph Isomorphism.” Proceedings
of the 57th Annual ACM Symposium on Theory of Computing, Association for Computing
Machinery, 2025, pp. 2098–106, doi:10.1145/3717823.3718173.
short: M. Anastos, M.A. Kwan, B. Moore, in:, Proceedings of the 57th Annual ACM
Symposium on Theory of Computing, Association for Computing Machinery, 2025, pp.
2098–2106.
conference:
end_date: 2025-06-27
location: Prague, Czechia
name: 'STOC: Symposium on Theory of Computing'
start_date: 2025-06-23
corr_author: '1'
date_created: 2025-07-13T22:01:23Z
date_published: 2025-06-15T00:00:00Z
date_updated: 2025-07-14T06:33:50Z
day: '15'
ddc:
- '000'
department:
- _id: MaKw
doi: 10.1145/3717823.3718173
ec_funded: 1
external_id:
arxiv:
- '2410.06095'
file:
- access_level: open_access
checksum: cf0ab9cb9c6abda188de13dc3f9a4c9b
content_type: application/pdf
creator: dernst
date_created: 2025-07-14T06:13:10Z
date_updated: 2025-07-14T06:13:10Z
file_id: '20012'
file_name: 2025_STOC_Anastos.pdf
file_size: 706445
relation: main_file
success: 1
file_date_updated: 2025-07-14T06:13:10Z
fulldoi: https://doi.org/10.1145/3717823.3718173
has_accepted_license: '1'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 2098-2106
project:
- _id: bd95085b-d553-11ed-ba76-e55d3349be45
grant_number: '101076777'
name: Randomness and structure in combinatorics
- _id: fc2ed2f7-9c52-11eb-aca3-c01059dda49c
call_identifier: H2020
grant_number: '101034413'
name: 'IST-BRIDGE: International postdoctoral program'
- _id: 8f906bd2-16d5-11f0-9cad-e07be8aa9ac9
grant_number: ESP3863424
name: Combinatorial Optimisation Problems on Sparse Random Graphs
publication: Proceedings of the 57th Annual ACM Symposium on Theory of Computing
publication_identifier:
isbn:
- '9798400715105'
issn:
- 0737-8017
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: Smoothed analysis for graph isomorphism
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: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2025'
...
---
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.
Journal of the London Mathematical Society. 2024;110(6). doi:10.1112/jlms.70010
apa: Anastos, M., Cooley, O., Kang, M., & Kwan, M. A. (2024). Partitioning problems
via random processes. Journal of the London Mathematical Society. Wiley.
https://doi.org/10.1112/jlms.70010
chicago: Anastos, Michael, Oliver Cooley, Mihyun Kang, and Matthew Alan Kwan. “Partitioning
Problems via Random Processes.” Journal of the London Mathematical Society.
Wiley, 2024. https://doi.org/10.1112/jlms.70010.
ieee: M. Anastos, O. Cooley, M. Kang, and M. A. Kwan, “Partitioning problems via
random processes,” Journal of the London Mathematical Society, 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.” Journal
of the London Mathematical Society, vol. 110, no. 6, e70010, Wiley, 2024,
doi:10.1112/jlms.70010.
short: M. Anastos, O. Cooley, M. Kang, M.A. Kwan, Journal of the London Mathematical
Society 110 (2024).
corr_author: '1'
das_tickbox: '0'
date_created: 2024-11-24T23:01:48Z
date_published: 2024-12-01T00:00:00Z
date_updated: 2026-10-16T10:12:41Z
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
fulldoi: https://doi.org/10.1112/jlms.70010
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'
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: yes
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: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 110
year: '2024'
...
---
DOAJ_listed: '1'
OA_place: repository
OA_type: gold
_id: '18655'
abstract:
- lang: eng
text: "Let Qd be the d-dimensional binary hypercube. We say that P={v1,…,vk} is
an increasing path of length k−1 in Qd, if for every i∈[k−1] the edge vivi+1 is
obtained by switching some zero coordinate in vi to a one coordinate in vi+1.\r\nForm
a random subgraph Qdp by retaining each edge in E(Qd) independently with probability
p. We show that there is a phase transition with respect to the length of a longest
increasing path around p=ed. Let α be a constant and let p=αd. When αe, whp there is a path of length d−2 in
Qdp, and in fact, whether it is of length d−2,d−1, or d depends on whether the
all-zero and all-one vertices percolate or not."
acknowledgement: "Research supported by the European Union’s Horizon 2020 research
and innovation programme under the Marie Skłodowska-Curie grant agreement No. 101034413.\r\nThe
authors wish to thank Ross Pinsky for his comments on an earlier version of the
paper, and for bringing reference [12] to our attention. The authors are grateful
to the anonymous referees for their helpful comments and suggestions."
article_number: '70'
article_processing_charge: Yes
article_type: original
arxiv: 1
author:
- first_name: Michael
full_name: Anastos, Michael
id: 0b2a4358-bb35-11ec-b7b9-e3279b593dbb
last_name: Anastos
- first_name: Sahar
full_name: Diskin, Sahar
last_name: Diskin
- first_name: Dor
full_name: Elboim, Dor
last_name: Elboim
- first_name: Michael
full_name: Krivelevich, Michael
last_name: Krivelevich
citation:
ama: Anastos M, Diskin S, Elboim D, Krivelevich M. Climbing up a random subgraph
of the hypercube. Electronic Communications in Probability. 2024;29. doi:10.1214/24-ECP639
apa: Anastos, M., Diskin, S., Elboim, D., & Krivelevich, M. (2024). Climbing
up a random subgraph of the hypercube. Electronic Communications in Probability.
Duke University Press. https://doi.org/10.1214/24-ECP639
chicago: Anastos, Michael, Sahar Diskin, Dor Elboim, and Michael Krivelevich. “Climbing
up a Random Subgraph of the Hypercube.” Electronic Communications in Probability.
Duke University Press, 2024. https://doi.org/10.1214/24-ECP639.
ieee: M. Anastos, S. Diskin, D. Elboim, and M. Krivelevich, “Climbing up a random
subgraph of the hypercube,” Electronic Communications in Probability, vol.
29. Duke University Press, 2024.
ista: Anastos M, Diskin S, Elboim D, Krivelevich M. 2024. Climbing up a random subgraph
of the hypercube. Electronic Communications in Probability. 29, 70.
mla: Anastos, Michael, et al. “Climbing up a Random Subgraph of the Hypercube.”
Electronic Communications in Probability, vol. 29, 70, Duke University
Press, 2024, doi:10.1214/24-ECP639.
short: M. Anastos, S. Diskin, D. Elboim, M. Krivelevich, Electronic Communications
in Probability 29 (2024).
corr_author: '1'
das_tickbox: '0'
date_created: 2024-12-15T23:01:51Z
date_published: 2024-11-24T00:00:00Z
date_updated: 2026-10-16T10:13:13Z
day: '24'
ddc:
- '510'
department:
- _id: MaKw
doi: 10.1214/24-ECP639
ec_funded: 1
external_id:
arxiv:
- '2311.16631'
isi:
- '001356019700001'
file:
- access_level: open_access
checksum: 307a9d049325e6ca9bfe8b4a1f275983
content_type: application/pdf
creator: dernst
date_created: 2024-12-16T07:33:34Z
date_updated: 2024-12-16T07:33:34Z
file_id: '18657'
file_name: 2024_ElectrCommProbability_Anastos.pdf
file_size: 530169
relation: main_file
success: 1
file_date_updated: 2024-12-16T07:33:34Z
fulldoi: https://doi.org/10.1214/24-ECP639
has_accepted_license: '1'
intvolume: ' 29'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2311.16631
month: '11'
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'
publication: Electronic Communications in Probability
publication_identifier:
eissn:
- 1083-589X
publication_status: published
publisher: Duke University Press
quality_controlled: '1'
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: yes
title: Climbing up a random subgraph of the hypercube
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: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 29
year: '2024'
...
---
OA_place: repository
OA_type: green
_id: '18702'
abstract:
- lang: eng
text: 'In this work we prove lower bounds on the (communication) cost of maintaining
a shared key among a dynamic group of users. Being “dynamic” means one can add
and remove users from the group. This captures important protocols like multicast
encryption (ME) and continuous group-key agreement (CGKA), which is the primitive
underlying many group messaging applications. We prove our bounds in a combinatorial
setting where the state of the protocol progresses in rounds. The state of the
protocol in each round is captured by a set system, with each of its elements
specifying a set of users who share a secret key. We show this combinatorial model
implies bounds in symbolic models for ME and CGKA that capture, as building blocks,
PRGs, PRFs, dual PRFs, secret sharing, and symmetric encryption in the setting
of ME, and PRGs, PRFs, dual PRFs, secret sharing, public-key encryption, and key-updatable
public-key encryption in the setting of CGKA. The models are related to the ones
used by Micciancio and Panjwani (Eurocrypt’04) and Bienstock et al. (TCC’20) to
analyze ME and CGKA, respectively. We prove – using the Bollobás’ Set Pairs Inequality
– that the cost (number of uploaded ciphertexts) for replacing a set of d users
in a group of size n is Ω(dln(n/d)). Our lower bound is asymptotically tight and
both improves on a bound of Ω(d) by Bienstock et al. (TCC’20), and generalizes
a result by Micciancio and Panjwani (Eurocrypt’04), who proved a lower bound of
Ω(log(n)) for d=1. '
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Michael
full_name: Anastos, Michael
id: 0b2a4358-bb35-11ec-b7b9-e3279b593dbb
last_name: Anastos
- first_name: Benedikt
full_name: Auerbach, Benedikt
id: D33D2B18-E445-11E9-ABB7-15F4E5697425
last_name: Auerbach
orcid: 0000-0002-7553-6606
- first_name: Mirza Ahad
full_name: Baig, Mirza Ahad
id: 3EDE6DE4-AA5A-11E9-986D-341CE6697425
last_name: Baig
- first_name: Miguel
full_name: Cueto Noval, Miguel
id: ffc563a3-f6e0-11ea-865d-e3cce03d17cc
last_name: Cueto Noval
orcid: 0000-0002-2505-4246
- first_name: Matthew Alan
full_name: Kwan, Matthew Alan
id: 5fca0887-a1db-11eb-95d1-ca9d5e0453b3
last_name: Kwan
orcid: 0000-0002-4003-7567
- first_name: Guillermo
full_name: Pascual Perez, Guillermo
id: 2D7ABD02-F248-11E8-B48F-1D18A9856A87
last_name: Pascual Perez
orcid: 0000-0001-8630-415X
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
citation:
ama: 'Anastos M, Auerbach B, Baig MA, et al. The cost of maintaining keys in dynamic
groups with applications to multicast encryption and group messaging. In: 22nd
International Conference on Theory of Cryptography. Vol 15364. Springer Nature;
2024:413-443. doi:10.1007/978-3-031-78011-0_14'
apa: 'Anastos, M., Auerbach, B., Baig, M. A., Cueto Noval, M., Kwan, M. A., Pascual
Perez, G., & Pietrzak, K. Z. (2024). The cost of maintaining keys in dynamic
groups with applications to multicast encryption and group messaging. In 22nd
International Conference on Theory of Cryptography (Vol. 15364, pp. 413–443).
Milan, Italy: Springer Nature. https://doi.org/10.1007/978-3-031-78011-0_14'
chicago: Anastos, Michael, Benedikt Auerbach, Mirza Ahad Baig, Miguel Cueto Noval,
Matthew Alan Kwan, Guillermo Pascual Perez, and Krzysztof Z Pietrzak. “The Cost
of Maintaining Keys in Dynamic Groups with Applications to Multicast Encryption
and Group Messaging.” In 22nd International Conference on Theory of Cryptography,
15364:413–43. Springer Nature, 2024. https://doi.org/10.1007/978-3-031-78011-0_14.
ieee: M. Anastos et al., “The cost of maintaining keys in dynamic groups
with applications to multicast encryption and group messaging,” in 22nd International
Conference on Theory of Cryptography, Milan, Italy, 2024, vol. 15364, pp.
413–443.
ista: 'Anastos M, Auerbach B, Baig MA, Cueto Noval M, Kwan MA, Pascual Perez G,
Pietrzak KZ. 2024. The cost of maintaining keys in dynamic groups with applications
to multicast encryption and group messaging. 22nd International Conference on
Theory of Cryptography. TCC: Theory of Cryptography, LNCS, vol. 15364, 413–443.'
mla: Anastos, Michael, et al. “The Cost of Maintaining Keys in Dynamic Groups with Applications
to Multicast Encryption and Group Messaging.” 22nd International Conference
on Theory of Cryptography, vol. 15364, Springer Nature, 2024, pp. 413–43,
doi:10.1007/978-3-031-78011-0_14.
short: M. Anastos, B. Auerbach, M.A. Baig, M. Cueto Noval, M.A. Kwan, G. Pascual
Perez, K.Z. Pietrzak, in:, 22nd International Conference on Theory of Cryptography,
Springer Nature, 2024, pp. 413–443.
conference:
end_date: 2024-12-06
location: Milan, Italy
name: 'TCC: Theory of Cryptography'
start_date: 2024-12-02
corr_author: '1'
das_tickbox: '0'
date_created: 2024-12-22T23:01:47Z
date_published: 2024-12-02T00:00:00Z
date_updated: 2026-10-16T10:14:41Z
day: '02'
department:
- _id: MaKw
- _id: KrPi
doi: 10.1007/978-3-031-78011-0_14
external_id:
isi:
- '001545628900014'
fulldoi: https://doi.org/10.1007/978-3-031-78011-0_14
intvolume: ' 15364'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2024/1097
month: '12'
oa: 1
oa_version: Preprint
page: 413-443
publication: 22nd International Conference on Theory of Cryptography
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783031780103'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '22664'
relation: dissertation_contains
status: public
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: no
title: The cost of maintaining keys in dynamic groups with applications to multicast
encryption and group messaging
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 15364
year: '2024'
...
---
_id: '13042'
abstract:
- lang: eng
text: Let Lc,n denote the size of the longest cycle in G(n, c/n),c >1 constant. We
show that there exists a continuous function f(c) such that Lc,n/n→f(c) a.s. for
c>20, thus extending a result of Frieze and the author to smaller values of
c. Thereafter, for c>20, we determine the limit of the probability that
G(n, c/n)contains cycles of every length between the length of its shortest and its longest
cycles as n→∞.
acknowledgement: We would like to thank the reviewers for their helpful comments and
remarks.
article_number: P2.21
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Michael
full_name: Anastos, Michael
id: 0b2a4358-bb35-11ec-b7b9-e3279b593dbb
last_name: Anastos
citation:
ama: Anastos M. A note on long cycles in sparse random graphs. Electronic Journal
of Combinatorics. 2023;30(2). doi:10.37236/11471
apa: Anastos, M. (2023). A note on long cycles in sparse random graphs. Electronic
Journal of Combinatorics. Electronic Journal of Combinatorics. https://doi.org/10.37236/11471
chicago: Anastos, Michael. “A Note on Long Cycles in Sparse Random Graphs.” Electronic
Journal of Combinatorics. Electronic Journal of Combinatorics, 2023. https://doi.org/10.37236/11471.
ieee: M. Anastos, “A note on long cycles in sparse random graphs,” Electronic
Journal of Combinatorics, vol. 30, no. 2. Electronic Journal of Combinatorics,
2023.
ista: Anastos M. 2023. A note on long cycles in sparse random graphs. Electronic
Journal of Combinatorics. 30(2), P2.21.
mla: Anastos, Michael. “A Note on Long Cycles in Sparse Random Graphs.” Electronic
Journal of Combinatorics, vol. 30, no. 2, P2.21, Electronic Journal of Combinatorics,
2023, doi:10.37236/11471.
short: M. Anastos, Electronic Journal of Combinatorics 30 (2023).
corr_author: '1'
date_created: 2023-05-21T22:01:05Z
date_published: 2023-05-05T00:00:00Z
date_updated: 2024-10-09T21:05:26Z
day: '05'
ddc:
- '510'
department:
- _id: MaKw
doi: 10.37236/11471
external_id:
arxiv:
- '2105.13828'
isi:
- '000988285500001'
file:
- access_level: open_access
checksum: 6269ed3b3eded6536d3d9d6baad2d5b9
content_type: application/pdf
creator: dernst
date_created: 2023-05-22T07:43:19Z
date_updated: 2023-05-22T07:43:19Z
file_id: '13046'
file_name: 2023_JourCombinatorics_Anastos.pdf
file_size: 448736
relation: main_file
success: 1
file_date_updated: 2023-05-22T07:43:19Z
fulldoi: https://doi.org/10.37236/11471
has_accepted_license: '1'
intvolume: ' 30'
isi: 1
issue: '2'
language:
- iso: eng
month: '05'
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: A note on long cycles in sparse 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: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 30
year: '2023'
...
---
_id: '14319'
abstract:
- lang: eng
text: "We study multigraphs whose edge-sets are the union of three perfect matchings,
M1, M2, and M3. Given such a graph G and any a1; a2; a3 2 N with a1 +a2 +a3 6
n - 2, we show there exists a matching M of G with jM \\ Mij = ai for each i 2
f1; 2; 3g. The bound n - 2 in the theorem is best possible in general. We conjecture
however that if G is bipartite, the same result holds with n - 2 replaced by n
- 1. We give a construction that shows such a result would be tight. We\r\nalso
make a conjecture generalising the Ryser-Brualdi-Stein conjecture with colour\r\nmultiplicities."
acknowledgement: Anastos has received funding from the European Union’s Horizon 2020
research and in-novation programme under the Marie Sk lodowska-Curie grant agreement
No 101034413.Fabian’s research is supported by the Deutsche Forschungsgemeinschaft
(DFG, GermanResearch Foundation) Graduiertenkolleg “Facets of Complexity” (GRK 2434).
article_number: P3.10
article_processing_charge: Yes
article_type: original
arxiv: 1
author:
- first_name: Michael
full_name: Anastos, Michael
id: 0b2a4358-bb35-11ec-b7b9-e3279b593dbb
last_name: Anastos
- first_name: David
full_name: Fabian, David
last_name: Fabian
- first_name: Alp
full_name: Müyesser, Alp
last_name: Müyesser
- first_name: Tibor
full_name: Szabó, Tibor
last_name: Szabó
citation:
ama: Anastos M, Fabian D, Müyesser A, Szabó T. Splitting matchings and the Ryser-Brualdi-Stein
conjecture for multisets. Electronic Journal of Combinatorics. 2023;30(3).
doi:10.37236/11714
apa: Anastos, M., Fabian, D., Müyesser, A., & Szabó, T. (2023). Splitting matchings
and the Ryser-Brualdi-Stein conjecture for multisets. Electronic Journal of
Combinatorics. Electronic Journal of Combinatorics. https://doi.org/10.37236/11714
chicago: Anastos, Michael, David Fabian, Alp Müyesser, and Tibor Szabó. “Splitting
Matchings and the Ryser-Brualdi-Stein Conjecture for Multisets.” Electronic
Journal of Combinatorics. Electronic Journal of Combinatorics, 2023. https://doi.org/10.37236/11714.
ieee: M. Anastos, D. Fabian, A. Müyesser, and T. Szabó, “Splitting matchings and
the Ryser-Brualdi-Stein conjecture for multisets,” Electronic Journal of Combinatorics,
vol. 30, no. 3. Electronic Journal of Combinatorics, 2023.
ista: Anastos M, Fabian D, Müyesser A, Szabó T. 2023. Splitting matchings and the
Ryser-Brualdi-Stein conjecture for multisets. Electronic Journal of Combinatorics.
30(3), P3.10.
mla: Anastos, Michael, et al. “Splitting Matchings and the Ryser-Brualdi-Stein Conjecture
for Multisets.” Electronic Journal of Combinatorics, vol. 30, no. 3, P3.10,
Electronic Journal of Combinatorics, 2023, doi:10.37236/11714.
short: M. Anastos, D. Fabian, A. Müyesser, T. Szabó, Electronic Journal of Combinatorics
30 (2023).
date_created: 2023-09-10T22:01:12Z
date_published: 2023-07-28T00:00:00Z
date_updated: 2025-09-09T12:54:51Z
day: '28'
ddc:
- '510'
department:
- _id: MaKw
doi: 10.37236/11714
ec_funded: 1
external_id:
arxiv:
- '2212.03100'
isi:
- '001042382200001'
file:
- access_level: open_access
checksum: 52c46c8cb329f9aaee9ade01525f317b
content_type: application/pdf
creator: dernst
date_created: 2023-09-15T08:02:09Z
date_updated: 2023-09-15T08:02:09Z
file_id: '14338'
file_name: 2023_elecJournCombinatorics_Anastos.pdf
file_size: 247917
relation: main_file
success: 1
file_date_updated: 2023-09-15T08:02:09Z
fulldoi: https://doi.org/10.37236/11714
has_accepted_license: '1'
intvolume: ' 30'
isi: 1
issue: '3'
language:
- iso: eng
license: https://creativecommons.org/licenses/by-nd/4.0/
month: '07'
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'
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: Splitting matchings and the Ryser-Brualdi-Stein conjecture for multisets
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: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 30
year: '2023'
...
---
_id: '14344'
abstract:
- lang: eng
text: We study the Hamilton cycle problem with input a random graph G ~ G(n,p) in
two different settings. In the first one, G is given to us in the form of randomly
ordered adjacency lists while in the second one, we are given the adjacency matrix
of G. In each of the two settings we derive a deterministic algorithm that w.h.p.
either finds a Hamilton cycle or returns a certificate that such a cycle does
not exist for p = p(n) ≥ 0. The running times of our algorithms are O(n) and respectively,
each being best possible in its own setting.
article_processing_charge: No
arxiv: 1
author:
- first_name: Michael
full_name: Anastos, Michael
id: 0b2a4358-bb35-11ec-b7b9-e3279b593dbb
last_name: Anastos
citation:
ama: 'Anastos M. Fast algorithms for solving the Hamilton cycle problem with high
probability. In: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms.
Vol 2023. Society for Industrial and Applied Mathematics; 2023:2286-2323. doi:10.1137/1.9781611977554.ch88'
apa: 'Anastos, M. (2023). Fast algorithms for solving the Hamilton cycle problem
with high probability. In Proceedings of the Annual ACM-SIAM Symposium on Discrete
Algorithms (Vol. 2023, pp. 2286–2323). Florence, Italy: Society for Industrial
and Applied Mathematics. https://doi.org/10.1137/1.9781611977554.ch88'
chicago: Anastos, Michael. “Fast Algorithms for Solving the Hamilton Cycle Problem
with High Probability.” In Proceedings of the Annual ACM-SIAM Symposium on
Discrete Algorithms, 2023:2286–2323. Society for Industrial and Applied Mathematics,
2023. https://doi.org/10.1137/1.9781611977554.ch88.
ieee: M. Anastos, “Fast algorithms for solving the Hamilton cycle problem with high
probability,” in Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms,
Florence, Italy, 2023, vol. 2023, pp. 2286–2323.
ista: 'Anastos M. 2023. Fast algorithms for solving the Hamilton cycle problem with
high probability. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms.
SODA: Symposium on Discrete Algorithms vol. 2023, 2286–2323.'
mla: Anastos, Michael. “Fast Algorithms for Solving the Hamilton Cycle Problem with
High Probability.” Proceedings of the Annual ACM-SIAM Symposium on Discrete
Algorithms, vol. 2023, Society for Industrial and Applied Mathematics, 2023,
pp. 2286–323, doi:10.1137/1.9781611977554.ch88.
short: M. Anastos, in:, Proceedings of the Annual ACM-SIAM Symposium on Discrete
Algorithms, Society for Industrial and Applied Mathematics, 2023, pp. 2286–2323.
conference:
end_date: 2023-01-25
location: Florence, Italy
name: 'SODA: Symposium on Discrete Algorithms'
start_date: 2023-01-22
corr_author: '1'
date_created: 2023-09-17T22:01:10Z
date_published: 2023-01-01T00:00:00Z
date_updated: 2024-10-09T21:07:01Z
day: '01'
department:
- _id: MaKw
doi: 10.1137/1.9781611977554.ch88
external_id:
arxiv:
- '2111.14759'
fulldoi: https://doi.org/10.1137/1.9781611977554.ch88
intvolume: ' 2023'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2111.14759
month: '01'
oa: 1
oa_version: Preprint
page: 2286-2323
publication: Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
publication_identifier:
isbn:
- '9781611977554'
publication_status: published
publisher: Society for Industrial and Applied Mathematics
quality_controlled: '1'
scopus_import: '1'
status: public
title: Fast algorithms for solving the Hamilton cycle problem with high probability
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 2023
year: '2023'
...
---
_id: '14867'
abstract:
- lang: eng
text: Starting with the empty graph on $[n]$, at each round, a set of $K=K(n)$
edges is presented chosen uniformly at random from the ones that have not been
presented yet. We are then asked to choose at most one of the presented edges
and add it to the current graph. Our goal is to construct a Hamiltonian graph
with $(1+o(1))n$ edges within as few rounds as possible. We show that in this
process, one can build a Hamiltonian graph of size $(1+o(1))n$ in $(1+o(1))(1+(\log
n)/2K) n$ rounds w.h.p. The case $K=1$ implies that w.h.p. one can build a Hamiltonian
graph by choosing $(1+o(1))n$ edges in an online fashion as they appear along
the first $(0.5+o(1))n\log n$ rounds of the random graph process. This answers
a question of Frieze, Krivelevich and Michaeli. Observe that the number of rounds
is asymptotically optimal as the first $0.5n\log n$ edges do not span a Hamilton
cycle w.h.p. The case $K=\Theta(\log n)$ implies that the Hamiltonicity threshold
of the corresponding Achlioptas process is at most $(1+o(1))(1+(\log n)/2K) n$.
This matches the $(1-o(1))(1+(\log n)/2K) n$ lower bound due to Krivelevich, Lubetzky
and Sudakov and resolves the problem of determining the Hamiltonicity threshold
of the Achlioptas process with $K=\Theta(\log n)$. We also show that in the above
process one can construct a graph $G$ that spans a matching of size $\lfloor V(G)/2)
\rfloor$ and $(0.5+o(1))n$ edges within $(1+o(1))(0.5+(\log n)/2K) n$ rounds w.h.p.
Our proof relies on a robust Hamiltonicity property of the strong $4$-core of
the binomial random graph which we use as a black-box. This property allows it
to absorb paths covering vertices outside the strong $4$-core into a cycle.
acknowledgement: "This project has received funding from the European Union’s Horizon
2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement
No 101034413.\r\n"
article_processing_charge: No
arxiv: 1
author:
- first_name: Michael
full_name: Anastos, Michael
id: 0b2a4358-bb35-11ec-b7b9-e3279b593dbb
last_name: Anastos
citation:
ama: 'Anastos M. Constructing Hamilton cycles and perfect matchings efficiently.
In: Proceedings of the 12th European Conference on Combinatorics, Graph Theory
and Applications. Masaryk University Press; 2023:36-41. doi:10.5817/cz.muni.eurocomb23-005'
apa: 'Anastos, M. (2023). Constructing Hamilton cycles and perfect matchings efficiently.
In Proceedings of the 12th European Conference on Combinatorics, Graph Theory
and Applications (pp. 36–41). Prague, Czech Republic: Masaryk University Press.
https://doi.org/10.5817/cz.muni.eurocomb23-005'
chicago: Anastos, Michael. “Constructing Hamilton Cycles and Perfect Matchings Efficiently.”
In Proceedings of the 12th European Conference on Combinatorics, Graph Theory
and Applications, 36–41. Masaryk University Press, 2023. https://doi.org/10.5817/cz.muni.eurocomb23-005.
ieee: M. Anastos, “Constructing Hamilton cycles and perfect matchings efficiently,”
in Proceedings of the 12th European Conference on Combinatorics, Graph Theory
and Applications, Prague, Czech Republic, 2023, pp. 36–41.
ista: 'Anastos M. 2023. Constructing Hamilton cycles and perfect matchings efficiently.
Proceedings of the 12th European Conference on Combinatorics, Graph Theory and
Applications. EUROCOMB: European Conference on Combinatorics, Graph Theory and
Applications, 36–41.'
mla: Anastos, Michael. “Constructing Hamilton Cycles and Perfect Matchings Efficiently.”
Proceedings of the 12th European Conference on Combinatorics, Graph Theory
and Applications, Masaryk University Press, 2023, pp. 36–41, doi:10.5817/cz.muni.eurocomb23-005.
short: M. Anastos, in:, Proceedings of the 12th European Conference on Combinatorics,
Graph Theory and Applications, Masaryk University Press, 2023, pp. 36–41.
conference:
end_date: 2023-09-01
location: Prague, Czech Republic
name: 'EUROCOMB: European Conference on Combinatorics, Graph Theory and Applications'
start_date: 2023-08-28
corr_author: '1'
date_created: 2024-01-22T12:20:15Z
date_published: 2023-09-01T00:00:00Z
date_updated: 2025-09-09T14:24:21Z
day: '01'
ddc:
- '510'
department:
- _id: MaKw
doi: 10.5817/cz.muni.eurocomb23-005
ec_funded: 1
external_id:
arxiv:
- '2209.09860'
isi:
- '001448447300005'
file:
- access_level: open_access
checksum: fb1d9a1e7389d90ec0e5e76934373cf8
content_type: application/pdf
creator: dernst
date_created: 2024-01-24T09:34:43Z
date_updated: 2024-01-24T09:34:43Z
file_id: '14881'
file_name: 2023_Eurocomb_Anastos.pdf
file_size: 464230
relation: main_file
success: 1
file_date_updated: 2024-01-24T09:34:43Z
fulldoi: https://doi.org/10.5817/cz.muni.eurocomb23-005
has_accepted_license: '1'
isi: 1
language:
- iso: eng
license: https://creativecommons.org/licenses/by-nc-nd/4.0/
month: '09'
oa: 1
oa_version: Published Version
page: 36-41
project:
- _id: fc2ed2f7-9c52-11eb-aca3-c01059dda49c
call_identifier: H2020
grant_number: '101034413'
name: 'IST-BRIDGE: International postdoctoral program'
publication: Proceedings of the 12th European Conference on Combinatorics, Graph Theory
and Applications
publication_identifier:
eissn:
- 2788-3116
publication_status: published
publisher: Masaryk University Press
quality_controlled: '1'
status: public
title: Constructing Hamilton cycles and perfect matchings efficiently
tmp:
image: /images/cc_by_nc_nd.png
legal_code_url: https://creativecommons.org/licenses/by-nc-nd/4.0/legalcode
name: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International
(CC BY-NC-ND 4.0)
short: CC BY-NC-ND (4.0)
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
year: '2023'
...
---
_id: '12432'
abstract:
- lang: eng
text: "We present CertifyHAM, a deterministic algorithm that takes a graph G as
input and either finds a Hamilton cycle of G or outputs that such a cycle does
not exist. If G ∼ G(n, p) and p ≥\r\n100 log n/n then the expected running time
of CertifyHAM is O(n/p) which is best possible. This improves upon previous results
due to Gurevich and Shelah, Thomason and Alon, and\r\nKrivelevich, who proved
analogous results for p being constant, p ≥ 12n −1/3 and p ≥ 70n\r\n−1/2 respectively."
acknowledgement: "This project has received funding from the European Union’s Horizon
2020\r\nresearch and innovation programme under the Marie Skłodowska-Curie grant\r\nagreement
No 101034413"
article_processing_charge: No
author:
- first_name: Michael
full_name: Anastos, Michael
id: 0b2a4358-bb35-11ec-b7b9-e3279b593dbb
last_name: Anastos
citation:
ama: 'Anastos M. Solving the Hamilton cycle problem fast on average. In: 63rd
Annual IEEE Symposium on Foundations of Computer Science. Vol 2022-October.
IEEE; 2022:919-930. doi:10.1109/FOCS54457.2022.00091'
apa: 'Anastos, M. (2022). Solving the Hamilton cycle problem fast on average. In
63rd Annual IEEE Symposium on Foundations of Computer Science (Vol. 2022–October,
pp. 919–930). Denver, CO, United States: IEEE. https://doi.org/10.1109/FOCS54457.2022.00091'
chicago: Anastos, Michael. “Solving the Hamilton Cycle Problem Fast on Average.”
In 63rd Annual IEEE Symposium on Foundations of Computer Science, 2022–October:919–30.
IEEE, 2022. https://doi.org/10.1109/FOCS54457.2022.00091.
ieee: M. Anastos, “Solving the Hamilton cycle problem fast on average,” in 63rd
Annual IEEE Symposium on Foundations of Computer Science, Denver, CO, United
States, 2022, vol. 2022–October, pp. 919–930.
ista: 'Anastos M. 2022. Solving the Hamilton cycle problem fast on average. 63rd
Annual IEEE Symposium on Foundations of Computer Science. FOCS: Foundations of
Computer Science vol. 2022–October, 919–930.'
mla: Anastos, Michael. “Solving the Hamilton Cycle Problem Fast on Average.” 63rd
Annual IEEE Symposium on Foundations of Computer Science, vol. 2022–October,
IEEE, 2022, pp. 919–30, doi:10.1109/FOCS54457.2022.00091.
short: M. Anastos, in:, 63rd Annual IEEE Symposium on Foundations of Computer Science,
IEEE, 2022, pp. 919–930.
conference:
end_date: 2022-11-03
location: Denver, CO, United States
name: 'FOCS: Foundations of Computer Science'
start_date: 2022-10-31
corr_author: '1'
date_created: 2023-01-29T23:00:59Z
date_published: 2022-12-01T00:00:00Z
date_updated: 2026-08-12T06:34:24Z
day: '01'
department:
- _id: MaKw
doi: 10.1109/FOCS54457.2022.00091
ec_funded: 1
external_id:
isi:
- '000909382900084'
fulldoi: https://doi.org/10.1109/FOCS54457.2022.00091
isi: 1
language:
- iso: eng
month: '12'
oa_version: None
page: 919-930
project:
- _id: fc2ed2f7-9c52-11eb-aca3-c01059dda49c
call_identifier: H2020
grant_number: '101034413'
name: 'IST-BRIDGE: International postdoctoral program'
publication: 63rd Annual IEEE Symposium on Foundations of Computer Science
publication_identifier:
isbn:
- '9781665455190'
issn:
- 0272-5428
publication_status: published
publisher: IEEE
quality_controlled: '1'
scopus_import: '1'
status: public
title: Solving the Hamilton cycle problem fast on average
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 2022-October
year: '2022'
...