---
DOAJ_listed: '1'
OA_place: publisher
OA_type: gold
_id: '19859'
abstract:
- lang: eng
text: "We consider a recently introduced model of color-avoiding percolation (abbreviated
CA-percolation) defined as follows. Every edge in a graph G is colored in some
of k>=2 colors. Two vertices u and v in G are said to be CA-connected if u and
v may be connected using any subset of k-1 colors. CA-connectivity defines an
equivalence relation on the vertex set of G whose classes are called CA-components.\r\nWe
study the component structure of a randomly colored Erdős–Rényi random graph of
constant average degree. We distinguish three regimes for the size of the largest
component: a supercritical regime, a so-called intermediate regime, and a subcritical
regime, in which the largest CA-component has respectively linear, logarithmic,
and bounded size. Interestingly, in the subcritical regime, the bound is deterministic
and given by the number of colors."
acknowledgement: "We thank Dieter Mitsche for enlightening discussions, Balázs Ráth
for a number of comments\r\nand corrections on a first version of this paper, and
an anonymous referee for several useful remarks."
article_processing_charge: Yes
article_type: original
arxiv: 1
author:
- first_name: Lyuben
full_name: Lichev, Lyuben
id: 9aa8388e-d003-11ee-8458-c4c1d7447977
last_name: Lichev
- first_name: Bruno
full_name: Schapira, Bruno
last_name: Schapira
citation:
ama: Lichev L, Schapira B. Color-avoiding percolation on the Erdős–Rényi random
graph. Annales Henri Lebesgue. 2025;8:35-65. doi:10.5802/ahl.228
apa: Lichev, L., & Schapira, B. (2025). Color-avoiding percolation on the Erdős–Rényi
random graph. Annales Henri Lebesgue. École normale supérieure de Rennes.
https://doi.org/10.5802/ahl.228
chicago: Lichev, Lyuben, and Bruno Schapira. “Color-Avoiding Percolation on the
Erdős–Rényi Random Graph.” Annales Henri Lebesgue. École normale supérieure
de Rennes, 2025. https://doi.org/10.5802/ahl.228.
ieee: L. Lichev and B. Schapira, “Color-avoiding percolation on the Erdős–Rényi
random graph,” Annales Henri Lebesgue, vol. 8. École normale supérieure
de Rennes, pp. 35–65, 2025.
ista: Lichev L, Schapira B. 2025. Color-avoiding percolation on the Erdős–Rényi
random graph. Annales Henri Lebesgue. 8, 35–65.
mla: Lichev, Lyuben, and Bruno Schapira. “Color-Avoiding Percolation on the Erdős–Rényi
Random Graph.” Annales Henri Lebesgue, vol. 8, École normale supérieure
de Rennes, 2025, pp. 35–65, doi:10.5802/ahl.228.
short: L. Lichev, B. Schapira, Annales Henri Lebesgue 8 (2025) 35–65.
corr_author: '1'
date_created: 2025-06-22T22:02:07Z
date_published: 2025-06-01T00:00:00Z
date_updated: 2025-06-23T12:01:36Z
day: '01'
ddc:
- '510'
department:
- _id: MaKw
doi: 10.5802/ahl.228
external_id:
arxiv:
- '2211.16086 '
file:
- access_level: open_access
checksum: cca22d171b7affa010d17f5e793b0045
content_type: application/pdf
creator: dernst
date_created: 2025-06-23T11:59:22Z
date_updated: 2025-06-23T11:59:22Z
file_id: '19875'
file_name: 2025_AnnalesHenriLebesgue_Lichev.pdf
file_size: 746588
relation: main_file
success: 1
file_date_updated: 2025-06-23T11:59:22Z
has_accepted_license: '1'
intvolume: ' 8'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 35-65
publication: Annales Henri Lebesgue
publication_identifier:
eissn:
- 2644-9463
publication_status: published
publisher: École normale supérieure de Rennes
quality_controlled: '1'
scopus_import: '1'
status: public
title: Color-avoiding percolation on the Erdős–Rényi random graph
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: 8
year: '2025'
...
---
OA_place: publisher
OA_type: hybrid
_id: '19879'
abstract:
- lang: eng
text: We consider the 4-precoloring extension problem in planar near-Eulerian- triangulations,
i.e., plane graphs where all faces except possibly for the outer one have length
three, all vertices not incident with the outer face have even degree, and exactly
the vertices incident with the outer face are precolored. We give a necessary
topological condition for the precoloring to extend, and give a complete characterization
when the outer face has length at most five and when all vertices of the outer
face have odd degree and are colored using only three colors.
acknowledgement: Supported by project 22-17398S (Flows and cycles in graphs on surfaces)
of Czech Science Foundation. An extended abstract appeared in Proceedings of the
12th European Conference on Combinatorics, Graph Theory and Applications (EUROCOMB’23)
article_number: '104138'
article_processing_charge: Yes (via OA deal)
article_type: original
arxiv: 1
author:
- first_name: Zdeněk
full_name: Dvořák, Zdeněk
last_name: Dvořák
- first_name: Benjamin
full_name: Moore, Benjamin
id: 6dc1a1be-bf1c-11ed-8d2b-d044840f49d6
last_name: Moore
- first_name: Michaela
full_name: Seifrtová, Michaela
last_name: Seifrtová
- first_name: Robert
full_name: Šámal, Robert
last_name: Šámal
citation:
ama: Dvořák Z, Moore B, Seifrtová M, Šámal R. Precoloring extension in planar near-Eulerian-triangulations.
European Journal of Combinatorics. 2025;127. doi:10.1016/j.ejc.2025.104138
apa: Dvořák, Z., Moore, B., Seifrtová, M., & Šámal, R. (2025). Precoloring extension
in planar near-Eulerian-triangulations. European Journal of Combinatorics.
Elsevier. https://doi.org/10.1016/j.ejc.2025.104138
chicago: Dvořák, Zdeněk, Benjamin Moore, Michaela Seifrtová, and Robert Šámal. “Precoloring
Extension in Planar Near-Eulerian-Triangulations.” European Journal of Combinatorics.
Elsevier, 2025. https://doi.org/10.1016/j.ejc.2025.104138.
ieee: Z. Dvořák, B. Moore, M. Seifrtová, and R. Šámal, “Precoloring extension in
planar near-Eulerian-triangulations,” European Journal of Combinatorics,
vol. 127. Elsevier, 2025.
ista: Dvořák Z, Moore B, Seifrtová M, Šámal R. 2025. Precoloring extension in planar
near-Eulerian-triangulations. European Journal of Combinatorics. 127, 104138.
mla: Dvořák, Zdeněk, et al. “Precoloring Extension in Planar Near-Eulerian-Triangulations.”
European Journal of Combinatorics, vol. 127, 104138, Elsevier, 2025, doi:10.1016/j.ejc.2025.104138.
short: Z. Dvořák, B. Moore, M. Seifrtová, R. Šámal, European Journal of Combinatorics
127 (2025).
corr_author: '1'
date_created: 2025-06-23T13:54:46Z
date_published: 2025-06-01T00:00:00Z
date_updated: 2025-09-30T13:42:59Z
day: '01'
ddc:
- '510'
department:
- _id: MaKw
doi: 10.1016/j.ejc.2025.104138
external_id:
arxiv:
- '2312.13061'
isi:
- '001443061400001'
file:
- access_level: open_access
checksum: 8b3585df45b25091fba9bee9854b7d01
content_type: application/pdf
creator: dernst
date_created: 2025-06-24T06:33:30Z
date_updated: 2025-06-24T06:33:30Z
file_id: '19887'
file_name: 2025_EuropJournCombinatorics_Dvorak.pdf
file_size: 564203
relation: main_file
success: 1
file_date_updated: 2025-06-24T06:33:30Z
has_accepted_license: '1'
intvolume: ' 127'
isi: 1
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
publication: European Journal of Combinatorics
publication_identifier:
issn:
- 0195-6698
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: Precoloring extension in planar near-Eulerian-triangulations
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: 127
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
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: '20320'
abstract:
- lang: eng
text: "The pseudoforest version of the Strong Nine Dragon Tree Conjecture states
that if a graph G has maximum average degree mad(G) = 2 maxH⊆G e(H)/v(H) at most
2(k + d/d+k+1), then it has a decomposition into k + 1 pseudoforests where in
one pseudoforest F the components of F have at most d edges. This was proven in
2020 in Grout and Moore (2020). We strengthen this\r\ntheorem by showing that
we can find such a decomposition where additionally F is acyclic, the diameter
of the components of F is at most 2ℓ + 2, where ℓ =⌊d−1/k+1⌋, and at most 2ℓ +
1 if\r\nd ≡ 1 mod (k + 1). Furthermore, for any component K of F and any z ∈ N,
we have diam(K) ≤ 2z if e(K) ≥ d − z(k − 1) + 1. We also show that both diameter
bounds are best possible as an\r\nextension for both the Strong Nine Dragon Tree
Conjecture for pseudoforests and its original conjecture for forests. In fact,
they are still optimal even if we only enforce F to have any constant maximum
degree, instead of enforcing every component of F to have at most d edges."
acknowledgement: This work was completed while Benjamin Moore was a postdoc at Charles
University, supported by project 22-17398S (Flows and cycles in graphs on surfaces)
of Czech Science Foundation, Czechia.
article_number: '104214'
article_processing_charge: Yes (via OA deal)
article_type: original
arxiv: 1
author:
- first_name: Sebastian
full_name: Mies, Sebastian
last_name: Mies
- first_name: Benjamin
full_name: Moore, Benjamin
id: 6dc1a1be-bf1c-11ed-8d2b-d044840f49d6
last_name: Moore
- first_name: Evelyne
full_name: Smith-Roberge, Evelyne
last_name: Smith-Roberge
citation:
ama: Mies S, Moore B, Smith-Roberge E. Beyond the pseudoforest strong Nine Dragon
Tree theorem. European Journal of Combinatorics. 2025;130(12). doi:10.1016/j.ejc.2025.104214
apa: Mies, S., Moore, B., & Smith-Roberge, E. (2025). Beyond the pseudoforest
strong Nine Dragon Tree theorem. European Journal of Combinatorics. Elsevier.
https://doi.org/10.1016/j.ejc.2025.104214
chicago: Mies, Sebastian, Benjamin Moore, and Evelyne Smith-Roberge. “Beyond the
Pseudoforest Strong Nine Dragon Tree Theorem.” European Journal of Combinatorics.
Elsevier, 2025. https://doi.org/10.1016/j.ejc.2025.104214.
ieee: S. Mies, B. Moore, and E. Smith-Roberge, “Beyond the pseudoforest strong Nine
Dragon Tree theorem,” European Journal of Combinatorics, vol. 130, no.
12. Elsevier, 2025.
ista: Mies S, Moore B, Smith-Roberge E. 2025. Beyond the pseudoforest strong Nine
Dragon Tree theorem. European Journal of Combinatorics. 130(12), 104214.
mla: Mies, Sebastian, et al. “Beyond the Pseudoforest Strong Nine Dragon Tree Theorem.”
European Journal of Combinatorics, vol. 130, no. 12, 104214, Elsevier,
2025, doi:10.1016/j.ejc.2025.104214.
short: S. Mies, B. Moore, E. Smith-Roberge, European Journal of Combinatorics 130
(2025).
corr_author: '1'
date_created: 2025-09-10T05:36:50Z
date_published: 2025-12-01T00:00:00Z
date_updated: 2025-12-30T10:19:10Z
day: '01'
ddc:
- '500'
department:
- _id: MaKw
doi: 10.1016/j.ejc.2025.104214
external_id:
arxiv:
- '2310.00931'
isi:
- '001529769300002'
file:
- access_level: open_access
checksum: b1536e9256c4510a0e21452032e43a26
content_type: application/pdf
creator: dernst
date_created: 2025-12-30T10:18:56Z
date_updated: 2025-12-30T10:18:56Z
file_id: '20913'
file_name: 2025_EuropJournCombinatorics_Mies.pdf
file_size: 737845
relation: main_file
success: 1
file_date_updated: 2025-12-30T10:18:56Z
has_accepted_license: '1'
intvolume: ' 130'
isi: 1
issue: '12'
language:
- iso: eng
month: '12'
oa: 1
oa_version: Published Version
publication: European Journal of Combinatorics
publication_identifier:
issn:
- 0195-6698
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: Beyond the pseudoforest strong Nine Dragon Tree theorem
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: 130
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: '18157'
abstract:
- lang: eng
text: "Interest in sliding block puzzles dates back to the 15-puzzle, seemingly
invented by Noyes Chapman in 1874 (see [23] for an account of the fascinating
history of the puzzle). The game consists of fifteen movable square blocks numbered
\r\n and arranged within a \r\n square box, leaving one empty space (see Figure
1). The task at hand is to start from a given configuration of the numbered blocks
and reach the desired target configuration, where the only allowed move is to
slide a numbered block into an adjacent empty space. This task seemed to be unpredictably
either very easy to accomplish, or completely impossible, and the puzzle turned
into a worldwide sensation in the spring of 1880. A particularly challenging instance,
known as the 13-15-14 puzzle, consisted of initial and target configurations that
differed by a single swap (historically this swap involved the blocks labeled
14 and 15). The craze of this puzzle was such that it consistently made newspaper
headlines in 1880, with an article in the New York Times lamenting that it was
“threatening our free institutions” [23, p. 9]. Various prizes were offered for
anyone who could solve this challenge, beginning with a $25 set of teeth and culminating
with Sam Loyd’s famous $1,000 cash prize."
acknowledgement: Open access funding provided by Copenhagen University.
article_processing_charge: Yes (via OA deal)
article_type: original
arxiv: 1
author:
- first_name: Florestan R
full_name: Brunck, Florestan R
id: 6ab6e556-f394-11eb-9cf6-9dfb78f00d8d
last_name: Brunck
- 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: 'Brunck FR, Kwan MA. Books, Hallways, and social butterflies: A note on sliding
block puzzles. Mathematical Intelligencer. 2025;47:52-65. doi:10.1007/s00283-024-10358-x'
apa: 'Brunck, F. R., & Kwan, M. A. (2025). Books, Hallways, and social butterflies:
A note on sliding block puzzles. Mathematical Intelligencer. Springer Nature.
https://doi.org/10.1007/s00283-024-10358-x'
chicago: 'Brunck, Florestan R, and Matthew Alan Kwan. “Books, Hallways, and Social
Butterflies: A Note on Sliding Block Puzzles.” Mathematical Intelligencer.
Springer Nature, 2025. https://doi.org/10.1007/s00283-024-10358-x.'
ieee: 'F. R. Brunck and M. A. Kwan, “Books, Hallways, and social butterflies: A
note on sliding block puzzles,” Mathematical Intelligencer, vol. 47. Springer
Nature, pp. 52–65, 2025.'
ista: 'Brunck FR, Kwan MA. 2025. Books, Hallways, and social butterflies: A note
on sliding block puzzles. Mathematical Intelligencer. 47, 52–65.'
mla: 'Brunck, Florestan R., and Matthew Alan Kwan. “Books, Hallways, and Social
Butterflies: A Note on Sliding Block Puzzles.” Mathematical Intelligencer,
vol. 47, Springer Nature, 2025, pp. 52–65, doi:10.1007/s00283-024-10358-x.'
short: F.R. Brunck, M.A. Kwan, Mathematical Intelligencer 47 (2025) 52–65.
date_created: 2024-09-29T22:01:38Z
date_published: 2025-03-01T00:00:00Z
date_updated: 2025-05-19T14:00:09Z
day: '01'
ddc:
- '510'
department:
- _id: UlWa
- _id: MaKw
doi: 10.1007/s00283-024-10358-x
external_id:
arxiv:
- '2303.09459'
isi:
- '001318056000001'
file:
- access_level: open_access
checksum: c932ebe45c460d4a73f5b2dcca643db1
content_type: application/pdf
creator: dernst
date_created: 2025-04-08T11:17:45Z
date_updated: 2025-04-08T11:17:45Z
file_id: '19530'
file_name: 2025_MathIntelligencer_Brunck.pdf
file_size: 1760643
relation: main_file
success: 1
file_date_updated: 2025-04-08T11:17:45Z
has_accepted_license: '1'
intvolume: ' 47'
isi: 1
language:
- iso: eng
month: '03'
oa: 1
oa_version: Published Version
page: 52-65
publication: Mathematical Intelligencer
publication_identifier:
issn:
- 0343-6993
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Books, Hallways, and social butterflies: A note on sliding block puzzles'
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: 47
year: '2025'
...
---
_id: '15163'
abstract:
- lang: eng
text: For some k∈Z≥0∪{∞}, we call a linear forest k-bounded if each of its components
has at most k edges. We will say a (k,ℓ)-bounded linear forest decomposition of
a graph G is a partition of E(G) into the edge sets of two linear forests Fk,Fℓ
where Fk is k-bounded and Fℓ is ℓ-bounded. We show that the problem of deciding
whether a given graph has such a decomposition is NP-complete if both k and ℓ
are at least 2, NP-complete if k≥9 and ℓ=1, and is in P for (k,ℓ)=(2,1). Before
this, the only known NP-complete cases were the (2,2) and (3,3) cases. Our hardness
result answers a question of Bermond et al. from 1984. We also show that planar
graphs of girth at least nine decompose into a linear forest and a matching, which
in particular is stronger than 3-edge-colouring such graphs.
acknowledgement: We wish to thank Dániel Marx and András Sebő for making us aware
of the results in [8] and some clarifications on them.
article_number: '113962'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Rutger
full_name: Campbell, Rutger
last_name: Campbell
- first_name: Florian
full_name: Hörsch, Florian
last_name: Hörsch
- first_name: Benjamin
full_name: Moore, Benjamin
id: 6dc1a1be-bf1c-11ed-8d2b-d044840f49d6
last_name: Moore
citation:
ama: Campbell R, Hörsch F, Moore B. Decompositions into two linear forests of bounded
lengths. Discrete Mathematics. 2024;347(6). doi:10.1016/j.disc.2024.113962
apa: Campbell, R., Hörsch, F., & Moore, B. (2024). Decompositions into two linear
forests of bounded lengths. Discrete Mathematics. Elsevier. https://doi.org/10.1016/j.disc.2024.113962
chicago: Campbell, Rutger, Florian Hörsch, and Benjamin Moore. “Decompositions into
Two Linear Forests of Bounded Lengths.” Discrete Mathematics. Elsevier,
2024. https://doi.org/10.1016/j.disc.2024.113962.
ieee: R. Campbell, F. Hörsch, and B. Moore, “Decompositions into two linear forests
of bounded lengths,” Discrete Mathematics, vol. 347, no. 6. Elsevier, 2024.
ista: Campbell R, Hörsch F, Moore B. 2024. Decompositions into two linear forests
of bounded lengths. Discrete Mathematics. 347(6), 113962.
mla: Campbell, Rutger, et al. “Decompositions into Two Linear Forests of Bounded
Lengths.” Discrete Mathematics, vol. 347, no. 6, 113962, Elsevier, 2024,
doi:10.1016/j.disc.2024.113962.
short: R. Campbell, F. Hörsch, B. Moore, Discrete Mathematics 347 (2024).
corr_author: '1'
date_created: 2024-03-24T23:00:58Z
date_published: 2024-06-01T00:00:00Z
date_updated: 2025-09-04T13:10:26Z
day: '01'
department:
- _id: MaKw
doi: 10.1016/j.disc.2024.113962
external_id:
arxiv:
- '2301.11615'
isi:
- '001226893800001'
intvolume: ' 347'
isi: 1
issue: '6'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2301.11615
month: '06'
oa: 1
oa_version: Preprint
publication: Discrete Mathematics
publication_identifier:
issn:
- 0012-365X
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: Decompositions into two linear forests of bounded lengths
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 347
year: '2024'
...
---
OA_place: repository
OA_type: green
_id: '18559'
abstract:
- lang: eng
text: We prove a 1973 conjecture due to Erdős on the existence of Steiner triple
systems with arbitrarily high girth.
acknowledgement: Sah and Sawhney were supported by NSF Graduate Research Fellowship
Program DGE1745302. Sah was supported by the PD Soros Fellowship. Simkin was supported
by the Center of Mathematical Sciences and Applications at Harvard University.
article_processing_charge: No
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: Mehtaab
full_name: Sawhney, Mehtaab
last_name: Sawhney
- first_name: Michael
full_name: Simkin, Michael
last_name: Simkin
citation:
ama: Kwan MA, Sah A, Sawhney M, Simkin M. High-girth Steiner triple systems. Annals
of Mathematics. 2024;200(3):1059-1156. doi:10.4007/annals.2024.200.3.4
apa: Kwan, M. A., Sah, A., Sawhney, M., & Simkin, M. (2024). High-girth Steiner
triple systems. Annals of Mathematics. Princeton University. https://doi.org/10.4007/annals.2024.200.3.4
chicago: Kwan, Matthew Alan, Ashwin Sah, Mehtaab Sawhney, and Michael Simkin. “High-Girth
Steiner Triple Systems.” Annals of Mathematics. Princeton University, 2024.
https://doi.org/10.4007/annals.2024.200.3.4.
ieee: M. A. Kwan, A. Sah, M. Sawhney, and M. Simkin, “High-girth Steiner triple
systems,” Annals of Mathematics, vol. 200, no. 3. Princeton University,
pp. 1059–1156, 2024.
ista: Kwan MA, Sah A, Sawhney M, Simkin M. 2024. High-girth Steiner triple systems.
Annals of Mathematics. 200(3), 1059–1156.
mla: Kwan, Matthew Alan, et al. “High-Girth Steiner Triple Systems.” Annals of
Mathematics, vol. 200, no. 3, Princeton University, 2024, pp. 1059–156, doi:10.4007/annals.2024.200.3.4.
short: M.A. Kwan, A. Sah, M. Sawhney, M. Simkin, Annals of Mathematics 200 (2024)
1059–1156.
corr_author: '1'
date_created: 2024-11-17T23:01:48Z
date_published: 2024-11-01T00:00:00Z
date_updated: 2025-09-08T14:40:55Z
day: '01'
department:
- _id: MaKw
doi: 10.4007/annals.2024.200.3.4
external_id:
arxiv:
- '2201.04554'
isi:
- '001366233800004'
intvolume: ' 200'
isi: 1
issue: '3'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2201.04554
month: '11'
oa: 1
oa_version: Preprint
page: 1059-1156
publication: Annals of Mathematics
publication_identifier:
eissn:
- 1939-8980
issn:
- 0003-486X
publication_status: published
publisher: Princeton University
quality_controlled: '1'
scopus_import: '1'
status: public
title: High-girth Steiner triple systems
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 200
year: '2024'
...
---
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'
...
---
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'
date_created: 2024-12-15T23:01:51Z
date_published: 2024-11-24T00:00:00Z
date_updated: 2025-09-09T11:46:53Z
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
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'
scopus_import: '1'
status: public
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'
date_created: 2024-12-22T23:01:47Z
date_published: 2024-12-02T00:00:00Z
date_updated: 2025-12-02T13:55:46Z
day: '02'
department:
- _id: MaKw
- _id: KrPi
doi: 10.1007/978-3-031-78011-0_14
external_id:
isi:
- '001545628900014'
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'
scopus_import: '1'
status: public
title: The cost of maintaining keys in dynamic groups with applications to multicast
encryption and group messaging
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 15364
year: '2024'
...
---
OA_place: publisher
OA_type: gold
_id: '18758'
abstract:
- lang: eng
text: 'MaxCut is a classical NP-complete problem and a crucial building block in
many combinatorial algorithms. The famous Edwards-Erdős bound states that any
connected graph on n vertices with m edges contains a cut of size at least m/2+(n-1)/4.
Crowston, Jones and Mnich [Algorithmica, 2015] showed that the MaxCut problem
on simple connected graphs admits an FPT algorithm, where the parameter k is the
difference between the desired cut size c and the lower bound given by the Edwards-Erdős
bound. This was later improved by Etscheid and Mnich [Algorithmica, 2017] to run
in parameterized linear time, i.e., f(k)⋅ O(m). We improve upon this result in
two ways: Firstly, we extend the algorithm to work also for multigraphs (alternatively,
graphs with positive integer weights). Secondly, we change the parameter; instead
of the difference to the Edwards-Erdős bound, we use the difference to the Poljak-Turzík
bound. The Poljak-Turzík bound states that any weighted graph G has a cut of size
at least (w(G))/2+(w_MSF(G))/4, where w(G) denotes the total weight of G, and
w_MSF(G) denotes the weight of its minimum spanning forest. In connected simple
graphs the two bounds are equivalent, but for multigraphs the Poljak-Turzík bound
can be larger and thus yield a smaller parameter k. Our algorithm also runs in
parameterized linear time, i.e., f(k)⋅ O(m+n).'
acknowledgement: "Kalina Petrova: Swiss National Science Foundation, grant no. CRSII5
173721. This project\r\nhas received funding from the European Union’s Horizon 2020
research and innovation programme under the Marie Skłodowska-Curie grant agreement
No 101034413.\r\nSimon Weber: Swiss National Science Foundation under project no.
204320"
alternative_title:
- LIPIcs
article_number: '2'
article_processing_charge: Yes
arxiv: 1
author:
- first_name: Jonas
full_name: Lill, Jonas
last_name: Lill
- first_name: Kalina H
full_name: Petrova, Kalina H
id: 554ff4e4-f325-11ee-b0c4-a10dbd523381
last_name: Petrova
- first_name: Simon
full_name: Weber, Simon
last_name: Weber
citation:
ama: 'Lill J, Petrova KH, Weber S. Linear-time MaxCut in multigraphs parameterized
above the Poljak-Turzík bound. In: 19th International Symposium on Parameterized
and Exact Computation. Vol 321. Schloss Dagstuhl - Leibniz-Zentrum für Informatik;
2024. doi:10.4230/LIPIcs.IPEC.2024.2'
apa: 'Lill, J., Petrova, K. H., & Weber, S. (2024). Linear-time MaxCut in multigraphs
parameterized above the Poljak-Turzík bound. In 19th International Symposium
on Parameterized and Exact Computation (Vol. 321). Egham, United Kingdom:
Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.IPEC.2024.2'
chicago: Lill, Jonas, Kalina H Petrova, and Simon Weber. “Linear-Time MaxCut in
Multigraphs Parameterized above the Poljak-Turzík Bound.” In 19th International
Symposium on Parameterized and Exact Computation, Vol. 321. Schloss Dagstuhl
- Leibniz-Zentrum für Informatik, 2024. https://doi.org/10.4230/LIPIcs.IPEC.2024.2.
ieee: J. Lill, K. H. Petrova, and S. Weber, “Linear-time MaxCut in multigraphs parameterized
above the Poljak-Turzík bound,” in 19th International Symposium on Parameterized
and Exact Computation, Egham, United Kingdom, 2024, vol. 321.
ista: 'Lill J, Petrova KH, Weber S. 2024. Linear-time MaxCut in multigraphs parameterized
above the Poljak-Turzík bound. 19th International Symposium on Parameterized and
Exact Computation. IPEC: Symposium on Parameterized and Exact Computation, LIPIcs,
vol. 321, 2.'
mla: Lill, Jonas, et al. “Linear-Time MaxCut in Multigraphs Parameterized above
the Poljak-Turzík Bound.” 19th International Symposium on Parameterized and
Exact Computation, vol. 321, 2, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2024, doi:10.4230/LIPIcs.IPEC.2024.2.
short: J. Lill, K.H. Petrova, S. Weber, in:, 19th International Symposium on Parameterized
and Exact Computation, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.
conference:
end_date: 2024-09-06
location: Egham, United Kingdom
name: 'IPEC: Symposium on Parameterized and Exact Computation'
start_date: 2024-09-04
corr_author: '1'
date_created: 2025-01-05T23:01:57Z
date_published: 2024-12-05T00:00:00Z
date_updated: 2026-01-05T13:46:07Z
day: '05'
ddc:
- '500'
department:
- _id: MaKw
doi: 10.4230/LIPIcs.IPEC.2024.2
ec_funded: 1
external_id:
arxiv:
- '2407.01071'
isi:
- '001534851900002'
file:
- access_level: open_access
checksum: a64b9a0e41f7b867d25cb155825ccd53
content_type: application/pdf
creator: dernst
date_created: 2025-01-08T09:14:59Z
date_updated: 2025-01-08T09:14:59Z
file_id: '18775'
file_name: 2024_LIPIcs_Lill.pdf
file_size: 927326
relation: main_file
success: 1
file_date_updated: 2025-01-08T09:14:59Z
has_accepted_license: '1'
intvolume: ' 321'
isi: 1
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'
publication: 19th International Symposium on Parameterized and Exact Computation
publication_identifier:
isbn:
- '9783959773539'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
related_material:
record:
- id: '19603'
relation: later_version
status: public
scopus_import: '1'
status: public
title: Linear-time MaxCut in multigraphs parameterized above the Poljak-Turzík bound
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
volume: 321
year: '2024'
...
---
DOAJ_listed: '1'
OA_place: repository
OA_type: gold
_id: '18951'
abstract:
- lang: eng
text: "We consider local dynamics of the dimer model (perfect matchings) on hypercubic
boxes [n] \r\nd . These consist of successively switching the dimers along alternating
cycles of prescribed (small) lengths. We study the connectivity properties of
the dimer configuration space equipped with these transitions. Answering a question
of Freire, Klivans, Milet, and Saldanha, we show that in three dimensions any
configuration admits an alternating cycle of length at most 6. We further establish
that any configuration on [n] d features order n d−2 alternating cycles of length
at most 4d−2. We also prove that the dynamics of dimer configurations on the unit
hypercube of dimension d is ergodic when switching alternating cycles of length
at most 4d−4. Finally, in the planar but non-bipartite case, we show that parallelogram-shaped
boxes in the triangular lattice are ergodic for switching alternating cycles of
lengths 4 and 6 only, thus improving a result of Kenyon and Rémila, which also
uses 8-cycles. None of our proofs make reference to height functions."
article_processing_charge: Yes
article_type: original
arxiv: 1
author:
- first_name: Ivailo
full_name: Hartarsky, Ivailo
last_name: Hartarsky
- first_name: Lyuben
full_name: Lichev, Lyuben
id: 9aa8388e-d003-11ee-8458-c4c1d7447977
last_name: Lichev
- first_name: Fabio Lucio
full_name: Toninelli, Fabio Lucio
last_name: Toninelli
citation:
ama: Hartarsky I, Lichev L, Toninelli FL. Local dimer dynamics in higher dimensions.
Annales de l’Institut Henri Poincaré D, Combinatorics, Physics and their Interactions.
2024. doi:10.4171/aihpd/200
apa: Hartarsky, I., Lichev, L., & Toninelli, F. L. (2024). Local dimer dynamics
in higher dimensions. Annales de l’Institut Henri Poincaré D, Combinatorics,
Physics and Their Interactions. EMS Press. https://doi.org/10.4171/aihpd/200
chicago: Hartarsky, Ivailo, Lyuben Lichev, and Fabio Lucio Toninelli. “Local Dimer
Dynamics in Higher Dimensions.” Annales de l’Institut Henri Poincaré D, Combinatorics,
Physics and Their Interactions. EMS Press, 2024. https://doi.org/10.4171/aihpd/200.
ieee: I. Hartarsky, L. Lichev, and F. L. Toninelli, “Local dimer dynamics in higher
dimensions,” Annales de l’Institut Henri Poincaré D, Combinatorics, Physics
and their Interactions. EMS Press, 2024.
ista: Hartarsky I, Lichev L, Toninelli FL. 2024. Local dimer dynamics in higher
dimensions. Annales de l’Institut Henri Poincaré D, Combinatorics, Physics and
their Interactions.
mla: Hartarsky, Ivailo, et al. “Local Dimer Dynamics in Higher Dimensions.” Annales
de l’Institut Henri Poincaré D, Combinatorics, Physics and Their Interactions,
EMS Press, 2024, doi:10.4171/aihpd/200.
short: I. Hartarsky, L. Lichev, F.L. Toninelli, Annales de l’Institut Henri Poincaré
D, Combinatorics, Physics and Their Interactions (2024).
date_created: 2025-01-29T10:57:09Z
date_published: 2024-08-26T00:00:00Z
date_updated: 2025-07-08T08:39:55Z
day: '26'
department:
- _id: MaKw
doi: 10.4171/aihpd/200
external_id:
arxiv:
- '2304.10930'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2304.10930
month: '08'
oa: 1
oa_version: Preprint
publication: Annales de l’Institut Henri Poincaré D, Combinatorics, Physics and their
Interactions
publication_identifier:
eissn:
- 2308-5835
issn:
- 2308-5827
publication_status: epub_ahead
publisher: EMS Press
quality_controlled: '1'
scopus_import: '1'
status: public
title: Local dimer dynamics in higher dimensions
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
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: '11706'
abstract:
- lang: eng
text: 'We say that (Formula presented.) if, in every edge coloring (Formula presented.),
we can find either a 1-colored copy of (Formula presented.) or a 2-colored copy
of (Formula presented.). The well-known states that the threshold for the property
(Formula presented.) is equal to (Formula presented.), where (Formula presented.)
is given by (Formula presented.) for any pair of graphs (Formula presented.) and
(Formula presented.) with (Formula presented.). In this article, we show the 0-statement
of the Kohayakawa–Kreuter conjecture for every pair of cycles and cliques. '
acknowledgement: "This work was started at the thematic program GRAPHS@IMPA (January–March
2018), in Rio de Janeiro. We thank IMPA and the organisers for the hospitality and
for providing a pleasant research environment. We thank Rob Morris for helpful discussions,
and the anonymous referees for their careful reading and many helpful suggestions.
Open Access funding enabled and organized by Projekt DEAL.\r\nA. Liebenau was supported
by an ARC DECRA Fellowship Grant DE170100789. L. Mattos was supported by CAPES and
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). W. Mendonça was supported by CAPES project 88882.332408/2010-01."
article_processing_charge: Yes (in subscription journal)
article_type: original
author:
- first_name: Anita
full_name: Liebenau, Anita
last_name: Liebenau
- first_name: Letícia
full_name: Mattos, Letícia
last_name: Mattos
- first_name: Walner
full_name: Mendonca Dos Santos, Walner
id: 12c6bd4d-2cd0-11ec-a0da-e28f42f65ebd
last_name: Mendonca Dos Santos
- first_name: Jozef
full_name: Skokan, Jozef
last_name: Skokan
citation:
ama: Liebenau A, Mattos L, Mendonca dos Santos W, Skokan J. Asymmetric Ramsey properties
of random graphs involving cliques and cycles. Random Structures and Algorithms.
2023;62(4):1035-1055. doi:10.1002/rsa.21106
apa: Liebenau, A., Mattos, L., Mendonca dos Santos, W., & Skokan, J. (2023).
Asymmetric Ramsey properties of random graphs involving cliques and cycles. Random
Structures and Algorithms. Wiley. https://doi.org/10.1002/rsa.21106
chicago: Liebenau, Anita, Letícia Mattos, Walner Mendonca dos Santos, and Jozef
Skokan. “Asymmetric Ramsey Properties of Random Graphs Involving Cliques and Cycles.”
Random Structures and Algorithms. Wiley, 2023. https://doi.org/10.1002/rsa.21106.
ieee: A. Liebenau, L. Mattos, W. Mendonca dos Santos, and J. Skokan, “Asymmetric
Ramsey properties of random graphs involving cliques and cycles,” Random Structures
and Algorithms, vol. 62, no. 4. Wiley, pp. 1035–1055, 2023.
ista: Liebenau A, Mattos L, Mendonca dos Santos W, Skokan J. 2023. Asymmetric Ramsey
properties of random graphs involving cliques and cycles. Random Structures and
Algorithms. 62(4), 1035–1055.
mla: Liebenau, Anita, et al. “Asymmetric Ramsey Properties of Random Graphs Involving
Cliques and Cycles.” Random Structures and Algorithms, vol. 62, no. 4,
Wiley, 2023, pp. 1035–55, doi:10.1002/rsa.21106.
short: A. Liebenau, L. Mattos, W. Mendonca dos Santos, J. Skokan, Random Structures
and Algorithms 62 (2023) 1035–1055.
date_created: 2022-07-31T22:01:49Z
date_published: 2023-07-01T00:00:00Z
date_updated: 2023-10-04T09:38:45Z
day: '01'
ddc:
- '510'
department:
- _id: MaKw
doi: 10.1002/rsa.21106
external_id:
isi:
- '000828530400001'
file:
- access_level: open_access
checksum: 3a5969d0c512aef01c30f3dc81c6d59b
content_type: application/pdf
creator: dernst
date_created: 2023-10-04T09:37:26Z
date_updated: 2023-10-04T09:37:26Z
file_id: '14389'
file_name: 2023_RandomStructureAlgorithms_Liebenau.pdf
file_size: 1362334
relation: main_file
success: 1
file_date_updated: 2023-10-04T09:37:26Z
has_accepted_license: '1'
intvolume: ' 62'
isi: 1
issue: '4'
language:
- iso: eng
license: https://creativecommons.org/licenses/by-nc/4.0/
month: '07'
oa: 1
oa_version: Published Version
page: 1035-1055
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: Asymmetric Ramsey properties of random graphs involving cliques and cycles
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: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 62
year: '2023'
...
---
_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
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
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'
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: '14444'
abstract:
- lang: eng
text: "We prove several results about substructures in Latin squares. First, we
explain how to adapt our recent work on high-girth Steiner triple systems to the
setting of Latin squares, resolving a conjecture of Linial that there exist Latin
squares with arbitrarily high girth. As a consequence, we see that the number
of order- n Latin squares with no intercalate (i.e., no 2×2 Latin subsquare)
is at least (e−9/4n−o(n))n2. Equivalently, P[N=0]≥e−n2/4−o(n2)=e−(1+o(1))EN\r\n
, where N is the number of intercalates in a uniformly random order- n Latin
square. \r\nIn fact, extending recent work of Kwan, Sah, and Sawhney, we resolve
the general large-deviation problem for intercalates in random Latin squares,
up to constant factors in the exponent: for any constant 0<δ≤1 we have P[N≤(1−δ)EN]=exp(−Θ(n2))
and for any constant δ>0 we have P[N≥(1+δ)EN]=exp(−Θ(n4/3logn)). \r\nFinally,
as an application of some new general tools for studying substructures in random
Latin squares, we show that in almost all order- n Latin squares, the number of
cuboctahedra (i.e., the number of pairs of possibly degenerate 2×2 submatrices
with the same arrangement of symbols) is of order n4, which is the minimum possible.
As observed by Gowers and Long, this number can be interpreted as measuring ``how
associative'' the quasigroup associated with the Latin square is."
acknowledgement: Sah and Sawhney were supported by NSF Graduate Research Fellowship
Program DGE-1745302. Sah was supported by the PD Soros Fellowship. Simkin was supported
by the Center of Mathematical Sciences and Applications at Harvard University.
article_processing_charge: Yes (in subscription journal)
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: Mehtaab
full_name: Sawhney, Mehtaab
last_name: Sawhney
- first_name: Michael
full_name: Simkin, Michael
last_name: Simkin
citation:
ama: Kwan MA, Sah A, Sawhney M, Simkin M. Substructures in Latin squares. Israel
Journal of Mathematics. 2023;256(2):363-416. doi:10.1007/s11856-023-2513-9
apa: Kwan, M. A., Sah, A., Sawhney, M., & Simkin, M. (2023). Substructures in
Latin squares. Israel Journal of Mathematics. Springer Nature. https://doi.org/10.1007/s11856-023-2513-9
chicago: Kwan, Matthew Alan, Ashwin Sah, Mehtaab Sawhney, and Michael Simkin. “Substructures
in Latin Squares.” Israel Journal of Mathematics. Springer Nature, 2023.
https://doi.org/10.1007/s11856-023-2513-9.
ieee: M. A. Kwan, A. Sah, M. Sawhney, and M. Simkin, “Substructures in Latin squares,”
Israel Journal of Mathematics, vol. 256, no. 2. Springer Nature, pp. 363–416,
2023.
ista: Kwan MA, Sah A, Sawhney M, Simkin M. 2023. Substructures in Latin squares.
Israel Journal of Mathematics. 256(2), 363–416.
mla: Kwan, Matthew Alan, et al. “Substructures in Latin Squares.” Israel Journal
of Mathematics, vol. 256, no. 2, Springer Nature, 2023, pp. 363–416, doi:10.1007/s11856-023-2513-9.
short: M.A. Kwan, A. Sah, M. Sawhney, M. Simkin, Israel Journal of Mathematics 256
(2023) 363–416.
date_created: 2023-10-22T22:01:14Z
date_published: 2023-09-01T00:00:00Z
date_updated: 2025-09-09T13:08:47Z
day: '01'
department:
- _id: MaKw
doi: 10.1007/s11856-023-2513-9
external_id:
arxiv:
- '2202.05088'
isi:
- '001081646400001'
intvolume: ' 256'
isi: 1
issue: '2'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2202.05088
month: '09'
oa: 1
oa_version: Preprint
page: 363-416
publication: Israel Journal of Mathematics
publication_identifier:
eissn:
- 1565-8511
issn:
- 0021-2172
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Substructures in Latin squares
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 256
year: '2023'
...