Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userHigh dimensional expansion using zig-zag product
111
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We wish to renew the discussion over recent combinatorial structures that are 3-uniform hypergraph expanders, viewing them in a more general perspective, shedding light on a previously unknown relation to the zig-zag product. We do so by introducing a new structure called triplet structure, that maintains the same local environment around each vertex. The structure is expected to yield, in some cases, a bounded family of hypergraph expanders whose 2-dimensional random walk converges. We have applied the results obtained here to several known constructions, obtaining a better expansion rate than previously known. Namely, we did so in the case of Conlons construction and the $S=[1,1,0]$ construction by Chapman, Linal and Peled.
rate research
Read More
The zig-zag symmetry transition is a phase transition in 1D quantum wires, in which a Wigner lattice of electrons transitions to two staggered lattices. Previous studies model this transition as a Luttinger liquid coupled to a Majorana fermion. The model exhibits interesting RG flows, involving quenching of velocities in subsectors of the theory. We suggest an extension of the model which replaces the Majorana fermion by a more general CFT; this includes an experimentally realizable case with two Majorana fermions. We analyse the RG flow both in field theory and using AdS/CFT techniques in the large central charge limit of the CFT. The model has a rich phase structure with new qualitative features, already in the two Majorana fermion case. The AdS/CFT calculation involves considering back reaction in space-time to capture subleading effects.
When can $t$ terminal pairs in an $m times n$ grid be connected by $t$ vertex-disjoint paths that cover all vertices of the grid? We prove that this problem is NP-complete. Our hardness result can be compared to two previous NP-hardness proofs: Lynchs 1975 proof without the ``cover all vertices constraint, and Kotsuma and Takenagas 2010 proof when the paths are restricted to have the fewest possible corners within their homotopy class. The latter restriction is a common form of the famous Nikoli puzzle emph{Numberlink}; our problem is another common form of Numberlink, sometimes called emph{Zig-Zag Numberlink} and popularized by the smartphone app emph{Flow Free}.
We prove the unimodality of the Ehrhart $delta$-polynomial of the chain polytope of the zig-zag poset, which was conjectured by Kirillov. First, based on a result due to Stanley, we show that this polynomial coincides with the $W$-polynomial for the zig-zag poset with some natural labeling. Then, its unimodality immediately follows from a result of Gasharov, which states that the $W$-polynomials of naturally labeled graded posets of rank $1$ or $2$ are unimodal.
The Frank-Wolfe algorithm has regained much interest in its use in structurally constrained machine learning applications. However, one major limitation of the Frank-Wolfe algorithm is the slow local convergence property due to the zig-zagging behavior. We observe that this zig-zagging phenomenon can be viewed as an artifact of discretization, as when the method is viewed as an Euler discretization of a continuous time flow, that flow does not zig-zag. For this reason, we propose multistep Frank-Wolfe variants based on discretizations of the same flow whose truncation errors decay as $O(Delta^p)$, where $p$ is the methods order. We observe speedups using these variants, but at a cost of extra gradient calls per iteration. However, because the multistep methods present better search directions, we show that they are better able to leverage line search and momentum speedups.
The phase diagram of a frustrated spin-$S$ zig-zag ladder is studied through different numerical and analytical methods. We show that for arbitrary $S$, there is a family of Hamiltonians for which a fully-dimerized state is an exact ground state, being the Majumdar-Ghosh point a particular member of the family. We show that the system presents a transition between a dimerized phase to a Neel-like phase for $S=1/2$, and spiral phases can appear for large $S$. The phase diagram is characterized by means of a generalization of the usual Mean Field Approximation (MFA). The novelty in the present implementation is to consider the strongest coupled sites as the unit cell. The gap and the excitation spectrum is analyzed through the Random Phase Approximation (RPA). Also, a perturbative treatment to obtain the critical points is discussed. Comparisons of the results with numerical methods like DMRG are also presented.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
