[{"publication":"Journal of Combinatorial Theory. Series A","has_accepted_license":"1","month":"10","article_number":"105776","oa_version":"Published Version","language":[{"iso":"eng"}],"date_published":"2023-10-01T00:00:00Z","type":"journal_article","tmp":{"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)","image":"/images/cc_by_nc_sa.png","short":"CC BY-NC-SA (4.0)"},"oa":1,"publication_identifier":{"eissn":["1096-0899"],"issn":["0097-3165"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","status":"public","file":[{"date_updated":"2024-01-30T12:03:10Z","content_type":"application/pdf","file_name":"2023_JourCombinatiorialTheory_Fang.pdf","date_created":"2024-01-30T12:03:10Z","file_size":352555,"checksum":"9eebc213b4182a66063a99083ff5bd04","file_id":"14902","creator":"dernst","success":1,"relation":"main_file","access_level":"open_access"}],"author":[{"full_name":"Fang, Lixing","last_name":"Fang","first_name":"Lixing"},{"full_name":"Huang, Hao","last_name":"Huang","first_name":"Hao"},{"id":"E62E3130-B088-11EA-B919-BF823C25FEA4","full_name":"Pach, János","last_name":"Pach","first_name":"János"},{"full_name":"Tardos, Gábor","first_name":"Gábor","last_name":"Tardos"},{"last_name":"Zuo","first_name":"Junchi","full_name":"Zuo, Junchi"}],"issue":"10","_id":"13165","scopus_import":"1","license":"https://creativecommons.org/licenses/by-nc-sa/4.0/","title":"Successive vertex orderings of fully regular graphs","intvolume":"       199","publication_status":"published","date_created":"2023-06-25T22:00:45Z","department":[{"_id":"HeEd"}],"article_processing_charge":"Yes (in subscription journal)","file_date_updated":"2024-01-30T12:03:10Z","quality_controlled":"1","article_type":"original","publisher":"Elsevier","external_id":{"arxiv":["2206.13592"]},"date_updated":"2024-01-30T12:03:51Z","citation":{"short":"L. Fang, H. Huang, J. Pach, G. Tardos, J. Zuo, Journal of Combinatorial Theory. Series A 199 (2023).","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>.","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.","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>","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>","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.","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>."},"year":"2023","abstract":[{"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.","lang":"eng"}],"arxiv":1,"doi":"10.1016/j.jcta.2023.105776","day":"01","ddc":["510"],"volume":199},{"publist_id":"2070","oa":1,"publication_identifier":{"eissn":["1096-0899"],"issn":["0097-3165"]},"date_published":"1991-03-01T00:00:00Z","type":"journal_article","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","status":"public","main_file_link":[{"url":"https://www.sciencedirect.com/science/article/pii/009731659190042F?via%3Dihub","open_access":"1"}],"month":"03","oa_version":"Published Version","publication":"Journal of Combinatorial Theory Series A","language":[{"iso":"eng"}],"abstract":[{"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.","lang":"eng"}],"doi":"10.1016/0097-3165(91)90042-F","day":"01","date_updated":"2022-03-02T09:56:10Z","year":"1991","citation":{"short":"H. Edelsbrunner, P. Hajnal, Journal of Combinatorial Theory Series A 56 (1991) 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>.","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.","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."},"extern":"1","volume":56,"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.","title":"A lower bound on the number of unit distances between the vertices of a convex polygon","intvolume":"        56","publication_status":"published","date_created":"2018-12-11T12:06:41Z","article_processing_charge":"No","author":[{"orcid":"0000-0002-9823-6833","full_name":"Edelsbrunner, Herbert","first_name":"Herbert","last_name":"Edelsbrunner","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Hajnal, Péter","last_name":"Hajnal","first_name":"Péter"}],"issue":"2","_id":"4056","scopus_import":"1","article_type":"original","publisher":"Elsevier","page":"312 - 316","quality_controlled":"1"},{"language":[{"iso":"eng"}],"publication":"Journal of Combinatorial Theory Series A","oa_version":"None","month":"11","main_file_link":[{"open_access":"1","url":"https://www.sciencedirect.com/science/article/pii/0097316586900750?via%3Dihub"}],"user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","status":"public","date_published":"1986-11-01T00:00:00Z","type":"journal_article","publication_identifier":{"eissn":["1096-0899"],"issn":["0097-3165"]},"oa":1,"publist_id":"2020","page":"344 - 349","quality_controlled":"1","publisher":"Elsevier","article_type":"original","_id":"4098","scopus_import":"1","author":[{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","first_name":"Herbert","last_name":"Edelsbrunner","orcid":"0000-0002-9823-6833","full_name":"Edelsbrunner, Herbert"},{"full_name":"Stöckl, Gerd","last_name":"Stöckl","first_name":"Gerd"}],"issue":"2","publication_status":"published","date_created":"2018-12-11T12:06:56Z","article_processing_charge":"No","title":"The number of extreme pairs of finite point-sets in Euclidean spaces","intvolume":"        43","volume":43,"extern":"1","date_updated":"2022-02-01T14:02:41Z","citation":{"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.","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>","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.","short":"H. Edelsbrunner, G. Stöckl, Journal of Combinatorial Theory Series A 43 (1986) 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>."},"year":"1986","doi":"10.1016/0097-3165(86)90075-0","day":"01","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."}]},{"language":[{"iso":"eng"}],"oa_version":"Published Version","month":"11","publication":"Journal of Combinatorial Theory Series A","main_file_link":[{"url":"https://www.sciencedirect.com/science/article/pii/0097316586900786?via%3Dihub","open_access":"1"}],"user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","status":"public","publication_identifier":{"eissn":["1096-0899"],"issn":["0097-3165"]},"publist_id":"2015","oa":1,"type":"journal_article","date_published":"1986-11-01T00:00:00Z","publisher":"Elsevier","quality_controlled":"1","page":"159 - 166","date_created":"2018-12-11T12:06:57Z","article_processing_charge":"No","publication_status":"published","intvolume":"        41","title":"On the maximal number of edges of many faces in an arrangement","scopus_import":"1","_id":"4103","issue":"2","author":[{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","last_name":"Edelsbrunner","first_name":"Herbert","full_name":"Edelsbrunner, Herbert","orcid":"0000-0002-9823-6833"},{"first_name":"Emo","last_name":"Welzl","full_name":"Welzl, Emo"}],"volume":41,"acknowledgement":"The second author thanks Gan Gusfield for useful discussion.","extern":"1","day":"01","doi":"10.1016/0097-3165(86)90078-6","abstract":[{"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).","lang":"eng"}],"year":"1986","citation":{"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.","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.","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>","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.","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>."},"date_updated":"2022-02-01T09:46:55Z"},{"publication":"Journal of Combinatorial Theory Series A","month":"01","oa_version":"None","language":[{"iso":"eng"}],"type":"journal_article","date_published":"1985-01-01T00:00:00Z","publist_id":"2011","publication_identifier":{"issn":["0097-3165"],"eissn":["1096-0899"]},"user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","status":"public","issue":"1","author":[{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","full_name":"Edelsbrunner, Herbert","orcid":"0000-0002-9823-6833","last_name":"Edelsbrunner","first_name":"Herbert"},{"last_name":"Welzl","first_name":"Emo","full_name":"Welzl, Emo"}],"scopus_import":"1","_id":"4113","intvolume":"        38","title":"On the number of line separations of a finite set in the plane","article_processing_charge":"No","date_created":"2018-12-11T12:07:01Z","publication_status":"published","quality_controlled":"1","page":"15 - 29","article_type":"original","publisher":"Elsevier","citation":{"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.","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>.","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>","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."},"year":"1985","date_updated":"2022-01-31T14:14:25Z","abstract":[{"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.","lang":"eng"}],"day":"01","doi":"10.1016/0097-3165(85)90017-2","extern":"1","volume":38}]