Search

A class of graphs is defined in which each vertex of a discrete torus is replaced by a Boolean hypercube in such a way that vertices in a fixed subset of each replacement cube are adjacent to corresponding vertices of a neighboring replacement cube. Bases of eigenvectors of the Laplacians of the resulting graphs are described in a manner suitable for quantifying the concentration of a low-spectrum vertex function on a single vertex replacement. Functions that optimize this concentration on these graphs can be regarded as analogues of Slepian prolate functions that optimize concentration of a bandlimited signal on an interval in the classical setting of the real line. Comparison to the case of a simple discrete cycle shows that replacement allows for higher concentration. [ABSTRACT FROM AUTHOR]

We prove a discrete analogue of the Poisson summation formula. [ABSTRACT FROM AUTHOR]

In this article we obtain for d ≥ 3 an approximation of the zero-average Gaussian free field on the discrete d -dimensional torus of large side length N by the Gaussian free field on Z d , valid in boxes of roughly side length N − N δ with δ ∈ (1 ∕ 2 , 1). As an implication, the level sets of the zero-average Gaussian free field on the torus can be approximated by the level sets of the Gaussian free field on Z d. This leads to a series of applications related to level-set percolation. [ABSTRACT FROM AUTHOR]

We present a detailed probabilistic and structural analysis of the set of weighted homomorphisms from the discrete torus Z m n , where m is even, to any fixed graph: we show that the corresponding probability distribution on such homomorphisms is close to a distribution defined constructively as a certain random perturbation of some dominant phase. This has several consequences, including solutions (in a strong form) to conjectures of Engbers and Galvin and a conjecture of Kahn and Park. Special cases include sharp asymptotics for the number of independent sets and the number of proper q -colourings of Z m n (so in particular, the discrete hypercube). We give further applications to the study of height functions and (generalised) rank functions on the discrete hypercube and disprove a conjecture of Kahn and Lawrenz. For the proof we combine methods from statistical physics, entropy and graph containers and exploit isoperimetric and algebraic properties of the torus. [ABSTRACT FROM AUTHOR]

Let Z be the set of integers and Zl be the set of integers modulo l. A set L⊆T=Zl1×Zl2×⋯×Zlm is called a line if there exist a,b∈T such that L={a+tb∈T:t∈Z}. A set X⊆T is called a no-three-in-line set if |X∩L|≤2 for all the lines L in T. The maximum size of a no-three-in-line set is denoted by τT. Let m≥2 and k1,k2,…,km be positive integers such that gcd(ki,kj)=1 for all i, j with i≠j. In this paper, we will show that τZk1n×Zk2n×⋯×Zkmn≤2nm-1.We will give sufficient conditions for which the equality holds. When k1=k2=⋯=km=1 and n=pl where p is a prime and l≥1 is an integer, we will show that equality holds if and only if p=2 and l=1, i.e., τZpl×Zpl×⋯×Zpl=2pl(m-1) if and only if p=2 and l=1. [ABSTRACT FROM AUTHOR]

In this paper we show that at most 2 gcd ( m , n ) points can be placed with no three in a line on an m × n discrete torus. In the situation when gcd ( m , n ) is a prime, we completely solve the problem. [ABSTRACT FROM AUTHOR]

This paper considers an algebraic method of digital images processing, based on the representation of images as functions on 'finite complex planes' called complex discrete tori. Properties of such tori are studied; in particular, the concept of complex rotation of a digital image is introduced. The concept of modular logarithm is introduced and used to define a new invertible discrete transform called modular Mellin transform. Next, the modular Fourier-Mellin transform, which is invariant under circular shifts, scaling, and complex rotations of digital images, is defined. [ABSTRACT FROM AUTHOR]

Abstract: For graphs G and H, an H-coloring of G is a function from the vertices of G to the vertices of H that preserves adjacency. H-colorings encode graph theory notions such as independent sets and proper colorings, and are a natural setting for the study of hard-constraint models in statistical physics. We study the set of H-colorings of the even discrete torus , the graph on vertex set (m even) with two strings adjacent if they differ by 1 (mod m) on one coordinate and agree on all others. This is a bipartite graph, with bipartition classes and . In the case the even discrete torus is the discrete hypercube or Hamming cube , the usual nearest neighbor graph on . We obtain, for any H and fixed m, a structural characterization of the space of H-colorings of . We show that it may be partitioned into an exceptional subset of negligible size (as d grows) and a collection of subsets indexed by certain pairs , with each H-coloring in the subset indexed by having all but a vanishing proportion of vertices from mapped to vertices from A, and all but a vanishing proportion of vertices from mapped to vertices from B. This implies a long-range correlation phenomenon for uniformly chosen H-colorings of with m fixed and d growing. The special pairs are characterized by every vertex in A being adjacent to every vertex in B, and having maximal subject to this condition. Our main technical result is an upper bound on the probability, for an arbitrary edge uv of , that in a uniformly chosen H-coloring f of the pair is not one of these special pairs (where indicates neighborhood). Our proof proceeds through an analysis of the entropy of f, and extends an approach of Kahn, who had considered the case of and H a doubly infinite path. All our results generalize to a natural weighted model of H-colorings. [Copyright &y& Elsevier]

The paper is devoted to estimates of the spanning tree congestion for grid graphs and discrete toruses of dimensions two and three. [ABSTRACT FROM AUTHOR]

We present a simple proof of the result published by Karakhanyan [Doklady AN Arm. SSR, LXXIV (1982), pp. 61–65] and Riordan [SIAM J. Discrete Math., 11 (1998), pp. 110—127] concerning the vertex–isoperimetric problem on the n–dimensional torus. The proof method is a reduction of this problem to a similar problem on some (2n)–dimensional grid, for which a solution is known [B. Bollob'as and I. Leader, J. Combin. Theory, A–56 (1991), pp. 47–62]. We also simplify and clarify the structure of the involved isoperimetric order. [ABSTRACT FROM AUTHOR]

The even discrete torus Tn(k1, …, kn) is the graph on (Z/k1Z) × … × (Z/knZ), where each ki is even and x = (x1, …, xn) is joined to y = (y1, …,yn) if for some i we have xi = yi ± 1 and xj = yj for all j ≠ i. The main aim of this paper is to describe an ordering on the even discrete torus whose initial segments give a best possible isoperimetric inequality. This extends the partial solution of Bollobás and Leader [SIAM J. Discrete Math., 3 (1990), pp. 32-37] to a problem posed by Wang and Wang [SIAM J. Appl. Math., 33 (1977), pp. 55-59]. [ABSTRACT FROM AUTHOR]

Let (Cdm ∞ denote the graph whose set of vertices is Zdm in which two distinct vertices are adjacent iff in each coordinate either they are equal or they differ, modulo m, by at most 1. Bollobás, Kindler, Leader, and O'Donaell proved that the minimum possible cardinality of a set of vertices of (Cdm) ∞ whose deletion destroys all topologically nontrivial cycles is md - (m - 1)d. We present a short proof of this result, using the Brunn-Minkowski inequality, and also show that the bound can be achieved only by selecting a value ξi in each coordinate i. 1 ≤ i ≤ d, and by keeping only the vertices whose ith coordinate is not ξi for all i. [ABSTRACT FROM AUTHOR]

Let τ m , n denote the maximal number of points on the discrete torus (discrete toric grid) of sizes m × n with no three collinear points. The value τ m , n is known for the case where gcd (m , n) is prime. It is also known that τ m , n ≤ 2 gcd (m , n). In this paper we generalize some of the known tools for determining τ m , n and also show some new. Using these tools we prove that the sequence (τ z , n) n ∈ N is periodic for all fixed z > 1. In general, we do not know the period; however, if z = p a for p prime, then we can bound it. We prove that τ p a , p (a − 1) p + 2 = 2 p a which implies that the period for the sequence is p b , where b is at most (a − 1) p + 2. [ABSTRACT FROM AUTHOR]