Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userForbidden subposet problems with size restrictions
49
0
0.0
(
0
)
Authors
Daniel T. Nagy
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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.
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$.
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.
Given a graph $G$, a decomposition of $G$ is a partition of its edges. A graph is $(d, h)$-decomposable if its edge set can be partitioned into a $d$-degenerate graph and a graph with maximum degree at most $h$. For $d le 4$, we are interested in the minimum integer $h_d$ such that every planar graph is $(d,h_d)$-decomposable. It was known that $h_3 le 4$, $h_2le 8$, and $h_1 = infty$. This paper proves that $h_4=1, h_3=2$, and $4 le h_2 le 6$.
All planar graphs are 4-colorable and 5-choosable, while some planar graphs are not 4-choosable. Determining which properties guarantee that a planar graph can be colored using lists of size four has received significant attention. In terms of constraining the structure of the graph, for any $ell in {3,4,5,6,7}$, a planar graph is 4-choosable if it is $ell$-cycle-free. In terms of constraining the list assignment, one refinement of $k$-choosability is choosability with separation. A graph is $(k,s)$-choosable if the graph is colorable from lists of size $k$ where adjacent vertices have at most $s$ common colors in their lists. Every planar graph is $(4,1)$-choosable, but there exist planar graphs that are not $(4,3)$-choosable. It is an open question whether planar graphs are always $(4,2)$-choosable. A chorded $ell$-cycle is an $ell$-cycle with one additional edge. We demonstrate for each $ell in {5,6,7}$ that a planar graph is $(4,2)$-choosable if it does not contain chorded $ell$-cycles.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
