Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userTight bounds and conjectures for the isolation lemma
77
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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$.
rate research
Read More
Changs lemma (Duke Mathematical Journal, 2002) is a classical result with applications across several areas in mathematics and computer science. For a Boolean function $f$ that takes values in {-1,1} let $r(f)$ denote its Fourier rank. For each positive threshold $t$, Changs lemma provides a lower bound on $wt(f):=Pr[f(x)=-1]$ in terms of the dimension of the span of its characters with Fourier coefficients of magnitude at least $1/t$. We examine the tightness of Changs lemma w.r.t. the following three natural settings of the threshold: - the Fourier sparsity of $f$, denoted $k(f)$, - the Fourier max-supp-entropy of $f$, denoted $k(f)$, defined to be $max {1/|hat{f}(S)| : hat{f}(S) eq 0}$, - the Fourier max-rank-entropy of $f$, denoted $k(f)$, defined to be the minimum $t$ such that characters whose Fourier coefficients are at least $1/t$ in absolute value span a space of dimension $r(f)$. We prove new lower bounds on $wt(f)$ in terms of these measures. One of our lower bounds subsumes and refines the previously best known upper bound on $r(f)$ in terms of $k(f)$ by Sanyal (ToC, 2019). Another lower bound is based on our improvement of a bound by Chattopadhyay, Hatami, Lovett and Tal (ITCS, 2019) on the sum of the absolute values of the level-$1$ Fourier coefficients. We also show that Changs lemma for the these choices of the threshold is asymptotically outperformed by our bounds for most settings of the parameters involved. Next, we show that our bounds are tight for a wide range of the parameters involved, by constructing functions (which are modifications of the Addressing function) witnessing their tightness. Finally we construct Boolean functions $f$ for which - our lower bounds asymptotically match $wt(f)$, and - for any choice of the threshold $t$, the lower bound obtained from Changs lemma is asymptotically smaller than $wt(f)$.
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$.
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.
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$.
The operator nabla, introduced by Garsia and the author, plays a crucial role in many aspect of the study of diagonal harmonics. Besides giving several new formulas involving this operator, we show how one is lead to representation theoretic explanations for conjectures about the effect of this operator on Schur functions.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
