Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userAsymptotic bounds on numbers of bent functions and partitions of the Boolean hypercube into linear and affine subspaces
43
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
The main result of the present paper is a new lower bound on the number of Boolean bent functions. This bound is based on a modification of the Maiorana--McFarland family of bent functions and recent progress in the estimation of the number of transversals in latin squares and hypercubes. In addition, we find the asymptotics of the logarithm of the numbers of partitions of the Boolean hypercube into $2$-dimensional linear and affine subspaces.
rate research
Read More
We show that if $fcolon S_n to {0,1}$ is $epsilon$-close to linear in $L_2$ and $mathbb{E}[f] leq 1/2$ then $f$ is $O(epsilon)$-close to a union of mostly disjoint cosets, and moreover this is sharp: any such union is close to linear. This constitutes a sharp Friedgut-Kalai-Naor theorem for the symmetric group. Using similar techniques, we show that if $fcolon S_n to mathbb{R}$ is linear, $Pr[f otin {0,1}] leq epsilon$, and $Pr[f = 1] leq 1/2$, then $f$ is $O(epsilon)$-close to a union of mostly disjoint cosets, and this is also sharp; and that if $fcolon S_n to mathbb{R}$ is linear and $epsilon$-close to ${0,1}$ in $L_infty$ then $f$ is $O(epsilon)$-close in $L_infty$ to a union of disjoint cosets.
A pebbling move on a graph removes two pebbles at a vertex and adds one pebble at an adjacent vertex. Rubbling is a version of pebbling where an additional move is allowed. In this new move, one pebble each is removed at vertices $v$ and $w$ adjacent to a vertex $u$, and an extra pebble is added at vertex $u$. A vertex is reachable from a pebble distribution if it is possible to move a pebble to that vertex using rubbling moves. The rubbling number is the smallest number $m$ needed to guarantee that any vertex is reachable from any pebble distribution of $m$ pebbles. The optimal rubbling number is the smallest number $m$ needed to guarantee a pebble distribution of $m$ pebbles from which any vertex is reachable. We give bounds for rubbling and optimal rubbling numbers. In particular, we find an upper bound for the rubbling number of $n$-vertex, diameter $d$ graphs, and estimates for the maximum rubbling number of diameter 2 graphs. We also give a sharp upper bound for the optimal rubbling number, and sharp upper and lower bounds in terms of the diameter.
We give some new bounds for the clique and independence numbers of a graph in terms of its eigenvalues.
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.
For each skew shape we define a nonhomogeneous symmetric function, generalizing a construction of Pak and Postnikov. In two special cases, we show that the coefficients of this function when expanded in the complete homogeneous basis are given in terms of the (reduced) type of $k$-divisible noncrossing partitions. Our work extends Haimans notion of a parking function symmetric function.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
