skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.


Title: Forbidding $K_{2,t}$ Traces in Triple Systems
Let $$H$$ and $$F$$ be hypergraphs. We say $$H$$ {\em contains $$F$$ as a trace} if there exists some set $$S \subseteq V(H)$$ such that $$H|_S:=\{E\cap S: E \in E(H)\}$$ contains a subhypergraph isomorphic to $$F$$. In this paper we give an upper bound on the number of edges in a $$3$$-uniform hypergraph that does not contain $$K_{2,t}$$ as a trace when $$t$$ is large. In particular, we show that $$\lim_{t\to \infty}\lim_{n\to \infty} \frac{\mathrm{ex}(n, \mathrm{Tr}_3(K_{2,t}))}{t^{3/2}n^{3/2}} = \frac{1}{6}.$$ Moreover, we show $$\frac{1}{2} n^{3/2} + o(n^{3/2}) \leqslant \mathrm{ex}(n, \mathrm{Tr}_3(C_4)) \leqslant \frac{5}{6} n^{3/2} + o(n^{3/2})$$.  more » « less
Award ID(s):
1902808
PAR ID:
10458414
Author(s) / Creator(s):
;
Date Published:
Journal Name:
The Electronic Journal of Combinatorics
Volume:
28
Issue:
2
ISSN:
1077-8926
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. 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 er-t 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
  2. null (Ed.)
    For integers $$n\ge 0$$, an iterated triangulation $$\mathrm{Tr}(n)$$ is defined recursively as follows: $$\mathrm{Tr}(0)$$ is the plane triangulation on three vertices and, for $$n\ge 1$$, $$\mathrm{Tr}(n)$$ is the plane triangulation obtained from the plane triangulation $$\mathrm{Tr}(n-1)$$ by, for each inner face $$F$$ of $$\mathrm{Tr}(n-1)$$, adding inside $$F$$ a new vertex and three edges joining this new vertex to the three vertices incident with $$F$$. In this paper, we show that there exists a 2-edge-coloring of $$\mathrm{Tr}(n)$$ such that $$\mathrm{Tr}(n)$$ contains no monochromatic copy of the cycle $$C_k$$ for any $$k\ge 5$$. As a consequence, the answer to one of two questions asked by Axenovich et al. is negative. We also determine the radius 2 graphs $$H$$ for which there exists $$n$$ such that every 2-edge-coloring of $$\mathrm{Tr}(n)$$ contains a monochromatic copy of $$H$$, extending a result of Axenovich et al. for radius 2 trees. 
    more » « less
  3. Abstract A conjecture of Alon, Krivelevich and Sudakov states that, for any graph $$F$$ , there is a constant $$c_F \gt 0$$ such that if $$G$$ is an $$F$$ -free graph of maximum degree $$\Delta$$ , then $$\chi\!(G) \leqslant c_F \Delta/ \log\!\Delta$$ . Alon, Krivelevich and Sudakov verified this conjecture for a class of graphs $$F$$ that includes all bipartite graphs. Moreover, it follows from recent work by Davies, Kang, Pirot and Sereni that if $$G$$ is $$K_{t,t}$$ -free, then $$\chi\!(G) \leqslant (t + o(1)) \Delta/ \log\!\Delta$$ as $$\Delta \to \infty$$ . We improve this bound to $$(1+o(1)) \Delta/\log\!\Delta$$ , making the constant factor independent of $$t$$ . We further extend our result to the DP-colouring setting (also known as correspondence colouring), introduced by Dvoล™รกk and Postle. 
    more » « less
  4. F or c e d at a f or a fl a p pi n g f oil e n er g y h ar v e st er wit h a cti v e l e a di n g e d g e m oti o n o p er ati n g i n t h e l o w r e d u c e d fr e q u e n c y r a n g e i s c oll e ct e d t o d et er mi n e h o w l e a di n g e d g e m oti o n aff e ct s e n er g y h ar v e sti n g p erf or m a n c e. T h e f oil pi v ot s a b o ut t h e mi dc h or d a n d o p er at e s i n t h e l o w r e d u c e d fr e q u e n c y r a n g e of ๐‘“๐‘“ ๐‘“๐‘“ / ๐‘ˆ๐‘ˆ โˆž = 0. 0 6 , 0. 0 8, a n d 0. 1 0 wit h ๐‘…๐‘… ๐‘…๐‘… = 2 0 ,0 0 0 โˆ’ 3 0 ,0 0 0 , wit h a pit c hi n g a m plit u d e of ๐œƒ๐œƒ 0 = 7 0 โˆ˜ , a n d a h e a vi n g a m plit u d e of โ„Ž 0 = 0. 5 ๐‘“๐‘“ . It i s f o u n d t h at l e a di n g e d g e m oti o n s t h at r e d u c e t h e eff e cti v e a n gl e of att a c k e arl y t h e str o k e w or k t o b ot h i n cr e a s e t h e lift f or c e s a s w ell a s s hift t h e p e a k lift f or c e l at er i n t h e fl a p pi n g str o k e. L e a di n g e d g e m oti o n s i n w hi c h t h e eff e cti v e a n gl e of att a c k i s i n cr e a s e d e arl y i n t h e str o k e s h o w d e cr e a s e d p erf or m a n c e. I n a d diti o n a di s cr et e v ort e x m o d el wit h v ort e x s h e d di n g at t h e l e a di n g e d g e i s i m pl e m e nt f or t h e m oti o n s st u di e d; it i s f o u n d t h at t h e m e c h a ni s m f or s h e d di n g at t h e l e a di n g e d g e i s n ot a d e q u at e f or t hi s p ar a m et er r a n g e a n d t h e m o d el c o n si st e ntl y o v er pr e di ct s t h e a er o d y n a mi c f or c e s. 
    more » « less
  5. A s a c om pl e men t t o da ta d edupli cat ion , de lta c om p ress i on fu r- t he r r edu c es t h e dat a vo l u m e by c o m pr e ssi n g n o n - dup li c a t e d ata chunk s r e l a t iv e to t h e i r s i m il a r chunk s (bas e chunk s). H ow ever, ex is t i n g p o s t - d e dup li c a t i o n d e l t a c o m pr e ssi o n a p- p ro a ches fo r bac kup s t or ag e e i t h e r su ffe r f ro m t h e l ow s i m - il a r i t y b e twee n m any de te c ted c hun ks o r m i ss so me po t e n - t i a l s i m il a r c hunks , o r su ffer f r om l ow (ba ckup and r es t ore ) th r oug hpu t du e t o extr a I/ Os f or r e a d i n g b a se c hun ks o r a dd a dd i t i on a l s e r v i c e - d i s r up t ive op e r a t i on s to b a ck up s ys t em s. I n t h i s pa p e r, w e pr opo se L oop D e l t a t o a dd ress the above - m e n t i on e d prob l e m s by an e nha nced em b e ddi n g d e l t a c o m p - r e ss i on sc heme i n d e dup li c a t i on i n a non - i n t ru s ive way. T h e e nha nce d d elt a c o mpr ess ion s che m e co m b in e s f our key t e c h - ni qu e s : (1) du a l - l o c a li t y - b a s e d s i m il a r i t y t r a c k i n g to d e t ect po t e n t i a l si m il a r chun k s b y e x p l o i t i n g both l o g i c a l and ph y - s i c a l l o c a li t y, ( 2 ) l o c a li t y - a wa r e pr e f e t c h i n g to pr efe tc h ba se c hun ks to a vo i d ex t ra I/ Os fo r r e a d i n g ba s e chun ks on t h e w r i t e p at h , (3) c a che -aware fil t e r to avo i d ext r a I/Os f or b a se c hunk s on t he read p at h, a nd (4) i nver sed de l ta co mpressi on t o perf orm de lt a co mpress i o n fo r d at a chunk s t hat a re o th e r wi se f o r b i dd e n to s er ve as ba se c hunk s by r ew r i t i n g t e c hn i qu e s d e s i g n e d t o i m p r ove r es t o re pe rf o rma nc e. E x p e r i m e n t a l re su lts indi ca te t hat L oop D e l t a i ncr ea se s t he c o m pr e ss i o n r a t i o by 1 .2410 .97 t i m e s on t op of d e dup li c a - t i on , wi t hou t no t a b l y a ffe c t i n g th e ba ck up th rou ghpu t, a nd i t i m p r ove s t he res to re p er fo r m an ce b y 1.23.57 t i m e 
    more » « less