Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userDimension of posets with planar cover graphs excluding two long incomparable chains
76
0
0.0
(
0
)
Added by
Bartosz Walczak
Publication date
2016
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
We study covering numbers and local covering numbers with respect to difference graphs and complete bipartite graphs. In particular we show that in every cover of a Young diagram with $binom{2k}{k}$ steps with generalized rectangles there is a row or a column in the diagram that is used by at least $k+1$ rectangles, and prove that this is best-possible. This answers two questions by Kim, Martin, Masa{v{r}}{i}k, Shull, Smith, Uzzell, and Wang (Europ. J. Comb. 2020), namely: - What is the local complete bipartite cover number of a difference graph? - Is there a sequence of graphs with constant local difference graph cover number and unbounded local complete bipartite cover number? We add to the study of these local covering numbers with a lower bound construction and some examples. Following Kim emph{et al.}, we use the results on local covering numbers to provide lower and upper bounds for the local dimension of partially ordered sets of height~2. We discuss the local dimension of some posets related to Boolean lattices and show that the poset induced by the first two layers of the Boolean lattice has local dimension $(1 + o(1))log_2log_2 n$. We conclude with some remarks on covering numbers for digraphs and Ferrers dimension.
We discuss a possible characterization, by means of forbidden configurations, of posets which are embeddable in a product of finitely many scattered chains.
A cornerstone theorem in the Graph Minors series of Robertson and Seymour is the result that every graph $G$ with no minor isomorphic to a fixed graph $H$ has a certain structure. The structure can then be exploited to deduce far-reaching consequences. The exact statement requires some explanation, but roughly it says that there exist integers $k,n$ depending on $H$ only such that $0<k<n$ and for every $ntimes n$ grid minor $J$ of $G$ the graph $G$ has a a $k$-near embedding in a surface $Sigma$ that does not embed $H$ in such a way that a substantial part of $J$ is embedded in $Sigma$. Here a $k$-near embedding means that after deleting at most $k$ vertices the graph can be drawn in $Sigma$ without crossings, except for local areas of non-planarity, where crossings are permitted, but at most $k$ of these areas are attached to the rest of the graph by four or more vertices and inside those the graph is constrained in a different way, again depending on the parameter $k$. The original and only proof so far is quite long and uses many results developed in the Graph Minors series. We give a proof that uses only our earlier paper [A new proof of the flat wall theorem, {it J.~Combin. Theory Ser. B bf 129} (2018), 158--203] and results from graduate textbooks. Our proof is constructive and yields a polynomial time algorithm to construct such a structure. We also give explicit constants for the structure theorem, whereas the original proof only guarantees the existence of such constants.
Let $mathscr{G}$ be the class of plane graphs without triangles normally adjacent to $8^{-}$-cycles, without $4$-cycles normally adjacent to $6^{-}$-cycles, and without normally adjacent $5$-cycles. In this paper, it is showed that every graph in $mathscr{G}$ is $3$-choosable. Instead of proving this result, we directly prove a stronger result in the form of weakly DP-$3$-coloring. The main theorem improves the results in [J. Combin. Theory Ser. B 129 (2018) 38--54; European J. Combin. 82 (2019) 102995]. Consequently, every planar graph without $4$-, $6$-, $8$-cycles is $3$-choosable, and every planar graph without $4$-, $5$-, $7$-, $8$-cycles is $3$-choosable. In the third section, it is proved that the vertex set of every graph in $mathscr{G}$ can be partitioned into an independent set and a set that induces a forest, which strengthens the result in [Discrete Appl. Math. 284 (2020) 626--630]. In the final section, tightness is considered.
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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
