Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userRegarding two conjectures on clique and biclique partitions
106
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
For a graph $G$, let $cp(G)$ denote the minimum number of cliques of $G$ needed to cover the edges of $G$ exactly once. Similarly, let $bp_k(G)$ denote the minimum number of bicliques (i.e. complete bipartite subgraphs of $G$) needed to cover each edge of $G$ exactly $k$ times. We consider two conjectures -- one regarding the maximum possible value of $cp(G) + cp(overline{G})$ (due to de Caen, ErdH{o}s, Pullman and Wormald) and the other regarding $bp_k(K_n)$ (due to de Caen, Gregory and Pritikin). We disprove the first, obtaining improved lower and upper bounds on $max_G cp(G) + cp(overline{G})$, and we prove an asymptotic version of the second, showing that $bp_k(K_n) = (1+o(1))n$.
rate research
Read More
We prove three main conjectures of Berkovich and Uncu (Ann. Comb. 23 (2019) 263--284) on the inequalities between the numbers of partitions of $n$ with bounded gap between largest and smallest parts for sufficiently large $n$. Actually our theorems are stronger than their original conjectures. The analytic version of our results shows that the coefficients of some partition $q$-series are eventually positive.
In this work, we give combinatorial proofs for generating functions of two problems, i.e., flushed partitions and concave compositions of even length. We also give combinatorial interpretation of one problem posed by Sylvester involving flushed partitions and then prove it. For these purposes, we first describe an involution and use it to prove core identities. Using this involution with modifications, we prove several problems of different nature, including Andrews partition identities involving initial repetitions and partition theoretical interpretations of three mock theta functions of third order $f(q)$, $phi(q)$ and $psi(q)$. An identity of Ramanujan is proved combinatorially. Several new identities are also established.
A emph{set partition} of the set $[n]={1,...c,n}$ is a collection of disjoint blocks $B_1,B_2,...c, B_d$ whose union is $[n]$. We choose the ordering of the blocks so that they satisfy $min B_1<min B_2<...b<min B_d$. We represent such a set partition by a emph{canonical sequence} $pi_1,pi_2,...c,pi_n$, with $pi_i=j$ if $iin B_j$. We say that a partition $pi$ emph{contains} a partition $sigma$ if the canonical sequence of $pi$ contains a subsequence that is order-isomorphic to the canonical sequence of $sigma$. Two partitions $sigma$ and $sigma$ are emph{equivalent}, if there is a size-preserving bijection between $sigma$-avoiding and $sigma$-avoiding partitions. We determine several infinite families of sets of equivalent patterns; for instance, we prove that there is a bijection between $k$-noncrossing and $k$-nonnesting partitions, with a notion of crossing and nesting based on the canonical sequence. We also provide new combinatorial interpretations of the Catalan numbers and the Stirling numbers. Using a systematic computer search, we verify that our results characterize all the pairs of equivalent partitions of size at most seven. We also present a correspondence between set partitions and fillings of Ferrers shapes and stack polyominoes. This correspondence allows us to apply recent results on polyomino fillings in the study of partitions, and conversely, some of our results on partitions imply new results on polyomino fillings and ordered graphs.
A systematic study of avoidance of mesh patterns of length 2 was conducted by Hilmarsson et al. in 2015. In a recent paper Kitaev and Zhang examined the distribution of the aforementioned patterns. The aim of this paper is to prove more equidistributions of mesh pattern and confirm Kitaev and Zhangs four conjectures by constructing two involutions on permutations.
The Stern poset $mathcal{S}$ is a graded infinite poset naturally associated to Sterns triangle, which was defined by Stanley analogously to Pascals triangle. Let $P_n$ denote the interval of $mathcal{S}$ from the unique element of row $0$ of Sterns triangle to the $n$-th element of row $r$ for sufficiently large $r$. For $ngeq 1$ let begin{align*} L_n(q)&=2cdotleft(sum_{k=1}^{2^n-1}A_{P_k}(q)right)+A_{P_{2^n}}(q), end{align*} where $A_{P}(q)$ represents the corresponding $P$-Eulerian polynomial. For any $ngeq 1$ Stanley conjectured that $L_n(q)$ has only real zeros and $L_{4n+1}(q)$ is divisible by $L_{2n}(q)$. In this paper we obtain a simple recurrence relation satisfied by $L_n(q)$ and affirmatively solve Stanleys conjectures. We also establish the asymptotic normality of the coefficients of $L_n(q)$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
