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