---
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
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
PlanS_conform: '1'
_id: '20504'
abstract:
- lang: eng
text: "Let r, k, be integers such that 0 ≤ ≤ (k/r). Given a large r-uniform hypergraph
G, we consider the\r\nfraction of k-vertex subsets that span exactly edges. If
\ is 0 or (k/r), this fraction can be exactly 1 (by taking G to be empty or complete),
but for all other values of , one might suspect that this fraction is always significantly
smaller than 1.\r\nIn this paper we prove an essentially optimal result along
these lines: if is not 0 or (k/r), then this\r\nfraction is at most (1/e) + ε,
assuming k is sufficiently large in terms of r and ε > 0, and G is sufficiently
large in terms of k. Previously, this was only known for a very limited range
of values of r, k, (due to Kwan–Sudakov–Tran, Fox–Sauermann, and Martinsson–Mousset–Noever–Trujic).
Our result answers a question of Alon–Hefetz–Krivelevich–Tyomkyn, who suggested
this as a hypergraph generalization of their edge-statistics conjecture. We also
prove a much stronger bound when is far from 0 and (k/r)."
acknowledgement: "This work was supported by NSF CAREER award DMS-2237646 [to V.J.],
ERC Starting Grant “RANDSTRUCT” [no. 101076777 to M.K.], NSF grant DMS-2153576 [to
D.M.], and the National Key Research and Development Program of China [2023YFA101020
to T.T.].\r\nWe would like to thank Lisa Sauermann for her helpful comments. We
would also like to thank Alex Grebennikov for identifying an oversight in the application
of Theorem 7.1 (in a previous version of this paper)."
article_number: rnaf273
article_processing_charge: Yes (via OA deal)
article_type: original
arxiv: 1
author:
- first_name: Vishesh
full_name: Jain, Vishesh
last_name: Jain
- 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: Dhruv
full_name: Mubayi, Dhruv
last_name: Mubayi
- first_name: Tuan
full_name: Tran, Tuan
last_name: Tran
citation:
ama: Jain V, Kwan MA, Mubayi D, Tran T. The edge-statistics conjecture for hypergraphs.
International Mathematics Research Notices. 2025;2025(18). doi:10.1093/imrn/rnaf273
apa: Jain, V., Kwan, M. A., Mubayi, D., & Tran, T. (2025). The edge-statistics
conjecture for hypergraphs. International Mathematics Research Notices.
Oxford University Press. https://doi.org/10.1093/imrn/rnaf273
chicago: Jain, Vishesh, Matthew Alan Kwan, Dhruv Mubayi, and Tuan Tran. “The Edge-Statistics
Conjecture for Hypergraphs.” International Mathematics Research Notices.
Oxford University Press, 2025. https://doi.org/10.1093/imrn/rnaf273.
ieee: V. Jain, M. A. Kwan, D. Mubayi, and T. Tran, “The edge-statistics conjecture
for hypergraphs,” International Mathematics Research Notices, vol. 2025,
no. 18. Oxford University Press, 2025.
ista: Jain V, Kwan MA, Mubayi D, Tran T. 2025. The edge-statistics conjecture for
hypergraphs. International Mathematics Research Notices. 2025(18), rnaf273.
mla: Jain, Vishesh, et al. “The Edge-Statistics Conjecture for Hypergraphs.” International
Mathematics Research Notices, vol. 2025, no. 18, rnaf273, Oxford University
Press, 2025, doi:10.1093/imrn/rnaf273.
short: V. Jain, M.A. Kwan, D. Mubayi, T. Tran, International Mathematics Research
Notices 2025 (2025).
corr_author: '1'
date_created: 2025-10-20T11:08:57Z
date_published: 2025-09-11T00:00:00Z
date_updated: 2025-12-01T13:00:35Z
day: '11'
ddc:
- '510'
department:
- _id: MaKw
doi: 10.1093/imrn/rnaf273
external_id:
arxiv:
- '2505.03954'
isi:
- '001575137400001'
file:
- access_level: open_access
checksum: 016aa4df9453dc180ae7504ac77bf72f
content_type: application/pdf
creator: dernst
date_created: 2025-10-21T07:36:56Z
date_updated: 2025-10-21T07:36:56Z
file_id: '20511'
file_name: 2025_IMRN_Jain.pdf
file_size: 774323
relation: main_file
success: 1
file_date_updated: 2025-10-21T07:36:56Z
has_accepted_license: '1'
intvolume: ' 2025'
isi: 1
issue: '18'
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: International Mathematics Research Notices
publication_identifier:
eissn:
- 1687-0247
issn:
- 1073-7928
publication_status: published
publisher: Oxford University Press
quality_controlled: '1'
scopus_import: '1'
status: public
title: The edge-statistics conjecture for hypergraphs
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: 2025
year: '2025'
...
---
OA_place: publisher
OA_type: hybrid
_id: '18753'
abstract:
- lang: eng
text: "We continue a line of research which studies which hereditary families of
digraphs have bounded dichromatic number. For a class of digraphs C, a hero in
\ C is any digraph H\r\n such that H -free digraphs in C have bounded dichromatic
number. We show that if F\r\n is an oriented star of degree at least five, the
only heroes for the class of F -free digraphs are transitive tournaments. For
oriented stars F of degree exactly four, we show the only heroes in F -free
digraphs are transitive tournaments, or possibly special joins of transitive tournaments.
Aboulker et al. characterized the set of heroes of {H,K1+P2→} -free digraphs
almost completely, and we show the same characterization for the class of {H,rK1+P3→}
-free digraphs. Lastly, we show that if we forbid two \"valid\" orientations of
brooms, then every transitive tournament is a hero for this class of digraphs."
acknowledgement: "We thank the anonymous referees for their careful proofreading which
helped improve the presentation of this paper. We also thank one of the anonymous
referees for pointing out our construction implies Theorem 1.7!\r\nBenjamin Moore
finished this project while a postdoctoral researcher at Charles University, and
was supported by project 22-17398S (Flows and cycles in graphs on surfaces) of the
Czech Science Foundation. Benjamin Moore is currently funded by RANDSTRUCT No. 101076777,
and appreciates the gracious support. We acknowledge the support of the Natural
Sciences and Engineering Research Council of Canada (NSERC), [funding reference
number RGPIN-2020-03912]. Cette recherche a été financée par le Conseil de recherches
en sciences naturelles et en génie du Canada (CRSNG), [numéro de référence RGPIN-2020-03912].
This project was funded in part by the Government of Ontario ."
article_number: '104104'
article_processing_charge: Yes (in subscription journal)
article_type: original
arxiv: 1
author:
- first_name: Alvaro
full_name: Carbonero, Alvaro
last_name: Carbonero
- first_name: Hidde
full_name: Koerts, Hidde
last_name: Koerts
- first_name: Benjamin
full_name: Moore, Benjamin
id: 6dc1a1be-bf1c-11ed-8d2b-d044840f49d6
last_name: Moore
- first_name: Sophie
full_name: Spirkl, Sophie
last_name: Spirkl
citation:
ama: Carbonero A, Koerts H, Moore B, Spirkl S. On heroes in digraphs with forbidden
induced forests. European Journal of Combinatorics. 2025;125. doi:10.1016/j.ejc.2024.104104
apa: Carbonero, A., Koerts, H., Moore, B., & Spirkl, S. (2025). On heroes in
digraphs with forbidden induced forests. European Journal of Combinatorics.
Elsevier. https://doi.org/10.1016/j.ejc.2024.104104
chicago: Carbonero, Alvaro, Hidde Koerts, Benjamin Moore, and Sophie Spirkl. “On
Heroes in Digraphs with Forbidden Induced Forests.” European Journal of Combinatorics.
Elsevier, 2025. https://doi.org/10.1016/j.ejc.2024.104104.
ieee: A. Carbonero, H. Koerts, B. Moore, and S. Spirkl, “On heroes in digraphs with
forbidden induced forests,” European Journal of Combinatorics, vol. 125.
Elsevier, 2025.
ista: Carbonero A, Koerts H, Moore B, Spirkl S. 2025. On heroes in digraphs with
forbidden induced forests. European Journal of Combinatorics. 125, 104104.
mla: Carbonero, Alvaro, et al. “On Heroes in Digraphs with Forbidden Induced Forests.”
European Journal of Combinatorics, vol. 125, 104104, Elsevier, 2025, doi:10.1016/j.ejc.2024.104104.
short: A. Carbonero, H. Koerts, B. Moore, S. Spirkl, European Journal of Combinatorics
125 (2025).
corr_author: '1'
date_created: 2025-01-05T23:01:55Z
date_published: 2025-03-01T00:00:00Z
date_updated: 2025-05-19T14:06:00Z
day: '01'
ddc:
- '510'
department:
- _id: MaKw
doi: 10.1016/j.ejc.2024.104104
external_id:
arxiv:
- '2306.04710'
isi:
- '001400113700001'
file:
- access_level: open_access
checksum: 2c75f78f40ebb93d16fe3765bda2905a
content_type: application/pdf
creator: dernst
date_created: 2025-04-16T09:16:25Z
date_updated: 2025-04-16T09:16:25Z
file_id: '19577'
file_name: 2025_EuropJournCombinatorics_Carbonero.pdf
file_size: 1110657
relation: main_file
success: 1
file_date_updated: 2025-04-16T09:16:25Z
has_accepted_license: '1'
intvolume: ' 125'
isi: 1
language:
- iso: eng
month: '03'
oa: 1
oa_version: Published Version
project:
- _id: bd95085b-d553-11ed-ba76-e55d3349be45
grant_number: '101076777'
name: Randomness and structure in combinatorics
publication: European Journal of Combinatorics
publication_identifier:
issn:
- 0195-6698
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: On heroes in digraphs with forbidden induced forests
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: 125
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
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: '19554'
abstract:
- lang: eng
text: 'In 1981, Karp and Sipser proved a law of large numbers for the matching number
of a sparse Erdős–Rényi random graph, in an influential paper pioneering the so-called
differential equation method for analysis of random graph processes. Strengthening
this classical result, and answering a question of Aronson, Frieze and Pittel,
we prove a central limit theorem in the same setting: the fluctuations in the
matching number of a sparse random graph are asymptotically Gaussian. Our new
contribution is to prove this central limit theorem in the subcritical and critical
regimes, according to a celebrated algorithmic phase transition first observed
by Karp and Sipser. Indeed, in the supercritical regime, a central limit theorem
has recently been proved in the PhD thesis of Kreačić, using a stochastic generalisation
of the differential equation method (comparing the so-called Karp–Sipser process
to a system of stochastic differential equations). Our proof builds on these methods,
and introduces new techniques to handle certain degeneracies present in the subcritical
and critical cases. Curiously, our new techniques lead to a non-constructive result:
we are able to characterise the fluctuations of the matching number around its
mean, despite these fluctuations being much smaller than the error terms in our
best estimates of the mean. We also prove a central limit theorem for the rank
of the adjacency matrix of a sparse random graph.'
acknowledgement: "We would like to thank Christina Goldschmidt and Eleonora Kreačić
for insightful discussions and clarifications about their work in the thesis [26].
Matthew Kwan was supported by ERC Starting Grant ‘RANDSTRUCT’ No. 101076777. Ashwin
Sah and Mehtaab Sawhney were supported by NSF Graduate Research Fellowship Program
DGE-2141064. Ashwin Sah was supported by the PD Soros Fellowship.\r\nOpen access
funding provided by Institute of Science and Technology Austria/KEMÖ."
article_number: e70101
article_processing_charge: Yes (via OA deal)
article_type: original
arxiv: 1
author:
- first_name: Margalit
full_name: Glasgow, Margalit
last_name: Glasgow
- 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: Ashwin
full_name: Sah, Ashwin
last_name: Sah
- first_name: Mehtaab
full_name: Sawhney, Mehtaab
last_name: Sawhney
citation:
ama: Glasgow M, Kwan MA, Sah A, Sawhney M. A central limit theorem for the matching
number of a sparse random graph. Journal of the London Mathematical Society.
2025;111(4). doi:10.1112/jlms.70101
apa: Glasgow, M., Kwan, M. A., Sah, A., & Sawhney, M. (2025). A central limit
theorem for the matching number of a sparse random graph. Journal of the London
Mathematical Society. Wiley. https://doi.org/10.1112/jlms.70101
chicago: Glasgow, Margalit, Matthew Alan Kwan, Ashwin Sah, and Mehtaab Sawhney.
“A Central Limit Theorem for the Matching Number of a Sparse Random Graph.” Journal
of the London Mathematical Society. Wiley, 2025. https://doi.org/10.1112/jlms.70101.
ieee: M. Glasgow, M. A. Kwan, A. Sah, and M. Sawhney, “A central limit theorem for
the matching number of a sparse random graph,” Journal of the London Mathematical
Society, vol. 111, no. 4. Wiley, 2025.
ista: Glasgow M, Kwan MA, Sah A, Sawhney M. 2025. A central limit theorem for the
matching number of a sparse random graph. Journal of the London Mathematical Society.
111(4), e70101.
mla: Glasgow, Margalit, et al. “A Central Limit Theorem for the Matching Number
of a Sparse Random Graph.” Journal of the London Mathematical Society,
vol. 111, no. 4, e70101, Wiley, 2025, doi:10.1112/jlms.70101.
short: M. Glasgow, M.A. Kwan, A. Sah, M. Sawhney, Journal of the London Mathematical
Society 111 (2025).
corr_author: '1'
date_created: 2025-04-13T22:01:19Z
date_published: 2025-04-01T00:00:00Z
date_updated: 2025-09-30T11:35:55Z
day: '01'
ddc:
- '510'
department:
- _id: MaKw
doi: 10.1112/jlms.70101
external_id:
arxiv:
- '2402.05851'
isi:
- '001473087200024'
file:
- access_level: open_access
checksum: 69ce9feaf64e776b99f3afd1041b1b11
content_type: application/pdf
creator: dernst
date_created: 2025-04-15T13:18:43Z
date_updated: 2025-04-15T13:18:43Z
file_id: '19564'
file_name: 2025_JourLondMathSoc_Glasgow.pdf
file_size: 392208
relation: main_file
success: 1
file_date_updated: 2025-04-15T13:18:43Z
has_accepted_license: '1'
intvolume: ' 111'
isi: 1
issue: '4'
language:
- iso: eng
month: '04'
oa: 1
oa_version: Published Version
project:
- _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: A central limit theorem for the matching number of a sparse random graph
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: 111
year: '2025'
...
---
DOAJ_listed: '1'
OA_place: publisher
OA_type: diamond
PlanS_conform: '1'
_id: '21263'
abstract:
- lang: eng
text: Two landmark results in combinatorial random matrix theory, due to Komlós
and Costello–Tao–Vu, show that discrete random matrices and symmetric discrete
random matrices are typically nonsingular. In particular, in the language of graph
theory, when p is a fixed constant, the biadjacency matrix of a random Erdős–Rényi
bipartite graph G(n,n,p) and the adjacency matrix of an Erdős–Rényi random graph
G(n,p) are both nonsingular with high probability. However, very sparse random
graphs (i.e., where p is allowed to decay rapidly with n) are typically singular,
due to the presence of “local” dependencies such as isolated vertices and pairs
of degree-1 vertices with the same neighbour. In this paper, we give a combinatorial
description of the rank of a sparse random graph G(n,n,c/n) or G(n,c/n) in terms
of such local dependencies, for all constants c=e (and we present some evidence
that the situation is very different for c=e). This gives an essentially complete
answer to a question raised by Vu (2014). As applications of our main theorem
and its proof, we also determine the asymptotic singularity probability of the
2-core of a sparse random graph, we show that the rank of a sparse random graph
is extremely well approximated by its matching number, and we deduce a central
limit theorem for the rank of G(n,c/n).
acknowledgement: "We would like to thank Noga Alon for suggesting that our main result
gives\r\na linear-time algorithm for computing the rank. We also thank the referees
for a number of thoughtful comments and suggestions. Glasgow was supported by NSF
graduate research fellowship program award DGE1656518. Kwan was supported by ERC
Starting Grant “RANDSTRUCT” No. 101076777. Sah and Sawhney were supported by NSF
Graduate Research Fellowship Program DGE-1745302.\r\n"
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Margalit
full_name: Glasgow, Margalit
last_name: Glasgow
- 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: Ashwin
full_name: Sah, Ashwin
last_name: Sah
- first_name: Mehtaab
full_name: Sawhney, Mehtaab
last_name: Sawhney
citation:
ama: Glasgow M, Kwan MA, Sah A, Sawhney M. The exact rank of sparse random graphs.
Journal of the European Mathematical Society. 2025. doi:10.4171/jems/1692
apa: Glasgow, M., Kwan, M. A., Sah, A., & Sawhney, M. (2025). The exact rank
of sparse random graphs. Journal of the European Mathematical Society.
European Mathematical Society Press. https://doi.org/10.4171/jems/1692
chicago: Glasgow, Margalit, Matthew Alan Kwan, Ashwin Sah, and Mehtaab Sawhney.
“The Exact Rank of Sparse Random Graphs.” Journal of the European Mathematical
Society. European Mathematical Society Press, 2025. https://doi.org/10.4171/jems/1692.
ieee: M. Glasgow, M. A. Kwan, A. Sah, and M. Sawhney, “The exact rank of sparse
random graphs,” Journal of the European Mathematical Society. European
Mathematical Society Press, 2025.
ista: Glasgow M, Kwan MA, Sah A, Sawhney M. 2025. The exact rank of sparse random
graphs. Journal of the European Mathematical Society.
mla: Glasgow, Margalit, et al. “The Exact Rank of Sparse Random Graphs.” Journal
of the European Mathematical Society, European Mathematical Society Press,
2025, doi:10.4171/jems/1692.
short: M. Glasgow, M.A. Kwan, A. Sah, M. Sawhney, Journal of the European Mathematical
Society (2025).
corr_author: '1'
date_created: 2026-02-17T07:41:59Z
date_published: 2025-09-02T00:00:00Z
date_updated: 2026-02-23T10:44:41Z
day: '02'
ddc:
- '510'
department:
- _id: MaKw
doi: 10.4171/jems/1692
external_id:
arxiv:
- '2303.05435'
has_accepted_license: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.4171/JEMS/1692
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: Journal of the European Mathematical Society
publication_identifier:
eissn:
- 1435-9863
issn:
- 1435-9855
publication_status: epub_ahead
publisher: European Mathematical Society Press
quality_controlled: '1'
status: public
title: The exact rank of 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: 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'
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'
...
---
OA_place: publisher
OA_type: hybrid
_id: '17376'
abstract:
- lang: eng
text: "The inertia bound and ratio bound (also known as the Cvetković bound and
Hoffman bound) are two fundamental inequalities in spectral graph theory, giving
upper bounds on the independence number α(G) of a graph G in terms of spectral
information about a weighted adjacency matrix of G. For both inequalities, given
a graph G, one needs to make a judicious choice of weighted adjacency matrix to
obtain as strong a bound as possible.\r\nWhile there is a well-established theory
surrounding the ratio bound, the inertia bound is much more mysterious, and its
limits are rather unclear. In fact, only recently did Sinkovic find the first
example of a graph for which the inertia bound is not tight (for any weighted
adjacency matrix), answering a longstanding question of Godsil. We show that the
inertia bound can be extremely far from tight, and in fact can significantly underperform
the ratio bound: for example, one of our results is that for infinitely many n,
there is an n-vertex graph for which even the unweighted ratio bound can prove
α(G)≤4n3/4, but the inertia bound is always at least n/4. In particular, these
results address questions of Rooney, Sinkovic, and Wocjan--Elphick--Abiad."
acknowledgement: "The authors are grateful to Noga Alon, Anurag Bishnoi, Clive Elphick,
and Ferdinand Ihringer for helpful comments and interesting discussions on earlier
drafts of this paper. Matthew Kwan is supported by ERC Starting Grant “RANDSTRUCT”
No. 101076777. Yuval Wigderson is supported by Dr. Max Rössler, the Walter Haefner
Foundation, and the ETH Zürich Foundation.\r\nOpen access funding provided by Eidgenossische
Technische Hochschule Zurich."
article_processing_charge: Yes (via OA deal)
article_type: original
arxiv: 1
author:
- 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: Yuval
full_name: Wigderson, Yuval
last_name: Wigderson
citation:
ama: Kwan MA, Wigderson Y. The inertia bound is far from tight. Bulletin of the
London Mathematical Society. 2024;56(10):3196-3208. doi:10.1112/blms.13127
apa: Kwan, M. A., & Wigderson, Y. (2024). The inertia bound is far from tight.
Bulletin of the London Mathematical Society. London Mathematical Society.
https://doi.org/10.1112/blms.13127
chicago: Kwan, Matthew Alan, and Yuval Wigderson. “The Inertia Bound Is Far from
Tight.” Bulletin of the London Mathematical Society. London Mathematical
Society, 2024. https://doi.org/10.1112/blms.13127.
ieee: M. A. Kwan and Y. Wigderson, “The inertia bound is far from tight,” Bulletin
of the London Mathematical Society, vol. 56, no. 10. London Mathematical Society,
pp. 3196–3208, 2024.
ista: Kwan MA, Wigderson Y. 2024. The inertia bound is far from tight. Bulletin
of the London Mathematical Society. 56(10), 3196–3208.
mla: Kwan, Matthew Alan, and Yuval Wigderson. “The Inertia Bound Is Far from Tight.”
Bulletin of the London Mathematical Society, vol. 56, no. 10, London Mathematical
Society, 2024, pp. 3196–208, doi:10.1112/blms.13127.
short: M.A. Kwan, Y. Wigderson, Bulletin of the London Mathematical Society 56 (2024)
3196–3208.
date_created: 2024-08-04T22:01:22Z
date_published: 2024-10-01T00:00:00Z
date_updated: 2025-09-08T08:45:39Z
day: '01'
ddc:
- '510'
department:
- _id: MaKw
doi: 10.1112/blms.13127
external_id:
arxiv:
- '2312.04925'
isi:
- '001279563300001'
file:
- access_level: open_access
checksum: 7117f9819eaeb45eef1b0a226f9c2709
content_type: application/pdf
creator: dernst
date_created: 2025-01-09T13:36:53Z
date_updated: 2025-01-09T13:36:53Z
file_id: '18814'
file_name: 2024_BulletinLondonMathSoc_Kwan.pdf
file_size: 175966
relation: main_file
success: 1
file_date_updated: 2025-01-09T13:36:53Z
has_accepted_license: '1'
intvolume: ' 56'
isi: 1
issue: '10'
language:
- iso: eng
month: '10'
oa: 1
oa_version: Published Version
page: 3196-3208
project:
- _id: bd95085b-d553-11ed-ba76-e55d3349be45
grant_number: '101076777'
name: Randomness and structure in combinatorics
publication: Bulletin of the London Mathematical Society
publication_identifier:
eissn:
- 1469-2120
issn:
- 0024-6093
publication_status: published
publisher: London Mathematical Society
quality_controlled: '1'
scopus_import: '1'
status: public
title: The inertia bound is far from tight
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: 56
year: '2024'
...
---
_id: '17475'
abstract:
- lang: eng
text: "As a discrete analogue of Kac’s celebrated question on ‘hearing the shape
of a drum’ and towards a practical\r\ngraph isomorphism test, it is of interest
to understand which graphs are determined up to isomorphism by\r\ntheir spectrum
(of their adjacency matrix). A striking conjecture in this area, due to van Dam
and Haemers,\r\nis that ‘almost all graphs are determined by their spectrum’,
meaning that the fraction of unlabelled n-vertex\r\ngraphs which are determined
by their spectrum converges to 1 as n → ∞.\r\nIn this paper, we make a step towards
this conjecture, showing that there are exponentially many n-vertex\r\ngraphs
which are determined by their spectrum. This improves on previous bounds (of shape
e\r\nc\r\n√\r\nn\r\n). We also\r\npropose a number of further directions of research.\r\n"
acknowledgement: Matthew Kwan was supported by ERC Starting Grant ‘RANDSTRUCT’ No.
101076777.
article_processing_charge: Yes (via OA deal)
article_type: original
arxiv: 1
author:
- first_name: Illya
full_name: Koval, Illya
id: 2eed1f3b-896a-11ed-bdf8-93c7c4bf159e
last_name: Koval
- 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: Koval I, Kwan MA. Exponentially many graphs are determined by their spectrum.
Quarterly Journal of Mathematics. 2024;75(3):869-899. doi:10.1093/qmath/haae030
apa: Koval, I., & Kwan, M. A. (2024). Exponentially many graphs are determined
by their spectrum. Quarterly Journal of Mathematics. Oxford University
Press. https://doi.org/10.1093/qmath/haae030
chicago: Koval, Illya, and Matthew Alan Kwan. “Exponentially Many Graphs Are Determined
by Their Spectrum.” Quarterly Journal of Mathematics. Oxford University
Press, 2024. https://doi.org/10.1093/qmath/haae030.
ieee: I. Koval and M. A. Kwan, “Exponentially many graphs are determined by their
spectrum,” Quarterly Journal of Mathematics, vol. 75, no. 3. Oxford University
Press, pp. 869–899, 2024.
ista: Koval I, Kwan MA. 2024. Exponentially many graphs are determined by their
spectrum. Quarterly Journal of Mathematics. 75(3), 869–899.
mla: Koval, Illya, and Matthew Alan Kwan. “Exponentially Many Graphs Are Determined
by Their Spectrum.” Quarterly Journal of Mathematics, vol. 75, no. 3, Oxford
University Press, 2024, pp. 869–99, doi:10.1093/qmath/haae030.
short: I. Koval, M.A. Kwan, Quarterly Journal of Mathematics 75 (2024) 869–899.
corr_author: '1'
date_created: 2024-09-01T22:01:07Z
date_published: 2024-06-19T00:00:00Z
date_updated: 2025-09-08T09:09:41Z
day: '19'
ddc:
- '500'
department:
- _id: MaKw
- _id: VaKa
doi: 10.1093/qmath/haae030
external_id:
arxiv:
- '2309.09788'
isi:
- '001249741500001'
file:
- access_level: open_access
checksum: abf200d37ad69e6f2c0750a30296ad97
content_type: application/pdf
creator: cchlebak
date_created: 2024-09-06T12:23:57Z
date_updated: 2024-09-06T12:23:57Z
file_id: '17851'
file_name: 2024_QuJofMath_Koval.pdf
file_size: 946411
relation: main_file
success: 1
file_date_updated: 2024-09-06T12:23:57Z
has_accepted_license: '1'
intvolume: ' 75'
isi: 1
issue: '3'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 869-899
project:
- _id: bd95085b-d553-11ed-ba76-e55d3349be45
grant_number: '101076777'
name: Randomness and structure in combinatorics
publication: Quarterly Journal of Mathematics
publication_identifier:
eissn:
- 1464-3847
issn:
- 0033-5606
publication_status: published
publisher: Oxford University Press
quality_controlled: '1'
scopus_import: '1'
status: public
title: Exponentially many graphs are determined by their spectrum
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: 75
year: '2024'
...
---
_id: '14499'
abstract:
- lang: eng
text: "An n-vertex graph is called C-Ramsey if it has no clique or independent set
of size Clog2n (i.e., if it has near-optimal Ramsey behavior). In this paper,
we study edge statistics in Ramsey graphs, in particular obtaining very precise
control of the distribution of the number of edges in a random vertex subset of
a C-Ramsey graph. This brings together two ongoing lines of research: the study
of ‘random-like’ properties of Ramsey graphs and the study of small-ball probability
for low-degree polynomials of independent random variables.\r\n\r\nThe proof proceeds
via an ‘additive structure’ dichotomy on the degree sequence and involves a wide
range of different tools from Fourier analysis, random matrix theory, the theory
of Boolean functions, probabilistic combinatorics and low-rank approximation.
In particular, a key ingredient is a new sharpened version of the quadratic Carbery–Wright
theorem on small-ball probability for polynomials of Gaussians, which we believe
is of independent interest. One of the consequences of our result is the resolution
of an old conjecture of Erdős and McKay, for which Erdős reiterated in several
of his open problem collections and for which he offered one of his notorious
monetary prizes."
acknowledgement: Kwan was supported for part of this work by ERC Starting Grant ‘RANDSTRUCT’
No. 101076777. Sah and Sawhney were supported by NSF Graduate Research Fellowship
Program DGE-2141064. Sah was supported by the PD Soros Fellowship. Sauermann was
supported by NSF Award DMS-2100157, and for part of this work by a Sloan Research
Fellowship.
article_number: e21
article_processing_charge: Yes
article_type: original
arxiv: 1
author:
- 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: Ashwin
full_name: Sah, Ashwin
last_name: Sah
- first_name: Lisa
full_name: Sauermann, Lisa
last_name: Sauermann
- first_name: Mehtaab
full_name: Sawhney, Mehtaab
last_name: Sawhney
citation:
ama: Kwan MA, Sah A, Sauermann L, Sawhney M. Anticoncentration in Ramsey graphs
and a proof of the Erdős–McKay conjecture. Forum of Mathematics, Pi. 2023;11.
doi:10.1017/fmp.2023.17
apa: Kwan, M. A., Sah, A., Sauermann, L., & Sawhney, M. (2023). Anticoncentration
in Ramsey graphs and a proof of the Erdős–McKay conjecture. Forum of Mathematics,
Pi. Cambridge University Press. https://doi.org/10.1017/fmp.2023.17
chicago: Kwan, Matthew Alan, Ashwin Sah, Lisa Sauermann, and Mehtaab Sawhney. “Anticoncentration
in Ramsey Graphs and a Proof of the Erdős–McKay Conjecture.” Forum of Mathematics,
Pi. Cambridge University Press, 2023. https://doi.org/10.1017/fmp.2023.17.
ieee: M. A. Kwan, A. Sah, L. Sauermann, and M. Sawhney, “Anticoncentration in Ramsey
graphs and a proof of the Erdős–McKay conjecture,” Forum of Mathematics, Pi,
vol. 11. Cambridge University Press, 2023.
ista: Kwan MA, Sah A, Sauermann L, Sawhney M. 2023. Anticoncentration in Ramsey
graphs and a proof of the Erdős–McKay conjecture. Forum of Mathematics, Pi. 11,
e21.
mla: Kwan, Matthew Alan, et al. “Anticoncentration in Ramsey Graphs and a Proof
of the Erdős–McKay Conjecture.” Forum of Mathematics, Pi, vol. 11, e21,
Cambridge University Press, 2023, doi:10.1017/fmp.2023.17.
short: M.A. Kwan, A. Sah, L. Sauermann, M. Sawhney, Forum of Mathematics, Pi 11
(2023).
corr_author: '1'
date_created: 2023-11-07T09:02:48Z
date_published: 2023-08-24T00:00:00Z
date_updated: 2025-09-09T13:16:15Z
day: '24'
ddc:
- '510'
department:
- _id: MaKw
doi: 10.1017/fmp.2023.17
external_id:
arxiv:
- '2208.02874'
isi:
- '001123866200001'
file:
- access_level: open_access
checksum: 54b824098d59073cc87a308d458b0a3e
content_type: application/pdf
creator: dernst
date_created: 2023-11-07T09:16:23Z
date_updated: 2023-11-07T09:16:23Z
file_id: '14500'
file_name: 2023_ForumMathematics_Kwan.pdf
file_size: 1218719
relation: main_file
success: 1
file_date_updated: 2023-11-07T09:16:23Z
has_accepted_license: '1'
intvolume: ' 11'
isi: 1
keyword:
- Discrete Mathematics and Combinatorics
- Geometry and Topology
- Mathematical Physics
- Statistics and Probability
- Algebra and Number Theory
- Analysis
language:
- iso: eng
month: '08'
oa: 1
oa_version: Published Version
project:
- _id: bd95085b-d553-11ed-ba76-e55d3349be45
grant_number: '101076777'
name: Randomness and structure in combinatorics
publication: Forum of Mathematics, Pi
publication_identifier:
issn:
- 2050-5086
publication_status: published
publisher: Cambridge University Press
quality_controlled: '1'
scopus_import: '1'
status: public
title: Anticoncentration in Ramsey graphs and a proof of the Erdős–McKay conjecture
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: 11
year: '2023'
...