Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userForbidding rank-preserving copies of a poset
104
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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}$.
rate research
Read More
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 number 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 by 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 partitions 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.
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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
