Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA Sauer-Shelah-Perles Lemma for Lattices
110
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We study lattice-theoretical extensions of the celebrated Sauer-Shelah-Perles Lemma. We conjecture that a general Sauer-Shelah-Perlem Lemma holds for a lattice $L$ if and only if $L$ is relatively complemented, and prove partial results towards this conjecture.
rate research
Read More
We develop a new method for constructing approximate decompositions of dense graphs into sparse graphs and apply it to longstanding decomposition problems. For instance, our results imply the following. Let $G$ be a quasi-random $n$-vertex graph and suppose $H_1,dots,H_s$ are bounded degree $n$-vertex graphs with $sum_{i=1}^{s} e(H_i) leq (1-o(1)) e(G)$. Then $H_1,dots,H_s$ can be packed edge-disjointly into $G$. The case when $G$ is the complete graph $K_n$ implies an approximate version of the tree packing conjecture of Gyarfas and Lehel for bounded degree trees, and of the Oberwolfach problem. We provide a more general version of the above approximate decomposition result which can be applied to super-regular graphs and thus can be combined with Szemeredis regularity lemma. In particular our result can be viewed as an extension of the classical blow-up lemma of Komlos, SarkH{o}zy and Szemeredi to the setting of approximate decompositions.
A subgraph of an edge-coloured graph is called rainbow if all its edges have different colours. We prove a rainbow version of the blow-up lemma of Komlos, Sarkozy and Szemeredi that applies to almost optimally bounded colourings. A corollary of this is that there exists a rainbow copy of any bounded-degree spanning subgraph $H$ in a quasirandom host graph $G$, assuming that the edge-colouring of $G$ fulfills a boundedness condition that is asymptotically best possible. This has many applications beyond rainbow colourings, for example to graph decompositions, orthogonal double covers and graph labellings.
Kim, Kuhn, Osthus and Tyomkyn (Trans. Amer. Math. Soc. 371 (2019), 4655--4742) greatly extended the well-known blow-up lemma of Komlos, Sarkozy and Szemeredi by proving a `blow-up lemma for approximate decompositions which states that multipartite quasirandom graphs can be almost decomposed into any collection of bounded degree graphs with the same multipartite structure and slightly fewer edges. This result has already been used by Joos, Kim, Kuhn and Osthus to prove the tree packing conjecture due to Gyarfas and Lehel from 1976 and Ringels conjecture from 1963 for bounded degree trees as well as implicitly in the recent resolution of the Oberwolfach problem (asked by Ringel in 1967) by Glock, Joos, Kim, Kuhn and Osthus. Here we present a new and significantly shorter proof of the blow-up lemma for approximate decompositions. In fact, we prove a more general theorem that yields packings with stronger quasirandom properties so that it can be combined with Keevashs results on designs to obtain results of the following form. For all $varepsilon>0$, $rin mathbb{N}$ and all large $n$ (such that $r$ divides $n-1$), there is a decomposition of $K_n$ into any collection of $r$-regular graphs $H_1,ldots,H_{(n-1)/r}$ on $n$ vertices provided that $H_1,ldots,H_{varepsilon n}$ contain each at least $varepsilon n$ vertices in components of size at most $varepsilon^{-1}$.
Given a hypergraph $H$ and a weight function $w: V rightarrow {1, dots, M}$ on its vertices, we say that $w$ is isolating if there is exactly one edge of minimum weight $w(e) = sum_{i in e} w(i)$. The Isolation Lemma is a combinatorial principle introduced in Mulmuley et. al (1987) which gives a lower bound on the number of isolating weight functions. Mulmuley used this as the basis of a parallel algorithm for finding perfect graph matchings. It has a number of other applications to parallel algorithms and to reductions of general search problems to unique search problems (in which there are one or zero solutions). The original bound given by Mulmuley et al. was recently improved by Ta-Shma (2015). In this paper, we show improved lower bounds on the number of isolating weight functions, and we conjecture that the extremal case is when $H$ consists of $n$ singleton edges. When $M gg n$ our improved bound matches this extremal case asymptotically. We are able to show that this conjecture holds in a number of special cases: when $H$ is a linear hypergraph or is 1-degenerate, or when $M = 2$. We also show that it holds asymptotically when $M gg n gg 1$.
The clique removal lemma says that for every $r geq 3$ and $varepsilon>0$, there exists some $delta>0$ so that every $n$-vertex graph $G$ with fewer than $delta n^r$ copies of $K_r$ can be made $K_r$-free by removing at most $varepsilon n^2$ edges. The dependence of $delta$ on $varepsilon$ in this result is notoriously difficult to determine: it is known that $delta^{-1}$ must be at least super-polynomial in $varepsilon^{-1}$, and that it is at most of tower type in $log varepsilon^{-1}$. We prove that if one imposes an appropriate minimum degree condition on $G$, then one can actually take $delta$ to be a linear function of $varepsilon$ in the clique removal lemma. Moreover, we determine the threshold for such a minimum degree requirement, showing that above this threshold we have linear bounds, whereas below the threshold the bounds are once again super-polynomial, as in the unrestricted removal lemma. We also investigate this question for other graphs besides cliques, and prove some general results about how minimum degree conditions affect the bounds in the graph removal lemma.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
