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