Expansion and random walks in $\mathrm {SL}_d(\mathbb {Z}/p^n\mathbb {Z})$: I

Jean Bourgain; Alex Gamburd

Displaying similar documents to “Expansion and random walks in ${SL}_{d} (ℤ / p^{n} ℤ)$ : I”

Expansion in $S L_{d} (𝒪_{K} / I)$ , $I$ square-free

Péter P. Varjú (2012)

Journal of the European Mathematical Society

Similarity:

Let $S$ be a fixed symmetric finite subset of $S L_{d} (𝒪_{K})$ that generates a Zariski dense subgroup of $S L_{d} (𝒪_{K})$ when we consider it as an algebraic group over $m a t h b b Q$ by restriction of scalars. We prove that the Cayley graphs of $S L_{d} (𝒪_{K} / I)$ with respect to the projections of $S$ is an expander family if $I$ ranges over square-free ideals of $𝒪_{K}$ if $d = 2$ and $K$ is an arbitrary numberfield, or if $d = 3$ and $K = ℚ$ .

Intrinsic linking and knotting are arbitrarily complex

Erica Flapan, Blake Mellor, Ramin Naimi (2008)

Fundamenta Mathematicae

Similarity:

We show that, given any n and α, any embedding of any sufficiently large complete graph in ℝ³ contains an oriented link with components Q₁, ..., Qₙ such that for every i ≠ j, $| l k (Q_{i}, Q_{j}) | \geq α$ and $| a ₂ (Q_{i}) | \geq α$ , where $a ₂ (Q_{i})$ denotes the second coefficient of the Conway polynomial of $Q_{i}$ .

Remarks on $D$ -integral complete multipartite graphs

Pavel Híc, Milan Pokorný (2016)

Czechoslovak Mathematical Journal

Similarity:

A graph is called distance integral (or $D$ -integral) if all eigenvalues of its distance matrix are integers. In their study of $D$ -integral complete multipartite graphs, Yang and Wang (2015) posed two questions on the existence of such graphs. We resolve these questions and present some further results on $D$ -integral complete multipartite graphs. We give the first known distance integral complete multipartite graphs $K_{p_{1}, p_{2}, p_{3}}$ with $p_{1} < p_{2} < p_{3}$ , and $K_{p_{1}, p_{2}, p_{3}, p_{4}}$ with $p_{1} < p_{2} < p_{3} < p_{4}$ , as well as the infinite classes of distance integral...

Note on a conjecture for the sum of signless Laplacian eigenvalues

Xiaodan Chen, Guoliang Hao, Dequan Jin, Jingjian Li (2018)

Czechoslovak Mathematical Journal

Similarity:

For a simple graph $G$ on $n$ vertices and an integer $k$ with $1 \leq k \leq n$ , denote by $𝒮_{k}^{+} (G)$ the sum of $k$ largest signless Laplacian eigenvalues of $G$ . It was conjectured that $𝒮_{k}^{+} (G) \leq e (G) + (\binom{k + 1}{2})$ , where $e (G)$ is the number of edges of $G$ . This conjecture has been proved to be true for all graphs when $k \in {1, 2, n - 1, n}$ , and for trees, unicyclic graphs, bicyclic graphs and regular graphs (for all $k$ ). In this note, this conjecture is proved to be true for all graphs when $k = n - 2$ , and for some new classes of graphs.

A note on sumsets of subgroups in $ℤ *_{p}$

Derrick Hart (2013)

Acta Arithmetica

Similarity:

Let A be a multiplicative subgroup of $ℤ *_{p}$ . Define the k-fold sumset of A to be $k A = x_{1} + . . . + x_{k} : x_{i} \in A, 1 \leq i \leq k$ . We show that $6 A \supseteq ℤ *_{p}$ for $| A | > p^{11 / 23 + ϵ}$ . In addition, we extend a result of Shkredov to show that ${| 2 A | ≫ | A |}^{8 / 5 - ϵ}$ for $| A | ≪ p^{5 / 9}$ .

Generalized connectivity of some total graphs

Yinkui Li, Yaping Mao, Zhao Wang, Zongtian Wei (2021)

Czechoslovak Mathematical Journal

Similarity:

We study the generalized $k$ -connectivity $κ_{k} (G)$ as introduced by Hager in 1985, as well as the more recently introduced generalized $k$ -edge-connectivity $λ_{k} (G)$ . We determine the exact value of $κ_{k} (G)$ and $λ_{k} (G)$ for the line graphs and total graphs of trees, unicyclic graphs, and also for complete graphs for the case $k = 3$ .

Edit distance measure for graphs

Tomasz Dzido, Krzysztof Krzywdziński (2015)

Czechoslovak Mathematical Journal

Similarity:

In this paper, we investigate a measure of similarity of graphs similar to the Ramsey number. We present values and bounds for $g (n, l)$ , the biggest number $k$ guaranteeing that there exist $l$ graphs on $n$ vertices, each two having edit distance at least $k$ . By edit distance of two graphs $G$ , $F$ we mean the number of edges needed to be added to or deleted from graph $G$ to obtain graph $F$ . This new extremal number $g (n, l)$ is closely linked to the edit distance of graphs. Using probabilistic methods we show...

Embedding products of graphs into Euclidean spaces

Mikhail Skopenkov (2003)

Fundamenta Mathematicae

Similarity:

For any collection of graphs $G ₁, . . ., G_{N}$ we find the minimal dimension d such that the product $G ₁ \times . . . \times G_{N}$ is embeddable into $ℝ^{d}$ (see Theorem 1 below). In particular, we prove that (K₅)ⁿ and $(K_{3, 3}) ⁿ$ are not embeddable into $ℝ^{2 n}$ , where K₅ and $K_{3, 3}$ are the Kuratowski graphs. This is a solution of a problem of Menger from 1929. The idea of the proof is a reduction to a problem from so-called Ramsey link theory: we show that any embedding $L k O \to S^{2 n - 1}$ , where O is a vertex of (K₅)ⁿ, has a pair of linked (n-1)-spheres.

On distinguishing and distinguishing chromatic numbers of hypercubes

Werner Klöckl (2008)

Discussiones Mathematicae Graph Theory

Similarity:

The distinguishing number D(G) of a graph G is the least integer d such that G has a labeling with d colors that is not preserved by any nontrivial automorphism. The restriction to proper labelings leads to the definition of the distinguishing chromatic number $χ_{D} (G)$ of G. Extending these concepts to infinite graphs we prove that $D (Q_{ℵ} ₀) = 2$ and $χ_{D} (Q_{ℵ} ₀) = 3$ , where $Q_{ℵ} ₀$ denotes the hypercube of countable dimension. We also show that $χ_{D} (Q ₄) = 4$ , thereby completing the investigation of finite hypercubes with respect to $χ_{D}$ . Our...

On $R$ -conjugate-permutability of Sylow subgroups

Xianhe Zhao, Ruifang Chen (2016)

Czechoslovak Mathematical Journal

Similarity:

A subgroup $H$ of a finite group $G$ is said to be conjugate-permutable if $H H^{g} = H^{g} H$ for all $g \in G$ . More generaly, if we limit the element $g$ to a subgroup $R$ of $G$ , then we say that the subgroup $H$ is $R$ -conjugate-permutable. By means of the $R$ -conjugate-permutable subgroups, we investigate the relationship between the nilpotence of $G$ and the $R$ -conjugate-permutability of the Sylow subgroups of $A$ and $B$ under the condition that $G = A B$ , where $A$ and $B$ are subgroups of $G$ . Some results known in the literature are improved...

Every $2$ -group with all subgroups normal-by-finite is locally finite

Enrico Jabara (2018)

Czechoslovak Mathematical Journal

Similarity:

A group $G$ has all of its subgroups normal-by-finite if $H / H_{G}$ is finite for all subgroups $H$ of $G$ . The Tarski-groups provide examples of $p$ -groups ( $p$ a “large” prime) of nonlocally finite groups in which every subgroup is normal-by-finite. The aim of this paper is to prove that a $2$ -group with every subgroup normal-by-finite is locally finite. We also prove that if $| H / H_{G} | \leq 2$ for every subgroup $H$ of $G$ , then $G$ contains an Abelian subgroup of index at most $8$ .

Persistency in the Traveling Salesman Problem on Halin graphs

Vladimír Lacko (2000)

Discussiones Mathematicae Graph Theory

Similarity:

For the Traveling Salesman Problem (TSP) on Halin graphs with three types of cost functions: sum, bottleneck and balanced and with arbitrary real edge costs we compute in polynomial time the persistency partition $E_{A l l}$ , $E_{S o m e}$ , $E_{N o n e}$ of the edge set E, where: $E_{A l l}$ = e ∈ E, e belongs to all optimum solutions, $E_{N o n e}$ = e ∈ E, e does not belong to any optimum solution and $E_{S o m e}$ = e ∈ E, e belongs to some but not to all optimum solutions.

Finite groups with some SS-supplemented subgroups

Mengling Jiang, Jianjun Liu (2021)

Czechoslovak Mathematical Journal

Similarity:

A subgroup $H$ of a finite group $G$ is said to be SS-supplemented in $G$ if there exists a subgroup $K$ of $G$ such that $G = H K$ and $H \cap K$ is S-quasinormal in $K$ . We analyze how certain properties of SS-supplemented subgroups influence the structure of finite groups. Our results improve and generalize several recent results.

Note on improper coloring of $1$ -planar graphs

Yanan Chu, Lei Sun, Jun Yue (2019)

Czechoslovak Mathematical Journal

Similarity:

A graph $G = (V, E)$ is called improperly $(d_{1}, \dots, d_{k})$ -colorable if the vertex set $V$ can be partitioned into subsets $V_{1}, \dots, V_{k}$ such that the graph $G [V_{i}]$ induced by the vertices of $V_{i}$ has maximum degree at most $d_{i}$ for all $1 \leq i \leq k$ . In this paper, we mainly study the improper coloring of $1$ -planar graphs and show that $1$ -planar graphs with girth at least $7$ are $(2, 0, 0, 0)$ -colorable.

Equivalent classes for K₃-gluings of wheels

Halina Bielak (1998)

Discussiones Mathematicae Graph Theory

Similarity:

In this paper, the chromaticity of K₃-gluings of two wheels is studied. For each even integer n ≥ 6 and each odd integer 3 ≤ q ≤ [n/2] all K₃-gluings of wheels $W_{q + 2}$ and $W_{n - q + 2}$ create an χ-equivalent class.

Finite groups whose all proper subgroups are $𝒞$ -groups

Pengfei Guo, Jianjun Liu (2018)

Czechoslovak Mathematical Journal

Similarity:

A group $G$ is said to be a $𝒞$ -group if for every divisor $d$ of the order of $G$ , there exists a subgroup $H$ of $G$ of order $d$ such that $H$ is normal or abnormal in $G$ . We give a complete classification of those groups which are not $𝒞$ -groups but all of whose proper subgroups are $𝒞$ -groups.

Displaying similar documents to “Expansion and random walks in SL d ( ℤ / p n ℤ ) : I”

Displaying similar documents to “Expansion and random walks in ${SL}_{d} (ℤ / p^{n} ℤ)$ : I”