Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userIndependent Chains in Acyclic Posets
159
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We consider the problem of determining the maximum order of an induced vertex-disjoint union of cliques in a graph. More specifically, given some family of graphs $mathcal{G}$ of equal order, we are interested in the parameter $a(mathcal{G}) = min_{G in mathcal{G}} max { |U| : U subseteq V, G[U] text{ is a vertex-disjoint union of cliques} }$. We determine the value of this parameter precisely when $mathcal{G}$ is the family of comparability graphs of $n$-element posets with acyclic cover graph. In particular, we show that $a(mathcal{G}) = (n+o(n))/log_2 (n)$ in this class.
rate research
Read More
It has been known for more than 40 years that there are posets with planar cover graphs and arbitrarily large dimension. Recently, Streib and Trotter proved that such posets must have large height. In fact, all known constructions of such posets have two large disjoint chains with all points in one chain incomparable with all points in the other. Gutowski and Krawczyk conjectured that this feature is necessary. More formally, they conjectured that for every $kgeq 1$, there is a constant $d$ such that if $P$ is a poset with a planar cover graph and $P$ excludes $mathbf{k}+mathbf{k}$, then $dim(P)leq d$. We settle their conjecture in the affirmative. We also discuss possibilities of generalizing the result by relaxing the condition that the cover graph is planar.
Motivated by generalizing Khovanovs categorification of the Jones polynomial, we study functors $F$ from thin posets $P$ to abelian categories $mathcal{A}$. Such functors $F$ produce cohomology theories $H^*(P,mathcal{A},F)$. We find that CW posets, that is, face posets of regular CW complexes, satisfy conditions making them particularly suitable for the construction of such cohomology theories. We consider a category of tuples $(P,mathcal{A},F,c)$, where $c$ is a certain ${1,-1}$-coloring of the cover relations in $P$, and show the cohomology arising from a tuple $(P,mathcal{A},F,c)$ is functorial, and independent of the coloring $c$ up to natural isomorphism. Such a construction provides a framework for the categorification of a variety of familiar topological/combinatorial invariants: anything expressible as a rank-alternating sum over a thin poset.
Let $cX$ be a family of subsets of a finite set $E$. A matroid on $E$ is called an $cX$-matroid if each set in $cX$ is a circuit. We consider the problem of determining when there exists a unique maximal $cX$-matroid in the weak order poset of all $cX$-matroids on $E$, and characterizing its rank function when it exists.
For any graded poset $P$, we define a new graded poset, $mathcal E(P)$, whose elements are the edges in the Hasse diagram of P. For any group, $G$, acting on the boolean algebra, $B_n$, we conjecture that $mathcal E(B_n/G)$ is Peck. We prove that the conjecture holds for common cover transitive actions. We give some infinite families of common cover transitive actions and show that the common cover transitive actions are closed under direct and semidirect products.
We consider 3 (weighted) posets associated with a graph G - the poset P(G) of distinct induced unlabelled subgraphs, the lattice Omega(G) of distinct unlabelled graphs induced by connected partitions, and the poset Q(G) of distinct unlabelled edge-subgraphs. We study these posets given up to isomorphism, and their relation to the reconstruction conjectures. We show that when G is not a star or a disjoint union of edges, P(G) and Omega(G) can be constructed from each other. The result implies that trees are reconstructible from their abstract bond lattice. We present many results on the reconstruction questions about the chromatic symmetric function and the symmetric Tutte polynomial. In particular, we show that the symmetric Tutte polynomial of a tree can be constructed from its chromatic symmetric function. We classify graphs that are not reconstructible from their abstract edge-subgraph posets, and further show that the families presented here are the only graphs not Q-reconstructible if and only if the edge reconstruction conjecture is true. Let f be a bijection from the set of all unlabelled graphs to itself such that for all unlabelled graphs G and H, hom(G,H) = hom(f(G), f(H)). We conjecture that f is an identity map. We show that this conjecture is weaker than the edge reconstruction conjecture. Our conjecture is motivated by homomorphism cancellation results due to Lovasz.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
