Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe Core Conjecture of Hilton and Zhao I: Pseudo-multifan and Lollipop
97
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
A simple graph $G$ with maximum degree $Delta$ is overfull if $|E(G)|>Delta lfloor |V(G)|/2rfloor$. The core of $G$, denoted $G_{Delta}$, is the subgraph of $G$ induced by its vertices of degree $Delta$. Clearly, the chromatic index of $G$ equals $Delta+1$ if $G$ is overfull. Conversely, Hilton and Zhao in 1996 conjectured that if $G$ is a simple connected graph with $Deltage 3$ and $Delta(G_Delta)le 2$, then $chi(G)=Delta+1$ implies that $G$ is overfull or $G=P^*$, where $P^*$ is obtained from the Petersen graph by deleting a vertex (Core Conjecture). The goal of this paper is to develop the concepts of pseudo-multifan and lollipop and study their properties in an edge colored graph. These concepts and properties are of independent interests, and will be particularly used to prove the Core Conjecture in a subsequent paper.
rate research
Read More
Let $G$ be a simple graph with maximum degree $Delta$. We call $G$ emph{overfull} if $|E(G)|>Delta lfloor |V(G)|/2rfloor$. The emph{core} of $G$, denoted $G_{Delta}$, is the subgraph of $G$ induced by its vertices of degree $Delta$. A classic result of Vizing shows that $chi(G)$, the chromatic index of $G$, is either $Delta$ or $Delta+1$. It is NP-complete to determine the chromatic index for a general graph. However, if $G$ is overfull then $chi(G)=Delta+1$. Hilton and Zhao in 1996 conjectured that if $G$ is a simple connected graph with $Deltage 3$ and $Delta(G_Delta)le 2$, then $chi(G)=Delta+1$ if and only if $G$ is overfull or $G=P^*$, where $P^*$ is obtained from the Petersen graph by deleting a vertex. This conjecture, if true, implies an easy approach for calculating $chi(G)$ for graphs $G$ satisfying the conditions. The progress on the conjecture has been slow: it was only confirmed for $Delta=3,4$, respectively, in 2003 and 2017. In this paper, we confirm this conjecture for all $Deltage 4$.
A simple graph $G$ with maximum degree $Delta$ is overfull if $|E(G)|>Delta lfloor |V(G)|/2rfloor$. The core of $G$, denoted $G_{Delta}$, is the subgraph of $G$ induced by its vertices of degree $Delta$. Clearly, the chromatic index of $G$ equals $Delta+1$ if $G$ is overfull. Conversely, Hilton and Zhao in 1996 conjectured that if $G$ is a simple connected graph with $Deltage 3$ and $Delta(G_Delta)le 2$, then $chi(G)=Delta+1$ implies that $G$ is overfull or $G=P^*$, where $P^*$ is obtained from the Petersen graph by deleting a vertex. Cariolaro and Cariolaro settled the base case $Delta=3$ in 2003, and Cranston and Rabern proved the next case $Delta=4$ in 2019. In this paper, we give a proof of this conjecture for all $Deltage 4$.
Babson and Steingr{i}msson introduced generalized permutation patterns and showed that most of the Mahonian statistics in the literature can be expressed by the combination of generalized pattern functions. Particularly, they defined a new Mahonian statistic in terms of generalized pattern functions, which is denoted $stat$. Given a permutation $pi$, let $des(pi)$ denote the descent number of $pi$ and $maj(pi)$ denote the major index of $pi$. Babson and Steingr{i}msson conjectured that $(des,stat)$ and $(des,maj)$ are equidistributed on $S_n$. Foata and Zeilberger settled this conjecture using q-enumeration, generating functions and Maple packages ROTA and PERCY. Later, Burstein provided a bijective proof of a refinement of this conjecture. In this paper, we give a new bijective proof of this conjecture.
Let $m$, $n$, and $k$ be integers satisfying $0 < k leq n < 2k leq m$. A family of sets $mathcal{F}$ is called an $(m,n,k)$-intersecting family if $binom{[n]}{k} subseteq mathcal{F} subseteq binom{[m]}{k}$ and any pair of members of $mathcal{F}$ have nonempty intersection. Maximum $(m,k,k)$- and $(m,k+1,k)$-intersecting families are determined by the theorems of ErdH{o}s-Ko-Rado and Hilton-Milner, respectively. We determine the maximum families for the cases $n = 2k-1, 2k-2, 2k-3$, and $m$ sufficiently large.
A conjecture of Graver from 1991 states that the generic $3$-dimensional rigidity matroid is the unique maximal abstract $3$-rigidity matroid with respect to the weak order on matroids. Based on a close similarity between the generic $d$-dimensional rigidity matroid and the generic $C_{d-2}^{d-1}$-cofactor matroid from approximation theory, Whiteley made an analogous conjecture in 1996 that the generic $C_{d-2}^{d-1}$-cofactor matroid is the unique maximal abstract $d$-rigidity matroid for all $dgeq 2$. We verify the case $d=3$ of Whiteleys conjecture in this paper. A key step in our proof is to verify a second conjecture of Whiteley that the `double V-replacement operation preserves independence in the generic $C_2^1$-cofactor matroid.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
