Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe Grothendieck to Lascoux conjecture
149
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
This report formulates a conjectural combinatorial rule that positively expands Grothendieck polynomials into Lascoux polynomials. It generalizes one such formula expanding Schubert polynomials into key polynomials, and refines another one expanding stable Grothendieck polynomials.
rate research
Read More
We establish the conjecture of Reiner and Yong for an explicit combinatorial formula for the expansion of a Grothendieck polynomial into the basis of Lascoux polynomials. This expansion is a subtle refinement of its symmetric function version due to Buch, Kresch, Shimozono, Tamvakis, and Yong, which gives the expansion of stable Grothendieck polynomials indexed by permutations into Grassmannian stable Grothendieck polynomials. Our expansion is the K-theoretic analogue of that of a Schubert polynomial into Demazure characters, whose symmetric analogue is the expansion of a Stanley symmetric function into Schur functions. Our expansions extend to flagged Grothendieck polynomials.
For a simple graph $G$, denote by $n$, $Delta(G)$, and $chi(G)$ its order, maximum degree, and chromatic index, respectively. A connected class 2 graph $G$ is edge-chromatic critical if $chi(G-e)<Delta(G)+1$ for every edge $e$ of $G$. Define $G$ to be overfull if $|E(G)|>Delta(G) lfloor n/2 rfloor$. Clearly, overfull graphs are class 2 and any graph obtained from a regular graph of even order by splitting a vertex is overfull. Let $G$ be an $n$-vertex connected regular class 1 graph with $Delta(G) >n/3$. Hilton and Zhao in 1997 conjectured that if $G^*$ is obtained from $G$ by splitting one vertex of $G$ into two vertices, then $G^*$ is edge-chromatic critical, and they verified the conjecture for graphs $G$ with $Delta(G)ge frac{n}{2}(sqrt{7}-1)approx 0.82n$. The graph $G^*$ is easily verified to be overfull, and so the hardness of the conjecture lies in showing that the deletion of every of its edge decreases the chromatic index. Except in 2002, Song showed that the conjecture is true for a special class of graphs $G$ with $Delta(G)ge frac{n}{2}$, no other progress on this conjecture had been made. In this paper, we confirm the conjecture for graphs $G$ with $Delta(G) ge 0.75n$.
Hedetniemi conjectured in 1966 that $chi(G times H) = min{chi(G), chi(H)}$ for all graphs $G$ and $H$. Here $Gtimes H$ is the graph with vertex set $ V(G)times V(H)$ defined by putting $(x,y)$ and $(x,y)$ adjacent if and only if $xxin E(G)$ and $yyin E(H)$. This conjecture received a lot of attention in the past half century. Recently, Shitov refuted this conjecture. Let $p$ be the minimum number of vertices in a graph of odd girth $7$ and fractional chromatic number greater than $3+4/(p-1)$. Shitovs proof shows that Hedetniemis conjecture fails for some graphs with chromatic number about $p^22^{p+1} $ and with about $(p^22^{p+1})^{p^32^{p-1}} $ vertices. In this paper, we show that the conjecture fails already for some graphs $G$ and $H$ with chromatic number $3lceil frac {p+1}2 rceil $ and with $p lceil (p-1)/2 rceil$ and $3 lceil frac {p+1}2 rceil (p+1)-p$ vertices, respectively. The currently known upper bound for $p$ is $148$. Thus Hedetniemis conjecture fails for some graphs $G$ and $H$ with chromatic number $225$, and with $10,952$ and $33,377$ vertices, respectively.
In 1990, Cvetkovi{c} and Rowlinson [The largest eigenvalue of a graph: a survey, Linear Multilinear Algebra 28(1-2) (1990), 3--33] conjectured that among all outerplanar graphs on $n$ vertices, $K_1vee P_{n-1}$ attains the maximum spectral radius. In 2017, Tait and Tobin [Three conjectures in extremal spectral graph theory, J. Combin. Theory, Ser. B 126 (2017) 137-161] confirmed the conjecture for sufficiently large values of $n$. In this article, we show the conjecture is true for all $ngeq2$ except for $n=6$.
The conjecture, still widely open, posed by Marco Buratti, Peter Horak and Alex Rosa states that a list $L$ of $v-1$ positive integers not exceeding $leftlfloor frac{v}{2}rightrfloor$ is the list of edge-lengths of a suitable Hamiltonian path of the complete graph with vertex-set ${0,1,ldots,v-1}$ if and only if, for every divisor $d$ of $v$, the number of multiples of $d$ appearing in $L$ is at most $v-d$. In this paper we present new methods that are based on linear realizations and can be applied to prove the validity of this conjecture for a vast choice of lists. As example of their flexibility, we consider lists whose underlying set is one of the following: ${x,y,x+y}$, ${1,2,3,4}$, ${1,2,4,ldots,2x}$, ${1,2,4,ldots,2x,2x+1}$. We also consider lists with many consecutive elements.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
