@article{13165, abstract = {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. As 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. As 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.}, author = {Fang, Lixing and Huang, Hao and Pach, János and Tardos, Gábor and Zuo, Junchi}, issn = {1096-0899}, journal = {Journal of Combinatorial Theory. Series A}, number = {10}, publisher = {Elsevier}, title = {{Successive vertex orderings of fully regular graphs}}, doi = {10.1016/j.jcta.2023.105776}, volume = {199}, year = {2023}, } @article{9587, abstract = {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.}, author = {Kwan, Matthew Alan and Sudakov, Benny and Vieira, Pedro}, issn = {0097-3165}, journal = {Journal of Combinatorial Theory Series A}, pages = {44--60}, publisher = {Elsevier}, title = {{Non-trivially intersecting multi-part families}}, doi = {10.1016/j.jcta.2017.12.001}, volume = {156}, year = {2018}, } @article{4056, abstract = {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.}, author = {Edelsbrunner, Herbert and Hajnal, Péter}, issn = {1096-0899}, journal = {Journal of Combinatorial Theory Series A}, number = {2}, pages = {312 -- 316}, publisher = {Elsevier}, title = {{A lower bound on the number of unit distances between the vertices of a convex polygon}}, doi = {10.1016/0097-3165(91)90042-F}, volume = {56}, year = {1991}, } @article{4098, abstract = {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.}, author = {Edelsbrunner, Herbert and Stöckl, Gerd}, issn = {1096-0899}, journal = {Journal of Combinatorial Theory Series A}, number = {2}, pages = {344 -- 349}, publisher = {Elsevier}, title = {{The number of extreme pairs of finite point-sets in Euclidean spaces}}, doi = {10.1016/0097-3165(86)90075-0}, volume = {43}, year = {1986}, } @article{4103, abstract = {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).}, author = {Edelsbrunner, Herbert and Welzl, Emo}, issn = {1096-0899}, journal = {Journal of Combinatorial Theory Series A}, number = {2}, pages = {159 -- 166}, publisher = {Elsevier}, title = {{On the maximal number of edges of many faces in an arrangement}}, doi = {10.1016/0097-3165(86)90078-6}, volume = {41}, year = {1986}, } @article{4113, abstract = {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.}, author = {Edelsbrunner, Herbert and Welzl, Emo}, issn = {1096-0899}, journal = {Journal of Combinatorial Theory Series A}, number = {1}, pages = {15 -- 29}, publisher = {Elsevier}, title = {{On the number of line separations of a finite set in the plane}}, doi = {10.1016/0097-3165(85)90017-2}, volume = {38}, year = {1985}, }