Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userNew methods to attack the Buratti-Horak-Rosa conjecture
93
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
Label the vertices of the complete graph $K_v$ with the integers ${ 0, 1, ldots, v-1 }$ and define the length of the edge between $x$ and $y$ to be $min( |x-y| , v - |x-y| )$. Let $L$ be a multiset of size $v-1$ with underlying set contained in ${ 1, ldots, lfloor v/2 rfloor }$. The Buratti-Horak-Rosa Conjecture is that there is a Hamiltonian path in $K_v$ whose edge lengths are exactly $L$ if and only if for any divisor $d$ of $v$ the number of multiples of $d$ appearing in $L$ is at most $v-d$. We introduce growable realizations, which enable us to prove many new instances of the conjecture and to reprove known results in a simpler way. As examples of the new method, we give a complete solution when the underlying set is contained in ${ 1,4,5 }$ or in ${ 1,2,3,4 }$ and a partial result when the underlying set has the form ${ 1, x, 2x }$. We believe that for any set $U$ of positive integers there is a finite set of growable realizations that implies the truth of the Buratti-Horak-Rosa Conjecture for all but finitely many multisets with underlying set $U$.
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.
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$.
A Latin square of order $n$ is an $n times n$ array filled with $n$ symbols such that each symbol appears only once in every row or column and a transversal is a collection of cells which do not share the same row, column or symbol. The study of Latin squares goes back more than 200 years to the work of Euler. One of the most famous open problems in this area is a conjecture of Ryser-Brualdi-Stein from 60s which says that every Latin square of order $ntimes n$ contains a transversal of order $n-1$. In this paper we prove the existence of a transversal of order $n-O(log{n}/log{log{n}})$, improving the celebrated bound of $n-O(log^2n)$ by Hatami and Shor. Our approach (different from that of Hatami-Shor) is quite general and gives several other applications as well. We obtain a new lower bound on a 40 year old conjecture of Brouwer on the maximum matching in Steiner triple systems, showing that every such system of order $n$ is guaranteed to have a matching of size $n/3-O(log{n}/log{log{n}})$. This substantially improves the current best result of Alon, Kim and Spencer which has the error term of order $n^{1/2+o(1)}$. Finally, we also show that $O(nlog{n}/log{log{n}})$ many symbols in Latin arrays suffice to guarantee a full transversal, improving on previously known bound of $n^{2-varepsilon}$. The proofs combine in a novel way the semirandom method together with the robust expansion properties of edge coloured pseudorandom graphs to show the existence of a rainbow matching covering all but $O(log n/log{log{n}})$ vertices. All previous results, based on the semi-random method, left uncovered at least $Omega(n^{alpha})$ (for some constant $alpha$) vertices.
A well-known combinatorial theorem says that a set of n non-collinear points in the plane determines at least n distinct lines. Chen and Chvatal conjectured that this theorem extends to metric spaces, with an appropriated definition of line. In this work we prove a slightly stronger version of Chen and Chvatal conjecture for a family of graphs containing chordal graphs and distance-hereditary graphs.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
