More Like this

1. Triangle-degrees in graphs and tetrahedron coverings in 3-graphs

   https://doi.org/10.1017/S0963548320000061  

   Falgas-Ravry, Victor; Markström, Klas; Zhao, Yi (March 2021, Combinatorics, Probability and Computing)

   null (Ed.)

   Abstract We investigate a covering problem in 3-uniform hypergraphs (3-graphs): Given a 3-graph F , what is c 1 ( n , F ), the least integer d such that if G is an n -vertex 3-graph with minimum vertex-degree $$\delta_1(G)>d$$ then every vertex of G is contained in a copy of F in G ? We asymptotically determine c 1 ( n , F ) when F is the generalized triangle $$K_4^{(3)-}$$ , and we give close to optimal bounds in the case where F is the tetrahedron $$K_4^{(3)}$$ (the complete 3-graph on 4 vertices). This latter problem turns out to be a special instance of the following problem for graphs: Given an n -vertex graph G with $m> n^2/4$ edges, what is the largest t such that some vertex in G must be contained in t triangles? We give upper bound constructions for this problem that we conjecture are asymptotically tight. We prove our conjecture for tripartite graphs, and use flag algebra computations to give some evidence of its truth in the general case. 

   more » « less
2. The Positive Tropical Grassmannian, the Hypersimplex, and the m = 2 Amplituhedron

   https://doi.org/10.1093/imrn/rnad010  

   Łukowski, Tomasz; Parisi, Matteo; Williams, Lauren K (March 2023, International Mathematics Research Notices)

   Abstract The positive Grassmannian $$Gr^{\geq 0}_{k,n}$$ is a cell complex consisting of all points in the real Grassmannian whose Plücker coordinates are non-negative. In this paper we consider the image of the positive Grassmannian and its positroid cells under two different maps: the moment map$$\mu $$ onto the hypersimplex [ 31] and the amplituhedron map$$\tilde{Z}$$ onto the amplituhedron [ 6]. For either map, we define a positroid dissection to be a collection of images of positroid cells that are disjoint and cover a dense subset of the image. Positroid dissections of the hypersimplex are of interest because they include many matroid subdivisions; meanwhile, positroid dissections of the amplituhedron can be used to calculate the amplituhedron’s ‘volume’, which in turn computes scattering amplitudes in $$\mathcal{N}=4$$ super Yang-Mills. We define a map we call T-duality from cells of $$Gr^{\geq 0}_{k+1,n}$$ to cells of $$Gr^{\geq 0}_{k,n}$$ and conjecture that it induces a bijection from positroid dissections of the hypersimplex $$\Delta _{k+1,n}$$ to positroid dissections of the amplituhedron $$\mathcal{A}_{n,k,2}$$; we prove this conjecture for the (infinite) class of BCFW dissections. We note that T-duality is particularly striking because the hypersimplex is an $(n-1)$-dimensional polytope while the amplituhedron $$\mathcal{A}_{n,k,2}$$ is a $2k$-dimensional non-polytopal subset of the Grassmannian $$Gr_{k,k+2}$$. Moreover, we prove that the positive tropical Grassmannian is the secondary fan for the regular positroid subdivisions of the hypersimplex, and prove that a matroid polytope is a positroid polytope if and only if all 2D faces are positroid polytopes. Finally, toward the goal of generalizing T-duality for higher $$m$$, we define the momentum amplituhedron for any even $$m$$. 

   more » « less
3. Arbitrarily slow decay in the Möbius disjointness conjecture

   https://doi.org/10.1017/etds.2022.61  

   ALGOM, AMIR; WANG, ZHIREN (September 2023, Ergodic Theory and Dynamical Systems)

   Abstract Sarnak’s Möbius disjointness conjecture asserts that for any zero entropy dynamical system $(X,T)$ , $$({1}/{N})\! \sum _{n=1}^{N}\! f(T^{n} x) \mu (n)= o(1)$$ for every $$f\in \mathcal {C}(X)$$ and every $$x\in X$$ . We construct examples showing that this $o(1)$ can go to zero arbitrarily slowly. In fact, our methods yield a more general result, where in lieu of $$\mu (n)$$ , one can put any bounded sequence $$a_{n}$$ such that the Cesàro mean of the corresponding sequence of absolute values does not tend to zero. Moreover, in our construction, the choice of x depends on the sequence $$a_{n}$$ but $(X,T)$ does not. 

   more » « less
4. An Ore-Type Condition for Hamiltonicity in Tough Graphs and the Extremal Examples

   https://doi.org/10.37236/12483  

   Sanka, Masahiro; Shan, Songling (January 2024, The Electronic Journal of Combinatorics)

   Let $$G$$ be a $$t$$-tough graph on $$n\ge 3$$ vertices for some $t>0$. It was shown by Bauer et al. in 1995 that if the minimum degree of $$G$$ is greater than $$\frac{n}{t+1}-1$$, then $$G$$ is hamiltonian. In terms of Ore-type hamiltonicity conditions, the problem was only studied when $$t$$ is between 1 and 2, and recently the second author proved a general result. The result states that if the degree sum of any two nonadjacent vertices of $$G$$ is greater than $$\frac{2n}{t+1}+t-2$$, then $$G$$ is hamiltonian. It was conjectured in the same paper that the $+t$ in the bound $$\frac{2n}{t+1}+t-2$$ can be removed. Here we confirm the conjecture. The result generalizes the result by Bauer, Broersma, van den Heuvel, and Veldman. Furthermore, we characterize all $$t$$-tough graphs $$G$$ on $$n\ge 3$$ vertices for which $$\sigma_2(G) = \frac{2n}{t+1}-2$$ but $$G$$ is non-hamiltonian. 

   more » « less
5. The spread of a finite group

   https://doi.org/doi.org/10.4007/annals.2021.193.2.5  

   Burness, Tim; Guralnick, Robert; Harper, Scott (January 2021, Annals of mathematics)

   null (Ed.)

   A group G is said to be 3/2-generated if every nontrivial element belongs to a generating pair. It is easy to see that if G has this property, then every proper quotient of G is cyclic. In this paper we prove that the converse is true for finite groups, which settles a conjecture of Breuer, Guralnick and Kantor from 2008. In fact, we prove a much stronger result, which solves a problem posed by Brenner and Wiegold in 1975. Namely, if G is a finite group and every proper quotient of G is cyclic, then for any pair of nontrivial elements x1, x2 ϵ G, there exists y ϵ G such that G = ⟨x1, y⟩ = ⟨x2, y⟩. In other words, s(G) ⩾ 2, where s(G) is the spread of G. Moreover, if u(G) denotes the more restrictive uniform spread of G, then we can completely characterise the finite groups G with u(G) = 0 and u(G) = 1. To prove these results, we first establish a reduction to almost simple groups. For simple groups, the result was proved by Guralnick and Kantor in 2000 using probabilistic methods, and since then the almost simple groups have been the subject of several papers. By combining our reduction theorem and this earlier work, it remains to handle the groups with socle an exceptional group of Lie type, and this is the case we treat in this paper. 

   more » « less