Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA proof of Ringels Conjecture
114
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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$.
rate research
Read More
We prove that any quasirandom graph with $n$ vertices and $rn$ edges can be decomposed into $n$ copies of any fixed tree with $r$ edges. The case of decomposing a complete graph establishes a conjecture of Ringel from 1963.
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)$.
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.
We give a new proof of a sumset conjecture of Furstenberg that was first proved by Hochman and Shmerkin in 2012: if $log r / log s$ is irrational and $X$ and $Y$ are $times r$- and $times s$-invariant subsets of $[0,1]$, respectively, then $dim_text{H} (X+Y) = min ( 1, dim_text{H} X + dim_text{H} Y)$. Our main result yields information on the size of the sumset $lambda X + eta Y$ uniformly across a compact set of parameters at fixed scales. The proof is combinatorial and avoids the machinery of local entropy averages and CP-processes, relying instead on a quantitative, discrete Marstrand projection theorem and a subtree regularity theorem that may be of independent interest.
A computer search through the oriented matroid programs with dimension 5 and 10 facets shows that the maximum strictly monotone diameter is 5. Thus $Delta_{sm}(5,10)=5$. This enumeration is analogous to that of Bremner and Schewe for the non-monotone diameter of 6-polytopes with 12 facets. Similar enumerations show that $Delta_{sm}(4,9)=5$ and $Delta_m(4,9)=Delta_m(5,10)=6.$ We shorten the known non-computer proof of the strict monotone 4-step conjecture.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
