Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userFlag vectors of Eulerian partially ordered sets
109
0
0.0
(
0
)
Authors
Margaret M. Bayer
Ask ChatGPT about the research
No Arabic abstract
The closed cone of flag vectors of Eulerian partially ordered sets is studied. It is completely determined up through rank seven. Half-Eulerian posets are defined. Certain limit posets of Billera and Hetyei are half-Eulerian; they give rise to extreme rays of the cone for Eulerian posets. A new family of linear inequalities valid for flag vectors of Eulerian posets is given.
rate research
Read More
For a (finite) partially ordered set (poset) $P$, we call a dominating set $D$ in the comparability graph of $P$, an order-sensitive dominating set in $P$ if either $xin D$ or else $a<x<b$ in $P$ for some $a,bin D$ for every element $x$ in $P$ which is neither maximal nor minimal, and denote by $gamma_{os}(P)$, the least size of an order-sensitive dominating set of $P$. For every graph $G$ and integer $kgeq 2$, we associate a graded poset $mathscr{P}_k(G)$ of height $k$, and prove that $gamma_{os}(mathscr{P}_3(G))=gamma_{text{R}}(G)$ and $gamma_{os}(mathscr{P}_4(G))=2gamma(G)$ hold, where $gamma(G)$ and $gamma_{text{R}}(G)$ are the domination and Roman domination number of $G$, respectively. Apart from these, we introduce the notion of a Helly poset, and prove that when $P$ is a Helly poset, the computation of order-sensitive domination number of $P$ can be interpreted as a weighted clique partition number of a graph, the middle graph of $P$. Moreover, we show that the order-sensitive domination number of a poset $P$ exactly corresponds to the biclique vertex-partition number of the associated bipartite transformation of $P$. Finally, we prove that the decision problem of order-sensitive domination on posets of arbitrary height is NP-complete, which is obtained by using a reduction from EQUAL-$3$-SAT problem.
We investigate the $alpha$-colored Eulerian polynomials and a notion of descents introduced in a recent paper of Hedmark and show that such polynomials can be computed as a polynomial encoding descents computed over a quotient of the wreath product $mathbb{Z}_alphawrmathfrak{S}_n$. Moreover, we consider the flag descent statistic computed over this same quotient and find that the flag Eulerian polynomial remains palindromic. We prove that the flag descent polynomial is palindromic over this same quotient by giving a combinatorial proof that the flag descent statistic is symmetrically distributed over the collection of colored permutations with fixed last color by way of a new combinatorial tool, the colored winding number of a colored permutation. We conclude with some conjectures, observations, and open questions.
Interior and exterior angle vectors of polytopes capture curvature information at faces of all dimensions and can be seen as metric variants of $f$-vectors. In this context, Grams relation takes the place of the Euler-Poincare relation as the unique linear relation among interior angles. We show the existence and uniqueness of Euler-Poincare-type relations for generalized angle vectors by building a bridge to the algebraic combinatorics of geometric lattices, generalizing work of Klivans-Swartz. We introduce flag-angles of polytopes as a geometric counterpart to flag-$f$-vectors. Flag-angles generalize the angle deficiencies of Descartes-Shephard, Grassmann angles, and spherical intrinsic volumes. Using the machinery of incidence algebras, we relate flag-angles of zonotopes to flag-$f$-vectors of graded posets. This allows us to determine the linear relations satisfied by interior/exterior flag-angle vectors.
We present some enumerative and structural results for flag homology spheres. For a flag homology sphere $Delta$, we show that its $gamma$-vector $gamma^Delta=(1,gamma_1,gamma_2,ldots)$ satisfies: begin{align*} gamma_j=0,text{ for all } j>gamma_1, quad gamma_2leqbinom{gamma_1}{2}, quad gamma_{gamma_1}in{0,1}, quad text{ and }gamma_{gamma_1-1}in{0,1,2,gamma_1}, end{align*} supporting a conjecture of Nevo and Petersen. Further we characterize the possible structures for $Delta$ in extremal cases. As an application, the techniques used produce infinitely many $f$-vectors of flag balanced simplicial complexes that are not $gamma$-vectors of flag homology spheres (of any dimension); these are the first examples of this kind. In addition, we prove a flag analog of Perles 1970 theorem on $k$-skeleta of polytopes with few vertices, specifically: the number of combinatorial types of $k$-skeleta of flag homology spheres with $gamma_1leq b$, of any given dimension, is bounded independently of the dimension.
Unsupervised learning of visual similarities is of paramount importance to computer vision, particularly due to lacking training data for fine-grained similarities. Deep learning of similarities is often based on relationships between pairs or triplets of samples. Many of these relations are unreliable and mutually contradicting, implying inconsistencies when trained without supervision information that relates different tuples or triplets to each other. To overcome this problem, we use local estimates of reliable (dis-)similarities to initially group samples into compact surrogate classes and use local partial orders of samples to classes to link classes to each other. Similarity learning is then formulated as a partial ordering task with soft correspondences of all samples to classes. Adopting a strategy of self-supervision, a CNN is trained to optimally represent samples in a mutually consistent manner while updating the classes. The similarity learning and grouping procedure are integrated in a single model and optimized jointly. The proposed unsupervised approach shows competitive performance on detailed pose estimation and object classification.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
