---
OA_place: publisher
OA_type: hybrid
PlanS_conform: '1'
_id: '21159'
abstract:
- lang: eng
text: "One of the foundational theorems of extremal graph theory is Dirac’s theorem,
which\r\nsays that if an n-vertex graph G has minimum degree at least n/2, then
G has a\r\nHamilton cycle, and therefore a perfect matching (if n is even). Later
work by Sárközy,\r\nSelkow and Szemerédi showed that in fact Dirac graphs have
many Hamilton cycles\r\nand perfect matchings, culminating in a result of Cuckler
and Kahn that gives a precise\r\ndescription of the numbers of Hamilton cycles
and perfect matchings in a Dirac graph\r\nG (in terms of an entropy-like parameter
of G). In this paper we extend Cuckler\r\nand Kahn’s result to perfect matchings
in hypergraphs. For positive integers d < k,\r\nand for n divisible by k, let
md (k, n) be the minimum d-degree that ensures the\r\nexistence of a perfect matching
in an n-vertex k-uniform hypergraph. In general, it is\r\nan open question to
determine (even asymptotically) the values of md (k, n), but we are\r\nnonetheless
able to prove an analogue of the Cuckler–Kahn theorem, showing that if\r\nan n-vertex
k-uniform hypergraph G has minimum d-degree at least (1+γ )md (k, n)\r\n(for any
constantγ > 0), then the number of perfect matchings in G is controlled by\r\nan
entropy-like parameter of G. This strengthens cruder estimates arising from work\r\nof
Kang–Kelly–Kühn–Osthus–Pfenninger and Pham–Sah–Sawhney–Simkin."
acknowledgement: We would like to thank the referees for a number of helpful comments
and suggestions, which have substantially improved the paper. Open access funding
provided by Institute of Science and Technology (IST Austria).
article_number: '5'
article_processing_charge: Yes (via OA deal)
article_type: original
arxiv: 1
author:
- first_name: Matthew Alan
full_name: Kwan, Matthew Alan
id: 5fca0887-a1db-11eb-95d1-ca9d5e0453b3
last_name: Kwan
orcid: 0000-0002-4003-7567
- first_name: Roodabeh
full_name: Safavi Hemami, Roodabeh
id: 72ed2640-8972-11ed-ae7b-f9c81ec75154
last_name: Safavi Hemami
- first_name: Yiting
full_name: Wang, Yiting
id: 1917d194-076e-11ed-97cd-837255f88785
last_name: Wang
orcid: 0000-0002-2856-767X
citation:
ama: Kwan MA, Safavi Hemami R, Wang Y. Counting perfect matchings in Dirac hypergraphs.
Combinatorica. 2026;46. doi:10.1007/s00493-025-00194-8
apa: Kwan, M. A., Safavi Hemami, R., & Wang, Y. (2026). Counting perfect matchings
in Dirac hypergraphs. Combinatorica. Springer Nature. https://doi.org/10.1007/s00493-025-00194-8
chicago: Kwan, Matthew Alan, Roodabeh Safavi Hemami, and Yiting Wang. “Counting
Perfect Matchings in Dirac Hypergraphs.” Combinatorica. Springer Nature,
2026. https://doi.org/10.1007/s00493-025-00194-8.
ieee: M. A. Kwan, R. Safavi Hemami, and Y. Wang, “Counting perfect matchings in
Dirac hypergraphs,” Combinatorica, vol. 46. Springer Nature, 2026.
ista: Kwan MA, Safavi Hemami R, Wang Y. 2026. Counting perfect matchings in Dirac
hypergraphs. Combinatorica. 46, 5.
mla: Kwan, Matthew Alan, et al. “Counting Perfect Matchings in Dirac Hypergraphs.”
Combinatorica, vol. 46, 5, Springer Nature, 2026, doi:10.1007/s00493-025-00194-8.
short: M.A. Kwan, R. Safavi Hemami, Y. Wang, Combinatorica 46 (2026).
corr_author: '1'
date_created: 2026-02-08T23:02:49Z
date_published: 2026-02-01T00:00:00Z
date_updated: 2026-02-16T09:55:17Z
day: '01'
ddc:
- '510'
department:
- _id: MaKw
- _id: MoHe
doi: 10.1007/s00493-025-00194-8
external_id:
arxiv:
- '2408.09589'
file:
- access_level: open_access
checksum: 47b0031d90b0e6b9a843f422a1486089
content_type: application/pdf
creator: dernst
date_created: 2026-02-16T09:52:38Z
date_updated: 2026-02-16T09:52:38Z
file_id: '21228'
file_name: 2026_Combinatorica_Kwan.pdf
file_size: 539646
relation: main_file
success: 1
file_date_updated: 2026-02-16T09:52:38Z
has_accepted_license: '1'
intvolume: ' 46'
language:
- iso: eng
license: https://creativecommons.org/licenses/by/4.0/
month: '02'
oa: 1
oa_version: Published Version
publication: Combinatorica
publication_identifier:
eissn:
- 1439-6912
issn:
- 0209-9683
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Counting perfect matchings in Dirac hypergraphs
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 46
year: '2026'
...
---
OA_place: repository
OA_type: green
_id: '22159'
abstract:
- lang: eng
text: 'The size Ramsey number of a graph H is defined as the minimum number of edges
in a graph G such that there is a monochromatic copy of H in every two-coloring
of E(G). The size Ramsey number was introduced by Erdős, Faudree, Rousseau, and
Schelp in 1978 and they ended their foundational paper by asking whether one can
determine up to a constant factor the size Ramsey numbers of three families of
graphs: complete bipartite graphs, book graphs (obtained by adding many common
neighbors to the vertices of a clique), and starburst graphs (obtained by adding
many pendant edges to each vertex of a clique). In this paper, we completely resolve
the latter two questions and make substantial progress on the first by determining
the size Ramsey number of Ks,t up to a constant factor for all t=Ω(s log s).'
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: Yuval
full_name: Wigderson, Yuval
id: 2d0023a0-1567-11f0-833d-d5c1e476d4b5
last_name: Wigderson
citation:
ama: Conlon D, Fox J, Wigderson Y. Three early problems on size Ramsey numbers.
Combinatorica. 2023;43(4):743-768. doi:10.1007/s00493-023-00034-7
apa: Conlon, D., Fox, J., & Wigderson, Y. (2023). Three early problems on size
Ramsey numbers. Combinatorica. Springer Nature. https://doi.org/10.1007/s00493-023-00034-7
chicago: Conlon, David, Jacob Fox, and Yuval Wigderson. “Three Early Problems on
Size Ramsey Numbers.” Combinatorica. Springer Nature, 2023. https://doi.org/10.1007/s00493-023-00034-7.
ieee: D. Conlon, J. Fox, and Y. Wigderson, “Three early problems on size Ramsey
numbers,” Combinatorica, vol. 43, no. 4. Springer Nature, pp. 743–768,
2023.
ista: Conlon D, Fox J, Wigderson Y. 2023. Three early problems on size Ramsey numbers.
Combinatorica. 43(4), 743–768.
mla: Conlon, David, et al. “Three Early Problems on Size Ramsey Numbers.” Combinatorica,
vol. 43, no. 4, Springer Nature, 2023, pp. 743–68, doi:10.1007/s00493-023-00034-7.
short: D. Conlon, J. Fox, Y. Wigderson, Combinatorica 43 (2023) 743–768.
date_created: 2026-06-29T10:51:32Z
date_published: 2023-08-01T00:00:00Z
date_updated: 2026-07-08T10:34:40Z
day: '01'
doi: 10.1007/s00493-023-00034-7
extern: '1'
external_id:
arxiv:
- '2111.05420'
intvolume: ' 43'
issue: '4'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2111.05420
month: '08'
oa: 1
oa_version: Preprint
page: 743-768
publication: Combinatorica
publication_identifier:
eissn:
- 1439-6912
issn:
- 0209-9683
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Three early problems on size Ramsey numbers
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 43
year: '2023'
...
---
_id: '10335'
abstract:
- lang: eng
text: "Van der Holst and Pendavingh introduced a graph parameter σ, which coincides
with the more famous Colin de Verdière graph parameter μ for small values. However,
the definition of a is much more geometric/topological directly reflecting embeddability
properties of the graph. They proved μ(G) ≤ σ(G) + 2 and conjectured σ(G) ≤ σ(G)
for any graph G. We confirm this conjecture. As far as we know, this is the first
topological upper bound on σ(G) which is, in general, tight.\r\nEquality between
μ and σ does not hold in general as van der Holst and Pendavingh showed that there
is a graph G with μ(G) ≤ 18 and σ(G) ≥ 20. We show that the gap appears at much
smaller values, namely, we exhibit a graph H for which μ(H) ≥ 7 and σ(H) ≥ 8.
We also prove that, in general, the gap can be large: The incidence graphs Hq
of finite projective planes of order q satisfy μ(Hq) ∈ O(q3/2) and σ(Hq) ≥ q2."
acknowledgement: 'V. K. gratefully acknowledges the support of Austrian Science Fund
(FWF): P 30902-N35. This work was done mostly while he was employed at the University
of Innsbruck. During the early stage of this research, V. K. was partially supported
by Charles University project GAUK 926416. M. T. is supported by the grant no. 19-04113Y
of the Czech Science Foundation(GA ˇCR) and partially supported by Charles University
project UNCE/SCI/004.'
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Vojtech
full_name: Kaluza, Vojtech
id: 21AE5134-9EAC-11EA-BEA2-D7BD3DDC885E
last_name: Kaluza
orcid: 0000-0002-2512-8698
- first_name: Martin
full_name: Tancer, Martin
id: 38AC689C-F248-11E8-B48F-1D18A9856A87
last_name: Tancer
orcid: 0000-0002-1191-6714
citation:
ama: Kaluza V, Tancer M. Even maps, the Colin de Verdière number and representations
of graphs. Combinatorica. 2022;42:1317-1345. doi:10.1007/s00493-021-4443-7
apa: Kaluza, V., & Tancer, M. (2022). Even maps, the Colin de Verdière number
and representations of graphs. Combinatorica. Springer Nature. https://doi.org/10.1007/s00493-021-4443-7
chicago: Kaluza, Vojtech, and Martin Tancer. “Even Maps, the Colin de Verdière Number
and Representations of Graphs.” Combinatorica. Springer Nature, 2022. https://doi.org/10.1007/s00493-021-4443-7.
ieee: V. Kaluza and M. Tancer, “Even maps, the Colin de Verdière number and representations
of graphs,” Combinatorica, vol. 42. Springer Nature, pp. 1317–1345, 2022.
ista: Kaluza V, Tancer M. 2022. Even maps, the Colin de Verdière number and representations
of graphs. Combinatorica. 42, 1317–1345.
mla: Kaluza, Vojtech, and Martin Tancer. “Even Maps, the Colin de Verdière Number
and Representations of Graphs.” Combinatorica, vol. 42, Springer Nature,
2022, pp. 1317–45, doi:10.1007/s00493-021-4443-7.
short: V. Kaluza, M. Tancer, Combinatorica 42 (2022) 1317–1345.
corr_author: '1'
date_created: 2021-11-25T13:49:16Z
date_published: 2022-12-01T00:00:00Z
date_updated: 2024-10-09T20:53:51Z
day: '01'
ddc:
- '514'
- '516'
department:
- _id: UlWa
doi: 10.1007/s00493-021-4443-7
external_id:
arxiv:
- '1907.05055'
isi:
- '000798210100003'
intvolume: ' 42'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: ' https://doi.org/10.48550/arXiv.1907.05055'
month: '12'
oa: 1
oa_version: Preprint
page: 1317-1345
publication: Combinatorica
publication_identifier:
issn:
- 0209-9683
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Even maps, the Colin de Verdière number and representations of graphs
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 42
year: '2022'
...
---
OA_place: repository
OA_type: green
_id: '22174'
abstract:
- lang: eng
text: "The book graph B\r\n(k)\r\nn consists of n copies of Kk+1 joined along a
common Kk. The Ramsey\r\nnumbers of B\r\n(k)\r\nn are known to have strong connections
to the classical Ramsey numbers\r\nof cliques. Recently, the first author determined
the asymptotic order of these Ramsey\r\nnumbers for fixed k, thus answering an
old question of Erd˝os, Faudree, Rousseau, and\r\nSchelp. In this paper, we first
provide a simpler proof of this theorem. Next, answering a\r\nquestion of the
first author, we present a different proof that avoids the use of Szemer´edi’s\r\nregularity
lemma, thus providing much tighter control on the error term. Finally, we prove\r\na
conjecture of Nikiforov, Rousseau, and Schelp by showing that all extremal colorings
for\r\nthis Ramsey problem are quasirandom"
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: Yuval
full_name: Wigderson, Yuval
id: 2d0023a0-1567-11f0-833d-d5c1e476d4b5
last_name: Wigderson
citation:
ama: Conlon D, Fox J, Wigderson Y. Ramsey numbers of books and quasirandomness.
Combinatorica. 2022;42(3):309-363. doi:10.1007/s00493-021-4409-9
apa: Conlon, D., Fox, J., & Wigderson, Y. (2022). Ramsey numbers of books and
quasirandomness. Combinatorica. Springer Nature. https://doi.org/10.1007/s00493-021-4409-9
chicago: Conlon, David, Jacob Fox, and Yuval Wigderson. “Ramsey Numbers of Books
and Quasirandomness.” Combinatorica. Springer Nature, 2022. https://doi.org/10.1007/s00493-021-4409-9.
ieee: D. Conlon, J. Fox, and Y. Wigderson, “Ramsey numbers of books and quasirandomness,”
Combinatorica, vol. 42, no. 3. Springer Nature, pp. 309–363, 2022.
ista: Conlon D, Fox J, Wigderson Y. 2022. Ramsey numbers of books and quasirandomness.
Combinatorica. 42(3), 309–363.
mla: Conlon, David, et al. “Ramsey Numbers of Books and Quasirandomness.” Combinatorica,
vol. 42, no. 3, Springer Nature, 2022, pp. 309–63, doi:10.1007/s00493-021-4409-9.
short: D. Conlon, J. Fox, Y. Wigderson, Combinatorica 42 (2022) 309–363.
date_created: 2026-06-29T10:57:27Z
date_published: 2022-06-01T00:00:00Z
date_updated: 2026-07-14T08:57:12Z
day: '01'
doi: 10.1007/s00493-021-4409-9
extern: '1'
external_id:
arxiv:
- '2001.00407'
intvolume: ' 42'
issue: '3'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2001.00407
month: '06'
oa: 1
oa_version: Preprint
page: 309-363
publication: Combinatorica
publication_identifier:
eissn:
- 1439-6912
issn:
- 0209-9683
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Ramsey numbers of books and quasirandomness
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 42
year: '2022'
...
---
_id: '15275'
abstract:
- lang: eng
text: In 1916, Schur introduced the Ramsey number r(3; m), which is the minimum
integer n > 1 such that for any m-coloring of the edges of the complete graph
Kn, there is a monochromatic copy of K3. He showed that r(3; m) ≤ O(m!), and a
simple construction demonstrates that r(3; m) ≥ 2Ω(m). An old conjecture of Erdős
states that r(3; m) = 2Θ(m). In this note, we prove the conjecture for m-colorings
with bounded VC-dimension, that is, for m-colorings with the property that the
set system induced by the neighborhoods of the vertices with respect to each color
class has bounded VC-dimension.
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Jacob
full_name: Fox, Jacob
last_name: Fox
- first_name: János
full_name: Pach, János
id: E62E3130-B088-11EA-B919-BF823C25FEA4
last_name: Pach
- first_name: Andrew
full_name: Suk, Andrew
last_name: Suk
citation:
ama: Fox J, Pach J, Suk A. Bounded VC-dimension implies the Schur-Erdős conjecture.
Combinatorica. 2021;41(6):803-813. doi:10.1007/s00493-021-4530-9
apa: Fox, J., Pach, J., & Suk, A. (2021). Bounded VC-dimension implies the Schur-Erdős
conjecture. Combinatorica. Springer Nature. https://doi.org/10.1007/s00493-021-4530-9
chicago: Fox, Jacob, János Pach, and Andrew Suk. “Bounded VC-Dimension Implies the
Schur-Erdős Conjecture.” Combinatorica. Springer Nature, 2021. https://doi.org/10.1007/s00493-021-4530-9.
ieee: J. Fox, J. Pach, and A. Suk, “Bounded VC-dimension implies the Schur-Erdős
conjecture,” Combinatorica, vol. 41, no. 6. Springer Nature, pp. 803–813,
2021.
ista: Fox J, Pach J, Suk A. 2021. Bounded VC-dimension implies the Schur-Erdős conjecture.
Combinatorica. 41(6), 803–813.
mla: Fox, Jacob, et al. “Bounded VC-Dimension Implies the Schur-Erdős Conjecture.”
Combinatorica, vol. 41, no. 6, Springer Nature, 2021, pp. 803–13, doi:10.1007/s00493-021-4530-9.
short: J. Fox, J. Pach, A. Suk, Combinatorica 41 (2021) 803–813.
date_created: 2024-04-03T07:59:57Z
date_published: 2021-11-20T00:00:00Z
date_updated: 2024-04-09T10:40:08Z
day: '20'
department:
- _id: HeEd
doi: 10.1007/s00493-021-4530-9
external_id:
arxiv:
- '1912.02342'
intvolume: ' 41'
issue: '6'
keyword:
- Computational Mathematics
- Discrete Mathematics and Combinatorics
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.1912.02342
month: '11'
oa: 1
oa_version: Preprint
page: 803-813
publication: Combinatorica
publication_identifier:
eissn:
- 1439-6912
issn:
- 0209-9683
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
status: public
title: Bounded VC-dimension implies the Schur-Erdős conjecture
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 41
year: '2021'
...
---
_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: '7034'
abstract:
- lang: eng
text: We find a graph of genus 5 and its drawing on the orientable surface of genus
4 with every pair of independent edges crossing an even number of times. This
shows that the strong Hanani–Tutte theorem cannot be extended to the orientable
surface of genus 4. As a base step in the construction we use a counterexample
to an extension of the unified Hanani–Tutte theorem on the torus.
article_processing_charge: No
article_type: original
arxiv: 1
author:
- first_name: Radoslav
full_name: Fulek, Radoslav
id: 39F3FFE4-F248-11E8-B48F-1D18A9856A87
last_name: Fulek
orcid: 0000-0001-8485-1774
- first_name: Jan
full_name: Kynčl, Jan
last_name: Kynčl
citation:
ama: Fulek R, Kynčl J. Counterexample to an extension of the Hanani-Tutte theorem
on the surface of genus 4. Combinatorica. 2019;39(6):1267-1279. doi:10.1007/s00493-019-3905-7
apa: Fulek, R., & Kynčl, J. (2019). Counterexample to an extension of the Hanani-Tutte
theorem on the surface of genus 4. Combinatorica. Springer Nature. https://doi.org/10.1007/s00493-019-3905-7
chicago: Fulek, Radoslav, and Jan Kynčl. “Counterexample to an Extension of the
Hanani-Tutte Theorem on the Surface of Genus 4.” Combinatorica. Springer
Nature, 2019. https://doi.org/10.1007/s00493-019-3905-7.
ieee: R. Fulek and J. Kynčl, “Counterexample to an extension of the Hanani-Tutte
theorem on the surface of genus 4,” Combinatorica, vol. 39, no. 6. Springer
Nature, pp. 1267–1279, 2019.
ista: Fulek R, Kynčl J. 2019. Counterexample to an extension of the Hanani-Tutte
theorem on the surface of genus 4. Combinatorica. 39(6), 1267–1279.
mla: Fulek, Radoslav, and Jan Kynčl. “Counterexample to an Extension of the Hanani-Tutte
Theorem on the Surface of Genus 4.” Combinatorica, vol. 39, no. 6, Springer
Nature, 2019, pp. 1267–79, doi:10.1007/s00493-019-3905-7.
short: R. Fulek, J. Kynčl, Combinatorica 39 (2019) 1267–1279.
date_created: 2019-11-18T14:29:50Z
date_published: 2019-10-29T00:00:00Z
date_updated: 2025-04-14T13:52:37Z
day: '29'
department:
- _id: UlWa
doi: 10.1007/s00493-019-3905-7
ec_funded: 1
external_id:
arxiv:
- '1709.00508'
isi:
- '000493267200003'
intvolume: ' 39'
isi: 1
issue: '6'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1709.00508
month: '10'
oa: 1
oa_version: Preprint
page: 1267-1279
project:
- _id: 25681D80-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '291734'
name: International IST Postdoc Fellowship Programme
- _id: 261FA626-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: M02281
name: Eliminating intersections in drawings of graphs
publication: Combinatorica
publication_identifier:
eissn:
- 1439-6912
issn:
- 0209-9683
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Counterexample to an extension of the Hanani-Tutte theorem on the surface of
genus 4
type: journal_article
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 39
year: '2019'
...
---
_id: '1173'
abstract:
- lang: eng
text: We introduce the Voronoi functional of a triangulation of a finite set of
points in the Euclidean plane and prove that among all geometric triangulations
of the point set, the Delaunay triangulation maximizes the functional. This result
neither extends to topological triangulations in the plane nor to geometric triangulations
in three and higher dimensions.
acknowledgement: This research is partially supported by the Russian Government under
the Mega Project 11.G34.31.0053, by the Toposys project FP7-ICT-318493-STREP, by
ESF under the ACAT Research Network Programme, by RFBR grant 11-01-00735, and by
NSF grants DMS-1101688, DMS-1400876.
article_processing_charge: No
arxiv: 1
author:
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Alexey
full_name: Glazyrin, Alexey
last_name: Glazyrin
- first_name: Oleg
full_name: Musin, Oleg
last_name: Musin
- first_name: Anton
full_name: Nikitenko, Anton
id: 3E4FF1BA-F248-11E8-B48F-1D18A9856A87
last_name: Nikitenko
orcid: 0000-0002-0659-3201
citation:
ama: Edelsbrunner H, Glazyrin A, Musin O, Nikitenko A. The Voronoi functional is
maximized by the Delaunay triangulation in the plane. Combinatorica. 2017;37(5):887-910.
doi:10.1007/s00493-016-3308-y
apa: Edelsbrunner, H., Glazyrin, A., Musin, O., & Nikitenko, A. (2017). The
Voronoi functional is maximized by the Delaunay triangulation in the plane. Combinatorica.
Springer. https://doi.org/10.1007/s00493-016-3308-y
chicago: Edelsbrunner, Herbert, Alexey Glazyrin, Oleg Musin, and Anton Nikitenko.
“The Voronoi Functional Is Maximized by the Delaunay Triangulation in the Plane.”
Combinatorica. Springer, 2017. https://doi.org/10.1007/s00493-016-3308-y.
ieee: H. Edelsbrunner, A. Glazyrin, O. Musin, and A. Nikitenko, “The Voronoi functional
is maximized by the Delaunay triangulation in the plane,” Combinatorica,
vol. 37, no. 5. Springer, pp. 887–910, 2017.
ista: Edelsbrunner H, Glazyrin A, Musin O, Nikitenko A. 2017. The Voronoi functional
is maximized by the Delaunay triangulation in the plane. Combinatorica. 37(5),
887–910.
mla: Edelsbrunner, Herbert, et al. “The Voronoi Functional Is Maximized by the Delaunay
Triangulation in the Plane.” Combinatorica, vol. 37, no. 5, Springer, 2017,
pp. 887–910, doi:10.1007/s00493-016-3308-y.
short: H. Edelsbrunner, A. Glazyrin, O. Musin, A. Nikitenko, Combinatorica 37 (2017)
887–910.
date_created: 2018-12-11T11:50:32Z
date_published: 2017-10-01T00:00:00Z
date_updated: 2025-06-04T08:44:44Z
day: '01'
department:
- _id: HeEd
doi: 10.1007/s00493-016-3308-y
ec_funded: 1
external_id:
arxiv:
- '1411.6337'
isi:
- '000418056000005'
intvolume: ' 37'
isi: 1
issue: '5'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1411.6337
month: '10'
oa: 1
oa_version: Submitted Version
page: 887 - 910
project:
- _id: 255D761E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '318493'
name: Topological Complex Systems
publication: Combinatorica
publication_identifier:
issn:
- 0209-9683
publication_status: published
publisher: Springer
publist_id: '6182'
quality_controlled: '1'
scopus_import: '1'
status: public
title: The Voronoi functional is maximized by the Delaunay triangulation in the plane
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 37
year: '2017'
...
---
_id: '4053'
abstract:
- lang: eng
text: We show that the maximum number of edges bounding m faces in an arrangement
of n line segments in the plane is O(m2/3n2/3+nα(n)+nlog m). This improves a previous
upper bound of Edelsbrunner et al. [5] and almost matches the best known lower
bound which is Ω(m2/3n2/3+nα(n)). In addition, we show that the number of edges
bounding any m faces in an arrangement of n line segments with a total of t intersecting
pairs is O(m2/3t1/3+nα(t/n)+nmin{log m,log t/n}), almost matching the lower bound
of Ω(m2/3t1/3+nα(t/n)) demonstrated in this paper.
article_processing_charge: No
article_type: original
author:
- first_name: Boris
full_name: Aronov, Boris
last_name: Aronov
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
- first_name: Leonidas
full_name: Guibas, Leonidas
last_name: Guibas
- first_name: Micha
full_name: Sharir, Micha
last_name: Sharir
citation:
ama: Aronov B, Edelsbrunner H, Guibas L, Sharir M. The number of edges of many faces
in a line segment arrangement. Combinatorica. 1992;12(3):261-274. doi:10.1007/BF01285815
apa: Aronov, B., Edelsbrunner, H., Guibas, L., & Sharir, M. (1992). The number
of edges of many faces in a line segment arrangement. Combinatorica. Springer.
https://doi.org/10.1007/BF01285815
chicago: Aronov, Boris, Herbert Edelsbrunner, Leonidas Guibas, and Micha Sharir.
“The Number of Edges of Many Faces in a Line Segment Arrangement.” Combinatorica.
Springer, 1992. https://doi.org/10.1007/BF01285815.
ieee: B. Aronov, H. Edelsbrunner, L. Guibas, and M. Sharir, “The number of edges
of many faces in a line segment arrangement,” Combinatorica, vol. 12, no.
3. Springer, pp. 261–274, 1992.
ista: Aronov B, Edelsbrunner H, Guibas L, Sharir M. 1992. The number of edges of
many faces in a line segment arrangement. Combinatorica. 12(3), 261–274.
mla: Aronov, Boris, et al. “The Number of Edges of Many Faces in a Line Segment
Arrangement.” Combinatorica, vol. 12, no. 3, Springer, 1992, pp. 261–74,
doi:10.1007/BF01285815.
short: B. Aronov, H. Edelsbrunner, L. Guibas, M. Sharir, Combinatorica 12 (1992)
261–274.
date_created: 2018-12-11T12:06:40Z
date_published: 1992-09-01T00:00:00Z
date_updated: 2022-03-15T15:44:26Z
day: '01'
doi: 10.1007/BF01285815
extern: '1'
intvolume: ' 12'
issue: '3'
language:
- iso: eng
main_file_link:
- url: https://link.springer.com/article/10.1007/BF01285815
month: '09'
oa_version: None
page: 261 - 274
publication: Combinatorica
publication_identifier:
issn:
- 0209-9683
publication_status: published
publisher: Springer
publist_id: '2074'
quality_controlled: '1'
scopus_import: '1'
status: public
title: The number of edges of many faces in a line segment arrangement
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 12
year: '1992'
...
---
_id: '4069'
abstract:
- lang: eng
text: Let C be a cell complex in d-dimensional Euclidean space whose faces are obtained
by orthogonal projection of the faces of a convex polytope in d + 1 dimensions.
For example, the Delaunay triangulation of a finite point set is such a cell complex.
This paper shows that the in front/behind relation defined for the faces of C
with respect to any fixed viewpoint x is acyclic. This result has applications
to hidden line/surface removal and other problems in computational geometry.
acknowledgement: Research reported in this paper was supported by the National Science
Foundation under grant CCR-8714565.
article_processing_charge: No
article_type: original
author:
- first_name: Herbert
full_name: Edelsbrunner, Herbert
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
citation:
ama: Edelsbrunner H. An acyclicity theorem for cell complexes in d dimension. Combinatorica.
1990;10(3):251-260. doi:10.1007/BF02122779
apa: Edelsbrunner, H. (1990). An acyclicity theorem for cell complexes in d dimension.
Combinatorica. Springer. https://doi.org/10.1007/BF02122779
chicago: Edelsbrunner, Herbert. “An Acyclicity Theorem for Cell Complexes in d Dimension.”
Combinatorica. Springer, 1990. https://doi.org/10.1007/BF02122779.
ieee: H. Edelsbrunner, “An acyclicity theorem for cell complexes in d dimension,”
Combinatorica, vol. 10, no. 3. Springer, pp. 251–260, 1990.
ista: Edelsbrunner H. 1990. An acyclicity theorem for cell complexes in d dimension.
Combinatorica. 10(3), 251–260.
mla: Edelsbrunner, Herbert. “An Acyclicity Theorem for Cell Complexes in d Dimension.”
Combinatorica, vol. 10, no. 3, Springer, 1990, pp. 251–60, doi:10.1007/BF02122779.
short: H. Edelsbrunner, Combinatorica 10 (1990) 251–260.
date_created: 2018-12-11T12:06:45Z
date_published: 1990-09-01T00:00:00Z
date_updated: 2022-02-21T11:08:30Z
day: '01'
doi: 10.1007/BF02122779
extern: '1'
intvolume: ' 10'
issue: '3'
language:
- iso: eng
main_file_link:
- url: https://link.springer.com/article/10.1007/BF02122779
month: '09'
oa_version: None
page: 251 - 260
publication: Combinatorica
publication_identifier:
eissn:
- 1439-6912
issn:
- 0209-9683
publication_status: published
publisher: Springer
publist_id: '2050'
quality_controlled: '1'
scopus_import: '1'
status: public
title: An acyclicity theorem for cell complexes in d dimension
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 10
year: '1990'
...