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