Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userUnambiguous DNFs and Alon-Saks-Seymour
175
0
0.0
(
0
)
Added by
Robin Kothari
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We exhibit an unambiguous k-DNF formula that requires CNF width $tilde{Omega}(k^2)$, which is optimal up to logarithmic factors. As a consequence, we get a near-optimal solution to the Alon--Saks--Seymour problem in graph theory (posed in 1991), which asks: How large a gap can there be between the chromatic number of a graph and its biclique partition number? Our result is also known to imply several other improved separations in query and communication complexity.
rate research
Read More
In 1992 Mansour proved that every size-$s$ DNF formula is Fourier-concentrated on $s^{O(loglog s)}$ coefficients. We improve this to $s^{O(loglog k)}$ where $k$ is the read number of the DNF. Since $k$ is always at most $s$, our bound matches Mansours for all DNFs and strengthens it for small-read ones. The previous best bound for read-$k$ DNFs was $s^{O(k^{3/2})}$. For $k$ up to $tilde{Theta}(loglog s)$, we further improve our bound to the optimal $mathrm{poly}(s)$; previously no such bound was known for any $k = omega_s(1)$. Our techniques involve new connections between the term structure of a DNF, viewed as a set system, and its Fourier spectrum.
In analogy with epsilon-biased sets over Z_2^n, we construct explicit epsilon-biased sets over nonabelian finite groups G. That is, we find sets S subset G such that | Exp_{x in S} rho(x)| <= epsilon for any nontrivial irreducible representation rho. Equivalently, such sets make Gs Cayley graph an expander with eigenvalue |lambda| <= epsilon. The Alon-Roichman theorem shows that random sets of size O(log |G| / epsilon^2) suffice. For groups of the form G = G_1 x ... x G_n, our construction has size poly(max_i |G_i|, n, epsilon^{-1}), and we show that a set S subset G^n considered by Meka and Zuckerman that fools read-once branching programs over G is also epsilon-biased in this sense. For solvable groups whose abelian quotients have constant exponent, we obtain epsilon-biased sets of size (log |G|)^{1+o(1)} poly(epsilon^{-1}). Our techniques include derandomized squaring (in both the matrix product and tensor product senses) and a Chernoff-like bound on the expected norm of the product of independently random operators that may be of independent interest.
Motivated by questions in algebra and combinatorics we study two ideals associated to a simple graph G: --> the Lovasz-Saks-Schrijver ideal defining the d-dimensional orthogonal representations of the graph complementary to G and --> the determinantal ideal of the (d+1)-minors of a generic symmetric with 0s in positions prescribed by the graph G. In characteristic 0 these two ideals turns out to be closely related and algebraic properties such as being radical, prime or a complete intersection transfer from the Lovasz-Saks-Schrijver ideal to the determinantal ideal. For Lovasz-Saks-Schrijver ideals we link these properties to combinatorial properties of G and show that they always hold for d large enough. For specific classes of graph, such a forests, we can give a complete picture and classify the radical, prime and complete intersection Lovasz-Saks-Schrijver ideals.
A subset $A$ of a Banach space is called Banach-Saks when every sequence in $A$ has a Ces{`a}ro convergent subsequence. Our interest here focusses on the following problem: is the convex hull of a Banach-Saks set again Banach-Saks? By means of a combinatorial argument, we show that in general the answer is negative. However, sufficient conditions are given in order to obtain a positive result.
Let $G$ be a simple graph on $n$ vertices. Let $L_G text{ and } mathcal{I}_G : $ denote the Lovasz-Saks-Schrijver(LSS) ideal and parity binomial edge ideal of $G$ in the polynomial ring $S = mathbb{K}[x_1,ldots, x_n, y_1, ldots, y_n] $ respectively. We classify graphs whose LSS ideals and parity binomial edge ideals are complete intersections. We also classify graphs whose LSS ideals and parity binomial edge ideals are almost complete intersections, and we prove that their Rees algebra is Cohen-Macaulay. We compute the second graded Betti number and obtain a minimal presentation of LSS ideals of trees and odd unicyclic graphs. We also obtain an explicit description of the defining ideal of the symmetric algebra of LSS ideals of trees and odd unicyclic graphs.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
