---
_id: '13165'
abstract:
- lang: eng
  text: "A graph G=(V, E) is called fully regular if for every independent set I c
    V, the number of vertices in V\\I  that are not connected to any element of I
    depends only on the size of I. A linear ordering of the vertices of G is called
    successive if for every i, the first i vertices induce a connected subgraph of
    G. We give an explicit formula for the number of successive vertex orderings of
    a fully regular graph.\r\nAs an application of our results, we give alternative
    proofs of two theorems of Stanley and Gao & Peng, determining the number of linear
    edge orderings of complete graphs and complete bipartite graphs, respectively,
    with the property that the first i edges induce a connected subgraph.\r\nAs another
    application, we give a simple product formula for the number of linear orderings
    of the hyperedges of a complete 3-partite 3-uniform hypergraph such that, for
    every i, the first i hyperedges induce a connected subgraph. We found similar
    formulas for complete (non-partite) 3-uniform hypergraphs and in another closely
    related case, but we managed to verify them only when the number of vertices is
    small."
article_number: '105776'
article_processing_charge: Yes (in subscription journal)
article_type: original
arxiv: 1
author:
- first_name: Lixing
  full_name: Fang, Lixing
  last_name: Fang
- first_name: Hao
  full_name: Huang, Hao
  last_name: Huang
- first_name: János
  full_name: Pach, János
  id: E62E3130-B088-11EA-B919-BF823C25FEA4
  last_name: Pach
- first_name: Gábor
  full_name: Tardos, Gábor
  last_name: Tardos
- first_name: Junchi
  full_name: Zuo, Junchi
  last_name: Zuo
citation:
  ama: Fang L, Huang H, Pach J, Tardos G, Zuo J. Successive vertex orderings of fully
    regular graphs. <i>Journal of Combinatorial Theory Series A</i>. 2023;199(10).
    doi:<a href="https://doi.org/10.1016/j.jcta.2023.105776">10.1016/j.jcta.2023.105776</a>
  apa: Fang, L., Huang, H., Pach, J., Tardos, G., &#38; Zuo, J. (2023). Successive
    vertex orderings of fully regular graphs. <i>Journal of Combinatorial Theory.
    Series A</i>. Elsevier. <a href="https://doi.org/10.1016/j.jcta.2023.105776">https://doi.org/10.1016/j.jcta.2023.105776</a>
  chicago: Fang, Lixing, Hao Huang, János Pach, Gábor Tardos, and Junchi Zuo. “Successive
    Vertex Orderings of Fully Regular Graphs.” <i>Journal of Combinatorial Theory.
    Series A</i>. Elsevier, 2023. <a href="https://doi.org/10.1016/j.jcta.2023.105776">https://doi.org/10.1016/j.jcta.2023.105776</a>.
  ieee: L. Fang, H. Huang, J. Pach, G. Tardos, and J. Zuo, “Successive vertex orderings
    of fully regular graphs,” <i>Journal of Combinatorial Theory. Series A</i>, vol.
    199, no. 10. Elsevier, 2023.
  ista: Fang L, Huang H, Pach J, Tardos G, Zuo J. 2023. Successive vertex orderings
    of fully regular graphs. Journal of Combinatorial Theory. Series A. 199(10), 105776.
  mla: Fang, Lixing, et al. “Successive Vertex Orderings of Fully Regular Graphs.”
    <i>Journal of Combinatorial Theory. Series A</i>, vol. 199, no. 10, 105776, Elsevier,
    2023, doi:<a href="https://doi.org/10.1016/j.jcta.2023.105776">10.1016/j.jcta.2023.105776</a>.
  short: L. Fang, H. Huang, J. Pach, G. Tardos, J. Zuo, Journal of Combinatorial Theory.
    Series A 199 (2023).
date_created: 2023-06-25T22:00:45Z
date_published: 2023-10-01T00:00:00Z
date_updated: 2024-01-30T12:03:51Z
day: '01'
ddc:
- '510'
department:
- _id: HeEd
doi: 10.1016/j.jcta.2023.105776
external_id:
  arxiv:
  - '2206.13592'
file:
- access_level: open_access
  checksum: 9eebc213b4182a66063a99083ff5bd04
  content_type: application/pdf
  creator: dernst
  date_created: 2024-01-30T12:03:10Z
  date_updated: 2024-01-30T12:03:10Z
  file_id: '14902'
  file_name: 2023_JourCombinatiorialTheory_Fang.pdf
  file_size: 352555
  relation: main_file
  success: 1
file_date_updated: 2024-01-30T12:03:10Z
has_accepted_license: '1'
intvolume: '       199'
issue: '10'
language:
- iso: eng
month: '10'
oa: 1
oa_version: Published Version
publication: Journal of Combinatorial Theory. Series A
publication_identifier:
  eissn:
  - 1096-0899
  issn:
  - 0097-3165
publication_status: published
publisher: Elsevier
quality_controlled: '1'
scopus_import: '1'
status: public
title: Successive vertex orderings of fully regular graphs
tmp:
  image: /images/cc_by_nc_sa.png
  legal_code_url: https://creativecommons.org/licenses/by-nc-sa/4.0/legalcode
  name: Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC
    BY-NC-SA 4.0)
  short: CC BY-NC-SA (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 199
year: '2023'
...
---
_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
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: Pedro
  full_name: Vieira, Pedro
  last_name: Vieira
citation:
  ama: Kwan MA, Sudakov B, Vieira P. Non-trivially intersecting multi-part families.
    <i>Journal of Combinatorial Theory Series A</i>. 2018;156:44-60. doi:<a href="https://doi.org/10.1016/j.jcta.2017.12.001">10.1016/j.jcta.2017.12.001</a>
  apa: Kwan, M. A., Sudakov, B., &#38; Vieira, P. (2018). Non-trivially intersecting
    multi-part families. <i>Journal of Combinatorial Theory Series A</i>. Elsevier.
    <a href="https://doi.org/10.1016/j.jcta.2017.12.001">https://doi.org/10.1016/j.jcta.2017.12.001</a>
  chicago: Kwan, Matthew Alan, Benny Sudakov, and Pedro Vieira. “Non-Trivially Intersecting
    Multi-Part Families.” <i>Journal of Combinatorial Theory Series A</i>. Elsevier,
    2018. <a href="https://doi.org/10.1016/j.jcta.2017.12.001">https://doi.org/10.1016/j.jcta.2017.12.001</a>.
  ieee: M. A. Kwan, B. Sudakov, and P. Vieira, “Non-trivially intersecting multi-part
    families,” <i>Journal of Combinatorial Theory Series A</i>, 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.”
    <i>Journal of Combinatorial Theory Series A</i>, vol. 156, Elsevier, 2018, pp.
    44–60, doi:<a href="https://doi.org/10.1016/j.jcta.2017.12.001">10.1016/j.jcta.2017.12.001</a>.
  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: '4056'
abstract:
- lang: eng
  text: This paper proves that for every n ≥ 4 there is a convex n-gon such that the
    vertices of 2n - 7 vertex pairs are one unit of distance apart. This improves
    the previously best lower bound of ⌊ (5n - 5) 3⌋ given by Erdo{combining double
    acute accent}s and Moser if n ≥ 17.
acknowledgement: The first author is pleased to acknowledge partial support by the
  Amoco Fnd. Fat. Dev. Comput. Sci. i-6-44862 and 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
- first_name: Péter
  full_name: Hajnal, Péter
  last_name: Hajnal
citation:
  ama: Edelsbrunner H, Hajnal P. A lower bound on the number of unit distances between
    the vertices of a convex polygon. <i>Journal of Combinatorial Theory Series A</i>.
    1991;56(2):312-316. doi:<a href="https://doi.org/10.1016/0097-3165(91)90042-F">10.1016/0097-3165(91)90042-F</a>
  apa: Edelsbrunner, H., &#38; Hajnal, P. (1991). A lower bound on the number of unit
    distances between the vertices of a convex polygon. <i>Journal of Combinatorial
    Theory Series A</i>. Elsevier. <a href="https://doi.org/10.1016/0097-3165(91)90042-F">https://doi.org/10.1016/0097-3165(91)90042-F</a>
  chicago: Edelsbrunner, Herbert, and Péter Hajnal. “A Lower Bound on the Number of
    Unit Distances between the Vertices of a Convex Polygon.” <i>Journal of Combinatorial
    Theory Series A</i>. Elsevier, 1991. <a href="https://doi.org/10.1016/0097-3165(91)90042-F">https://doi.org/10.1016/0097-3165(91)90042-F</a>.
  ieee: H. Edelsbrunner and P. Hajnal, “A lower bound on the number of unit distances
    between the vertices of a convex polygon,” <i>Journal of Combinatorial Theory
    Series A</i>, vol. 56, no. 2. Elsevier, pp. 312–316, 1991.
  ista: Edelsbrunner H, Hajnal P. 1991. A lower bound on the number of unit distances
    between the vertices of a convex polygon. Journal of Combinatorial Theory Series
    A. 56(2), 312–316.
  mla: Edelsbrunner, Herbert, and Péter Hajnal. “A Lower Bound on the Number of Unit
    Distances between the Vertices of a Convex Polygon.” <i>Journal of Combinatorial
    Theory Series A</i>, vol. 56, no. 2, Elsevier, 1991, pp. 312–16, doi:<a href="https://doi.org/10.1016/0097-3165(91)90042-F">10.1016/0097-3165(91)90042-F</a>.
  short: H. Edelsbrunner, P. Hajnal, Journal of Combinatorial Theory Series A 56 (1991)
    312–316.
date_created: 2018-12-11T12:06:41Z
date_published: 1991-03-01T00:00:00Z
date_updated: 2022-03-02T09:56:10Z
day: '01'
doi: 10.1016/0097-3165(91)90042-F
extern: '1'
intvolume: '        56'
issue: '2'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://www.sciencedirect.com/science/article/pii/009731659190042F?via%3Dihub
month: '03'
oa: 1
oa_version: Published Version
page: 312 - 316
publication: Journal of Combinatorial Theory Series A
publication_identifier:
  eissn:
  - 1096-0899
  issn:
  - 0097-3165
publication_status: published
publisher: Elsevier
publist_id: '2070'
quality_controlled: '1'
scopus_import: '1'
status: public
title: A lower bound on the number of unit distances between the vertices of a convex
  polygon
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 56
year: '1991'
...
---
_id: '4098'
abstract:
- lang: eng
  text: To points p and q of a finite set S in d-dimensional Euclidean space Ed are
    extreme if {p, q} = S ∩ h, for some open halfspace h. Let e2(d)(n) be the maximum
    number of extreme pairs realized by any n points in Ed. We give geometric proofs
    of , if n⩾4, and e2(3)(n) = 3n−6, if n⩾6. These results settle the question since
    all other cases are trivial.
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
- first_name: Gerd
  full_name: Stöckl, Gerd
  last_name: Stöckl
citation:
  ama: Edelsbrunner H, Stöckl G. The number of extreme pairs of finite point-sets
    in Euclidean spaces. <i>Journal of Combinatorial Theory Series A</i>. 1986;43(2):344-349.
    doi:<a href="https://doi.org/10.1016/0097-3165(86)90075-0">10.1016/0097-3165(86)90075-0</a>
  apa: Edelsbrunner, H., &#38; Stöckl, G. (1986). The number of extreme pairs of finite
    point-sets in Euclidean spaces. <i>Journal of Combinatorial Theory Series A</i>.
    Elsevier. <a href="https://doi.org/10.1016/0097-3165(86)90075-0">https://doi.org/10.1016/0097-3165(86)90075-0</a>
  chicago: Edelsbrunner, Herbert, and Gerd Stöckl. “The Number of Extreme Pairs of
    Finite Point-Sets in Euclidean Spaces.” <i>Journal of Combinatorial Theory Series
    A</i>. Elsevier, 1986. <a href="https://doi.org/10.1016/0097-3165(86)90075-0">https://doi.org/10.1016/0097-3165(86)90075-0</a>.
  ieee: H. Edelsbrunner and G. Stöckl, “The number of extreme pairs of finite point-sets
    in Euclidean spaces,” <i>Journal of Combinatorial Theory Series A</i>, vol. 43,
    no. 2. Elsevier, pp. 344–349, 1986.
  ista: Edelsbrunner H, Stöckl G. 1986. The number of extreme pairs of finite point-sets
    in Euclidean spaces. Journal of Combinatorial Theory Series A. 43(2), 344–349.
  mla: Edelsbrunner, Herbert, and Gerd Stöckl. “The Number of Extreme Pairs of Finite
    Point-Sets in Euclidean Spaces.” <i>Journal of Combinatorial Theory Series A</i>,
    vol. 43, no. 2, Elsevier, 1986, pp. 344–49, doi:<a href="https://doi.org/10.1016/0097-3165(86)90075-0">10.1016/0097-3165(86)90075-0</a>.
  short: H. Edelsbrunner, G. Stöckl, Journal of Combinatorial Theory Series A 43 (1986)
    344–349.
date_created: 2018-12-11T12:06:56Z
date_published: 1986-11-01T00:00:00Z
date_updated: 2022-02-01T14:02:41Z
day: '01'
doi: 10.1016/0097-3165(86)90075-0
extern: '1'
intvolume: '        43'
issue: '2'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://www.sciencedirect.com/science/article/pii/0097316586900750?via%3Dihub
month: '11'
oa: 1
oa_version: None
page: 344 - 349
publication: Journal of Combinatorial Theory Series A
publication_identifier:
  eissn:
  - 1096-0899
  issn:
  - 0097-3165
publication_status: published
publisher: Elsevier
publist_id: '2020'
quality_controlled: '1'
scopus_import: '1'
status: public
title: The number of extreme pairs of finite point-sets in Euclidean spaces
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 43
year: '1986'
...
---
_id: '4103'
abstract:
- lang: eng
  text: Let A be an arrangement of n lines in the plane. Suppose F1,…, Fk are faces
    in the dissection induced by A and that Fi is a t(Fi)-gon. We give asymptotic
    bounds on the maximal sum ∑i=1kt(Fi) which can be realized by k different faces
    in an arrangement of n lines. The results improve known bounds for k of higher
    order than n(1/2).
acknowledgement: The second author thanks Gan Gusfield for useful discussion.
article_processing_charge: No
author:
- first_name: Herbert
  full_name: Edelsbrunner, Herbert
  id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
  last_name: Edelsbrunner
  orcid: 0000-0002-9823-6833
- first_name: Emo
  full_name: Welzl, Emo
  last_name: Welzl
citation:
  ama: Edelsbrunner H, Welzl E. On the maximal number of edges of many faces in an
    arrangement. <i>Journal of Combinatorial Theory Series A</i>. 1986;41(2):159-166.
    doi:<a href="https://doi.org/10.1016/0097-3165(86)90078-6">10.1016/0097-3165(86)90078-6</a>
  apa: Edelsbrunner, H., &#38; Welzl, E. (1986). On the maximal number of edges of
    many faces in an arrangement. <i>Journal of Combinatorial Theory Series A</i>.
    Elsevier. <a href="https://doi.org/10.1016/0097-3165(86)90078-6">https://doi.org/10.1016/0097-3165(86)90078-6</a>
  chicago: Edelsbrunner, Herbert, and Emo Welzl. “On the Maximal Number of Edges of
    Many Faces in an Arrangement.” <i>Journal of Combinatorial Theory Series A</i>.
    Elsevier, 1986. <a href="https://doi.org/10.1016/0097-3165(86)90078-6">https://doi.org/10.1016/0097-3165(86)90078-6</a>.
  ieee: H. Edelsbrunner and E. Welzl, “On the maximal number of edges of many faces
    in an arrangement,” <i>Journal of Combinatorial Theory Series A</i>, vol. 41,
    no. 2. Elsevier, pp. 159–166, 1986.
  ista: Edelsbrunner H, Welzl E. 1986. On the maximal number of edges of many faces
    in an arrangement. Journal of Combinatorial Theory Series A. 41(2), 159–166.
  mla: Edelsbrunner, Herbert, and Emo Welzl. “On the Maximal Number of Edges of Many
    Faces in an Arrangement.” <i>Journal of Combinatorial Theory Series A</i>, vol.
    41, no. 2, Elsevier, 1986, pp. 159–66, doi:<a href="https://doi.org/10.1016/0097-3165(86)90078-6">10.1016/0097-3165(86)90078-6</a>.
  short: H. Edelsbrunner, E. Welzl, Journal of Combinatorial Theory Series A 41 (1986)
    159–166.
date_created: 2018-12-11T12:06:57Z
date_published: 1986-11-01T00:00:00Z
date_updated: 2022-02-01T09:46:55Z
day: '01'
doi: 10.1016/0097-3165(86)90078-6
extern: '1'
intvolume: '        41'
issue: '2'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://www.sciencedirect.com/science/article/pii/0097316586900786?via%3Dihub
month: '11'
oa: 1
oa_version: Published Version
page: 159 - 166
publication: Journal of Combinatorial Theory Series A
publication_identifier:
  eissn:
  - 1096-0899
  issn:
  - 0097-3165
publication_status: published
publisher: Elsevier
publist_id: '2015'
quality_controlled: '1'
scopus_import: '1'
status: public
title: On the maximal number of edges of many faces in an arrangement
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 41
year: '1986'
...
---
_id: '4113'
abstract:
- lang: eng
  text: Let S denote a set of n points in the Euclidean plane. A subset S′ of S is
    termed a k-set of S if it contains k points and there exists a straight line which
    has no point of S on it and separates S′ from S−S′. We let fk(n) denote the maximum
    number of k-sets which can be realized by a set of n points. This paper studies
    the asymptotic behaviour of fk(n) as this function has applications to a number
    of problems in computational geometry. A lower and an upper bound on fk(n) is
    established. Both are nontrivial and improve bounds known before. In particular,  is
    shown by exhibiting special point-sets which realize that many k-sets. In addition,  is
    proved by the study of a combinatorial problem which is of interest in its own
    right.
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
- first_name: Emo
  full_name: Welzl, Emo
  last_name: Welzl
citation:
  ama: Edelsbrunner H, Welzl E. On the number of line separations of a finite set
    in the plane. <i>Journal of Combinatorial Theory Series A</i>. 1985;38(1):15-29.
    doi:<a href="https://doi.org/10.1016/0097-3165(85)90017-2">10.1016/0097-3165(85)90017-2</a>
  apa: Edelsbrunner, H., &#38; Welzl, E. (1985). On the number of line separations
    of a finite set in the plane. <i>Journal of Combinatorial Theory Series A</i>.
    Elsevier. <a href="https://doi.org/10.1016/0097-3165(85)90017-2">https://doi.org/10.1016/0097-3165(85)90017-2</a>
  chicago: Edelsbrunner, Herbert, and Emo Welzl. “On the Number of Line Separations
    of a Finite Set in the Plane.” <i>Journal of Combinatorial Theory Series A</i>.
    Elsevier, 1985. <a href="https://doi.org/10.1016/0097-3165(85)90017-2">https://doi.org/10.1016/0097-3165(85)90017-2</a>.
  ieee: H. Edelsbrunner and E. Welzl, “On the number of line separations of a finite
    set in the plane,” <i>Journal of Combinatorial Theory Series A</i>, vol. 38, no.
    1. Elsevier, pp. 15–29, 1985.
  ista: Edelsbrunner H, Welzl E. 1985. On the number of line separations of a finite
    set in the plane. Journal of Combinatorial Theory Series A. 38(1), 15–29.
  mla: Edelsbrunner, Herbert, and Emo Welzl. “On the Number of Line Separations of
    a Finite Set in the Plane.” <i>Journal of Combinatorial Theory Series A</i>, vol.
    38, no. 1, Elsevier, 1985, pp. 15–29, doi:<a href="https://doi.org/10.1016/0097-3165(85)90017-2">10.1016/0097-3165(85)90017-2</a>.
  short: H. Edelsbrunner, E. Welzl, Journal of Combinatorial Theory Series A 38 (1985)
    15–29.
date_created: 2018-12-11T12:07:01Z
date_published: 1985-01-01T00:00:00Z
date_updated: 2022-01-31T14:14:25Z
day: '01'
doi: 10.1016/0097-3165(85)90017-2
extern: '1'
intvolume: '        38'
issue: '1'
language:
- iso: eng
month: '01'
oa_version: None
page: 15 - 29
publication: Journal of Combinatorial Theory Series A
publication_identifier:
  eissn:
  - 1096-0899
  issn:
  - 0097-3165
publication_status: published
publisher: Elsevier
publist_id: '2011'
quality_controlled: '1'
scopus_import: '1'
status: public
title: On the number of line separations of a finite set in the plane
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 38
year: '1985'
...