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