---
_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: '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: 2023-09-15T08:12:30Z
day: '28'
ddc:
- '510'
department:
- _id: MaKw
doi: 10.37236/11714
ec_funded: 1
external_id:
arxiv:
- '2212.03100'
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'
issue: '3'
language:
- iso: eng
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: 2DF688A6-F248-11E8-B48F-1D18A9856A87
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
date_created: 2023-09-17T22:01:10Z
date_published: 2023-01-01T00:00:00Z
date_updated: 2023-09-25T09:13:41Z
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: 2023-10-31T11:27:30Z
day: '01'
department:
- _id: MaKw
doi: 10.1007/s11856-023-2513-9
external_id:
arxiv:
- '2202.05088'
intvolume: ' 256'
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: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 256
year: '2023'
...
---
_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).
date_created: 2023-11-07T09:02:48Z
date_published: 2023-08-24T00:00:00Z
date_updated: 2023-11-07T09:18:57Z
day: '24'
ddc:
- '510'
department:
- _id: MaKw
doi: 10.1017/fmp.2023.17
external_id:
arxiv:
- '2208.02874'
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'
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: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 11
year: '2023'
...
---
_id: '14867'
abstract:
- lang: eng
text: Starting with the empty graph on $[n]$, at each round, a set of $K=K(n)$
edges is presented chosen uniformly at random from the ones that have not been
presented yet. We are then asked to choose at most one of the presented edges
and add it to the current graph. Our goal is to construct a Hamiltonian graph
with $(1+o(1))n$ edges within as few rounds as possible. We show that in this
process, one can build a Hamiltonian graph of size $(1+o(1))n$ in $(1+o(1))(1+(\log
n)/2K) n$ rounds w.h.p. The case $K=1$ implies that w.h.p. one can build a Hamiltonian
graph by choosing $(1+o(1))n$ edges in an online fashion as they appear along
the first $(0.5+o(1))n\log n$ rounds of the random graph process. This answers
a question of Frieze, Krivelevich and Michaeli. Observe that the number of rounds
is asymptotically optimal as the first $0.5n\log n$ edges do not span a Hamilton
cycle w.h.p. The case $K=\Theta(\log n)$ implies that the Hamiltonicity threshold
of the corresponding Achlioptas process is at most $(1+o(1))(1+(\log n)/2K) n$.
This matches the $(1-o(1))(1+(\log n)/2K) n$ lower bound due to Krivelevich, Lubetzky
and Sudakov and resolves the problem of determining the Hamiltonicity threshold
of the Achlioptas process with $K=\Theta(\log n)$. We also show that in the above
process one can construct a graph $G$ that spans a matching of size $\lfloor V(G)/2)
\rfloor$ and $(0.5+o(1))n$ edges within $(1+o(1))(0.5+(\log n)/2K) n$ rounds w.h.p.
Our proof relies on a robust Hamiltonicity property of the strong $4$-core of
the binomial random graph which we use as a black-box. This property allows it
to absorb paths covering vertices outside the strong $4$-core into a cycle.
acknowledgement: "This project has received funding from the European Union’s Horizon
2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement
No 101034413.\r\n"
article_processing_charge: No
arxiv: 1
author:
- first_name: Michael
full_name: Anastos, Michael
id: 0b2a4358-bb35-11ec-b7b9-e3279b593dbb
last_name: Anastos
citation:
ama: 'Anastos M. Constructing Hamilton cycles and perfect matchings efficiently.
In: Proceedings of the 12th European Conference on Combinatorics, Graph Theory
and Applications. Masaryk University Press; 2023:36-41. doi:10.5817/cz.muni.eurocomb23-005'
apa: 'Anastos, M. (2023). Constructing Hamilton cycles and perfect matchings efficiently.
In Proceedings of the 12th European Conference on Combinatorics, Graph Theory
and Applications (pp. 36–41). Prague, Czech Republic: Masaryk University Press.
https://doi.org/10.5817/cz.muni.eurocomb23-005'
chicago: Anastos, Michael. “Constructing Hamilton Cycles and Perfect Matchings Efficiently.”
In Proceedings of the 12th European Conference on Combinatorics, Graph Theory
and Applications, 36–41. Masaryk University Press, 2023. https://doi.org/10.5817/cz.muni.eurocomb23-005.
ieee: M. Anastos, “Constructing Hamilton cycles and perfect matchings efficiently,”
in Proceedings of the 12th European Conference on Combinatorics, Graph Theory
and Applications, Prague, Czech Republic, 2023, pp. 36–41.
ista: 'Anastos M. 2023. Constructing Hamilton cycles and perfect matchings efficiently.
Proceedings of the 12th European Conference on Combinatorics, Graph Theory and
Applications. EUROCOMB: European Conference on Combinatorics, Graph Theory and
Applications, 36–41.'
mla: Anastos, Michael. “Constructing Hamilton Cycles and Perfect Matchings Efficiently.”
Proceedings of the 12th European Conference on Combinatorics, Graph Theory
and Applications, Masaryk University Press, 2023, pp. 36–41, doi:10.5817/cz.muni.eurocomb23-005.
short: M. Anastos, in:, Proceedings of the 12th European Conference on Combinatorics,
Graph Theory and Applications, Masaryk University Press, 2023, pp. 36–41.
conference:
end_date: 2023-09-01
location: Prague, Czech Republic
name: 'EUROCOMB: European Conference on Combinatorics, Graph Theory and Applications'
start_date: 2023-08-28
date_created: 2024-01-22T12:20:15Z
date_published: 2023-09-01T00:00:00Z
date_updated: 2024-01-24T09:38:44Z
day: '01'
ddc:
- '510'
department:
- _id: MaKw
doi: 10.5817/cz.muni.eurocomb23-005
ec_funded: 1
external_id:
arxiv:
- '2209.09860'
file:
- access_level: open_access
checksum: fb1d9a1e7389d90ec0e5e76934373cf8
content_type: application/pdf
creator: dernst
date_created: 2024-01-24T09:34:43Z
date_updated: 2024-01-24T09:34:43Z
file_id: '14881'
file_name: 2023_Eurocomb_Anastos.pdf
file_size: 464230
relation: main_file
success: 1
file_date_updated: 2024-01-24T09:34:43Z
has_accepted_license: '1'
language:
- iso: eng
month: '09'
oa: 1
oa_version: Published Version
page: 36-41
project:
- _id: fc2ed2f7-9c52-11eb-aca3-c01059dda49c
call_identifier: H2020
grant_number: '101034413'
name: 'IST-BRIDGE: International postdoctoral program'
publication: Proceedings of the 12th European Conference on Combinatorics, Graph Theory
and Applications
publication_identifier:
eissn:
- 2788-3116
publication_status: published
publisher: Masaryk University Press
quality_controlled: '1'
status: public
title: Constructing Hamilton cycles and perfect matchings efficiently
tmp:
image: /images/cc_by_nc_nd.png
legal_code_url: https://creativecommons.org/licenses/by-nc-nd/4.0/legalcode
name: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International
(CC BY-NC-ND 4.0)
short: CC BY-NC-ND (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
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).
date_created: 2023-05-21T22:01:05Z
date_published: 2023-05-05T00:00:00Z
date_updated: 2023-08-01T14:44:52Z
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: '10775'
abstract:
- lang: eng
text: List-decodability of Reed–Solomon codes has received a lot of attention, but
the best-possible dependence between the parameters is still not well-understood.
In this work, we focus on the case where the list-decoding radius is of the form
r = 1-ε for ε tending to zero. Our main result states that there exist Reed–Solomon
codes with rate Ω(ε) which are (1 - ε, O(1/ε))-list-decodable, meaning that any
Hamming ball of radius 1-ε contains at most O(1/ε) codewords. This trade-off between
rate and list-decoding radius is best-possible for any code with list size less
than exponential in the block length. By achieving this trade-off between rate
and list-decoding radius we improve a recent result of Guo, Li, Shangguan, Tamo,
and Wootters, and resolve the main motivating question of their work. Moreover,
while their result requires the field to be exponentially large in the block length,
we only need the field size to be polynomially large (and in fact, almost-linear
suffices). We deduce our main result from a more general theorem, in which we
prove good list-decodability properties of random puncturings of any given code
with very large distance.
acknowledgement: Research supported by NSF Award DMS-1953990.
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Asaf
full_name: Ferber, Asaf
last_name: Ferber
- 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: Lisa
full_name: Sauermann, Lisa
last_name: Sauermann
citation:
ama: Ferber A, Kwan MA, Sauermann L. List-decodability with large radius for Reed-Solomon
codes. IEEE Transactions on Information Theory. 2022;68(6):3823-3828. doi:10.1109/TIT.2022.3148779
apa: Ferber, A., Kwan, M. A., & Sauermann, L. (2022). List-decodability with
large radius for Reed-Solomon codes. IEEE Transactions on Information Theory.
IEEE. https://doi.org/10.1109/TIT.2022.3148779
chicago: Ferber, Asaf, Matthew Alan Kwan, and Lisa Sauermann. “List-Decodability
with Large Radius for Reed-Solomon Codes.” IEEE Transactions on Information
Theory. IEEE, 2022. https://doi.org/10.1109/TIT.2022.3148779.
ieee: A. Ferber, M. A. Kwan, and L. Sauermann, “List-decodability with large radius
for Reed-Solomon codes,” IEEE Transactions on Information Theory, vol.
68, no. 6. IEEE, pp. 3823–3828, 2022.
ista: Ferber A, Kwan MA, Sauermann L. 2022. List-decodability with large radius
for Reed-Solomon codes. IEEE Transactions on Information Theory. 68(6), 3823–3828.
mla: Ferber, Asaf, et al. “List-Decodability with Large Radius for Reed-Solomon
Codes.” IEEE Transactions on Information Theory, vol. 68, no. 6, IEEE,
2022, pp. 3823–28, doi:10.1109/TIT.2022.3148779.
short: A. Ferber, M.A. Kwan, L. Sauermann, IEEE Transactions on Information Theory
68 (2022) 3823–3828.
date_created: 2022-02-20T23:01:34Z
date_published: 2022-06-01T00:00:00Z
date_updated: 2023-08-03T06:57:01Z
day: '01'
department:
- _id: MaKw
doi: 10.1109/TIT.2022.3148779
external_id:
arxiv:
- '2012.10584'
isi:
- '000799622500022'
intvolume: ' 68'
isi: 1
issue: '6'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/2012.10584
month: '06'
oa: 1
oa_version: Preprint
page: 3823-3828
publication: IEEE Transactions on Information Theory
publication_identifier:
eissn:
- 1557-9654
issn:
- 0018-9448
publication_status: published
publisher: IEEE
quality_controlled: '1'
related_material:
record:
- id: '11145'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: List-decodability with large radius for Reed-Solomon codes
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 68
year: '2022'
...
---
_id: '11145'
abstract:
- lang: eng
text: List-decodability of Reed-Solomon codes has re-ceived a lot of attention,
but the best-possible dependence between the parameters is still not well-understood.
In this work, we focus on the case where the list-decoding radius is of the form
r=1−ε for ε tending to zero. Our main result states that there exist Reed-Solomon
codes with rate Ω(ε) which are (1−ε,O(1/ε) -list-decodable, meaning that any Hamming
ball of radius 1−ε contains at most O(1/ε) codewords. This trade-off between rate
and list-decoding radius is best-possible for any code with list size less than
exponential in the block length. By achieving this trade-off between rate and
list-decoding radius we improve a recent result of Guo, Li, Shangguan, Tamo, and
Wootters, and resolve the main motivating question of their work. Moreover, while
their result requires the field to be exponentially large in the block length,
we only need the field size to be polynomially large (and in fact, almost-linear
suffices). We deduce our main result from a more general theorem, in which we
prove good list-decodability properties of random puncturings of any given code
with very large distance.
article_processing_charge: No
arxiv: 1
author:
- first_name: Asaf
full_name: Ferber, Asaf
last_name: Ferber
- 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: Lisa
full_name: Sauermann, Lisa
last_name: Sauermann
citation:
ama: 'Ferber A, Kwan MA, Sauermann L. List-decodability with large radius for Reed-Solomon
codes. In: 62nd Annual IEEE Symposium on Foundations of Computer Science.
Vol 2022. IEEE; 2022:720-726. doi:10.1109/FOCS52979.2021.00075'
apa: 'Ferber, A., Kwan, M. A., & Sauermann, L. (2022). List-decodability with
large radius for Reed-Solomon codes. In 62nd Annual IEEE Symposium on Foundations
of Computer Science (Vol. 2022, pp. 720–726). Denver, CO, United States: IEEE.
https://doi.org/10.1109/FOCS52979.2021.00075'
chicago: Ferber, Asaf, Matthew Alan Kwan, and Lisa Sauermann. “List-Decodability
with Large Radius for Reed-Solomon Codes.” In 62nd Annual IEEE Symposium on
Foundations of Computer Science, 2022:720–26. IEEE, 2022. https://doi.org/10.1109/FOCS52979.2021.00075.
ieee: A. Ferber, M. A. Kwan, and L. Sauermann, “List-decodability with large radius
for Reed-Solomon codes,” in 62nd Annual IEEE Symposium on Foundations of Computer
Science, Denver, CO, United States, 2022, vol. 2022, pp. 720–726.
ista: 'Ferber A, Kwan MA, Sauermann L. 2022. List-decodability with large radius
for Reed-Solomon codes. 62nd Annual IEEE Symposium on Foundations of Computer
Science. FOCS: Symposium on Foundations of Computer Science vol. 2022, 720–726.'
mla: Ferber, Asaf, et al. “List-Decodability with Large Radius for Reed-Solomon
Codes.” 62nd Annual IEEE Symposium on Foundations of Computer Science,
vol. 2022, IEEE, 2022, pp. 720–26, doi:10.1109/FOCS52979.2021.00075.
short: A. Ferber, M.A. Kwan, L. Sauermann, in:, 62nd Annual IEEE Symposium on Foundations
of Computer Science, IEEE, 2022, pp. 720–726.
conference:
end_date: 2022-02-10
location: Denver, CO, United States
name: 'FOCS: Symposium on Foundations of Computer Science'
start_date: 2022-02-07
date_created: 2022-04-10T22:01:40Z
date_published: 2022-02-01T00:00:00Z
date_updated: 2023-08-03T06:57:02Z
day: '01'
department:
- _id: MaKw
doi: 10.1109/FOCS52979.2021.00075
external_id:
arxiv:
- '2012.10584'
isi:
- '000802209600065'
intvolume: ' 2022'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: ' https://doi.org/10.48550/arXiv.2012.10584'
month: '02'
oa: 1
oa_version: Preprint
page: 720-726
publication: 62nd Annual IEEE Symposium on Foundations of Computer Science
publication_identifier:
isbn:
- '9781665420556'
issn:
- 0272-5428
publication_status: published
publisher: IEEE
quality_controlled: '1'
related_material:
record:
- id: '10775'
relation: later_version
status: public
scopus_import: '1'
status: public
title: List-decodability with large radius for Reed-Solomon codes
type: conference
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 2022
year: '2022'
...
---
_id: '11186'
abstract:
- lang: eng
text: "In this note, we study large deviations of the number \U0001D40D of intercalates
( 2×2 combinatorial subsquares which are themselves Latin squares) in a random
\ \U0001D45B×\U0001D45B Latin square. In particular, for constant \U0001D6FF>0
\ we prove that exp(−\U0001D442(\U0001D45B2log\U0001D45B))⩽Pr(\U0001D40D⩽(1−\U0001D6FF)\U0001D45B2/4)⩽exp(−Ω(\U0001D45B2))
\ and exp(−\U0001D442(\U0001D45B4/3(log\U0001D45B)))⩽Pr(\U0001D40D⩾(1+\U0001D6FF)\U0001D45B2/4)⩽exp(−Ω(\U0001D45B4/3(log\U0001D45B)2/3))
. As a consequence, we deduce that a typical order- \U0001D45B Latin square has
\ (1+\U0001D45C(1))\U0001D45B2/4 intercalates, matching a lower bound due to
Kwan and Sudakov and resolving an old conjecture of McKay and Wanless."
acknowledgement: "We thank Zach Hunter for pointing out some important typographical
errors. We also thank the referee for several remarks which helped improve the paper
substantially.\r\nKwan was supported by NSF grant DMS-1953990. Sah and Sawhney were
supported by NSF Graduate Research Fellowship Program DGE-1745302."
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
citation:
ama: Kwan MA, Sah A, Sawhney M. Large deviations in random latin squares. Bulletin
of the London Mathematical Society. 2022;54(4):1420-1438. doi:10.1112/blms.12638
apa: Kwan, M. A., Sah, A., & Sawhney, M. (2022). Large deviations in random
latin squares. Bulletin of the London Mathematical Society. Wiley. https://doi.org/10.1112/blms.12638
chicago: Kwan, Matthew Alan, Ashwin Sah, and Mehtaab Sawhney. “Large Deviations
in Random Latin Squares.” Bulletin of the London Mathematical Society.
Wiley, 2022. https://doi.org/10.1112/blms.12638.
ieee: M. A. Kwan, A. Sah, and M. Sawhney, “Large deviations in random latin squares,”
Bulletin of the London Mathematical Society, vol. 54, no. 4. Wiley, pp.
1420–1438, 2022.
ista: Kwan MA, Sah A, Sawhney M. 2022. Large deviations in random latin squares.
Bulletin of the London Mathematical Society. 54(4), 1420–1438.
mla: Kwan, Matthew Alan, et al. “Large Deviations in Random Latin Squares.” Bulletin
of the London Mathematical Society, vol. 54, no. 4, Wiley, 2022, pp. 1420–38,
doi:10.1112/blms.12638.
short: M.A. Kwan, A. Sah, M. Sawhney, Bulletin of the London Mathematical Society
54 (2022) 1420–1438.
date_created: 2022-04-17T22:01:48Z
date_published: 2022-08-01T00:00:00Z
date_updated: 2023-08-03T06:47:29Z
day: '01'
ddc:
- '510'
department:
- _id: MaKw
doi: 10.1112/blms.12638
external_id:
arxiv:
- '2106.11932'
isi:
- '000779920900001'
file:
- access_level: open_access
checksum: 02d74e7ae955ba3c808e2a8aebe6ef98
content_type: application/pdf
creator: dernst
date_created: 2023-02-03T09:43:38Z
date_updated: 2023-02-03T09:43:38Z
file_id: '12499'
file_name: 2022_BulletinMathSociety_Kwan.pdf
file_size: 233758
relation: main_file
success: 1
file_date_updated: 2023-02-03T09:43:38Z
has_accepted_license: '1'
intvolume: ' 54'
isi: 1
issue: '4'
language:
- iso: eng
month: '08'
oa: 1
oa_version: Published Version
page: 1420-1438
publication: Bulletin of the London Mathematical Society
publication_identifier:
eissn:
- 1469-2120
issn:
- 0024-6093
publication_status: published
publisher: Wiley
quality_controlled: '1'
scopus_import: '1'
status: public
title: Large deviations in random latin squares
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: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 54
year: '2022'
...
---
_id: '11443'
abstract:
- lang: eng
text: Sometimes, it is possible to represent a complicated polytope as a projection
of a much simpler polytope. To quantify this phenomenon, the extension complexity
of a polytope P is defined to be the minimum number of facets of a (possibly higher-dimensional)
polytope from which P can be obtained as a (linear) projection. This notion is
motivated by its relevance to combinatorial optimisation, and has been studied
intensively for various specific polytopes associated with important optimisation
problems. In this paper we study extension complexity as a parameter of general
polytopes, more specifically considering various families of low-dimensional polytopes.
First, we prove that for a fixed dimension d, the extension complexity of a random
d-dimensional polytope (obtained as the convex hull of random points in a ball
or on a sphere) is typically on the order of the square root of its number of
vertices. Second, we prove that any cyclic n-vertex polygon (whose vertices lie
on a circle) has extension complexity at most 24√n. This bound is tight up to
the constant factor 24. Finally, we show that there exists an no(1)-dimensional
polytope with at most n vertices and extension complexity n1−o(1). Our theorems
are proved with a range of different techniques, which we hope will be of further
interest.
acknowledgement: "The research of the first author was supported by SNSF Project 178493
and NSF Award DMS-1953990. The research of the second author supported by NSF Award
DMS-1953772.\r\nThe research of the third author was supported by NSF Award DMS-1764176,
NSF CAREER Award DMS-2044606, a Sloan Research Fellowship, and the MIT Solomon Buchsbaum
Fund. "
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: Lisa
full_name: Sauermann, Lisa
last_name: Sauermann
- first_name: Yufei
full_name: Zhao, Yufei
last_name: Zhao
citation:
ama: Kwan MA, Sauermann L, Zhao Y. Extension complexity of low-dimensional polytopes.
Transactions of the American Mathematical Society. 2022;375(6):4209-4250.
doi:10.1090/tran/8614
apa: Kwan, M. A., Sauermann, L., & Zhao, Y. (2022). Extension complexity of
low-dimensional polytopes. Transactions of the American Mathematical Society.
American Mathematical Society. https://doi.org/10.1090/tran/8614
chicago: Kwan, Matthew Alan, Lisa Sauermann, and Yufei Zhao. “Extension Complexity
of Low-Dimensional Polytopes.” Transactions of the American Mathematical Society.
American Mathematical Society, 2022. https://doi.org/10.1090/tran/8614.
ieee: M. A. Kwan, L. Sauermann, and Y. Zhao, “Extension complexity of low-dimensional
polytopes,” Transactions of the American Mathematical Society, vol. 375,
no. 6. American Mathematical Society, pp. 4209–4250, 2022.
ista: Kwan MA, Sauermann L, Zhao Y. 2022. Extension complexity of low-dimensional
polytopes. Transactions of the American Mathematical Society. 375(6), 4209–4250.
mla: Kwan, Matthew Alan, et al. “Extension Complexity of Low-Dimensional Polytopes.”
Transactions of the American Mathematical Society, vol. 375, no. 6, American
Mathematical Society, 2022, pp. 4209–50, doi:10.1090/tran/8614.
short: M.A. Kwan, L. Sauermann, Y. Zhao, Transactions of the American Mathematical
Society 375 (2022) 4209–4250.
date_created: 2022-06-12T22:01:45Z
date_published: 2022-06-01T00:00:00Z
date_updated: 2023-08-03T07:17:37Z
day: '01'
department:
- _id: MaKw
doi: 10.1090/tran/8614
external_id:
arxiv:
- '2006.08836'
isi:
- '000798461500001'
intvolume: ' 375'
isi: 1
issue: '6'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: ' https://doi.org/10.48550/arXiv.2006.08836'
month: '06'
oa: 1
oa_version: Preprint
page: 4209-4250
publication: Transactions of the American Mathematical Society
publication_identifier:
eissn:
- 1088-6850
issn:
- 0002-9947
publication_status: published
publisher: American Mathematical Society
quality_controlled: '1'
scopus_import: '1'
status: public
title: Extension complexity of low-dimensional polytopes
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 375
year: '2022'
...
---
_id: '11740'
abstract:
- lang: eng
text: "We consider a generalised model of a random simplicial complex, which arises
from a random hypergraph. Our model is generated by taking the downward-closure
of a non-uniform binomial random hypergraph, in which for each k, each set of
k+1 vertices forms an edge with some probability pk independently. As a special
case, this contains an extensively studied model of a (uniform) random simplicial
complex, introduced by Meshulam and Wallach [Random Structures & Algorithms 34
(2009), no. 3, pp. 408–417].\r\nWe consider a higher-dimensional notion of connectedness
on this new model according to the vanishing of cohomology groups over an arbitrary
abelian group R. We prove that this notion of connectedness displays a phase transition
and determine the threshold. We also prove a hitting time result for a natural
process interpretation, in which simplices and their downward-closure are added
one by one. In addition, we determine the asymptotic behaviour of cohomology groups
inside the critical window around the time of the phase transition."
acknowledgement: 'Supported by Austrian Science Fund (FWF): I3747, W1230.'
article_number: P3.27
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Oliver
full_name: Cooley, Oliver
id: 43f4ddd0-a46b-11ec-8df6-ef3703bd721d
last_name: Cooley
- first_name: Nicola
full_name: Del Giudice, Nicola
last_name: Del Giudice
- first_name: Mihyun
full_name: Kang, Mihyun
last_name: Kang
- first_name: Philipp
full_name: Sprüssel, Philipp
last_name: Sprüssel
citation:
ama: Cooley O, Del Giudice N, Kang M, Sprüssel P. Phase transition in cohomology
groups of non-uniform random simplicial complexes. Electronic Journal of Combinatorics.
2022;29(3). doi:10.37236/10607
apa: Cooley, O., Del Giudice, N., Kang, M., & Sprüssel, P. (2022). Phase transition
in cohomology groups of non-uniform random simplicial complexes. Electronic
Journal of Combinatorics. Electronic Journal of Combinatorics. https://doi.org/10.37236/10607
chicago: Cooley, Oliver, Nicola Del Giudice, Mihyun Kang, and Philipp Sprüssel.
“Phase Transition in Cohomology Groups of Non-Uniform Random Simplicial Complexes.”
Electronic Journal of Combinatorics. Electronic Journal of Combinatorics,
2022. https://doi.org/10.37236/10607.
ieee: O. Cooley, N. Del Giudice, M. Kang, and P. Sprüssel, “Phase transition in
cohomology groups of non-uniform random simplicial complexes,” Electronic Journal
of Combinatorics, vol. 29, no. 3. Electronic Journal of Combinatorics, 2022.
ista: Cooley O, Del Giudice N, Kang M, Sprüssel P. 2022. Phase transition in cohomology
groups of non-uniform random simplicial complexes. Electronic Journal of Combinatorics.
29(3), P3.27.
mla: Cooley, Oliver, et al. “Phase Transition in Cohomology Groups of Non-Uniform
Random Simplicial Complexes.” Electronic Journal of Combinatorics, vol.
29, no. 3, P3.27, Electronic Journal of Combinatorics, 2022, doi:10.37236/10607.
short: O. Cooley, N. Del Giudice, M. Kang, P. Sprüssel, Electronic Journal of Combinatorics
29 (2022).
date_created: 2022-08-07T22:01:59Z
date_published: 2022-07-29T00:00:00Z
date_updated: 2023-08-03T12:37:54Z
day: '29'
ddc:
- '510'
department:
- _id: MaKw
doi: 10.37236/10607
external_id:
arxiv:
- '2005.07103'
isi:
- '000836200300001'
file:
- access_level: open_access
checksum: 057c676dcee70236aa234d4ce6138c69
content_type: application/pdf
creator: dernst
date_created: 2022-08-08T06:28:52Z
date_updated: 2022-08-08T06:28:52Z
file_id: '11742'
file_name: 2022_ElecJournCombinatorics_Cooley.pdf
file_size: 1768663
relation: main_file
success: 1
file_date_updated: 2022-08-08T06:28:52Z
has_accepted_license: '1'
intvolume: ' 29'
isi: 1
issue: '3'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
publication: Electronic Journal of Combinatorics
publication_identifier:
eissn:
- 1077-8926
publication_status: published
publisher: Electronic Journal of Combinatorics
quality_controlled: '1'
scopus_import: '1'
status: public
title: Phase transition in cohomology groups of non-uniform random simplicial complexes
tmp:
image: /image/cc_by_nd.png
legal_code_url: https://creativecommons.org/licenses/by-nd/4.0/legalcode
name: Creative Commons Attribution-NoDerivatives 4.0 International (CC BY-ND 4.0)
short: CC BY-ND (4.0)
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 29
year: '2022'
...
---
_id: '12151'
abstract:
- lang: eng
text: The k-sample G(k,W) from a graphon W:[0,1]2→[0,1] is the random graph on {1,…,k},
where we sample x1,…,xk∈[0,1] uniformly at random and make each pair {i,j}⊆{1,…,k}
an edge with probability W(xi,xj), with all these choices being mutually independent.
Let the random variable Xk(W) be the number of edges in G(k,W). Vera T. Sós asked
in 2012 whether two graphons U, W are necessarily weakly isomorphic if the random
variables Xk(U) and Xk(W) have the same distribution for every integer k≥2. This
question when one of the graphons W is a constant function was answered positively
by Endre Csóka and independently by Jacob Fox, Tomasz Łuczak and Vera T. Sós.
Here we investigate the question when W is a 2-step graphon and prove that the
answer is positive for a 3-dimensional family of such graphons. We also present
some related results.
acknowledgement: "Supported by Austrian Science Fund (FWF) Grant I3747. Supported
by ERC Advanced Grant 101020255 and Leverhulme Research Project Grant RPG-2018-424.\r\nAn
extended abstract of this paper appeared in the Proceedings of the European Conference\r\non
Combinatorics, Graph Theory and Applications (EuroComb 2021), CRM Research Perspectives,
Springer."
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Oliver
full_name: Cooley, Oliver
id: 43f4ddd0-a46b-11ec-8df6-ef3703bd721d
last_name: Cooley
- first_name: M.
full_name: Kang, M.
last_name: Kang
- first_name: O.
full_name: Pikhurko, O.
last_name: Pikhurko
citation:
ama: Cooley O, Kang M, Pikhurko O. On a question of Vera T. Sós about size forcing
of graphons. Acta Mathematica Hungarica. 2022;168:1-26. doi:10.1007/s10474-022-01265-8
apa: Cooley, O., Kang, M., & Pikhurko, O. (2022). On a question of Vera T. Sós
about size forcing of graphons. Acta Mathematica Hungarica. Springer Nature.
https://doi.org/10.1007/s10474-022-01265-8
chicago: Cooley, Oliver, M. Kang, and O. Pikhurko. “On a Question of Vera T. Sós
about Size Forcing of Graphons.” Acta Mathematica Hungarica. Springer Nature,
2022. https://doi.org/10.1007/s10474-022-01265-8.
ieee: O. Cooley, M. Kang, and O. Pikhurko, “On a question of Vera T. Sós about size
forcing of graphons,” Acta Mathematica Hungarica, vol. 168. Springer Nature,
pp. 1–26, 2022.
ista: Cooley O, Kang M, Pikhurko O. 2022. On a question of Vera T. Sós about size
forcing of graphons. Acta Mathematica Hungarica. 168, 1–26.
mla: Cooley, Oliver, et al. “On a Question of Vera T. Sós about Size Forcing of
Graphons.” Acta Mathematica Hungarica, vol. 168, Springer Nature, 2022,
pp. 1–26, doi:10.1007/s10474-022-01265-8.
short: O. Cooley, M. Kang, O. Pikhurko, Acta Mathematica Hungarica 168 (2022) 1–26.
date_created: 2023-01-12T12:07:59Z
date_published: 2022-11-23T00:00:00Z
date_updated: 2023-08-04T09:02:37Z
day: '23'
department:
- _id: MaKw
doi: 10.1007/s10474-022-01265-8
external_id:
arxiv:
- '2103.09114'
isi:
- '000886839900006'
intvolume: ' 168'
isi: 1
keyword:
- graphon
- k-sample
- graphon forcing
- graph container
language:
- iso: eng
main_file_link:
- open_access: '1'
url: ' https://doi.org/10.48550/arXiv.2103.09114'
month: '11'
oa: 1
oa_version: Preprint
page: 1-26
publication: Acta Mathematica Hungarica
publication_identifier:
eissn:
- 1588-2632
issn:
- 0236-5294
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: On a question of Vera T. Sós about size forcing of graphons
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 168
year: '2022'
...
---
_id: '12286'
abstract:
- lang: eng
text: "Inspired by the study of loose cycles in hypergraphs, we define the loose
core in hypergraphs as a structurewhich mirrors the close relationship between
cycles and $2$-cores in graphs. We prove that in the $r$-uniform binomial random
hypergraph $H^r(n,p)$, the order of the loose core undergoes a phase transition
at a certain critical threshold and determine this order, as well as the number
of edges, asymptotically in the subcritical and supercritical regimes.
\r\nOur
main tool is an algorithm called CoreConstruct, which enables us to analyse a
peeling process for the loose core. By analysing this algorithm we determine the
asymptotic degree distribution of vertices in the loose core and in particular
how many vertices and edges the loose core contains. As a corollary we obtain
an improved upper bound on the length of the longest loose cycle in $H^r(n,p)$."
acknowledgement: 'Supported by Austrian Science Fund (FWF): I3747, W1230.'
article_number: P4.13
article_processing_charge: No
article_type: original
author:
- first_name: Oliver
full_name: Cooley, Oliver
id: 43f4ddd0-a46b-11ec-8df6-ef3703bd721d
last_name: Cooley
- first_name: Mihyun
full_name: Kang, Mihyun
last_name: Kang
- first_name: Julian
full_name: Zalla, Julian
last_name: Zalla
citation:
ama: Cooley O, Kang M, Zalla J. Loose cores and cycles in random hypergraphs. The
Electronic Journal of Combinatorics. 2022;29(4). doi:10.37236/10794
apa: Cooley, O., Kang, M., & Zalla, J. (2022). Loose cores and cycles in random
hypergraphs. The Electronic Journal of Combinatorics. The Electronic Journal
of Combinatorics. https://doi.org/10.37236/10794
chicago: Cooley, Oliver, Mihyun Kang, and Julian Zalla. “Loose Cores and Cycles
in Random Hypergraphs.” The Electronic Journal of Combinatorics. The Electronic
Journal of Combinatorics, 2022. https://doi.org/10.37236/10794.
ieee: O. Cooley, M. Kang, and J. Zalla, “Loose cores and cycles in random hypergraphs,”
The Electronic Journal of Combinatorics, vol. 29, no. 4. The Electronic
Journal of Combinatorics, 2022.
ista: Cooley O, Kang M, Zalla J. 2022. Loose cores and cycles in random hypergraphs.
The Electronic Journal of Combinatorics. 29(4), P4.13.
mla: Cooley, Oliver, et al. “Loose Cores and Cycles in Random Hypergraphs.” The
Electronic Journal of Combinatorics, vol. 29, no. 4, P4.13, The Electronic
Journal of Combinatorics, 2022, doi:10.37236/10794.
short: O. Cooley, M. Kang, J. Zalla, The Electronic Journal of Combinatorics 29
(2022).
date_created: 2023-01-16T10:03:57Z
date_published: 2022-10-21T00:00:00Z
date_updated: 2023-08-04T10:29:18Z
day: '21'
ddc:
- '510'
department:
- _id: MaKw
doi: 10.37236/10794
external_id:
isi:
- '000876763300001'
file:
- access_level: open_access
checksum: 00122b2459f09b5ae43073bfba565e94
content_type: application/pdf
creator: dernst
date_created: 2023-01-30T11:45:13Z
date_updated: 2023-01-30T11:45:13Z
file_id: '12462'
file_name: 2022_ElecJournCombinatorics_Cooley_Kang_Zalla.pdf
file_size: 626953
relation: main_file
success: 1
file_date_updated: 2023-01-30T11:45:13Z
has_accepted_license: '1'
intvolume: ' 29'
isi: 1
issue: '4'
keyword:
- Computational Theory and Mathematics
- Geometry and Topology
- Theoretical Computer Science
- Applied Mathematics
- Discrete Mathematics and Combinatorics
language:
- iso: eng
month: '10'
oa: 1
oa_version: Published Version
publication: The Electronic Journal of Combinatorics
publication_identifier:
eissn:
- 1077-8926
publication_status: published
publisher: The Electronic Journal of Combinatorics
quality_controlled: '1'
scopus_import: '1'
status: public
title: Loose cores and cycles in random hypergraphs
tmp:
image: /image/cc_by_nd.png
legal_code_url: https://creativecommons.org/licenses/by-nd/4.0/legalcode
name: Creative Commons Attribution-NoDerivatives 4.0 International (CC BY-ND 4.0)
short: CC BY-ND (4.0)
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 29
year: '2022'
...
---
_id: '12432'
abstract:
- lang: eng
text: "We present CertifyHAM, a deterministic algorithm that takes a graph G as
input and either finds a Hamilton cycle of G or outputs that such a cycle does
not exist. If G ∼ G(n, p) and p ≥\r\n100 log n/n then the expected running time
of CertifyHAM is O(n/p) which is best possible. This improves upon previous results
due to Gurevich and Shelah, Thomason and Alon, and\r\nKrivelevich, who proved
analogous results for p being constant, p ≥ 12n −1/3 and p ≥ 70n\r\n−1/2 respectively."
acknowledgement: "This project has received funding from the European Union’s Horizon
2020\r\nresearch and innovation programme under the Marie Skłodowska-Curie grant\r\nagreement
No 101034413"
article_processing_charge: No
author:
- first_name: Michael
full_name: Anastos, Michael
id: 0b2a4358-bb35-11ec-b7b9-e3279b593dbb
last_name: Anastos
citation:
ama: 'Anastos M. Solving the Hamilton cycle problem fast on average. In: 63rd
Annual IEEE Symposium on Foundations of Computer Science. Vol 2022-October.
Institute of Electrical and Electronics Engineers; 2022:919-930. doi:10.1109/FOCS54457.2022.00091'
apa: 'Anastos, M. (2022). Solving the Hamilton cycle problem fast on average. In
63rd Annual IEEE Symposium on Foundations of Computer Science (Vol. 2022–October,
pp. 919–930). Denver, CO, United States: Institute of Electrical and Electronics
Engineers. https://doi.org/10.1109/FOCS54457.2022.00091'
chicago: Anastos, Michael. “Solving the Hamilton Cycle Problem Fast on Average.”
In 63rd Annual IEEE Symposium on Foundations of Computer Science, 2022–October:919–30.
Institute of Electrical and Electronics Engineers, 2022. https://doi.org/10.1109/FOCS54457.2022.00091.
ieee: M. Anastos, “Solving the Hamilton cycle problem fast on average,” in 63rd
Annual IEEE Symposium on Foundations of Computer Science, Denver, CO, United
States, 2022, vol. 2022–October, pp. 919–930.
ista: 'Anastos M. 2022. Solving the Hamilton cycle problem fast on average. 63rd
Annual IEEE Symposium on Foundations of Computer Science. FOCS: Symposium on Foundations
of Computer Science vol. 2022–October, 919–930.'
mla: Anastos, Michael. “Solving the Hamilton Cycle Problem Fast on Average.” 63rd
Annual IEEE Symposium on Foundations of Computer Science, vol. 2022–October,
Institute of Electrical and Electronics Engineers, 2022, pp. 919–30, doi:10.1109/FOCS54457.2022.00091.
short: M. Anastos, in:, 63rd Annual IEEE Symposium on Foundations of Computer Science,
Institute of Electrical and Electronics Engineers, 2022, pp. 919–930.
conference:
end_date: 2022-11-03
location: Denver, CO, United States
name: 'FOCS: Symposium on Foundations of Computer Science'
start_date: 2022-10-31
date_created: 2023-01-29T23:00:59Z
date_published: 2022-12-01T00:00:00Z
date_updated: 2023-08-04T09:37:56Z
day: '01'
department:
- _id: MaKw
doi: 10.1109/FOCS54457.2022.00091
ec_funded: 1
external_id:
isi:
- '000909382900084'
isi: 1
language:
- iso: eng
month: '12'
oa_version: None
page: 919-930
project:
- _id: fc2ed2f7-9c52-11eb-aca3-c01059dda49c
call_identifier: H2020
grant_number: '101034413'
name: 'IST-BRIDGE: International postdoctoral program'
publication: 63rd Annual IEEE Symposium on Foundations of Computer Science
publication_identifier:
isbn:
- '9781665455190'
issn:
- 0272-5428
publication_status: published
publisher: Institute of Electrical and Electronics Engineers
quality_controlled: '1'
scopus_import: '1'
status: public
title: Solving the Hamilton cycle problem fast on average
type: conference
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 2022-October
year: '2022'
...