Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userHypergraphs with many Kneser colorings (Extended Version)
137
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
For fixed positive integers $r, k$ and $ell$ with $1 leq ell < r$ and an $r$-uniform hypergraph $H$, let $kappa (H, k,ell)$ denote the number of $k$-colorings of the set of hyperedges of $H$ for which any two hyperedges in the same color class intersect in at least $ell$ elements. Consider the function $KC(n,r,k,ell)=max_{Hin{mathcal H}_{n}} kappa (H, k,ell) $, where the maximum runs over the family ${mathcal H}_n$ of all $r$-uniform hypergraphs on $n$ vertices. In this paper, we determine the asymptotic behavior of the function $KC(n,r,k,ell)$ for every fixed $r$, $k$ and $ell$ and describe the extremal hypergraphs. This variant of a problem of ErdH{o}s and Rothschild, who considered edge colorings of graphs without a monochromatic triangle, is related to the ErdH{o}s--Ko--Rado Theorem on intersecting systems of sets [Intersection Theorems for Systems of Finite Sets, Quarterly Journal of Mathematics, Oxford Series, Series 2, {bf 12} (1961), 313--320].
rate research
Read More
We show that any proper coloring of a Kneser graph $KG_{n,k}$ with $n-2k+2$ colors contains a trivial color (i.e., a color consisting of sets that all contain a fixed element), provided $n>(2+epsilon)k^2$, where $epsilonto 0$ as $kto infty$. This bound is essentially tight.
For every positive integer $t$ we construct a finite family of triple systems ${mathcal M}_t$, determine its Tur{a}n number, and show that there are $t$ extremal ${mathcal M}_t$-free configurations that are far from each other in edit-distance. We also prove a strong stability theorem: every ${mathcal M}_t$-free triple system whose size is close to the maximum size is a subgraph of one of these $t$ extremal configurations after removing a small proportion of vertices. This is the first stability theorem for a hypergraph problem with an arbitrary (finite) number of extremal configurations. Moreover, the extremal hypergraphs have very different shadow sizes (unlike the case of the famous Turan tetrahedron conjecture). Hence a corollary of our main result is that the boundary of the feasible region of ${mathcal M}_t$ has exactly $t$ global maxima.
In this short note, we show that for any $epsilon >0$ and $k<n^{0.5-epsilon}$ the choice number of the Kneser graph $KG_{n,k}$ is $Theta (nlog n)$.
In this paper, we study the rainbow ErdH{o}s-Rothschild problem with respect to 3-term arithmetic progressions. We obtain the asymptotic number of $r$-colorings of $[n]$ without rainbow 3-term arithmetic progressions, and we show that the typical colorings with this property are 2-colorings. We also prove that $[n]$ attains the maximum number of rainbow 3-term arithmetic progression-free $r$-colorings among all subsets of $[n]$. Moreover, the exact number of rainbow 3-term arithmetic progression-free $r$-colorings of $mathbb{Z}_p$ is obtained, where $p$ is any prime and $mathbb{Z}_p$ is the cyclic group of order $p$.
This work lies across three areas (in the title) of investigation that are by themselves of independent interest. A problem that arose in quantum computing led us to a link that tied these areas together. This link consists of a single formal power series with a multifaced interpretation. The deeper exploration of this link yielded results as well as methods for solving some numerical problems in each of these separate areas.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
