---
_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: '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: '9572'
abstract:
- lang: eng
text: We prove that every n-vertex tournament G has an acyclic subgraph with chromatic
number at least n5/9−o(1), while there exists an n-vertex tournament G whose every
acyclic subgraph has chromatic number at most n3/4+o(1). This establishes in a
strong form a conjecture of Nassar and Yuster and improves on another result of
theirs. Our proof combines probabilistic and spectral techniques together with
some additional ideas. In particular, we prove a lemma showing that every tournament
with many transitive subtournaments has a large subtournament that is almost transitive.
This may be of independent interest.
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Jacob
full_name: Fox, Jacob
last_name: Fox
- first_name: Matthew Alan
full_name: Kwan, Matthew Alan
id: 5fca0887-a1db-11eb-95d1-ca9d5e0453b3
last_name: Kwan
orcid: 0000-0002-4003-7567
- first_name: Benny
full_name: Sudakov, Benny
last_name: Sudakov
citation:
ama: Fox J, Kwan MA, Sudakov B. Acyclic subgraphs of tournaments with high chromatic
number. Bulletin of the London Mathematical Society. 2021;53(2):619-630.
doi:10.1112/blms.12446
apa: Fox, J., Kwan, M. A., & Sudakov, B. (2021). Acyclic subgraphs of tournaments
with high chromatic number. Bulletin of the London Mathematical Society.
Wiley. https://doi.org/10.1112/blms.12446
chicago: Fox, Jacob, Matthew Alan Kwan, and Benny Sudakov. “Acyclic Subgraphs of
Tournaments with High Chromatic Number.” Bulletin of the London Mathematical
Society. Wiley, 2021. https://doi.org/10.1112/blms.12446.
ieee: J. Fox, M. A. Kwan, and B. Sudakov, “Acyclic subgraphs of tournaments with
high chromatic number,” Bulletin of the London Mathematical Society, vol.
53, no. 2. Wiley, pp. 619–630, 2021.
ista: Fox J, Kwan MA, Sudakov B. 2021. Acyclic subgraphs of tournaments with high
chromatic number. Bulletin of the London Mathematical Society. 53(2), 619–630.
mla: Fox, Jacob, et al. “Acyclic Subgraphs of Tournaments with High Chromatic Number.”
Bulletin of the London Mathematical Society, vol. 53, no. 2, Wiley, 2021,
pp. 619–30, doi:10.1112/blms.12446.
short: J. Fox, M.A. Kwan, B. Sudakov, Bulletin of the London Mathematical Society
53 (2021) 619–630.
date_created: 2021-06-21T06:11:56Z
date_published: 2021-04-03T00:00:00Z
date_updated: 2023-02-23T14:01:21Z
day: '03'
doi: 10.1112/blms.12446
extern: '1'
external_id:
arxiv:
- '1912.07722'
intvolume: ' 53'
issue: '2'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1912.07722
month: '04'
oa: 1
oa_version: Preprint
page: 619-630
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: Acyclic subgraphs of tournaments with high chromatic number
type: journal_article
user_id: 6785fbc1-c503-11eb-8a32-93094b40e1cf
volume: 53
year: '2021'
...
---
_id: '9573'
abstract:
- lang: eng
text: It is a classical fact that for any ε>0, a random permutation of length n=(1+ε)k2/4
typically contains a monotone subsequence of length k. As a far-reaching generalization,
Alon conjectured that a random permutation of this same length n is typically
k-universal, meaning that it simultaneously contains every pattern of length k.
He also made the simple observation that for n=O(k2logk), a random length-n permutation
is typically k-universal. We make the first significant progress towards Alon's
conjecture by showing that n=2000k2loglogk suffices.
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Xiaoyu
full_name: He, Xiaoyu
last_name: He
- 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: He X, Kwan MA. Universality of random permutations. Bulletin of the London
Mathematical Society. 2020;52(3):515-529. doi:10.1112/blms.12345
apa: He, X., & Kwan, M. A. (2020). Universality of random permutations. Bulletin
of the London Mathematical Society. Wiley. https://doi.org/10.1112/blms.12345
chicago: He, Xiaoyu, and Matthew Alan Kwan. “Universality of Random Permutations.”
Bulletin of the London Mathematical Society. Wiley, 2020. https://doi.org/10.1112/blms.12345.
ieee: X. He and M. A. Kwan, “Universality of random permutations,” Bulletin of
the London Mathematical Society, vol. 52, no. 3. Wiley, pp. 515–529, 2020.
ista: He X, Kwan MA. 2020. Universality of random permutations. Bulletin of the
London Mathematical Society. 52(3), 515–529.
mla: He, Xiaoyu, and Matthew Alan Kwan. “Universality of Random Permutations.” Bulletin
of the London Mathematical Society, vol. 52, no. 3, Wiley, 2020, pp. 515–29,
doi:10.1112/blms.12345.
short: X. He, M.A. Kwan, Bulletin of the London Mathematical Society 52 (2020) 515–529.
date_created: 2021-06-21T06:23:42Z
date_published: 2020-06-01T00:00:00Z
date_updated: 2023-02-23T14:01:23Z
day: '01'
doi: 10.1112/blms.12345
extern: '1'
external_id:
arxiv:
- '1911.12878'
intvolume: ' 52'
issue: '3'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1911.12878
month: '06'
oa: 1
oa_version: Preprint
page: 515-529
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: Universality of random permutations
type: journal_article
user_id: 6785fbc1-c503-11eb-8a32-93094b40e1cf
volume: 52
year: '2020'
...
---
_id: '9576'
abstract:
- lang: eng
text: In 1989, Rota made the following conjecture. Given n bases B1,…,Bn in an n-dimensional
vector space V, one can always find n disjoint bases of V, each containing exactly
one element from each Bi (we call such bases transversal bases). Rota’s basis
conjecture remains wide open despite its apparent simplicity and the efforts of
many researchers (e.g., the conjecture was recently the subject of the collaborative
“Polymath” project). In this paper we prove that one can always find (1/2−o(1))n
disjoint transversal bases, improving on the previous best bound of Ω(n/logn).
Our results also apply to the more general setting of matroids.
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Matija
full_name: Bucić, Matija
last_name: Bucić
- 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: Alexey
full_name: Pokrovskiy, Alexey
last_name: Pokrovskiy
- first_name: Benny
full_name: Sudakov, Benny
last_name: Sudakov
citation:
ama: Bucić M, Kwan MA, Pokrovskiy A, Sudakov B. Halfway to Rota’s basis conjecture.
International Mathematics Research Notices. 2020;2020(21):8007-8026. doi:10.1093/imrn/rnaa004
apa: Bucić, M., Kwan, M. A., Pokrovskiy, A., & Sudakov, B. (2020). Halfway to
Rota’s basis conjecture. International Mathematics Research Notices. Oxford
University Press. https://doi.org/10.1093/imrn/rnaa004
chicago: Bucić, Matija, Matthew Alan Kwan, Alexey Pokrovskiy, and Benny Sudakov.
“Halfway to Rota’s Basis Conjecture.” International Mathematics Research Notices.
Oxford University Press, 2020. https://doi.org/10.1093/imrn/rnaa004.
ieee: M. Bucić, M. A. Kwan, A. Pokrovskiy, and B. Sudakov, “Halfway to Rota’s basis
conjecture,” International Mathematics Research Notices, vol. 2020, no.
21. Oxford University Press, pp. 8007–8026, 2020.
ista: Bucić M, Kwan MA, Pokrovskiy A, Sudakov B. 2020. Halfway to Rota’s basis conjecture.
International Mathematics Research Notices. 2020(21), 8007–8026.
mla: Bucić, Matija, et al. “Halfway to Rota’s Basis Conjecture.” International
Mathematics Research Notices, vol. 2020, no. 21, Oxford University Press,
2020, pp. 8007–26, doi:10.1093/imrn/rnaa004.
short: M. Bucić, M.A. Kwan, A. Pokrovskiy, B. Sudakov, International Mathematics
Research Notices 2020 (2020) 8007–8026.
date_created: 2021-06-21T08:12:30Z
date_published: 2020-11-01T00:00:00Z
date_updated: 2023-02-23T14:01:30Z
day: '01'
doi: 10.1093/imrn/rnaa004
extern: '1'
external_id:
arxiv:
- '1810.07462'
intvolume: ' 2020'
issue: '21'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv-export-lb.library.cornell.edu/abs/1810.07462
month: '11'
oa: 1
oa_version: Preprint
page: 8007-8026
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: Halfway to Rota’s basis conjecture
type: journal_article
user_id: 6785fbc1-c503-11eb-8a32-93094b40e1cf
volume: 2020
year: '2020'
...
---
_id: '9577'
abstract:
- lang: eng
text: An n-vertex graph is called C-Ramsey if it has no clique or independent set
of size Clogn. All known constructions of Ramsey graphs involve randomness in
an essential way, and there is an ongoing line of research towards showing that
in fact all Ramsey graphs must obey certain “richness” properties characteristic
of random graphs. Motivated by an old problem of Erd̋s and McKay, recently Narayanan,
Sahasrabudhe, and Tomon conjectured that for any fixed C, every n-vertex C-Ramsey
graph induces subgraphs of Θ(n2) different sizes. In this paper we prove this
conjecture.
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: Benny
full_name: Sudakov, Benny
last_name: Sudakov
citation:
ama: Kwan MA, Sudakov B. Ramsey graphs induce subgraphs of quadratically many sizes.
International Mathematics Research Notices. 2020;2020(6):1621–1638. doi:10.1093/imrn/rny064
apa: Kwan, M. A., & Sudakov, B. (2020). Ramsey graphs induce subgraphs of quadratically
many sizes. International Mathematics Research Notices. Oxford University
Press. https://doi.org/10.1093/imrn/rny064
chicago: Kwan, Matthew Alan, and Benny Sudakov. “Ramsey Graphs Induce Subgraphs
of Quadratically Many Sizes.” International Mathematics Research Notices.
Oxford University Press, 2020. https://doi.org/10.1093/imrn/rny064.
ieee: M. A. Kwan and B. Sudakov, “Ramsey graphs induce subgraphs of quadratically
many sizes,” International Mathematics Research Notices, vol. 2020, no.
6. Oxford University Press, pp. 1621–1638, 2020.
ista: Kwan MA, Sudakov B. 2020. Ramsey graphs induce subgraphs of quadratically
many sizes. International Mathematics Research Notices. 2020(6), 1621–1638.
mla: Kwan, Matthew Alan, and Benny Sudakov. “Ramsey Graphs Induce Subgraphs of Quadratically
Many Sizes.” International Mathematics Research Notices, vol. 2020, no.
6, Oxford University Press, 2020, pp. 1621–1638, doi:10.1093/imrn/rny064.
short: M.A. Kwan, B. Sudakov, International Mathematics Research Notices 2020 (2020)
1621–1638.
date_created: 2021-06-21T08:30:12Z
date_published: 2020-03-01T00:00:00Z
date_updated: 2023-02-23T14:01:33Z
day: '01'
doi: 10.1093/imrn/rny064
extern: '1'
external_id:
arxiv:
- '1711.02937'
intvolume: ' 2020'
issue: '6'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.1093/imrn/rny064
month: '03'
oa: 1
oa_version: Published Version
page: 1621–1638
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: Ramsey graphs induce subgraphs of quadratically many sizes
type: journal_article
user_id: 6785fbc1-c503-11eb-8a32-93094b40e1cf
volume: 2020
year: '2020'
...
---
_id: '9578'
abstract:
- lang: eng
text: How long a monotone path can one always find in any edge-ordering of the complete
graph Kn? This appealing question was first asked by Chvátal and Komlós in 1971,
and has since attracted the attention of many researchers, inspiring a variety
of related problems. The prevailing conjecture is that one can always find a monotone
path of linear length, but until now the best known lower bound was n2/3-o(1).
In this paper we almost close this gap, proving that any edge-ordering of the
complete graph contains a monotone path of length n1-o(1).
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Matija
full_name: Bucić, Matija
last_name: Bucić
- 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: Alexey
full_name: Pokrovskiy, Alexey
last_name: Pokrovskiy
- first_name: Benny
full_name: Sudakov, Benny
last_name: Sudakov
- first_name: Tuan
full_name: Tran, Tuan
last_name: Tran
- first_name: Adam Zsolt
full_name: Wagner, Adam Zsolt
last_name: Wagner
citation:
ama: Bucić M, Kwan MA, Pokrovskiy A, Sudakov B, Tran T, Wagner AZ. Nearly-linear
monotone paths in edge-ordered graphs. Israel Journal of Mathematics. 2020;238(2):663-685.
doi:10.1007/s11856-020-2035-7
apa: Bucić, M., Kwan, M. A., Pokrovskiy, A., Sudakov, B., Tran, T., & Wagner,
A. Z. (2020). Nearly-linear monotone paths in edge-ordered graphs. Israel Journal
of Mathematics. Springer. https://doi.org/10.1007/s11856-020-2035-7
chicago: Bucić, Matija, Matthew Alan Kwan, Alexey Pokrovskiy, Benny Sudakov, Tuan
Tran, and Adam Zsolt Wagner. “Nearly-Linear Monotone Paths in Edge-Ordered Graphs.”
Israel Journal of Mathematics. Springer, 2020. https://doi.org/10.1007/s11856-020-2035-7.
ieee: M. Bucić, M. A. Kwan, A. Pokrovskiy, B. Sudakov, T. Tran, and A. Z. Wagner,
“Nearly-linear monotone paths in edge-ordered graphs,” Israel Journal of Mathematics,
vol. 238, no. 2. Springer, pp. 663–685, 2020.
ista: Bucić M, Kwan MA, Pokrovskiy A, Sudakov B, Tran T, Wagner AZ. 2020. Nearly-linear
monotone paths in edge-ordered graphs. Israel Journal of Mathematics. 238(2),
663–685.
mla: Bucić, Matija, et al. “Nearly-Linear Monotone Paths in Edge-Ordered Graphs.”
Israel Journal of Mathematics, vol. 238, no. 2, Springer, 2020, pp. 663–85,
doi:10.1007/s11856-020-2035-7.
short: M. Bucić, M.A. Kwan, A. Pokrovskiy, B. Sudakov, T. Tran, A.Z. Wagner, Israel
Journal of Mathematics 238 (2020) 663–685.
date_created: 2021-06-21T13:24:35Z
date_published: 2020-07-01T00:00:00Z
date_updated: 2023-02-23T14:01:35Z
day: '01'
doi: 10.1007/s11856-020-2035-7
extern: '1'
external_id:
arxiv:
- '1809.01468'
intvolume: ' 238'
issue: '2'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1809.01468
month: '07'
oa: 1
oa_version: Preprint
page: 663-685
publication: Israel Journal of Mathematics
publication_identifier:
eissn:
- 1565-8511
issn:
- 0021-2172
publication_status: published
publisher: Springer
quality_controlled: '1'
scopus_import: '1'
status: public
title: Nearly-linear monotone paths in edge-ordered graphs
type: journal_article
user_id: 6785fbc1-c503-11eb-8a32-93094b40e1cf
volume: 238
year: '2020'
...
---
_id: '9581'
abstract:
- lang: eng
text: "We show that for any \U0001D45B divisible by 3, almost all order- \U0001D45B
\ Steiner triple systems have a perfect matching (also known as a parallel class
or resolution class). In fact, we prove a general upper bound on the number of
perfect matchings in a Steiner triple system and show that almost all Steiner
triple systems essentially attain this maximum. We accomplish this via a general
theorem comparing a uniformly random Steiner triple system to the outcome of the
triangle removal process, which we hope will be useful for other problems. Our
methods can also be adapted to other types of designs; for example, we sketch
a proof of the theorem that almost all Latin squares have transversals."
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
citation:
ama: Kwan MA. Almost all Steiner triple systems have perfect matchings. Proceedings
of the London Mathematical Society. 2020;121(6):1468-1495. doi:10.1112/plms.12373
apa: Kwan, M. A. (2020). Almost all Steiner triple systems have perfect matchings.
Proceedings of the London Mathematical Society. Wiley. https://doi.org/10.1112/plms.12373
chicago: Kwan, Matthew Alan. “Almost All Steiner Triple Systems Have Perfect Matchings.”
Proceedings of the London Mathematical Society. Wiley, 2020. https://doi.org/10.1112/plms.12373.
ieee: M. A. Kwan, “Almost all Steiner triple systems have perfect matchings,” Proceedings
of the London Mathematical Society, vol. 121, no. 6. Wiley, pp. 1468–1495,
2020.
ista: Kwan MA. 2020. Almost all Steiner triple systems have perfect matchings. Proceedings
of the London Mathematical Society. 121(6), 1468–1495.
mla: Kwan, Matthew Alan. “Almost All Steiner Triple Systems Have Perfect Matchings.”
Proceedings of the London Mathematical Society, vol. 121, no. 6, Wiley,
2020, pp. 1468–95, doi:10.1112/plms.12373.
short: M.A. Kwan, Proceedings of the London Mathematical Society 121 (2020) 1468–1495.
date_created: 2021-06-22T06:35:16Z
date_published: 2020-12-01T00:00:00Z
date_updated: 2023-02-23T14:01:43Z
day: '01'
doi: 10.1112/plms.12373
extern: '1'
external_id:
arxiv:
- '1611.02246'
intvolume: ' 121'
issue: '6'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1611.02246
month: '12'
oa: 1
oa_version: Preprint
page: 1468-1495
publication: Proceedings of the London Mathematical Society
publication_identifier:
eissn:
- 1460-244X
issn:
- 0024-6115
publication_status: published
publisher: Wiley
quality_controlled: '1'
scopus_import: '1'
status: public
title: Almost all Steiner triple systems have perfect matchings
type: journal_article
user_id: 6785fbc1-c503-11eb-8a32-93094b40e1cf
volume: 121
year: '2020'
...
---
_id: '9582'
abstract:
- lang: eng
text: The problem of finding dense induced bipartite subgraphs in H-free graphs
has a long history, and was posed 30 years ago by Erdős, Faudree, Pach and Spencer.
In this paper, we obtain several results in this direction. First we prove that
any H-free graph with minimum degree at least d contains an induced bipartite
subgraph of minimum degree at least cH log d/log log d, thus nearly confirming
one and proving another conjecture of Esperet, Kang and Thomassé. Complementing
this result, we further obtain optimal bounds for this problem in the case of
dense triangle-free graphs, and we also answer a question of Erdœs, Janson, Łuczak
and Spencer.
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: Shoham
full_name: Letzter, Shoham
last_name: Letzter
- first_name: Benny
full_name: Sudakov, Benny
last_name: Sudakov
- first_name: Tuan
full_name: Tran, Tuan
last_name: Tran
citation:
ama: Kwan MA, Letzter S, Sudakov B, Tran T. Dense induced bipartite subgraphs in
triangle-free graphs. Combinatorica. 2020;40(2):283-305. doi:10.1007/s00493-019-4086-0
apa: Kwan, M. A., Letzter, S., Sudakov, B., & Tran, T. (2020). Dense induced
bipartite subgraphs in triangle-free graphs. Combinatorica. Springer. https://doi.org/10.1007/s00493-019-4086-0
chicago: Kwan, Matthew Alan, Shoham Letzter, Benny Sudakov, and Tuan Tran. “Dense
Induced Bipartite Subgraphs in Triangle-Free Graphs.” Combinatorica. Springer,
2020. https://doi.org/10.1007/s00493-019-4086-0.
ieee: M. A. Kwan, S. Letzter, B. Sudakov, and T. Tran, “Dense induced bipartite
subgraphs in triangle-free graphs,” Combinatorica, vol. 40, no. 2. Springer,
pp. 283–305, 2020.
ista: Kwan MA, Letzter S, Sudakov B, Tran T. 2020. Dense induced bipartite subgraphs
in triangle-free graphs. Combinatorica. 40(2), 283–305.
mla: Kwan, Matthew Alan, et al. “Dense Induced Bipartite Subgraphs in Triangle-Free
Graphs.” Combinatorica, vol. 40, no. 2, Springer, 2020, pp. 283–305, doi:10.1007/s00493-019-4086-0.
short: M.A. Kwan, S. Letzter, B. Sudakov, T. Tran, Combinatorica 40 (2020) 283–305.
date_created: 2021-06-22T06:42:26Z
date_published: 2020-04-01T00:00:00Z
date_updated: 2023-02-23T14:01:45Z
day: '01'
doi: 10.1007/s00493-019-4086-0
extern: '1'
external_id:
arxiv:
- '1810.12144'
intvolume: ' 40'
issue: '2'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1810.12144
month: '04'
oa: 1
oa_version: Preprint
page: 283-305
publication: Combinatorica
publication_identifier:
eissn:
- 1439-6912
issn:
- 0209-9683
publication_status: published
publisher: Springer
quality_controlled: '1'
scopus_import: '1'
status: public
title: Dense induced bipartite subgraphs in triangle-free graphs
type: journal_article
user_id: 6785fbc1-c503-11eb-8a32-93094b40e1cf
volume: 40
year: '2020'
...
---
_id: '9583'
abstract:
- lang: eng
text: We show that for any n divisible by 3, almost all order-n Steiner triple systems
admit a decomposition of almost all their triples into disjoint perfect matchings
(that is, almost all Steiner triple systems are almost resolvable).
article_number: e39
article_processing_charge: No
article_type: original
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
citation:
ama: Ferber A, Kwan MA. Almost all Steiner triple systems are almost resolvable.
Forum of Mathematics. 2020;8. doi:10.1017/fms.2020.29
apa: Ferber, A., & Kwan, M. A. (2020). Almost all Steiner triple systems are
almost resolvable. Forum of Mathematics. Cambridge University Press. https://doi.org/10.1017/fms.2020.29
chicago: Ferber, Asaf, and Matthew Alan Kwan. “Almost All Steiner Triple Systems
Are Almost Resolvable.” Forum of Mathematics. Cambridge University Press,
2020. https://doi.org/10.1017/fms.2020.29.
ieee: A. Ferber and M. A. Kwan, “Almost all Steiner triple systems are almost resolvable,”
Forum of Mathematics, vol. 8. Cambridge University Press, 2020.
ista: Ferber A, Kwan MA. 2020. Almost all Steiner triple systems are almost resolvable.
Forum of Mathematics. 8, e39.
mla: Ferber, Asaf, and Matthew Alan Kwan. “Almost All Steiner Triple Systems Are
Almost Resolvable.” Forum of Mathematics, vol. 8, e39, Cambridge University
Press, 2020, doi:10.1017/fms.2020.29.
short: A. Ferber, M.A. Kwan, Forum of Mathematics 8 (2020).
date_created: 2021-06-22T09:12:23Z
date_published: 2020-11-03T00:00:00Z
date_updated: 2023-02-23T14:01:48Z
day: '03'
ddc:
- '510'
doi: 10.1017/fms.2020.29
extern: '1'
external_id:
pmid:
- '1907.06744'
file:
- access_level: open_access
checksum: 5553c596bb4db0f38226a56bee9c87a1
content_type: application/pdf
creator: asandaue
date_created: 2021-06-22T09:23:59Z
date_updated: 2021-06-22T09:23:59Z
file_id: '9584'
file_name: 2020_CambridgeUniversityPress_Ferber.pdf
file_size: 601516
relation: main_file
success: 1
file_date_updated: 2021-06-22T09:23:59Z
has_accepted_license: '1'
intvolume: ' 8'
language:
- iso: eng
month: '11'
oa: 1
oa_version: Published Version
pmid: 1
publication: Forum of Mathematics
publication_identifier:
eissn:
- 2050-5094
publication_status: published
publisher: Cambridge University Press
quality_controlled: '1'
scopus_import: '1'
status: public
title: Almost all Steiner triple systems are almost resolvable
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: 6785fbc1-c503-11eb-8a32-93094b40e1cf
volume: 8
year: '2020'
...
---
_id: '9580'
abstract:
- lang: eng
text: An r-cut of a k-uniform hypergraph H is a partition of the vertex set of H
into r parts and the size of the cut is the number of edges which have a vertex
in each part. A classical result of Edwards says that every m-edge graph has a
2-cut of size m/2+Ω)(m−−√) and this is best possible. That is, there exist cuts
which exceed the expected size of a random cut by some multiple of the standard
deviation. We study analogues of this and related results in hypergraphs. First,
we observe that similarly to graphs, every m-edge k-uniform hypergraph has an
r-cut whose size is Ω(m−−√) larger than the expected size of a random r-cut. Moreover,
in the case where k = 3 and r = 2 this bound is best possible and is attained
by Steiner triple systems. Surprisingly, for all other cases (that is, if k ≥
4 or r ≥ 3), we show that every m-edge k-uniform hypergraph has an r-cut whose
size is Ω(m5/9) larger than the expected size of a random r-cut. This is a significant
difference in behaviour, since the amount by which the size of the largest cut
exceeds the expected size of a random cut is now considerably larger than the
standard deviation.
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: David
full_name: Conlon, David
last_name: Conlon
- first_name: Jacob
full_name: Fox, Jacob
last_name: Fox
- first_name: Matthew Alan
full_name: Kwan, Matthew Alan
id: 5fca0887-a1db-11eb-95d1-ca9d5e0453b3
last_name: Kwan
orcid: 0000-0002-4003-7567
- first_name: Benny
full_name: Sudakov, Benny
last_name: Sudakov
citation:
ama: Conlon D, Fox J, Kwan MA, Sudakov B. Hypergraph cuts above the average. Israel
Journal of Mathematics. 2019;233(1):67-111. doi:10.1007/s11856-019-1897-z
apa: Conlon, D., Fox, J., Kwan, M. A., & Sudakov, B. (2019). Hypergraph cuts
above the average. Israel Journal of Mathematics. Springer. https://doi.org/10.1007/s11856-019-1897-z
chicago: Conlon, David, Jacob Fox, Matthew Alan Kwan, and Benny Sudakov. “Hypergraph
Cuts above the Average.” Israel Journal of Mathematics. Springer, 2019.
https://doi.org/10.1007/s11856-019-1897-z.
ieee: D. Conlon, J. Fox, M. A. Kwan, and B. Sudakov, “Hypergraph cuts above the
average,” Israel Journal of Mathematics, vol. 233, no. 1. Springer, pp.
67–111, 2019.
ista: Conlon D, Fox J, Kwan MA, Sudakov B. 2019. Hypergraph cuts above the average.
Israel Journal of Mathematics. 233(1), 67–111.
mla: Conlon, David, et al. “Hypergraph Cuts above the Average.” Israel Journal
of Mathematics, vol. 233, no. 1, Springer, 2019, pp. 67–111, doi:10.1007/s11856-019-1897-z.
short: D. Conlon, J. Fox, M.A. Kwan, B. Sudakov, Israel Journal of Mathematics 233
(2019) 67–111.
date_created: 2021-06-21T13:36:02Z
date_published: 2019-08-01T00:00:00Z
date_updated: 2023-02-23T14:01:41Z
day: '01'
doi: 10.1007/s11856-019-1897-z
extern: '1'
external_id:
arxiv:
- '1803.08462'
intvolume: ' 233'
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1803.08462
month: '08'
oa: 1
oa_version: Preprint
page: 67-111
publication: Israel Journal of Mathematics
publication_identifier:
eissn:
- 1565-8511
issn:
- 0021-2172
publication_status: published
publisher: Springer
quality_controlled: '1'
scopus_import: '1'
status: public
title: Hypergraph cuts above the average
type: journal_article
user_id: 6785fbc1-c503-11eb-8a32-93094b40e1cf
volume: 233
year: '2019'
...
---
_id: '9585'
abstract:
- lang: eng
text: An n-vertex graph is called C-Ramsey if it has no clique or independent set
of size C log n. All known constructions of Ramsey graphs involve randomness in
an essential way, and there is an ongoing line of research towards showing that
in fact all Ramsey graphs must obey certain “richness” properties characteristic
of random graphs. More than 25 years ago, Erdős, Faudree and Sós conjectured that
in any C-Ramsey graph there are Ω(n^5/2) induced subgraphs, no pair of which have
the same numbers of vertices and edges. Improving on earlier results of Alon,
Balogh, Kostochka and Samotij, in this paper we prove this conjecture.
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: Benny
full_name: Sudakov, Benny
last_name: Sudakov
citation:
ama: Kwan MA, Sudakov B. Proof of a conjecture on induced subgraphs of Ramsey graphs.
Transactions of the American Mathematical Society. 2019;372(8):5571-5594.
doi:10.1090/tran/7729
apa: Kwan, M. A., & Sudakov, B. (2019). Proof of a conjecture on induced subgraphs
of Ramsey graphs. Transactions of the American Mathematical Society. American
Mathematical Society. https://doi.org/10.1090/tran/7729
chicago: Kwan, Matthew Alan, and Benny Sudakov. “Proof of a Conjecture on Induced
Subgraphs of Ramsey Graphs.” Transactions of the American Mathematical Society.
American Mathematical Society, 2019. https://doi.org/10.1090/tran/7729.
ieee: M. A. Kwan and B. Sudakov, “Proof of a conjecture on induced subgraphs of
Ramsey graphs,” Transactions of the American Mathematical Society, vol.
372, no. 8. American Mathematical Society, pp. 5571–5594, 2019.
ista: Kwan MA, Sudakov B. 2019. Proof of a conjecture on induced subgraphs of Ramsey
graphs. Transactions of the American Mathematical Society. 372(8), 5571–5594.
mla: Kwan, Matthew Alan, and Benny Sudakov. “Proof of a Conjecture on Induced Subgraphs
of Ramsey Graphs.” Transactions of the American Mathematical Society, vol.
372, no. 8, American Mathematical Society, 2019, pp. 5571–94, doi:10.1090/tran/7729.
short: M.A. Kwan, B. Sudakov, Transactions of the American Mathematical Society
372 (2019) 5571–5594.
date_created: 2021-06-22T09:31:45Z
date_published: 2019-10-15T00:00:00Z
date_updated: 2023-02-23T14:01:50Z
day: '15'
doi: 10.1090/tran/7729
extern: '1'
external_id:
arxiv:
- '1712.05656'
intvolume: ' 372'
issue: '8'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.1090/tran/7729
month: '10'
oa: 1
oa_version: Submitted Version
page: 5571-5594
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: Proof of a conjecture on induced subgraphs of Ramsey graphs
type: journal_article
user_id: 6785fbc1-c503-11eb-8a32-93094b40e1cf
volume: 372
year: '2019'
...
---
_id: '9586'
abstract:
- lang: eng
text: "Consider integers \U0001D458,ℓ such that 0⩽ℓ⩽(\U0001D4582) . Given a large
graph \U0001D43A , what is the fraction of \U0001D458 -vertex subsets of \U0001D43A
\ which span exactly ℓ edges? When \U0001D43A is empty or complete, and ℓ
\ is zero or (\U0001D4582) , this fraction can be exactly 1. On the other hand,
if ℓ is far from these extreme values, one might expect that this fraction is
substantially smaller than 1. This was recently proved by Alon, Hefetz, Krivelevich,
and Tyomkyn who initiated the systematic study of this question and proposed several
natural conjectures.\r\nLet ℓ∗=min{ℓ,(\U0001D4582)−ℓ} . Our main result is that
for any \U0001D458 and ℓ , the fraction of \U0001D458 -vertex subsets that
span ℓ edges is at most log\U0001D442(1)(ℓ∗/\U0001D458)√ \U0001D458/ℓ∗, which
is best-possible up to the logarithmic factor. This improves on multiple results
of Alon, Hefetz, Krivelevich, and Tyomkyn, and resolves one of their conjectures.
In addition, we also make some first steps towards some analogous questions for
hypergraphs.\r\nOur proofs involve some Ramsey-type arguments, and a number of
different probabilistic tools, such as polynomial anticoncentration inequalities,
hypercontractivity, and a coupling trick for random variables defined on a ‘slice’
of the Boolean hypercube."
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: Benny
full_name: Sudakov, Benny
last_name: Sudakov
- first_name: Tuan
full_name: Tran, Tuan
last_name: Tran
citation:
ama: Kwan MA, Sudakov B, Tran T. Anticoncentration for subgraph statistics. Journal
of the London Mathematical Society. 2019;99(3):757-777. doi:10.1112/jlms.12192
apa: Kwan, M. A., Sudakov, B., & Tran, T. (2019). Anticoncentration for subgraph
statistics. Journal of the London Mathematical Society. Wiley. https://doi.org/10.1112/jlms.12192
chicago: Kwan, Matthew Alan, Benny Sudakov, and Tuan Tran. “Anticoncentration for
Subgraph Statistics.” Journal of the London Mathematical Society. Wiley,
2019. https://doi.org/10.1112/jlms.12192.
ieee: M. A. Kwan, B. Sudakov, and T. Tran, “Anticoncentration for subgraph statistics,”
Journal of the London Mathematical Society, vol. 99, no. 3. Wiley, pp.
757–777, 2019.
ista: Kwan MA, Sudakov B, Tran T. 2019. Anticoncentration for subgraph statistics.
Journal of the London Mathematical Society. 99(3), 757–777.
mla: Kwan, Matthew Alan, et al. “Anticoncentration for Subgraph Statistics.” Journal
of the London Mathematical Society, vol. 99, no. 3, Wiley, 2019, pp. 757–77,
doi:10.1112/jlms.12192.
short: M.A. Kwan, B. Sudakov, T. Tran, Journal of the London Mathematical Society
99 (2019) 757–777.
date_created: 2021-06-22T09:46:03Z
date_published: 2019-05-03T00:00:00Z
date_updated: 2023-02-23T14:01:53Z
day: '03'
doi: 10.1112/jlms.12192
extern: '1'
external_id:
arxiv:
- '1807.05202'
intvolume: ' 99'
issue: '3'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1807.05202
month: '05'
oa: 1
oa_version: Preprint
page: 757-777
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: Anticoncentration for subgraph statistics
type: journal_article
user_id: 6785fbc1-c503-11eb-8a32-93094b40e1cf
volume: 99
year: '2019'
...
---
_id: '9565'
abstract:
- lang: eng
text: Let D(n,p) be the random directed graph on n vertices where each of the n(n-1)
possible arcs is present independently with probability p. A celebrated result
of Frieze shows that if p≥(logn+ω(1))/n then D(n,p) typically has a directed Hamilton
cycle, and this is best possible. In this paper, we obtain a strengthening of
this result, showing that under the same condition, the number of directed Hamilton
cycles in D(n,p) is typically n!(p(1+o(1)))n. We also prove a hitting-time version
of this statement, showing that in the random directed graph process, as soon
as every vertex has in-/out-degrees at least 1, there are typically n!(logn/n(1+o(1)))n
directed Hamilton cycles.
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: Benny
full_name: Sudakov, Benny
last_name: Sudakov
citation:
ama: Ferber A, Kwan MA, Sudakov B. Counting Hamilton cycles in sparse random directed
graphs. Random Structures and Algorithms. 2018;53(4):592-603. doi:10.1002/rsa.20815
apa: Ferber, A., Kwan, M. A., & Sudakov, B. (2018). Counting Hamilton cycles
in sparse random directed graphs. Random Structures and Algorithms. Wiley.
https://doi.org/10.1002/rsa.20815
chicago: Ferber, Asaf, Matthew Alan Kwan, and Benny Sudakov. “Counting Hamilton
Cycles in Sparse Random Directed Graphs.” Random Structures and Algorithms.
Wiley, 2018. https://doi.org/10.1002/rsa.20815.
ieee: A. Ferber, M. A. Kwan, and B. Sudakov, “Counting Hamilton cycles in sparse
random directed graphs,” Random Structures and Algorithms, vol. 53, no.
4. Wiley, pp. 592–603, 2018.
ista: Ferber A, Kwan MA, Sudakov B. 2018. Counting Hamilton cycles in sparse random
directed graphs. Random Structures and Algorithms. 53(4), 592–603.
mla: Ferber, Asaf, et al. “Counting Hamilton Cycles in Sparse Random Directed Graphs.”
Random Structures and Algorithms, vol. 53, no. 4, Wiley, 2018, pp. 592–603,
doi:10.1002/rsa.20815.
short: A. Ferber, M.A. Kwan, B. Sudakov, Random Structures and Algorithms 53 (2018)
592–603.
date_created: 2021-06-18T12:06:28Z
date_published: 2018-12-01T00:00:00Z
date_updated: 2023-02-23T14:01:03Z
day: '01'
doi: 10.1002/rsa.20815
extern: '1'
external_id:
arxiv:
- '1708.07746'
intvolume: ' 53'
issue: '4'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1708.07746
month: '12'
oa: 1
oa_version: Preprint
page: 592-603
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: Counting Hamilton cycles in sparse random directed graphs
type: journal_article
user_id: 6785fbc1-c503-11eb-8a32-93094b40e1cf
volume: 53
year: '2018'
...
---
_id: '9567'
abstract:
- lang: eng
text: Let P be a graph property which is preserved by removal of edges, and consider
the random graph process that starts with the empty n-vertex graph and then adds
edges one-by-one, each chosen uniformly at random subject to the constraint that
P is not violated. These types of random processes have been the subject of extensive
research over the last 20 years, having striking applications in extremal combinatorics,
and leading to the discovery of important probabilistic tools. In this paper we
consider the k-matching-free process, where P is the property of not containing
a matching of size k. We are able to analyse the behaviour of this process for
a wide range of values of k; in particular we prove that if k=o(n) or if n−2k=o(n−−√/logn)
then this process is likely to terminate in a k-matching-free graph with the maximum
possible number of edges, as characterised by Erdős and Gallai. We also show that
these bounds on k are essentially best possible, and we make a first step towards
understanding the behaviour of the process in the intermediate regime.
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Michael
full_name: Krivelevich, Michael
last_name: Krivelevich
- 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: Po‐Shen
full_name: Loh, Po‐Shen
last_name: Loh
- first_name: Benny
full_name: Sudakov, Benny
last_name: Sudakov
citation:
ama: Krivelevich M, Kwan MA, Loh P, Sudakov B. The random k‐matching‐free process.
Random Structures and Algorithms. 2018;53(4):692-716. doi:10.1002/rsa.20814
apa: Krivelevich, M., Kwan, M. A., Loh, P., & Sudakov, B. (2018). The random
k‐matching‐free process. Random Structures and Algorithms. Wiley. https://doi.org/10.1002/rsa.20814
chicago: Krivelevich, Michael, Matthew Alan Kwan, Po‐Shen Loh, and Benny Sudakov.
“The Random K‐matching‐free Process.” Random Structures and Algorithms.
Wiley, 2018. https://doi.org/10.1002/rsa.20814.
ieee: M. Krivelevich, M. A. Kwan, P. Loh, and B. Sudakov, “The random k‐matching‐free
process,” Random Structures and Algorithms, vol. 53, no. 4. Wiley, pp.
692–716, 2018.
ista: Krivelevich M, Kwan MA, Loh P, Sudakov B. 2018. The random k‐matching‐free
process. Random Structures and Algorithms. 53(4), 692–716.
mla: Krivelevich, Michael, et al. “The Random K‐matching‐free Process.” Random
Structures and Algorithms, vol. 53, no. 4, Wiley, 2018, pp. 692–716, doi:10.1002/rsa.20814.
short: M. Krivelevich, M.A. Kwan, P. Loh, B. Sudakov, Random Structures and Algorithms
53 (2018) 692–716.
date_created: 2021-06-18T12:37:40Z
date_published: 2018-12-01T00:00:00Z
date_updated: 2023-02-23T14:01:07Z
day: '01'
doi: 10.1002/rsa.20814
extern: '1'
external_id:
arxiv:
- '1708.01054'
intvolume: ' 53'
issue: '4'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1708.01054
month: '12'
oa: 1
oa_version: Preprint
page: 692-716
publication: Random Structures and Algorithms
publication_identifier:
eissn:
- 1098-2418
issn:
- 1042-9832
publication_status: published
publisher: Wiley
quality_controlled: '1'
scopus_import: '1'
status: public
title: The random k‐matching‐free process
type: journal_article
user_id: 6785fbc1-c503-11eb-8a32-93094b40e1cf
volume: 53
year: '2018'
...
---
_id: '9568'
abstract:
- lang: eng
text: An intercalate in a Latin square is a 2×2 Latin subsquare. Let N be the number
of intercalates in a uniformly random n×n Latin square. We prove that asymptotically
almost surely N≥(1−o(1))n2/4, and that EN≤(1+o(1))n2/2 (therefore asymptotically
almost surely N≤fn2 for any f→∞). This significantly improves the previous best
lower and upper bounds. We also give an upper tail bound for the number of intercalates
in two fixed rows of a random Latin square. In addition, we discuss a problem
of Linial and Luria on low-discrepancy Latin squares.
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: Benny
full_name: Sudakov, Benny
last_name: Sudakov
citation:
ama: Kwan MA, Sudakov B. Intercalates and discrepancy in random Latin squares. Random
Structures and Algorithms. 2018;52(2):181-196. doi:10.1002/rsa.20742
apa: Kwan, M. A., & Sudakov, B. (2018). Intercalates and discrepancy in random
Latin squares. Random Structures and Algorithms. Wiley. https://doi.org/10.1002/rsa.20742
chicago: Kwan, Matthew Alan, and Benny Sudakov. “Intercalates and Discrepancy in
Random Latin Squares.” Random Structures and Algorithms. Wiley, 2018. https://doi.org/10.1002/rsa.20742.
ieee: M. A. Kwan and B. Sudakov, “Intercalates and discrepancy in random Latin squares,”
Random Structures and Algorithms, vol. 52, no. 2. Wiley, pp. 181–196, 2018.
ista: Kwan MA, Sudakov B. 2018. Intercalates and discrepancy in random Latin squares.
Random Structures and Algorithms. 52(2), 181–196.
mla: Kwan, Matthew Alan, and Benny Sudakov. “Intercalates and Discrepancy in Random
Latin Squares.” Random Structures and Algorithms, vol. 52, no. 2, Wiley,
2018, pp. 181–96, doi:10.1002/rsa.20742.
short: M.A. Kwan, B. Sudakov, Random Structures and Algorithms 52 (2018) 181–196.
date_created: 2021-06-18T12:47:25Z
date_published: 2018-03-01T00:00:00Z
date_updated: 2023-02-23T14:01:09Z
day: '01'
doi: 10.1002/rsa.20742
extern: '1'
external_id:
arxiv:
- '1607.04981'
intvolume: ' 52'
issue: '2'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1607.04981
month: '03'
oa: 1
oa_version: Preprint
page: 181-196
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: Intercalates and discrepancy in random Latin squares
type: journal_article
user_id: 6785fbc1-c503-11eb-8a32-93094b40e1cf
volume: 52
year: '2018'
...