---
OA_place: repository
OA_type: green
_id: '22201'
abstract:
- lang: eng
  text: We consider an analog of a conjecture of Montgomery and Soundararajan on the
    moments of primes in short intervals in number fields; this analog was discussed
    and heuristically derived in a paper of the second author, Rodgers, and Roditty-Gershon.
    Adapting work of the first author and Fiorilli in the integer case, we establish
    lower bounds on a weighted version of these moments which agree with the conjectured
    values.
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Régis
  full_name: de la Bretèche, Régis
  last_name: de la Bretèche
- first_name: Vivian Zieve
  full_name: Kuperberg, Vivian Zieve
  id: c3bac823-112d-11f0-a3f5-c264f852e697
  last_name: Kuperberg
citation:
  ama: de la Bretèche R, Kuperberg VZ. Lower bounds on weighted moments of primes
    in short intervals in number fields. <i>Israel Journal of Mathematics</i>. 2025;267(1):437-461.
    doi:<a href="https://doi.org/10.1007/s11856-024-2711-0">10.1007/s11856-024-2711-0</a>
  apa: de la Bretèche, R., &#38; Kuperberg, V. Z. (2025). Lower bounds on weighted
    moments of primes in short intervals in number fields. <i>Israel Journal of Mathematics</i>.
    Springer Nature. <a href="https://doi.org/10.1007/s11856-024-2711-0">https://doi.org/10.1007/s11856-024-2711-0</a>
  chicago: Bretèche, Régis de la, and Vivian Zieve Kuperberg. “Lower Bounds on Weighted
    Moments of Primes in Short Intervals in Number Fields.” <i>Israel Journal of Mathematics</i>.
    Springer Nature, 2025. <a href="https://doi.org/10.1007/s11856-024-2711-0">https://doi.org/10.1007/s11856-024-2711-0</a>.
  ieee: R. de la Bretèche and V. Z. Kuperberg, “Lower bounds on weighted moments of
    primes in short intervals in number fields,” <i>Israel Journal of Mathematics</i>,
    vol. 267, no. 1. Springer Nature, pp. 437–461, 2025.
  ista: de la Bretèche R, Kuperberg VZ. 2025. Lower bounds on weighted moments of
    primes in short intervals in number fields. Israel Journal of Mathematics. 267(1),
    437–461.
  mla: de la Bretèche, Régis, and Vivian Zieve Kuperberg. “Lower Bounds on Weighted
    Moments of Primes in Short Intervals in Number Fields.” <i>Israel Journal of Mathematics</i>,
    vol. 267, no. 1, Springer Nature, 2025, pp. 437–61, doi:<a href="https://doi.org/10.1007/s11856-024-2711-0">10.1007/s11856-024-2711-0</a>.
  short: R. de la Bretèche, V.Z. Kuperberg, Israel Journal of Mathematics 267 (2025)
    437–461.
date_created: 2026-06-29T13:00:06Z
date_published: 2025-06-01T00:00:00Z
date_updated: 2026-07-14T11:28:49Z
day: '01'
doi: 10.1007/s11856-024-2711-0
extern: '1'
external_id:
  arxiv:
  - '2305.02662'
fulldoi: https://doi.org/10.1007/s11856-024-2711-0
intvolume: '       267'
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.48550/arXiv.2305.02662
month: '06'
oa: 1
oa_version: Preprint
page: 437-461
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: Lower bounds on weighted moments of primes in short intervals in number fields
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 267
year: '2025'
...
---
OA_place: repository
OA_type: green
_id: '22179'
abstract:
- lang: eng
  text: "Burr and Erd˝os in 1975 conjectured, and Chv´atal, R¨odl, Szemer´edi and\r\nTrotter
    later proved, that the Ramsey number of any bounded degree\r\ngraph is linear
    in the number of vertices. In this paper, we disprove\r\nthe natural directed
    analogue of the Burr–Erd˝os conjecture, answering a\r\nquestion of Buci´c, Letzter,
    and Sudakov. If H is an acyclic digraph, the\r\noriented Ramsey number of H, denoted
    −→r1(H), is the least N such that\r\nevery tournament on N vertices contains a
    copy of H. We show that for\r\nany Δ ≥ 2 and any sufficiently large n, there exists
    an acyclic digraph H\r\nwith n vertices and maximum degree Δ such that\r\n−→r1(H)
    ≥ nΩ(Δ2/3/ log5/3 Δ).\r\nThis proves that −→r1(H) is not always linear in the
    number of vertices for\r\nbounded-degree H. On the other hand, we show that −→r1(H)
    is nearly linear\r\nin the number of vertices for typical bounded-degree acyclic
    digraphs H,\r\nand obtain linear or nearly linear bounds for several natural families
    of\r\nbounded-degree acyclic digraphs.\r\nFor multiple colors, we prove a quasi-polynomial
    upper bound −→rk(H)=\r\n2(log n)Ok(1) for all bounded-degree acyclic digraphs
    H on n vertices, where −→rk(H) is the least N such that every k-edge-colored tournament
    on N\r\nvertices contains a monochromatic copy of H. For k ≥ 2 and n ≥ 4, we\r\nexhibit
    an acyclic digraph H with n vertices and maximum degree 3 such\r\nthat −→rk(H)
    ≥ nΩ(log n/ log log n), showing that these Ramsey numbers can\r\ngrow faster than
    any polynomial in the number of vertices."
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Jacob
  full_name: Fox, Jacob
  last_name: Fox
- first_name: Xiaoyu
  full_name: He, Xiaoyu
  last_name: He
- first_name: Yuval
  full_name: Wigderson, Yuval
  id: 2d0023a0-1567-11f0-833d-d5c1e476d4b5
  last_name: Wigderson
citation:
  ama: Fox J, He X, Wigderson Y. Ramsey numbers of sparse digraphs. <i>Israel Journal
    of Mathematics</i>. 2024;263(1):1-48. doi:<a href="https://doi.org/10.1007/s11856-024-2624-y">10.1007/s11856-024-2624-y</a>
  apa: Fox, J., He, X., &#38; Wigderson, Y. (2024). Ramsey numbers of sparse digraphs.
    <i>Israel Journal of Mathematics</i>. Springer Nature. <a href="https://doi.org/10.1007/s11856-024-2624-y">https://doi.org/10.1007/s11856-024-2624-y</a>
  chicago: Fox, Jacob, Xiaoyu He, and Yuval Wigderson. “Ramsey Numbers of Sparse Digraphs.”
    <i>Israel Journal of Mathematics</i>. Springer Nature, 2024. <a href="https://doi.org/10.1007/s11856-024-2624-y">https://doi.org/10.1007/s11856-024-2624-y</a>.
  ieee: J. Fox, X. He, and Y. Wigderson, “Ramsey numbers of sparse digraphs,” <i>Israel
    Journal of Mathematics</i>, vol. 263, no. 1. Springer Nature, pp. 1–48, 2024.
  ista: Fox J, He X, Wigderson Y. 2024. Ramsey numbers of sparse digraphs. Israel
    Journal of Mathematics. 263(1), 1–48.
  mla: Fox, Jacob, et al. “Ramsey Numbers of Sparse Digraphs.” <i>Israel Journal of
    Mathematics</i>, vol. 263, no. 1, Springer Nature, 2024, pp. 1–48, doi:<a href="https://doi.org/10.1007/s11856-024-2624-y">10.1007/s11856-024-2624-y</a>.
  short: J. Fox, X. He, Y. Wigderson, Israel Journal of Mathematics 263 (2024) 1–48.
date_created: 2026-06-29T10:59:02Z
date_published: 2024-10-01T00:00:00Z
date_updated: 2026-07-14T09:08:32Z
day: '01'
doi: 10.1007/s11856-024-2624-y
extern: '1'
external_id:
  arxiv:
  - '2105.02383'
fulldoi: https://doi.org/10.1007/s11856-024-2624-y
intvolume: '       263'
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.48550/arXiv.2105.02383
month: '10'
oa: 1
oa_version: Preprint
page: 1-48
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: Ramsey numbers of sparse digraphs
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 263
year: '2024'
...
---
_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. <i>Israel
    Journal of Mathematics</i>. 2023;256(2):363-416. doi:<a href="https://doi.org/10.1007/s11856-023-2513-9">10.1007/s11856-023-2513-9</a>
  apa: Kwan, M. A., Sah, A., Sawhney, M., &#38; Simkin, M. (2023). Substructures in
    Latin squares. <i>Israel Journal of Mathematics</i>. Springer Nature. <a href="https://doi.org/10.1007/s11856-023-2513-9">https://doi.org/10.1007/s11856-023-2513-9</a>
  chicago: Kwan, Matthew Alan, Ashwin Sah, Mehtaab Sawhney, and Michael Simkin. “Substructures
    in Latin Squares.” <i>Israel Journal of Mathematics</i>. Springer Nature, 2023.
    <a href="https://doi.org/10.1007/s11856-023-2513-9">https://doi.org/10.1007/s11856-023-2513-9</a>.
  ieee: M. A. Kwan, A. Sah, M. Sawhney, and M. Simkin, “Substructures in Latin squares,”
    <i>Israel Journal of Mathematics</i>, 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.” <i>Israel Journal
    of Mathematics</i>, vol. 256, no. 2, Springer Nature, 2023, pp. 363–416, doi:<a
    href="https://doi.org/10.1007/s11856-023-2513-9">10.1007/s11856-023-2513-9</a>.
  short: M.A. Kwan, A. Sah, M. Sawhney, M. Simkin, Israel Journal of Mathematics 256
    (2023) 363–416.
date_created: 2023-10-22T22:01:14Z
date_published: 2023-09-01T00:00:00Z
date_updated: 2025-09-09T13:08:47Z
day: '01'
department:
- _id: MaKw
doi: 10.1007/s11856-023-2513-9
external_id:
  arxiv:
  - '2202.05088'
  isi:
  - '001081646400001'
fulldoi: https://doi.org/10.1007/s11856-023-2513-9
intvolume: '       256'
isi: 1
issue: '2'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.48550/arXiv.2202.05088
month: '09'
oa: 1
oa_version: Preprint
page: 363-416
publication: Israel Journal of Mathematics
publication_identifier:
  eissn:
  - 1565-8511
  issn:
  - 0021-2172
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Substructures in Latin squares
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 256
year: '2023'
...
---
_id: '14445'
abstract:
- lang: eng
  text: "We prove the following quantitative Borsuk–Ulam-type result (an equivariant
    analogue of Gromov’s Topological Overlap Theorem): Let X be a free ℤ/2-complex
    of dimension d with coboundary expansion at least ηk in dimension 0 ≤ k < d. Then
    for every equivariant map F: X →ℤ/2 ℝd, the fraction of d-simplices σ of X with
    0 ∈ F (σ) is at least 2−d Π d−1k=0ηk.\r\n\r\nAs an application, we show that for
    every sufficiently thick d-dimensional spherical building Y and every map f: Y
    → ℝ2d, we have f(σ) ∩ f(τ) ≠ ∅ for a constant fraction μd > 0 of pairs {σ, τ}
    of d-simplices of Y. In particular, such complexes are non-embeddable into ℝ2d,
    which proves a conjecture of Tancer and Vorwerk for sufficiently thick spherical
    buildings.\r\n\r\nWe complement these results by upper bounds on the coboundary
    expansion of two families of simplicial complexes; this indicates some limitations
    to the bounds one can obtain by straighforward applications of the quantitative
    Borsuk–Ulam theorem. Specifically, we prove\r\n\r\n• an upper bound of (d + 1)/2d
    on the normalized (d − 1)-th coboundary expansion constant of complete (d + 1)-partite
    d-dimensional complexes (under a mild divisibility assumption on the sizes of
    the parts); and\r\n\r\n• an upper bound of (d + 1)/2d + ε on the normalized (d
    − 1)-th coboundary expansion of the d-dimensional spherical building associated
    with GLd+2(Fq) for any ε > 0 and sufficiently large q. This disproves, in a rather
    strong sense, a conjecture of Lubotzky, Meshulam and Mozes."
article_processing_charge: Yes (via OA deal)
article_type: original
author:
- first_name: Uli
  full_name: Wagner, Uli
  id: 36690CA2-F248-11E8-B48F-1D18A9856A87
  last_name: Wagner
  orcid: 0000-0002-1494-0568
- first_name: Pascal
  full_name: Wild, Pascal
  id: 4C20D868-F248-11E8-B48F-1D18A9856A87
  last_name: Wild
citation:
  ama: Wagner U, Wild P. Coboundary expansion, equivariant overlap, and crossing numbers
    of simplicial complexes. <i>Israel Journal of Mathematics</i>. 2023;256(2):675-717.
    doi:<a href="https://doi.org/10.1007/s11856-023-2521-9">10.1007/s11856-023-2521-9</a>
  apa: Wagner, U., &#38; Wild, P. (2023). Coboundary expansion, equivariant overlap,
    and crossing numbers of simplicial complexes. <i>Israel Journal of Mathematics</i>.
    Springer Nature. <a href="https://doi.org/10.1007/s11856-023-2521-9">https://doi.org/10.1007/s11856-023-2521-9</a>
  chicago: Wagner, Uli, and Pascal Wild. “Coboundary Expansion, Equivariant Overlap,
    and Crossing Numbers of Simplicial Complexes.” <i>Israel Journal of Mathematics</i>.
    Springer Nature, 2023. <a href="https://doi.org/10.1007/s11856-023-2521-9">https://doi.org/10.1007/s11856-023-2521-9</a>.
  ieee: U. Wagner and P. Wild, “Coboundary expansion, equivariant overlap, and crossing
    numbers of simplicial complexes,” <i>Israel Journal of Mathematics</i>, vol. 256,
    no. 2. Springer Nature, pp. 675–717, 2023.
  ista: Wagner U, Wild P. 2023. Coboundary expansion, equivariant overlap, and crossing
    numbers of simplicial complexes. Israel Journal of Mathematics. 256(2), 675–717.
  mla: Wagner, Uli, and Pascal Wild. “Coboundary Expansion, Equivariant Overlap, and
    Crossing Numbers of Simplicial Complexes.” <i>Israel Journal of Mathematics</i>,
    vol. 256, no. 2, Springer Nature, 2023, pp. 675–717, doi:<a href="https://doi.org/10.1007/s11856-023-2521-9">10.1007/s11856-023-2521-9</a>.
  short: U. Wagner, P. Wild, Israel Journal of Mathematics 256 (2023) 675–717.
corr_author: '1'
date_created: 2023-10-22T22:01:14Z
date_published: 2023-09-01T00:00:00Z
date_updated: 2024-10-09T21:07:12Z
day: '01'
ddc:
- '510'
department:
- _id: UlWa
doi: 10.1007/s11856-023-2521-9
external_id:
  isi:
  - '001081646400010'
file:
- access_level: open_access
  checksum: fbb05619fe4b650f341cc730425dd9c3
  content_type: application/pdf
  creator: dernst
  date_created: 2023-10-31T11:20:31Z
  date_updated: 2023-10-31T11:20:31Z
  file_id: '14475'
  file_name: 2023_IsraelJourMath_Wagner.pdf
  file_size: 623787
  relation: main_file
  success: 1
file_date_updated: 2023-10-31T11:20:31Z
fulldoi: https://doi.org/10.1007/s11856-023-2521-9
has_accepted_license: '1'
intvolume: '       256'
isi: 1
issue: '2'
language:
- iso: eng
month: '09'
oa: 1
oa_version: Published Version
page: 675-717
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: Coboundary expansion, equivariant overlap, and crossing numbers of simplicial
  complexes
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: 256
year: '2023'
...
---
_id: '9652'
abstract:
- lang: eng
  text: In 1998 Burago and Kleiner and (independently) McMullen gave examples of separated
    nets in Euclidean space which are non-bilipschitz equivalent to the integer lattice.
    We study weaker notions of equivalence of separated nets and demonstrate that
    such notions also give rise to distinct equivalence classes. Put differently,
    we find occurrences of particularly strong divergence of separated nets from the
    integer lattice. Our approach generalises that of Burago and Kleiner and McMullen
    which takes place largely in a continuous setting. Existence of irregular separated
    nets is verified via the existence of non-realisable density functions ρ:[0,1]d→(0,∞).
    In the present work we obtain stronger types of non-realisable densities.
acknowledgement: 'This work was done while both authors were employed at the University
  of Innsbruck and enjoyed the full support of Austrian Science Fund (FWF): P 30902-N35.'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Michael
  full_name: Dymond, Michael
  last_name: Dymond
- first_name: Vojtech
  full_name: Kaluza, Vojtech
  id: 21AE5134-9EAC-11EA-BEA2-D7BD3DDC885E
  last_name: Kaluza
  orcid: 0000-0002-2512-8698
citation:
  ama: Dymond M, Kaluza V. Highly irregular separated nets. <i>Israel Journal of Mathematics</i>.
    2023;253:501-554. doi:<a href="https://doi.org/10.1007/s11856-022-2448-6">10.1007/s11856-022-2448-6</a>
  apa: Dymond, M., &#38; Kaluza, V. (2023). Highly irregular separated nets. <i>Israel
    Journal of Mathematics</i>. Springer Nature. <a href="https://doi.org/10.1007/s11856-022-2448-6">https://doi.org/10.1007/s11856-022-2448-6</a>
  chicago: Dymond, Michael, and Vojtech Kaluza. “Highly Irregular Separated Nets.”
    <i>Israel Journal of Mathematics</i>. Springer Nature, 2023. <a href="https://doi.org/10.1007/s11856-022-2448-6">https://doi.org/10.1007/s11856-022-2448-6</a>.
  ieee: M. Dymond and V. Kaluza, “Highly irregular separated nets,” <i>Israel Journal
    of Mathematics</i>, vol. 253. Springer Nature, pp. 501–554, 2023.
  ista: Dymond M, Kaluza V. 2023. Highly irregular separated nets. Israel Journal
    of Mathematics. 253, 501–554.
  mla: Dymond, Michael, and Vojtech Kaluza. “Highly Irregular Separated Nets.” <i>Israel
    Journal of Mathematics</i>, vol. 253, Springer Nature, 2023, pp. 501–54, doi:<a
    href="https://doi.org/10.1007/s11856-022-2448-6">10.1007/s11856-022-2448-6</a>.
  short: M. Dymond, V. Kaluza, Israel Journal of Mathematics 253 (2023) 501–554.
date_created: 2021-07-14T07:01:28Z
date_published: 2023-03-01T00:00:00Z
date_updated: 2023-08-14T11:26:34Z
day: '01'
ddc:
- '515'
- '516'
department:
- _id: UlWa
doi: 10.1007/s11856-022-2448-6
external_id:
  arxiv:
  - '1903.05923'
  isi:
  - '000904950300003'
file:
- access_level: open_access
  checksum: 6fa0a3207dd1d6467c309fd1bcc867d1
  content_type: application/pdf
  creator: vkaluza
  date_created: 2021-07-14T07:41:50Z
  date_updated: 2021-07-14T07:41:50Z
  file_id: '9653'
  file_name: separated_nets.pdf
  file_size: 900422
  relation: main_file
file_date_updated: 2021-07-14T07:41:50Z
fulldoi: https://doi.org/10.1007/s11856-022-2448-6
has_accepted_license: '1'
intvolume: '       253'
isi: 1
keyword:
- Lipschitz
- bilipschitz
- bounded displacement
- modulus of continuity
- separated net
- non-realisable density
- Burago--Kleiner construction
language:
- iso: eng
month: '03'
oa: 1
oa_version: Submitted Version
page: 501-554
publication: Israel Journal of Mathematics
publication_identifier:
  eissn:
  - 1565-8511
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Highly irregular separated nets
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 253
year: '2023'
...
---
OA_place: repository
OA_type: green
_id: '22162'
abstract:
- lang: eng
  text: "Given a bipartite graph G, the graphical matrix space SG consists of\r\nmatrices
    whose non-zero entries can only be at those positions corresponding to edges in
    G. Tutte (J. London Math. Soc., 1947), Edmonds\r\n(J. Res. Nat. Bur. Standards
    Sect. B, 1967) and Lov´asz (FCT, 1979) observed connections between perfect matchings
    in G and full-rank matrices\r\nin SG. Dieudonn´e (Arch. Math., 1948) proved a
    tight upper bound on\r\nthe dimensions of those matrix spaces containing only
    singular matrices.\r\nThe starting point of this paper is a simultaneous generalization
    of these\r\ntwo classical results: we show that the largest dimension over subspaces\r\nof
    SG containing only singular matrices is equal to the maximum size over\r\nsubgraphs
    of G without perfect matchings, based on Meshulam’s proof of\r\nDieudonn´e’s result
    (Quart. J. Math., 1985).\r\nStarting from this result, we go on to establish more
    connections\r\nbetween properties of graphs and matrix spaces. For example, we\r\nestablish
    connections between acyclicity and nilpotency, between strong\r\nconnectivity
    and irreducibility, and between isomorphism and\r\nconjugacy/congruence. For each
    connection, we study three types of correspondences, namely the basic correspondence,
    the inherited correspondence (for subgraphs and subspaces), and the induced correspondence\r\n(for
    induced subgraphs and restrictions). Some correspondences lead to\r\nintriguing
    generalizations of classical results, such as Dieudonn´e’s result\r\nmentioned
    above, and a celebrated theorem of Gerstenhaber regarding the\r\nlargest dimension
    of nil matrix spaces (Amer. J. Math., 1958).\r\nFinally, we show some implications
    of our results to quantum information and present open problems in computational
    complexity motivated\r\nby these results."
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Yinan
  full_name: Li, Yinan
  last_name: Li
- first_name: Youming
  full_name: Qiao, Youming
  last_name: Qiao
- first_name: Avi
  full_name: Wigderson, Avi
  last_name: Wigderson
- first_name: Yuval
  full_name: Wigderson, Yuval
  id: 2d0023a0-1567-11f0-833d-d5c1e476d4b5
  last_name: Wigderson
- first_name: Chuanqi
  full_name: Zhang, Chuanqi
  last_name: Zhang
citation:
  ama: Li Y, Qiao Y, Wigderson A, Wigderson Y, Zhang C. Connections between graphs
    and matrix spaces. <i>Israel Journal of Mathematics</i>. 2023;256(2):513-580.
    doi:<a href="https://doi.org/10.1007/s11856-023-2515-7">10.1007/s11856-023-2515-7</a>
  apa: Li, Y., Qiao, Y., Wigderson, A., Wigderson, Y., &#38; Zhang, C. (2023). Connections
    between graphs and matrix spaces. <i>Israel Journal of Mathematics</i>. Springer
    Nature. <a href="https://doi.org/10.1007/s11856-023-2515-7">https://doi.org/10.1007/s11856-023-2515-7</a>
  chicago: Li, Yinan, Youming Qiao, Avi Wigderson, Yuval Wigderson, and Chuanqi Zhang.
    “Connections between Graphs and Matrix Spaces.” <i>Israel Journal of Mathematics</i>.
    Springer Nature, 2023. <a href="https://doi.org/10.1007/s11856-023-2515-7">https://doi.org/10.1007/s11856-023-2515-7</a>.
  ieee: Y. Li, Y. Qiao, A. Wigderson, Y. Wigderson, and C. Zhang, “Connections between
    graphs and matrix spaces,” <i>Israel Journal of Mathematics</i>, vol. 256, no.
    2. Springer Nature, pp. 513–580, 2023.
  ista: Li Y, Qiao Y, Wigderson A, Wigderson Y, Zhang C. 2023. Connections between
    graphs and matrix spaces. Israel Journal of Mathematics. 256(2), 513–580.
  mla: Li, Yinan, et al. “Connections between Graphs and Matrix Spaces.” <i>Israel
    Journal of Mathematics</i>, vol. 256, no. 2, Springer Nature, 2023, pp. 513–80,
    doi:<a href="https://doi.org/10.1007/s11856-023-2515-7">10.1007/s11856-023-2515-7</a>.
  short: Y. Li, Y. Qiao, A. Wigderson, Y. Wigderson, C. Zhang, Israel Journal of Mathematics
    256 (2023) 513–580.
date_created: 2026-06-29T10:52:37Z
date_published: 2023-09-01T00:00:00Z
date_updated: 2026-07-08T10:44:50Z
day: '01'
doi: 10.1007/s11856-023-2515-7
extern: '1'
external_id:
  arxiv:
  - '2206.04815'
fulldoi: https://doi.org/10.1007/s11856-023-2515-7
intvolume: '       256'
issue: '2'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.48550/arXiv.2206.04815
month: '09'
oa: 1
oa_version: Preprint
page: 513-580
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: Connections between graphs and matrix spaces
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 256
year: '2023'
...
---
_id: '10220'
abstract:
- lang: eng
  text: "We study conditions under which a finite simplicial complex K can be mapped
    to ℝd without higher-multiplicity intersections. An almost r-embedding is a map
    f: K → ℝd such that the images of any r pairwise disjoint simplices of K do not
    have a common point. We show that if r is not a prime power and d ≥ 2r + 1, then
    there is a counterexample to the topological Tverberg conjecture, i.e., there
    is an almost r-embedding of the (d +1)(r − 1)-simplex in ℝd. This improves on
    previous constructions of counterexamples (for d ≥ 3r) based on a series of papers
    by M. Özaydin, M. Gromov, P. Blagojević, F. Frick, G. Ziegler, and the second
    and fourth present authors.\r\n\r\nThe counterexamples are obtained by proving
    the following algebraic criterion in codimension 2: If r ≥ 3 and if K is a finite
    2(r − 1)-complex, then there exists an almost r-embedding K → ℝ2r if and only
    if there exists a general position PL map f: K → ℝ2r such that the algebraic intersection
    number of the f-images of any r pairwise disjoint simplices of K is zero. This
    result can be restated in terms of a cohomological obstruction and extends an
    analogous codimension 3 criterion by the second and fourth authors. As another
    application, we classify ornaments f: S3 ⊔ S3 ⊔ S3 → ℝ5 up to ornament concordance.\r\n\r\nIt
    follows from work of M. Freedman, V. Krushkal and P. Teichner that the analogous
    criterion for r = 2 is false. We prove a lemma on singular higher-dimensional
    Borromean rings, yielding an elementary proof of the counterexample."
acknowledgement: Research supported by the Swiss National Science Foundation (Project
  SNSF-PP00P2-138948), by the Austrian Science Fund (FWF Project P31312-N35), by the
  Russian Foundation for Basic Research (Grants No. 15-01-06302 and 19-01-00169),
  by a Simons-IUM Fellowship, and by the D. Zimin Dynasty Foundation Grant. We would
  like to thank E. Alkin, A. Klyachko, V. Krushkal, S. Melikhov, M. Tancer, P. Teichner
  and anonymous referees for helpful comments and discussions.
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Sergey
  full_name: Avvakumov, Sergey
  id: 3827DAC8-F248-11E8-B48F-1D18A9856A87
  last_name: Avvakumov
  orcid: 0000-0002-7840-5062
- first_name: Isaac
  full_name: Mabillard, Isaac
  id: 32BF9DAA-F248-11E8-B48F-1D18A9856A87
  last_name: Mabillard
- first_name: Arkadiy B.
  full_name: Skopenkov, Arkadiy B.
  last_name: Skopenkov
- first_name: Uli
  full_name: Wagner, Uli
  id: 36690CA2-F248-11E8-B48F-1D18A9856A87
  last_name: Wagner
  orcid: 0000-0002-1494-0568
citation:
  ama: Avvakumov S, Mabillard I, Skopenkov AB, Wagner U. Eliminating higher-multiplicity
    intersections. III. Codimension 2. <i>Israel Journal of Mathematics</i>. 2021;245:501–534.
    doi:<a href="https://doi.org/10.1007/s11856-021-2216-z">10.1007/s11856-021-2216-z</a>
  apa: Avvakumov, S., Mabillard, I., Skopenkov, A. B., &#38; Wagner, U. (2021). Eliminating
    higher-multiplicity intersections. III. Codimension 2. <i>Israel Journal of Mathematics</i>.
    Springer Nature. <a href="https://doi.org/10.1007/s11856-021-2216-z">https://doi.org/10.1007/s11856-021-2216-z</a>
  chicago: Avvakumov, Sergey, Isaac Mabillard, Arkadiy B. Skopenkov, and Uli Wagner.
    “Eliminating Higher-Multiplicity Intersections. III. Codimension 2.” <i>Israel
    Journal of Mathematics</i>. Springer Nature, 2021. <a href="https://doi.org/10.1007/s11856-021-2216-z">https://doi.org/10.1007/s11856-021-2216-z</a>.
  ieee: S. Avvakumov, I. Mabillard, A. B. Skopenkov, and U. Wagner, “Eliminating higher-multiplicity
    intersections. III. Codimension 2,” <i>Israel Journal of Mathematics</i>, vol.
    245. Springer Nature, pp. 501–534, 2021.
  ista: Avvakumov S, Mabillard I, Skopenkov AB, Wagner U. 2021. Eliminating higher-multiplicity
    intersections. III. Codimension 2. Israel Journal of Mathematics. 245, 501–534.
  mla: Avvakumov, Sergey, et al. “Eliminating Higher-Multiplicity Intersections. III.
    Codimension 2.” <i>Israel Journal of Mathematics</i>, vol. 245, Springer Nature,
    2021, pp. 501–534, doi:<a href="https://doi.org/10.1007/s11856-021-2216-z">10.1007/s11856-021-2216-z</a>.
  short: S. Avvakumov, I. Mabillard, A.B. Skopenkov, U. Wagner, Israel Journal of
    Mathematics 245 (2021) 501–534.
corr_author: '1'
date_created: 2021-11-07T23:01:24Z
date_published: 2021-10-30T00:00:00Z
date_updated: 2025-07-02T10:54:52Z
day: '30'
department:
- _id: UlWa
doi: 10.1007/s11856-021-2216-z
external_id:
  arxiv:
  - '1511.03501'
  isi:
  - '000712942100013'
fulldoi: https://doi.org/10.1007/s11856-021-2216-z
intvolume: '       245'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://arxiv.org/abs/1511.03501
month: '10'
oa: 1
oa_version: Preprint
page: '501–534 '
project:
- _id: 26611F5C-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: P31312
  name: Algorithms for Embeddings and Homotopy Theory
publication: Israel Journal of Mathematics
publication_identifier:
  eissn:
  - 1565-8511
  issn:
  - 0021-2172
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
  record:
  - id: '9308'
    relation: earlier_version
    status: public
  - id: '8183'
    relation: earlier_version
    status: public
scopus_import: '1'
status: public
title: Eliminating higher-multiplicity intersections. III. Codimension 2
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 245
year: '2021'
...
---
_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. <i>Israel Journal of Mathematics</i>. 2020;238(2):663-685.
    doi:<a href="https://doi.org/10.1007/s11856-020-2035-7">10.1007/s11856-020-2035-7</a>
  apa: Bucić, M., Kwan, M. A., Pokrovskiy, A., Sudakov, B., Tran, T., &#38; Wagner,
    A. Z. (2020). Nearly-linear monotone paths in edge-ordered graphs. <i>Israel Journal
    of Mathematics</i>. Springer. <a href="https://doi.org/10.1007/s11856-020-2035-7">https://doi.org/10.1007/s11856-020-2035-7</a>
  chicago: Bucić, Matija, Matthew Alan Kwan, Alexey Pokrovskiy, Benny Sudakov, Tuan
    Tran, and Adam Zsolt Wagner. “Nearly-Linear Monotone Paths in Edge-Ordered Graphs.”
    <i>Israel Journal of Mathematics</i>. Springer, 2020. <a href="https://doi.org/10.1007/s11856-020-2035-7">https://doi.org/10.1007/s11856-020-2035-7</a>.
  ieee: M. Bucić, M. A. Kwan, A. Pokrovskiy, B. Sudakov, T. Tran, and A. Z. Wagner,
    “Nearly-linear monotone paths in edge-ordered graphs,” <i>Israel Journal of Mathematics</i>,
    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.”
    <i>Israel Journal of Mathematics</i>, vol. 238, no. 2, Springer, 2020, pp. 663–85,
    doi:<a href="https://doi.org/10.1007/s11856-020-2035-7">10.1007/s11856-020-2035-7</a>.
  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'
fulldoi: https://doi.org/10.1007/s11856-020-2035-7
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: '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. <i>Israel
    Journal of Mathematics</i>. 2019;233(1):67-111. doi:<a href="https://doi.org/10.1007/s11856-019-1897-z">10.1007/s11856-019-1897-z</a>
  apa: Conlon, D., Fox, J., Kwan, M. A., &#38; Sudakov, B. (2019). Hypergraph cuts
    above the average. <i>Israel Journal of Mathematics</i>. Springer. <a href="https://doi.org/10.1007/s11856-019-1897-z">https://doi.org/10.1007/s11856-019-1897-z</a>
  chicago: Conlon, David, Jacob Fox, Matthew Alan Kwan, and Benny Sudakov. “Hypergraph
    Cuts above the Average.” <i>Israel Journal of Mathematics</i>. Springer, 2019.
    <a href="https://doi.org/10.1007/s11856-019-1897-z">https://doi.org/10.1007/s11856-019-1897-z</a>.
  ieee: D. Conlon, J. Fox, M. A. Kwan, and B. Sudakov, “Hypergraph cuts above the
    average,” <i>Israel Journal of Mathematics</i>, 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.” <i>Israel Journal
    of Mathematics</i>, vol. 233, no. 1, Springer, 2019, pp. 67–111, doi:<a href="https://doi.org/10.1007/s11856-019-1897-z">10.1007/s11856-019-1897-z</a>.
  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'
fulldoi: https://doi.org/10.1007/s11856-019-1897-z
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'
...
