Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userTight bounds for Katonas shadow intersection theorem
93
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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$.
rate research
Read More
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$.
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)$.
Let $n > k > t geq j geq 1$ be integers. Let $X$ be an $n$-element set, ${Xchoose k}$ the collection of its $k$-subsets. A family $mathcal F subset {Xchoose k}$ is called $t$-intersecting if $|F cap F| geq t$ for all $F, F in mathcal F$. The $j$th shadow $partial^j mathcal F$ is the collection of all $(k - j)$-subsets that are contained in some member of~$mathcal F$. Estimating $|partial^j mathcal F|$ as a function of $|mathcal F|$ is a widely used tool in extremal set theory. A classical result of the second author (Theorem ref{th:1.3}) provides such a bound for $t$-intersecting families. It is best possible for $|mathcal F| = {2k - tchoose k}$. Our main result is Theorem ref{th:1.4} which gives an asymptotically optimal bound on $|partial^j mathcal F| / |mathcal F|$ for $|mathcal F|$ slightly larger, e.g., $|mathcal F| > frac32 {2k - tchoose k}$. We provide further improvements for $|mathcal F|$ very large as well.
Partition functions arise in statistical physics and probability theory as the normalizing constant of Gibbs measures and in combinatorics and graph theory as graph polynomials. For instance the partition functions of the hard-core model and monomer-dimer model are the independence and matching polynomials respectively. We show how stability results follow naturally from the recently developed occupancy method for maximizing and minimizing physical observables over classes of regular graphs, and then show these stability results can be used to obtain tight extremal bounds on the individual coefficients of the corresponding partition functions. As applications, we prove new bounds on the number of independent sets and matchings of a given size in regular graphs. For large enough graphs and almost all sizes, the bounds are tight and confirm the Upper Matching Conjecture of Friedland, Krop, and Markstrom and a conjecture of Kahn on independent sets for a wide range of parameters. Additionally we prove tight bounds on the number of $q$-colorings of cubic graphs with a given number of monochromatic edges, and tight bounds on the number of independent sets of a given size in cubic graphs of girth at least $5$.
Let $G$ be a simple graph with $2n$ vertices and a perfect matching. The forcing number of a perfect matching $M$ of $G$ is the smallest cardinality of a subset of $M$ that is contained in no other perfect matching of $G$. Let $f(G)$ and $F(G)$ denote the minimum and maximum forcing number of $G$ among all perfect matchings, respectively. Hetyei obtained that the maximum number of edges of graphs $G$ with a unique perfect matching is $n^2$ (see Lov{a}sz [20]). We know that $G$ has a unique perfect matching if and only if $f(G)=0$. Along this line, we generalize the classical result to all graphs $G$ with $f(G)=k$ for $0leq kleq n-1$, and obtain that the number of edges is at most $n^2+2nk-k^2-k$ and characterize the extremal graphs as well. Conversely, we get a non-trivial lower bound of $f(G)$ in terms of the order and size. For bipartite graphs, we gain corresponding stronger results. Further, we obtain a new upper bound of $F(G)$. Finally some open problems and conjectures are proposed.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
