Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userProof of a Conjecture of Galvin
166
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We prove that if the set of unordered pairs of real numbers is colored by finitely many colors, there is a set of reals homeomorphic to the rationals whose pairs have at most two colors. Our proof uses large cardinals and it verifies a conjecture of Galvin from the 1970s. We extend this result to an essentially optimal class of topological spaces in place of the reals.
rate research
Read More
We present a proof of the compositional shuffle conjecture, which generalizes the famous shuffle conjecture for the character of the diagonal coinvariant algebra. We first formulate the combinatorial side of the conjecture in terms of certain operators on a graded vector space $V_*$ whose degree zero part is the ring of symmetric functions $Sym[X]$ over $mathbb{Q}(q,t)$. We then extend these operators to an action of an algebra $tilde{AA}$ acting on this space, and interpret the right generalization of the $ abla$ using an involution of the algebra which is antilinear with respect to the conjugation $(q,t)mapsto (q^{-1},t^{-1})$.
The total influence of a function is a central notion in analysis of Boolean functions, and characterizing functions that have small total influence is one of the most fundamental questions associated with it. The KKL theorem and the Friedgut junta theorem give a strong characterization of such functions whenever the bound on the total influence is $o(log n)$. However, both results become useless when the total influence of the function is $omega(log n)$. The only case in which this logarithmic barrier has been broken for an interesting class of functions was proved by Bourgain and Kalai, who focused on functions that are symmetric under large enough subgroups of $S_n$. In this paper, we build and improve on the techniques of the Bourgain-Kalai paper and establish new concentration results on the Fourier spectrum of Boolean functions with small total influence. Our results include: 1. A quantitative improvement of the Bourgain--Kalai result regarding the total influence of functions that are transitively symmetric. 2. A slightly weaker version of the Fourier--Entropy Conjecture of Friedgut and Kalai. This weaker version implies in particular that the Fourier spectrum of a constant variance, Boolean function $f$ is concentrated on $2^{O(I[f]log I[f])}$ characters, improving an earlier result of Friedgut. Removing the $log I[f]$ factor would essentially resolve the Fourier--Entropy Conjecture, as well as settle a conjecture of Mansour regarding the Fourier spectrum of polynomial size DNF formulas. Our concentration result has new implications in learning theory: it implies that the class of functions whose total influence is at most $K$ is agnostically learnable in time $2^{O(Klog K)}$, using membership queries.
A finite subset of a Euclidean space is called an $s$-distance set if there exist exactly $s$ values of the Euclidean distances between two distinct points in the set. In this paper, we prove that the maximum cardinality among all 5-distance sets in $mathbb{R}^3$ is 20, and every $5$-distance set in $mathbb{R}^3$ with $20$ points is similar to the vertex set of a regular dodecahedron.
In this paper we introduce the concept of clique disjoint edge sets in graphs. Then, for a graph $G$, we define the invariant $eta(G)$ as the maximum size of a clique disjoint edge set in $G$. We show that the regularity of the binomial edge ideal of $G$ is bounded above by $eta(G)$. This, in particular, settles a conjecture on the regularity of binomial edge ideals in full generality.
Let $P_{n}$ be a set of $n$ points, including the origin, in the unit square $U = [0,1]^2$. We consider the problem of constructing $n$ axis-parallel and mutually disjoint rectangles inside $U$ such that the bottom-left corner of each rectangle coincides with a point in $P_{n}$ and the total area covered by the rectangles is maximized cite{ibmpuzzle}, cite{Winkler2007}, cite{Winkler2010a}, cite{Winkler2010b}. The longstanding conjecture has been that at least half of $U$ can be covered when such rectangles are properly placed. In this paper, we give an existential proof of the conjecture.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
