Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userTowards Tight(er) Bounds for the Excluded Grid Theorem
62
0
0.0
(
0
)
Added by
Zihan Tan
Publication date
2019
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We study the Excluded Grid Theorem, a fundamental structural result in graph theory, that was proved by Robertson and Seymour in their seminal work on graph minors. The theorem states that there is a function $f: mathbb{Z}^+ to mathbb{Z}^+$, such that for every integer $g>0$, every graph of treewidth at least $f(g)$ contains the $(gtimes g)$-grid as a minor. For every integer $g>0$, let $f(g)$ be the smallest value for which the theorem holds. Establishing tight bounds on $f(g)$ is an important graph-theoretic question. Robertson and Seymour showed that $f(g)=Omega(g^2log g)$ must hold. For a long time, the best known upper bounds on $f(g)$ were super-exponential in $g$. The first polynomial upper bound of $f(g)=O(g^{98}text{poly}log g)$ was proved by Chekuri and Chuzhoy. It was later improved to $f(g) = O(g^{36}text{poly} log g)$, and then to $f(g)=O(g^{19}text{poly}log g)$. In this paper we further improve this bound to $f(g)=O(g^{9}text{poly} log g)$. We believe that our proof is significantly simpler than the proofs of the previous bounds. Moreover, while there are natural barriers that seem to prevent the previous methods from yielding tight bounds for the theorem, it seems conceivable that the techniques proposed in this paper can lead to even tighter bounds on $f(g)$.
rate research
Read More
The following online bin packing problem is considered: Items with integer sizes are given and variable sized bins arrive online. A bin must be used if there is still an item remaining which fits in it when the bin arrives. The goal is to minimize the total size of all the bins used. Previously, a lower bound of 5/4 on the competitive ratio of this problem was achieved using jobs of size S and 2S-1. For these item sizes and maximum bin size 4S-3, we obtain asymptotically matching upper and lower bounds, which vary depending on the ratio of the number of small jobs to the number of large jobs.
We establish a bound for the classic PUSH-PULL rumor spreading protocol on arbitrary graphs, in terms of the vertex expansion of the graph. We show that O(log^2(n)/alpha) rounds suffice with high probability to spread a rumor from a single node to all n nodes, in any graph with vertex expansion at least alpha. This bound matches the known lower bound, and settles the question on the relationship between rumor spreading and vertex expansion asked by Chierichetti, Lattanzi, and Panconesi (SODA 2010). Further, some of the arguments used in the proof may be of independent interest, as they give new insights, for example, on how to choose a small set of nodes in which to plant the rumor initially, to guarantee fast rumor spreading.
We study the problem of exploring an oriented grid with autonomous agents governed by finite automata. In the case of a 2-dimensional grid, the question how many agents are required to explore the grid, or equivalently, find a hidden treasure in the grid, is fully understood in both the synchronous and the semi-synchronous setting. For higher dimensions, Dobrev, Narayanan, Opatrny, and Pankratov [ICALP19] showed very recently that, surprisingly, a (small) constant number of agents suffices to find the treasure, independent of the number of dimensions, thereby disproving a conjecture by Cohen, Emek, Louidor, and Uitto [SODA17]. Dobrev et al. left as an open question whether their bounds on the number of agents can be improved. We answer this question in the affirmative for deterministic finite automata: we show that 3 synchronous and 4 semi-synchronous agents suffice to explore an $n$-dimensional grid for any constant $n$. The bounds are optimal and notably, the matching lower bounds already hold in the 2-dimensional case. Our techniques can also be used to make progress on other open questions asked by Dobrev et al.: we prove that 4 synchronous and 5 semi-synchronous agents suffice for polynomial-time exploration, and we show that, under a natural assumption, 3 synchronous and 4 semi-synchronous agents suffice to explore unoriented grids of arbitrary dimension (which, again, is tight).
A fundamental result in extremal set theory is Katonas shadow intersection theorem, which extends the Kruskal-Katona theorem by giving a lower bound on the size of the shadow of an intersecting family of $k$-sets in terms of its size. We improve this classical result and a related result of Ahlswede, Aydinian, and Khachatrian by proving tight bounds for families that can be quite small. For example, when $k=3$ our result is sharp for all families with $n$ points and at least $3n-7$ triples. Katonas theorem was extended by Frankl to families with matching number $s$. We improve Frankls result by giving tight bounds for large $n$.
Cut and spectral sparsification of graphs have numerous applications, including e.g. speeding up algorithms for cuts and Laplacian solvers. These powerful notions have recently been extended to hypergraphs, which are much richer and may offer new applications. However, the current bounds on the size of hypergraph sparsifiers are not as tight as the corresponding bounds for graphs. Our first result is a polynomial-time algorithm that, given a hypergraph on $n$ vertices with maximum hyperedge size $r$, outputs an $epsilon$-spectral sparsifier with $O^*(nr)$ hyperedges, where $O^*$ suppresses $(epsilon^{-1} log n)^{O(1)}$ factors. This size bound improves the two previous bounds: $O^*(n^3)$ [Soma and Yoshida, SODA19] and $O^*(nr^3)$ [Bansal, Svensson and Trevisan, FOCS19]. Our main technical tool is a new method for proving concentration of the nonlinear analogue of the quadratic form of the Laplacians for hypergraph expanders. We complement this with lower bounds on the bit complexity of any compression scheme that $(1+epsilon)$-approximates all the cuts in a given hypergraph, and hence also on the bit complexity of every $epsilon$-cut/spectral sparsifier. These lower bounds are based on Ruzsa-Szemeredi graphs, and a particular instantiation yields an $Omega(nr)$ lower bound on the bit complexity even for fixed constant $epsilon$. This is tight up to polylogarithmic factors in $n$, due to recent hypergraph cut sparsifiers of [Chen, Khanna and Nagda, FOCS20]. Finally, for directed hypergraphs, we present an algorithm that computes an $epsilon$-spectral sparsifier with $O^*(n^2r^3)$ hyperarcs, where $r$ is the maximum size of a hyperarc. For small $r$, this improves over $O^*(n^3)$ known from [Soma and Yoshida, SODA19], and is getting close to the trivial lower bound of $Omega(n^2)$ hyperarcs.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
