Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA Proof of a Conjecture of Ohba
211
0
0.0
(
0
)
Added by
Jonathan Noel
Publication date
2012
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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)$.
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 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.
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.
Motivated by a hat guessing problem proposed by Iwasawa cite{Iwasawa10}, Butler and Graham cite{Butler11} made the following conjecture on the existence of certain way of marking the {em coordinate lines} in $[k]^n$: there exists a way to mark one point on each {em coordinate line} in $[k]^n$, so that every point in $[k]^n$ is marked exactly $a$ or $b$ times as long as the parameters $(a,b,n,k)$ satisfies that there are non-negative integers $s$ and $t$ such that $s+t = k^n$ and $as+bt = nk^{n-1}$. In this paper we prove this conjecture for any prime number $k$. Moreover, we prove the conjecture for the case when $a=0$ for general $k$.
We prove that for any $varepsilon>0$, for any large enough $t$, there is a graph $G$ that admits no $K_t$-minor but admits a $(frac32-varepsilon)t$-colouring that is frozen with respect to Kempe changes, i.e. any two colour classes induce a connected component. This disproves three conjectures of Las Vergnas and Meyniel from 1981.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
