---
_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
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: '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
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: '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
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'
...
---
_id: '9587'
abstract:
- lang: eng
text: We say a family of sets is intersecting if any two of its sets intersect,
and we say it is trivially intersecting if there is an element which appears in
every set of the family. In this paper we study the maximum size of a non-trivially
intersecting family in a natural “multi-part” setting. Here the ground set is
divided into parts, and one considers families of sets whose intersection with
each part is of a prescribed size. Our work is motivated by classical results
in the single-part setting due to Erdős, Ko and Rado, and Hilton and Milner, and
by a theorem of Frankl concerning intersecting families in this multi-part setting.
In the case where the part sizes are sufficiently large we determine the maximum
size of a non-trivially intersecting multi-part family, disproving a conjecture
of Alon and Katona.
article_processing_charge: No
article_type: original
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: Pedro
full_name: Vieira, Pedro
last_name: Vieira
citation:
ama: Kwan MA, Sudakov B, Vieira P. Non-trivially intersecting multi-part families.
Journal of Combinatorial Theory Series A. 2018;156:44-60. doi:10.1016/j.jcta.2017.12.001
apa: Kwan, M. A., Sudakov, B., & Vieira, P. (2018). Non-trivially intersecting
multi-part families. Journal of Combinatorial Theory Series A. Elsevier.
https://doi.org/10.1016/j.jcta.2017.12.001
chicago: Kwan, Matthew Alan, Benny Sudakov, and Pedro Vieira. “Non-Trivially Intersecting
Multi-Part Families.” Journal of Combinatorial Theory Series A. Elsevier,
2018. https://doi.org/10.1016/j.jcta.2017.12.001.
ieee: M. A. Kwan, B. Sudakov, and P. Vieira, “Non-trivially intersecting multi-part
families,” Journal of Combinatorial Theory Series A, vol. 156. Elsevier,
pp. 44–60, 2018.
ista: Kwan MA, Sudakov B, Vieira P. 2018. Non-trivially intersecting multi-part
families. Journal of Combinatorial Theory Series A. 156, 44–60.
mla: Kwan, Matthew Alan, et al. “Non-Trivially Intersecting Multi-Part Families.”
Journal of Combinatorial Theory Series A, vol. 156, Elsevier, 2018, pp.
44–60, doi:10.1016/j.jcta.2017.12.001.
short: M.A. Kwan, B. Sudakov, P. Vieira, Journal of Combinatorial Theory Series
A 156 (2018) 44–60.
date_created: 2021-06-22T11:42:48Z
date_published: 2018-05-01T00:00:00Z
date_updated: 2023-02-23T14:01:55Z
day: '01'
doi: 10.1016/j.jcta.2017.12.001
extern: '1'
external_id:
arxiv:
- '1703.09946'
intvolume: ' 156'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1703.09946
month: '05'
oa: 1
oa_version: Preprint
page: 44-60
publication: Journal of Combinatorial Theory Series A
publication_identifier:
issn:
- 0097-3165
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: Non-trivially intersecting multi-part families
type: journal_article
user_id: 6785fbc1-c503-11eb-8a32-93094b40e1cf
volume: 156
year: '2018'
...
---
_id: '9665'
abstract:
- lang: eng
text: We investigate the thermodynamics and kinetics of a hydrogen interstitial
in magnetic α-iron, taking account of the quantum fluctuations of the proton as
well as the anharmonicities of lattice vibrations and hydrogen hopping. We show
that the diffusivity of hydrogen in the lattice of bcc iron deviates strongly
from an Arrhenius behavior at and below room temperature. We compare a quantum
transition state theory to explicit ring polymer molecular dynamics in the calculation
of diffusivity. We then address the trapping of hydrogen by a vacancy as a prototype
lattice defect. By a sequence of steps in a thought experiment, each involving
a thermodynamic integration, we are able to separate out the binding free energy
of a proton to a defect into harmonic and anharmonic, and classical and quantum
contributions. We find that about 30% of a typical binding free energy of hydrogen
to a lattice defect in iron is accounted for by finite temperature effects, and
about half of these arise from quantum proton fluctuations. This has huge implications
for the comparison between thermal desorption and permeation experiments and standard
electronic structure theory. The implications are even greater for the interpretation
of muon spin resonance experiments.
article_number: '225901'
article_processing_charge: No
article_type: review
author:
- first_name: Bingqing
full_name: Cheng, Bingqing
id: cbe3cda4-d82c-11eb-8dc7-8ff94289fcc9
last_name: Cheng
orcid: 0000-0002-3584-9632
- first_name: Anthony T.
full_name: Paxton, Anthony T.
last_name: Paxton
- first_name: Michele
full_name: Ceriotti, Michele
last_name: Ceriotti
citation:
ama: 'Cheng B, Paxton AT, Ceriotti M. Hydrogen diffusion and trapping in α-iron:
The role of quantum and anharmonic fluctuations. Physical Review Letters.
2018;120(22). doi:10.1103/physrevlett.120.225901'
apa: 'Cheng, B., Paxton, A. T., & Ceriotti, M. (2018). Hydrogen diffusion and
trapping in α-iron: The role of quantum and anharmonic fluctuations. Physical
Review Letters. American Physical Society. https://doi.org/10.1103/physrevlett.120.225901'
chicago: 'Cheng, Bingqing, Anthony T. Paxton, and Michele Ceriotti. “Hydrogen Diffusion
and Trapping in α-Iron: The Role of Quantum and Anharmonic Fluctuations.” Physical
Review Letters. American Physical Society, 2018. https://doi.org/10.1103/physrevlett.120.225901.'
ieee: 'B. Cheng, A. T. Paxton, and M. Ceriotti, “Hydrogen diffusion and trapping
in α-iron: The role of quantum and anharmonic fluctuations,” Physical Review
Letters, vol. 120, no. 22. American Physical Society, 2018.'
ista: 'Cheng B, Paxton AT, Ceriotti M. 2018. Hydrogen diffusion and trapping in
α-iron: The role of quantum and anharmonic fluctuations. Physical Review Letters.
120(22), 225901.'
mla: 'Cheng, Bingqing, et al. “Hydrogen Diffusion and Trapping in α-Iron: The Role
of Quantum and Anharmonic Fluctuations.” Physical Review Letters, vol.
120, no. 22, 225901, American Physical Society, 2018, doi:10.1103/physrevlett.120.225901.'
short: B. Cheng, A.T. Paxton, M. Ceriotti, Physical Review Letters 120 (2018).
date_created: 2021-07-15T12:22:41Z
date_published: 2018-06-01T00:00:00Z
date_updated: 2021-08-09T12:36:22Z
day: '01'
doi: 10.1103/physrevlett.120.225901
extern: '1'
external_id:
arxiv:
- '1803.00600'
pmid:
- '29906144'
intvolume: ' 120'
issue: '22'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1803.00600
month: '06'
oa: 1
oa_version: Preprint
pmid: 1
publication: Physical Review Letters
publication_identifier:
eissn:
- 1079-7114
issn:
- 0031-9007
publication_status: published
publisher: American Physical Society
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Hydrogen diffusion and trapping in α-iron: The role of quantum and anharmonic
fluctuations'
type: journal_article
user_id: 6785fbc1-c503-11eb-8a32-93094b40e1cf
volume: 120
year: '2018'
...