Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userForbidden intersections for codes
71
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Determining the maximum size of a $t$-intersecting code in $[m]^n$ was a longstanding open problem of Frankl and Furedi, solved independently by Ahlswede and Khachatrian and by Frankl and Tokushige. We extend their result to the setting of forbidden intersections, by showing that for any $m>2$ and $n$ large compared with $t$ (but not necessarily $m$) that the same bound holds for codes with the weaker property of being $(t-1)$-avoiding, i.e. having no two vectors that agree on exactly $t-1$ coordinates. Our proof proceeds via a junta approximation result of independent interest, which we prove via a development of our recent theory of global hypercontractivity: we show that any $(t-1)$-avoiding code is approximately contained in a $t$-intersecting junta (a code where membership is determined by a constant number of co-ordinates). In particular, when $t=1$ this gives an alternative proof of a recent result of Eberhard, Kahn, Narayanan and Spirkl that symmetric intersecting codes in $[m]^n$ have size $o(m^n)$.
rate research
Read More
We extend the classical stability theorem of Erdos and Simonovits for forbidden graphs of logarithmic order.
We call a graph $G$ pancyclic if it contains at least one cycle of every possible length $m$, for $3le mle |V(G)|$. In this paper, we define a new property called chorded pancyclicity. We explore forbidden subgraphs in claw-free graphs sufficient to imply that the graph contains at least one chorded cycle of every possible length $4, 5, ldots, |V(G)|$. In particular, certain paths and triangles with pendant paths are forbidden.
We extend the classical stability theorem of Erdos and Simonovits in two directions: first, we allow the order of the forbidden graph to grow as log of order of the host graph, and second, our extremal condition is on the spectral radius of the host graph.
In this note, we fix a graph $H$ and ask into how many vertices can each vertex of a clique of size $n$ can be split such that the resulting graph is $H$-free. Formally: A graph is an $(n,k)$-graph if its vertex sets is a pairwise disjoint union of $n$ parts of size at most $k$ each such that there is an edge between any two distinct parts. Let $$ f(n,H) = min {k in mathbb N : mbox{there is an $(n,k)$-graph $G$ such that $H otsubseteq G$}} . $$ Barbanera and Ueckerdt observed that $f(n, H)=2$ for any graph $H$ that is not bipartite. If a graph $H$ is bipartite and has a well-defined Turan exponent, i.e., ${rm ex}(n, H) = Theta(n^r)$ for some $r$, we show that $Omega (n^{2/r -1}) = f(n, H) = O (n^{2/r-1} log ^{1/r} n)$. We extend this result to all bipartite graphs for which an upper and a lower Turan exponents do not differ by much. In addition, we prove that $f(n, K_{2,t}) =Theta(n^{1/3})$ for any fixed $t$.
The chromatic number of a graph is the minimum $k$ such that the graph has a proper $k$-coloring. There are many coloring parameters in the literature that are proper colorings that also forbid bicolored subgraphs. Some examples are $2$-distance coloring, acyclic coloring, and star coloring, which forbid a bicolored path on three vertices, bicolored cycles, and a bicolored path on four vertices, respectively. This notion was first suggested by Grunbaum in 1973, but no specific name was given. We revive this notion by defining an $H$-avoiding $k$-coloring to be a proper $k$-coloring that forbids a bicolored subgraph $H$. When considering the class $mathcal C$ of graphs with no $F$ as an induced subgraph, it is not hard to see that every graph in $mathcal C$ has bounded chromatic number if and only if $F$ is a complete graph of size at most two. We study this phenomena for the class of graphs with no $F$ as a subgraph for $H$-avoiding coloring. We completely characterize all graphs $F$ where the class of graphs with no $F$ as a subgraph has bounded $H$-avoiding chromatic number for a large class of graphs $H$. As a corollary, our main result implies a characterization of graphs $F$ where the class of graphs with no $F$ as a subgraph has bounded star chromatic number. We also obtain a complete characterization for the acyclic chromatic number.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
