Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userProof of Komloss conjecture on Hamiltonian subsets
97
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Komlos conjectured in 1981 that among all graphs with minimum degree at least $d$, the complete graph $K_{d+1}$ minimises the number of Hamiltonian subsets, where a subset of vertices is Hamiltonian if it contains a spanning cycle. We prove this conjecture when $d$ is sufficiently large. In fact we prove a stronger result: for large $d$, any graph $G$ with average degree at least $d$ contains almost twice as many Hamiltonian subsets as $K_{d+1}$, unless $G$ is isomorphic to $K_{d+1}$ or a certain other graph which we specify.
rate research
Read More
A typical decomposition question asks whether the edges of some graph $G$ can be partitioned into disjoint copies of another graph $H$. One of the oldest and best known conjectures in this area, posed by Ringel in 1963, concerns the decomposition of complete graphs into edge-disjoint copies of a tree. It says that any tree with $n$ edges packs $2n+1$ times into the complete graph $K_{2n+1}$. In this paper, we prove this conjecture for large $n$.
We prove a conjecture of Ohba which says that every graph $G$ on at most $2chi(G)+1$ vertices satisfies $chi_ell(G)=chi(G)$.
Given a multigraph $G=(V,E)$, the {em edge-coloring problem} (ECP) is to color the edges of $G$ with the minimum number of colors so that no two adjacent edges have the same color. This problem can be naturally formulated as an integer program, and its linear programming relaxation is called the {em fractional edge-coloring problem} (FECP). In the literature, the optimal value of ECP (resp. FECP) is called the {em chromatic index} (resp. {em fractional chromatic index}) of $G$, denoted by $chi(G)$ (resp. $chi^*(G)$). Let $Delta(G)$ be the maximum degree of $G$ and let [Gamma(G)=max Big{frac{2|E(U)|}{|U|-1}:,, U subseteq V, ,, |U|ge 3 hskip 2mm {rm and hskip 2mm odd} Big},] where $E(U)$ is the set of all edges of $G$ with both ends in $U$. Clearly, $max{Delta(G), , lceil Gamma(G) rceil }$ is a lower bound for $chi(G)$. As shown by Seymour, $chi^*(G)=max{Delta(G), , Gamma(G)}$. In the 1970s Goldberg and Seymour independently conjectured that $chi(G) le max{Delta(G)+1, , lceil Gamma(G) rceil}$. Over the past four decades this conjecture, a cornerstone in modern edge-coloring, has been a subject of extensive research, and has stimulated a significant body of work. In this paper we present a proof of this conjecture. Our result implies that, first, there are only two possible values for $chi(G)$, so an analogue to Vizings theorem on edge-colorings of simple graphs, a fundamental result in graph theory, holds for multigraphs; second, although it is $NP$-hard in general to determine $chi(G)$, we can approximate it within one of its true value, and find it exactly in polynomial time when $Gamma(G)>Delta(G)$; third, every multigraph $G$ satisfies $chi(G)-chi^*(G) le 1$, so FECP has a fascinating integer rounding property.
In the context of the (generalized) Delta Conjecture and its compositional form, DAdderio, Iraci, and Wyngaerd recently stated a conjecture relating two symmetric function operators, $D_k$ and $Theta_k$. We prove this Theta Operator Conjecture, finding it as a consequence of the five-term relation of Mellit and Garsia. As a result, we find surprising ways of writing the $D_k$ operators.
In this short note we prove an equivariant version of the formality of multidiffirential operators for a proper Lie group action. More precisely, we show that the equivariant Hochschild-Kostant-Rosenberg quasi-isomorphism between the cohomology of the equivariant multidifferential operators and the complex of equivariant multivector fields extends to an $L_infty$-quasi-isomorphism. We construct this $L_infty$-quasi-isomorphism using the $G$-invariant formality constructed by Dolgushev. This result has immediate consequences in deformation quantization, since it allows to obtain a quantum moment map from a classical momentum map with respect to a $G$-invariant Poisson structure.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
