ترغب بنشر مسار تعليمي؟ اضغط هنا

Forbidding rank-preserving copies of a poset

104   0   0.0 ( 0 )
 نشر من قبل Balazs Patkos
 تاريخ النشر 2017
  مجال البحث
والبحث باللغة English




اسأل ChatGPT حول البحث

The maximum size, $La(n,P)$, of a family of subsets of $[n]={1,2,...,n}$ without containing a copy of $P$ as a subposet, has been intensively studied. Let $P$ be a graded poset. We say that a family $mathcal{F}$ of subsets of $[n]={1,2,...,n}$ contains a emph{rank-preserving} copy of $P$ if it contains a copy of $P$ such that elements of $P$ having the same rank are mapped to sets of same size in $mathcal{F}$. The largest size of a family of subsets of $[n]={1,2,...,n}$ without containing a rank-preserving copy of $P$ as a subposet is denoted by $La_{rp}(n,P)$. Clearly, $La(n,P) le La_{rp}(n,P)$ holds. In this paper we prove asymptotically optimal upper bounds on $La_{rp}(n,P)$ for tree posets of height $2$ and monotone tree posets of height $3$, strengthening a result of Bukh in these cases. We also obtain the exact value of $La_{rp}(n,{Y_{h,s},Y_{h,s}})$ and $La(n,{Y_{h,s},Y_{h,s}})$, where $Y_{h,s}$ denotes the poset on $h+s$ elements $x_1,dots,x_h,y_1,dots,y_s$ with $x_1<dots<x_h<y_1,dots,y_s$ and $Y_{h,s}$ denotes the dual poset of $Y_{h,s}$.

قيم البحث

اقرأ أيضاً

Let $B_n$ be the poset generated by the subsets of $[n]$ with the inclusion as relation and let $P$ be a finite poset. We want to embed $P$ into $B_n$ as many times as possible such that the subsets in different copies are incomparable. The maximum n umber of such embeddings is asymptotically determined for all finite posets $P$ as $frac{{n choose lfloor n/2rfloor}}{M(P)}$, where $M(P)$ denotes the minimal size of the convex hull of a copy of $P$. We discuss both weak and strong (induced) embeddings.
Let $mathrm{G}$ be a subgroup of the symmetric group $mathfrak S(U)$ of all permutations of a countable set $U$. Let $overline{mathrm{G}}$ be the topological closure of $mathrm{G}$ in the function topology on $U^U$. We initiate the study of the poset $overline{mathrm{G}}[U]:={f[U]mid fin overline{mathrm{G}}}$ of images of the functions in $overline{mathrm{G}}$, being ordered under inclusion. This set $overline{mathrm{G}}[U]$ of subsets of the set $U$ will be called the emph{poset of copies for} the group $mathrm{G}$. A denomination being justified by the fact that for every subgroup $mathrm{G}$ of the symmetric group $mathfrak S(U)$ there exists a homogeneous relational structure $R$ on $U$ such that $overline G$ is the set of embeddings of the homogeneous structure $R$ into itself and $overline{mathrm{G}}[U]$ is the set of copies of $R$ in $R$ and that the set of bijections $overline Gcap mathfrak S(U)$ of $U$ to $U$ forms the group of automorphisms of $mathrm{R}$.
The abstract induced subgraph poset of a graph is the isomorphism class of the induced subgraph poset of the graph, suitably weighted by subgraph counting numbers. The abstract bond lattice and the abstract edge-subgraph poset are defined similarly b y considering the lattice of subgraphs induced by connected partitions and the poset of edge-subgraphs, respectively. Continuing our development of graph reconstruction theory on these structures, we show that if a graph has no isolated vertices, then its abstract bond lattice and the abstract induced subgraph poset can be constructed from the abstract edge-subgraph poset except for the families of graphs that we characterise. The construction of the abstract induced subgraph poset from the abstract edge-subgraph poset generalises a well known result in reconstruction theory that states that the vertex deck of a graph with at least 4 edges and without isolated vertices can be constructed from its edge deck.12
The partition lattice and noncrossing partition lattice are well studied objects in combinatorics. Given a graph $G$ on vertex set ${1,2,dots, n}$, its bond lattice, $L_G$, is the subposet of the partition lattice formed by restricting to the partiti ons whose blocks induce connected subgraphs of $G$. In this article, we introduce a natural noncrossing analogue of the bond lattice, the noncrossing bond poset, $NC_G$, obtained by restricting to the noncrossing partitions of $L_G$. Both the noncrossing partition lattice and the bond lattice have many nice combinatorial properties. We show that, for several families of graphs, the noncrossing bond poset also exhibits these properties. We present simple necessary and sufficient conditions on the graph to ensure the noncrossing bond poset is a lattice. Additionally, for several families of graphs, we give combinatorial descriptions of the Mobius function and characteristic polynomial of the noncrossing bond poset. These descriptions are in terms of a noncrossing analogue of non-broken circuit (NBC) sets of the graphs and can be thought of as a noncrossing version of Whitneys NBC theorem for the chromatic polynomial. We also consider the shellability and supersolvability of the noncrossing bond poset, providing sufficient conditions for both. We end with some open problems.
85 - John Lenz , Dhruv Mubayi 2012
Chung and Graham began the systematic study of k-uniform hypergraph quasirandom properties soon after the foundational results of Thomason and Chung-Graham-Wilson on quasirandom graphs. One feature that became apparent in the early work on k-uniform hypergraph quasirandomness is that properties that are equivalent for graphs are not equivalent for hypergraphs, and thus hypergraphs enjoy a variety of inequivalent quasirandom properties. In the past two decades, there has been an intensive study of these disparate notions of quasirandomness for hypergraphs, and an open problem that has emerged is to determine the relationship between them. Our main result is to determine the poset of implications between these quasirandom properties. This answers a recent question of Chung and continues a project begun by Chung and Graham in their first paper on hypergraph quasirandomness in the early 1990s.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا