Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userForbidden subposet problems in the grid
53
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
For posets $P$ and $Q$, extremal and saturation problems about weak and strong $P$-free subposets of $Q$ have been studied mostly in the case $Q$ is the Boolean poset $Q_n$, the poset of all subsets of an $n$-element set ordered by inclusion. In this paper, we study some instances of the problem with $Q$ being the grid, and its connections to the Boolean case and to the forbidden submatrix problem.
rate research
Read More
Upper bounds to the size of a family of subsets of an n-element set that avoids certain configurations are proved. These forbidden configurations can be described by inclusion patterns and some sets having the same size. Our results are closely related to the forbidden subposet problems, where the avoided configurations are described solely by inclusions.
A family of permutations $mathcal{F} subset S_{n}$ is said to be $t$-intersecting if any two permutations in $mathcal{F}$ agree on at least $t$ points. It is said to be $(t-1)$-intersection-free if no two permutations in $mathcal{F}$ agree on exactly $t-1$ points. If $S,T subset {1,2,ldots,n}$ with $|S|=|T|$, and $pi: S to T$ is a bijection, the $pi$-star in $S_n$ is the family of all permutations in $S_n$ that agree with $pi$ on all of $S$. An $s$-star is a $pi$-star such that $pi$ is a bijection between sets of size $s$. Friedgut and Pilpel, and independently the first author, showed that if $mathcal{F} subset S_n$ is $t$-intersecting, and $n$ is sufficiently large depending on $t$, then $|mathcal{F}| leq (n-t)!$; this proved a conjecture of Deza and Frankl from 1977. Equality holds only if $mathcal{F}$ is a $t$-star. In this paper, we give a more `robust proof of a strengthening of the Deza-Frankl conjecture, namely that if $n$ is sufficiently large depending on $t$, and $mathcal{F} subset S_n$ is $(t-1)$-intersection-free, then $|mathcal{F} leq (n-t)!$, with equality only if $mathcal{F}$ is a $t$-star. The main ingredient of our proof is a `junta approximation result, namely, that any $(t-1)$-intersection-free family of permutations is essentially contained in a $t$-intersecting {em junta} (a `junta being a union of a bounded number of $O(1)$-stars). The proof of our junta approximation result relies, in turn, on a weak regularity lemma for families of permutations, a combinatorial argument that `bootstraps a weak notion of pseudorandomness into a stronger one, and finally a spectral argument for pairs of highly-pseudorandom fractional families. Our proof employs four different notions of pseudorandomness, three being combinatorial in nature, and one being algebraic.
Tropical curves in $mathbb{R}^2$ correspond to metric planar graphs but not all planar graphs arise in this way. We describe several new classes of graphs which cannot occur. For instance, this yields a full combinatorial characterization of the tropically planar graphs of genus at most five.
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$.
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)$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
