Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe number of $k$-dimensional corner-free subsets of grids
169
0
0.0
(
0
)
Authors
Younjin Kim
Ask ChatGPT about the research
No Arabic abstract
A subset $A$ of the $k$-dimensional grid ${1,2, cdots, N}^k$ is called $k$-dimensional corner-free if it does not contain a set of points of the form ${ a } cup { a + de_i : 1 leq i leq k }$ for some $a in {1,2, cdots, N}^k$ and $d > 0$, where $e_1,e_2, cdots, e_k$ is the standard basis of $mathbb{R}^k$. We define the maximum size of a $k$-dimensional corner-free subset of ${1,2, cdots, N}^k$ by $c_k(N)$. In this paper, we show that the number of $k$-dimensional corner-free subsets of the $k$-dimensional grid ${1,2, cdots, N}^k$ is at most $2^{O(c_k(N))}$ for infinitely many values of $N$. Our main tool for the proof is a supersaturation result for $k$-dimensional corners in sets of size $Theta(c_k(N))$ and the hypergraph container method.
rate research
Read More
The areas of Ramsey theory and random graphs have been closely linked ever since ErdH{o}s famous proof in 1947 that the diagonal Ramsey numbers $R(k)$ grow exponentially in $k$. In the early 1990s, the triangle-free process was introduced as a model which might potentially provide good lower bounds for the off-diagonal Ramsey numbers $R(3,k)$. In this model, edges of $K_n$ are introduced one-by-one at random and added to the graph if they do not create a triangle; the resulting final (random) graph is denoted $G_{n,triangle}$. In 2009, Bohman succeeded in following this process for a positive fraction of its duration, and thus obtained a second proof of Kims celebrated result that $R(3,k) = Theta big( k^2 / log k big)$. In this paper we improve the results of both Bohman and Kim, and follow the triangle-free process all the way to its asymptotic end. In particular, we shall prove that $$ebig( G_{n,triangle} big) ,=, left( frac{1}{2sqrt{2}} + o(1) right) n^{3/2} sqrt{log n },$$ with high probability as $n to infty$. We also obtain several pseudorandom properties of $G_{n,triangle}$, and use them to bound its independence number, which gives as an immediate corollary $$R(3,k) , ge , left( frac{1}{4} - o(1) right) frac{k^2}{log k}.$$ This significantly improves Kims lower bound, and is within a factor of $4 + o(1)$ of the best known upper bound, proved by Shearer over 25 years ago.
The packet routing problem plays an essential role in communication networks. It involves how to transfer data from some origins to some destinations within a reasonable amount of time. In the $(ell,k)$-routing problem, each node can send at most $ell$ packets and receive at most $k$ packets. Permutation routing is the particular case $ell=k=1$. In the $r$-central routing problem, all nodes at distance at most $r$ from a fixed node $v$ want to send a packet to $v$. In this article we study the permutation routing, the $r$-central routing and the general $(ell,k)$-routing problems on plane grids, that is square grids, triangular grids and hexagonal grids. We use the emph{store-and-forward} $Delta$-port model, and we consider both full and half-duplex networks. We first survey the existing results in the literature about packet routing, with special emphasis on $(ell,k)$-routing on plane grids. Our main contributions are the following: 1. Tight permutation routing algorithms on full-duplex hexagonal grids, and half duplex triangular and hexagonal grids. 2. Tight $r$-central routing algorithms on triangular and hexagonal grids. 3. Tight $(k,k)$-routing algorithms on square, triangular and hexagonal grids. 4. Good approximation algorithms (in terms of running time) for $(ell,k)$-routing on square, triangular and hexagonal grids, together with new lower bounds on the running time of any algorithm using shortest path routing. These algorithms are all completely distributed, i.e., can be implemented independently at each node. Finally, we also formulate the $(ell,k)$-routing problem as a textsc{Weighted Edge Coloring} problem on bipartite graphs.
We determine the shape of all sum-free sets in ${1,dots,n}^2$ of size close to the maximum $frac{3}{5}n^2$, solving a problem of Elsholtz and Rackham. We show that all such asymptotic maximum sum-free sets lie completely in the stripe $frac{4}{5}n-o(n)le x+ylefrac{8}{5}n+ o(n)$. We also determine for any positive integer $p$ the maximum size of a subset $Asubseteq {1,dots,n}^2$ which forbids the triple $(x,y,z)$ satisfying $px+py=z$.
We count the ordered sum-free triplets of subsets in the group $mathbb{Z}/pmathbb{Z}$, i.e., the triplets $(A,B,C)$ of sets $A,B,C subset mathbb{Z}/pmathbb{Z}$ for which the equation $a+b=c$ has no solution with $ain A$, $b in B$ and $c in C$. Our main theorem improves on a recent result by Semchankau, Shabanov, and Shkredov using a different and simpler method. Our proof relates previous results on the number of independent sets of regular graphs by Kahn, Perarnau and Perkins, and Csikvari to produce explicit estimates on smaller order terms. We also obtain estimates for the number of sum-free triplets of subsets in a general abelian group.
A subfamily ${F_1,F_2,dots,F_{|P|}}subseteq mathcal F$ is a copy of the poset $P$ if there exists a bijection $i:Prightarrow {F_1,F_2,dots,F_{|P|}}$ such that $ple_P q$ implies $i(p)subseteq i(q)$. A family $mathcal F$ is $P$-free, if it does not contain a copy of $P$. In this paper we establish basic results on the maximum possible number of $k$-chains in a $P$-free family $mathcal Fsubseteq 2^{[n]}$. We prove that if the height of $P$, $h(P) > k$, then this number is of the order $Theta(prod_{i=1}^{k+1}binom{l_{i-1}}{l_i})$, where $l_0=n$ and $l_1ge l_2ge dots ge l_{k+1}$ are such that $n-l_1,l_1-l_2,dots, l_k-l_{k+1},l_{k+1}$ differ by at most one. On the other hand if $h(P)le k$, then we show that this number is of smaller order of magnitude. Let $vee_r$ denote the poset on $r+1$ elements $a, b_1, b_2, ldots, b_r$, where $a < b_i$ for all $1 le i le r$ and let $wedge_r$ denote its dual. For any values of $k$ and $l$, we construct a ${wedge_k,vee_l}$-free family and we conjecture that it contains asymptotically the maximum number of pairs in containment. We prove that this conjecture holds under the additional assumption that a chain of length 4 is forbidden. Moreover, we prove the conjecture for some small values of $k$ and $l$. We also derive the asymptotics of the maximum number of copies of certain tree posets $T$ of height 2 in ${wedge_k,vee_l}$-free families $mathcal F subseteq 2^{[n]}$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
