Source author record

Eleni Tzanaki

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Computational Geometry math.NT

Catalog footprint

Research overview

10works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2021arXiv

Symmetric decompositions, triangulations and real-rootedness

Polynomials which afford nonnegative, real-rooted symmetric decompositions have been investigated recently in algebraic, enumerative and geometric combinatorics. Brändén and Solus have given sufficient conditions under which the image of a polynomial under a certain operator associated to barycentric subdivision has such a decomposition. This paper gives a new proof of their result which generalizes to subdivision operators in the setting of uniform triangulations of simplicial complexes, introduced by the first named author. Sufficient conditions under which these decompositions are also interlacing are described. Applications yield new classes of polynomials in geometric combinatorics which afford nonnegative, real-rooted symmetric decompositions. Some interesting questions in $f$ -vector theory arise from this work.

preprint2016arXiv

Bijections between generalized Catalan families of types A and C

Motivated by the relation holding for the m-generalized Catalan numbers of type A and C, the connection between dominant regions of the m-Shi arrangement of type A and C is investigated. In the same line of thought, a bijection between mn+1 copies of each m-Dyck path of height n and the set of NE lattice paths inside an n times mn rectangle is provided.

preprint2016arXiv

On the multiplicative order of the roots of $bX^{q^r+1}-aX^{q^r}+dX-c$

In this paper, we find a lower bound for the order of the group $\langle θ+α\rangle \subset \overline{\mathbb F_{q}}^*$ , where $α\in \mathbb F_{q}$ , $θ$ is a generic root of the polynomial $F_{A,r}(X)=bX^{q^r+1}-aX^{q^r}+dX-c\in \mathbb F_{q}[X]$ and $ad-bc\ne0$ .

preprint2015arXiv

A geometric approach for the upper bound theorem for Minkowski sums of convex polytopes

We derive tight expressions for the maximum number of $k$ -faces, $0\le{}k\le{}d-1$ , of the Minkowski sum, $P_1+...+P_r$ , of $r$ convex $d$ -polytopes $P_1,...,P_r$ in $\mathbb{R}^d$ , where $d\ge{}2$ and $r<d$ , as a (recursively defined) function on the number of vertices of the polytopes. Our results coincide with those recently proved by Adiprasito and Sanyal [2]. In contrast to Adiprasito and Sanyal's approach, which uses tools from Combinatorial Commutative Algebra, our approach is purely geometric and uses basic notions such as $f$ - and $h$ -vector calculus and shellings, and generalizes the methodology used in [15] and [14] for proving upper bounds on the $f$ -vector of the Minkowski sum of two and three convex polytopes, respectively. The key idea behind our approach is to express the Minkowski sum $P_1+...+P_r$ as a section of the Cayley polytope $\mathcal{C}$ of the summands; bounding the $k$ -faces of $P_1+...+P_r$ reduces to bounding the subset of the $(k+r-1)$ -faces of $\mathcal{C}$ that contain vertices from each of the $r$ polytopes. We end our paper with a sketch of an explicit construction that establishes the tightness of the upper bounds.

preprint2013arXiv

Facets of the $m$ -generalized cluster complex and regions in the $m$ -extended Catalan arrangement of type $A_n$

In this paper we present a bijection $ω_n$ between two well known families of Catalan objects: the set of facets of the $m$ -generalized cluster complex $Δ^m(A_n)$ and the set of dominant regions in the $m$ -Catalan arrangement ${\rm Cat}^m(A_n)$ , where $m\in\mathbb{N}_{>0}$ . In particular, $ω_n$ bijects the facets containing the negative simple root $-α$ to dominant regions having the hyperplane $\{v\in V\mid<v,α>=m\}$ as separating wall. As a result, $ω_n$ restricts to a bijection between the set of facets of the positive part of $Δ^m(A_n)$ and the set of bounded dominant regions in ${\rm Cat}^m(A_n)$ . The map $ω_n$ is a composition of two bijections in which integer partitions in an $m$ -staircase shape come into play.

preprint2012arXiv

Counting Shi regions with a fixed separating wall

Athanasiadis introduced separating walls for a region in the extended Shi arrangement and used them to generalize the Narayana numbers. In this paper, we fix a hyperplane in the extended Shi arrangement for type A and calculate the number of dominant regions which have the fixed hyperplane as a separating wall; that is, regions where the hyperplane supports a facet of the region and separates the region from the origin.

preprint2012arXiv

The maximum number of faces of the Minkowski sum of three convex polytopes

We derive tight expressions for the maximum number of $k$ -faces, $0\le k\le d-1$ , of the Minkowski sum, $P_1+P_2+P_3$ , of three $d$ -dimensional convex polytopes $P_1$ , $P_2$ and $P_3$ , as a function of the number of vertices of the polytopes, for any $d\ge 2$ . Expressing the Minkowski sum of the three polytopes as a section of their Cayley polytope $\mathcal{C}$ , the problem of counting the number of $k$ -faces of $P_1+P_2+P_3$ , reduces to counting the number of $(k+2)$ -faces of the subset of $\mathcal{C}$ comprising of the faces that contain at least one vertex from each $P_i$ . In two dimensions our expressions reduce to known results, while in three dimensions, the tightness of our bounds follows by exploiting known tight bounds for the number of faces of $r$ $d$ -polytopes, where $r\ge d$ . For $d\ge 4$ , the maximum values are attained when $P_1$ , $P_2$ and $P_3$ are $d$ -polytopes, whose vertex sets are chosen appropriately from three distinct $d$ -dimensional moment-like curves.

preprint2011arXiv

Convex hulls of spheres and convex hulls of convex polytopes lying on parallel hyperplanes

Given a set $Σ$ of spheres in $\mathbb{E}^d$ , with $d\ge{}3$ and $d$ odd, having a fixed number of $m$ distinct radii $ρ_1,ρ_2,...,ρ_m$ , we show that the worst-case combinatorial complexity of the convex hull $CH_d(Σ)$ of $Σ$ is $Θ(\sum_{1\le{}i\ne{}j\le{}m}n_in_j^{\lfloor\frac{d}{2}\rfloor})$ , where $n_i$ is the number of spheres in $Σ$ with radius $ρ_i$ . To prove the lower bound, we construct a set of $Θ(n_1+n_2)$ spheres in $\mathbb{E}^d$ , with $d\ge{}3$ odd, where $n_i$ spheres have radius $ρ_i$ , $i=1,2$ , and $ρ_2\neρ_1$ , such that their convex hull has combinatorial complexity $Ω(n_1n_2^{\lfloor\frac{d}{2}\rfloor}+n_2n_1^{\lfloor\frac{d}{2}\rfloor})$ . Our construction is then generalized to the case where the spheres have $m\ge{}3$ distinct radii. For the upper bound, we reduce the sphere convex hull problem to the problem of computing the worst-case combinatorial complexity of the convex hull of a set of $m$ $d$ -dimensional convex polytopes lying on $m$ parallel hyperplanes in $\mathbb{E}^{d+1}$ , where $d\ge{}3$ odd, a problem which is of independent interest. More precisely, we show that the worst-case combinatorial complexity of the convex hull of a set $\{\mathcal{P}_1,\mathcal{P}_2,...,\mathcal{P}_m\}$ of $m$ $d$ -dimensional convex polytopes lying on $m$ parallel hyperplanes of $\mathbb{E}^{d+1}$ is $O(\sum_{1\le{}i\ne{}j\le{}m}n_in_j^{\lfloor\frac{d}{2}\rfloor})$ , where $n_i$ is the number of vertices of $\mathcal{P}_i$ . We end with algorithmic considerations, and we show how our tight bounds for the parallel polytope convex hull problem, yield tight bounds on the combinatorial complexity of the Minkowski sum of two convex polytopes in $\mathbb{E}^d$ .

preprint2011arXiv

The maximum number of faces of the Minkowski sum of two convex polytopes

We derive tight expressions for the maximum number of $k$ -faces, $0\le{}k\le{}d-1$ , of the Minkowski sum, $P_1\oplus{}P_2$ , of two $d$ -dimensional convex polytopes $P_1$ and $P_2$ , as a function of the number of vertices of the polytopes. For even dimensions $d\ge{}2$ , the maximum values are attained when $P_1$ and $P_2$ are cyclic $d$ -polytopes with disjoint vertex sets. For odd dimensions $d\ge{}3$ , the maximum values are attained when $P_1$ and $P_2$ are $\lfloor\frac{d}{2}\rfloor$ -neighborly $d$ -polytopes, whose vertex sets are chosen appropriately from two distinct $d$ -dimensional moment-like curves.

preprint2011arXiv

Tight lower bounds on the number of faces of the Minkowski sum of convex polytopes via the Cayley trick

Consider a set of $r$ convex $d$ -polytopes $P_1,P_2,...,P_r$ , where $d\ge{}3$ and $r\ge{}2$ , and let $n_i$ be the number of vertices of $P_i$ , $1\le{}i\le{}r$ . It has been shown by Fukuda and Weibel that the number of $k$ -faces of the Minkowski sum, $P_1+P_2+...+P_r$ , is bounded from above by $Φ_{k+r}(n_1,n_2,...,n_r)$ , where $Φ_{\ell}(n_1,n_2,...,n_r)= \sum_{\substack{1\le{}s_i\le{}n_i s_1+...+s_r=\ell}} \prod_{i=1}^r\binom{n_i}{s_i}$ , $\ell\ge{}r$ . Fukuda and Weibel have also shown that the upper bound mentioned above is tight for $d\ge{}4$ , $2\le{}r\le{}\lfloor\frac{d}{2}\rfloor$ , and for all $0\le{}k\le{}\lfloor\frac{d}{2}\rfloor-r$ . In this paper we construct a set of $r$ neighborly $d$ -polytopes $P_1,P_2,...,P_r$ , where $d\ge{}3$ and $2\le{}r\le{}d-1$ , for which the upper bound of Fukuda and Weibel is attained for all $0\le{}k\le{}\lfloor\frac{d+r-1}{2}\rfloor-r$ . Our approach is based on what is known as the Cayley trick for Minkowski sums. A direct consequence of our result is a tight asymptotic bound on the complexity of the Minkowski sum $P_1+P_2+...+P_r$ , for any fixed dimension $d$ and any $2\le{}r\le{}d-1$ , when the number of vertices of the polytopes is (asymptotically) the same.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Eleni Tzanaki

Research overview

Is this your work?

10 publications

Symmetric decompositions, triangulations and real-rootedness

Bijections between generalized Catalan families of types A and C

On the multiplicative order of the roots of $bX^{q^r+1}-aX^{q^r}+dX-c$

A geometric approach for the upper bound theorem for Minkowski sums of convex polytopes

Facets of the $m$ -generalized cluster complex and regions in the $m$ -extended Catalan arrangement of type $A_n$

Counting Shi regions with a fixed separating wall

The maximum number of faces of the Minkowski sum of three convex polytopes

Convex hulls of spheres and convex hulls of convex polytopes lying on parallel hyperplanes

The maximum number of faces of the Minkowski sum of two convex polytopes

Tight lower bounds on the number of faces of the Minkowski sum of convex polytopes via the Cayley trick

See the researcher in context

Building this map preview

Eleni Tzanaki

Research overview

Is this your work?

10 publications

Symmetric decompositions, triangulations and real-rootedness

Bijections between generalized Catalan families of types A and C

On the multiplicative order of the roots of bXqr+1−aXqr+dX−cbX^{q^r+1}-aX^{q^r}+dX-cbXqr+1−aXqr+dX−c

A geometric approach for the upper bound theorem for Minkowski sums of convex polytopes

Facets of the mmm-generalized cluster complex and regions in the mmm-extended Catalan arrangement of type AnA_nAn​

Counting Shi regions with a fixed separating wall

The maximum number of faces of the Minkowski sum of three convex polytopes

Convex hulls of spheres and convex hulls of convex polytopes lying on parallel hyperplanes

The maximum number of faces of the Minkowski sum of two convex polytopes

Tight lower bounds on the number of faces of the Minkowski sum of convex polytopes via the Cayley trick

See the researcher in context

Building this map preview

On the multiplicative order of the roots of $bX^{q^r+1}-aX^{q^r}+dX-c$

Facets of the $m$ -generalized cluster complex and regions in the $m$ -extended Catalan arrangement of type $A_n$