We prove a new generalization of the higherorder Cheeger inequality for partitioning with buffers. Consider a graph G=(V,E). The buffered expansion of a set S⊆V with a buffer B⊆V∖S is the edge expansion of S after removing all the edges from set S to its buffer B. An εbuffered kpartitioning is a partitioning of a graph into disjoint components Pi and buffers Bi, in which the size of buffer Bi for Pi is small relative to the size of Pi: Bi≤εPi. The buffered expansion of a buffered partition is the maximum of buffered expansions of the k sets Pi with buffers Bi. Let hk,εG be the buffered expansion of the optimal εbuffered kpartitioning, then for every δ>0,
hk,εG≤Oδ(1)⋅(logkε)⋅λ⌊(1+δ)k⌋, where λ⌊(1+δ)k⌋ is the ⌊(1+δ)k⌋th smallest eigenvalue of the normalized Laplacian of G. Our inequality is constructive and avoids the ``squareroot loss'' that is present in the standard Cheeger inequalities (even for k=2). We also provide a complementary lower bound, and a novel generalization to the setting with arbitrary vertex weights and edge costs. Moreover our result implies and generalizes the standard higherorder Cheeger inequalities and another recent Cheegertype inequality by Kwok, Lau, and Lee (2017) involving robust vertex expansion.
more »
« less
Some bounds arising from a polynomial ideal associated to any $t$design
We consider ordered pairs (X,B) where X is a finite set of size v and B is some collection of kelement subsets of X such that every telement subset of X is contained in exactly λ "blocks'' b ∈B for some fixed λ. We represent each block b by a zeroone vector c_b of length v and explore the ideal I(B) of polynomials in v variables with complex coefficients which vanish on the set { c_b ∣ b ∈ B}. After setting up the basic theory, we investigate two parameters related to this ideal: γ1(B) is the smallest degree of a nontrivial polynomial in the ideal I(B) and γ2(B) is the smallest integer s such that I(B) is generated by a set of polynomials of degree at most s. We first prove the general bounds t/2 < γ1(B) ≤ γ2(B) ≤ k. Examining important families of examples, we find that, for symmetric 2designs and Steiner systems, we have γ2(B) ≤ t. But we expect γ2(B) to be closer to k for less structured designs and we indicate this by constructing infinitely many triple systems satisfying γ2(B) = k.
more »
« less
 Award ID(s):
 1808376
 NSFPAR ID:
 10288400
 Date Published:
 Journal Name:
 Journal of Algebra Combinatorics Discrete Structures and Applications
 ISSN:
 2148838X
 Page Range / eLocation ID:
 163 to 183
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this


Byrka, Jaroslaw ; Meka, Raghu (Ed.)In this work, we prove new relations between the bias of multilinear forms, the correlation between multilinear forms and lower degree polynomials, and the rank of tensors over F₂. We show the following results for multilinear forms and tensors. Correlation bounds. We show that a random dlinear form has exponentially low correlation with lowdegree polynomials. More precisely, for d = 2^{o(k)}, we show that a random dlinear form f(X₁,X₂, … , X_d) : (F₂^{k}) ^d → F₂ has correlation 2^{k(1o(1))} with any polynomial of degree at most d/2 with high probability. This result is proved by giving nearoptimal bounds on the bias of a random dlinear form, which is in turn proved by giving nearoptimal bounds on the probability that a sum of t random ddimensional rank1 tensors is identically zero. Tensor rank vs Bias. We show that if a 3dimensional tensor has small rank then its bias, when viewed as a 3linear form, is large. More precisely, given any 3dimensional tensor T: [k]³ → F₂ of rank at most t, the bias of the 3linear form f_T(X₁, X₂, X₃) : = ∑_{(i₁, i₂, i₃) ∈ [k]³} T(i₁, i₂, i₃)⋅ X_{1,i₁}⋅ X_{2,i₂}⋅ X_{3,i₃} is at least (3/4)^t. This bias vs tensorrank connection suggests a natural approach to proving nontrivial tensorrank lower bounds. In particular, we use this approach to give a new proof that the finite field multiplication tensor has tensor rank at least 3.52 k, which is the best known rank lower bound for any explicit tensor in three dimensions over F₂. Moreover, this relation between bias and tensor rank holds for ddimensional tensors for any fixed d.more » « less

null (Ed.)Relying on the classical second moment formula of Rogers we give an effective asymptotic formula for the number of integer vectors v in a ball of radius t, with value Q(v) in a shrinking interval of size t^{−λ}, that is valid for almost all indefinite quadratic forms in n variables for any λ
more » « less 
Abstract Let f : ℙ 1 → ℙ 1 {f:\mathbb{P}^{1}\to\mathbb{P}^{1}} be a map of degree > 1 {>1} defined over a function field k = K ( X ) {k=K(X)} , where K is a number field and X is a projective curve over K . For each point a ∈ ℙ 1 ( k ) {a\in\mathbb{P}^{1}(k)} satisfying a dynamical stability condition, we prove that the Call–Silverman canonical height for specialization f t {f_{t}} at point a t {a_{t}} , for t ∈ X ( ℚ ¯ ) {t\in X(\overline{\mathbb{Q}})} outside a finite set, induces a Weil height on the curve X ; i.e., we prove the existence of a ℚ {\mathbb{Q}} divisor D = D f , a {D=D_{f,a}} on X so that the function t ↦ h ^ f t ( a t )  h D ( t ) {t\mapsto\hat{h}_{f_{t}}(a_{t})h_{D}(t)} is bounded on X ( ℚ ¯ ) {X(\overline{\mathbb{Q}})} for any choice of Weil height associated to D . We also prove a local version, that the local canonical heights t ↦ λ ^ f t , v ( a t ) {t\mapsto\hat{\lambda}_{f_{t},v}(a_{t})} differ from a Weil function for D by a continuous function on X ( ℂ v ) {X(\mathbb{C}_{v})} , at each place v of the number field K . These results were known for polynomial maps f and all points a ∈ ℙ 1 ( k ) {a\in\mathbb{P}^{1}(k)} without the stability hypothesis,[21, 14],and for maps f that are quotients of endomorphisms of elliptic curves E over k and all points a ∈ ℙ 1 ( k ) {a\in\mathbb{P}^{1}(k)} . [32, 29].Finally, we characterize our stability condition in terms of the geometry of the induced map f ~ : X × ℙ 1 ⇢ X × ℙ 1 {\tilde{f}:X\times\mathbb{P}^{1}\dashrightarrow X\times\mathbb{P}^{1}} over K ; and we prove the existence of relative Néron models for the pair ( f , a ) {(f,a)} , when a is a Fatou point at a place γ of k , where the local canonical height λ ^ f , γ ( a ) {\hat{\lambda}_{f,\gamma}(a)} can be computed as an intersection number.more » « less

A gr e at d e al of i nt er e st s urr o u n d s t h e u s e of tr a n s cr a ni al dir e ct c urr e nt sti m ul ati o n (t D C S) t o a u g m e nt c o g niti v e tr ai ni n g. H o w e v er, eff e ct s ar e i n c o n si st e nt a cr o s s st u di e s, a n d m et aa n al yti c e vi d e n c e i s mi x e d, e s p e ci all y f o r h e alt h y, y o u n g a d ult s. O n e m aj or s o ur c e of t hi s i n c o n si st e n c y i s i n di vi d u al diff er e n c e s a m o n g t h e p arti ci p a nt s, b ut t h e s e diff er e n c e s ar e r ar el y e x a mi n e d i n t h e c o nt e xt of c o m bi n e d tr ai ni n g/ sti m ul ati o n st u di e s. I n a d diti o n, it i s u n cl e ar h o w l o n g t h e eff e ct s of sti m ul ati o n l a st, e v e n i n s u c c e s sf ul i nt er v e nti o n s. S o m e st u di e s m a k e u s e of f oll o w u p a s s e s s m e nt s, b ut v er y f e w h a v e m e a s ur e d p erf or m a n c e m or e t h a n a f e w m o nt hs aft er a n i nt er v e nti o n. H er e, w e utili z e d d at a fr o m a pr e vi o u s st u d y of t D C S a n d c o g niti v e tr ai ni n g [ A u, J., K at z, B., B u s c h k u e hl, M., B u n arj o, K., S e n g er, T., Z a b el, C., et al. E n h a n ci n g w or ki n g m e m or y tr ai ni n g wit h tr a n scr a ni al dir e ct c urr e nt sti m ul ati o n. J o u r n al of C o g niti v e N e u r os ci e n c e, 2 8, 1 4 1 9 – 1 4 3 2, 2 0 1 6] i n w hi c h p arti ci p a nts tr ai n e d o n a w or ki n g m e m or y t as k o v er 7 d a y s w hil e r e c ei vi n g a cti v e or s h a m t D C S. A n e w, l o n g ert er m f oll o w u p t o a ss es s l at er p erf or m a n c e w a s c o n d u ct e d, a n d a d diti o n al p arti ci p a nt s w er e a d d e d s o t h at t h e s h a m c o n diti o n w a s b ett er p o w er e d. W e a s s e s s e d b a s eli n e c o g niti v e a bilit y, g e n d er, tr ai ni n g sit e, a n d m oti v ati o n l e v el a n d f o u n d si g nifi c a nt i nt er a cti o ns b et w e e n b ot h b as eli n e a bilit y a n d m oti v ati o n wit h c o n diti o n ( a cti v e or s h a m) i n m o d els pr e di cti n g tr ai ni n g g ai n. I n a d diti o n, t h e i m pr o v e m e nt s i n t h e a cti v e c o nditi o n v er s u s s h a m c o n diti o n a p p e ar t o b e st a bl e e v e n a s l o n g a s a y e ar aft er t h e ori gi n al i nt er v e nti o n. ■more » « less