Displaying similar documents to “Expansion in S L d ( 𝒪 K / I ) , I square-free”

Uniform mixing time for random walk on lamplighter graphs

Júlia Komjáthy, Jason Miller, Yuval Peres (2014)

Annales de l'I.H.P. Probabilités et statistiques

Similarity:

Suppose that 𝒢 is a finite, connected graph and X is a lazy random walk on 𝒢 . The lamplighter chain X associated with X is the random walk on the wreath product 𝒢 = 𝐙 2 𝒢 , the graph whose vertices consist of pairs ( f ̲ , x ) where f is a labeling of the vertices of 𝒢 by elements of 𝐙 2 = { 0 , 1 } and x is a vertex in 𝒢 . There is an edge between ( f ̲ , x ) and ( g ̲ , y ) in 𝒢 if and only if x is adjacent to y in 𝒢 and f z = g z for all z x , y . In each step, X moves from a configuration ( f ̲ , x ) by updating x to y using the transition rule of X and then...

The real symmetric matrices of odd order with a P-set of maximum size

Zhibin Du, Carlos Martins da Fonseca (2016)

Czechoslovak Mathematical Journal

Similarity:

Suppose that A is a real symmetric matrix of order n . Denote by m A ( 0 ) the nullity of A . For a nonempty subset α of { 1 , 2 , ... , n } , let A ( α ) be the principal submatrix of A obtained from A by deleting the rows and columns indexed by α . When m A ( α ) ( 0 ) = m A ( 0 ) + | α | , we call α a P-set of A . It is known that every P-set of A contains at most n / 2 elements. The graphs of even order for which one can find a matrix attaining this bound are now completely characterized. However, the odd case turned out to be more difficult to tackle. As...

A new characterization of symmetric group by NSE

Azam Babai, Zeinab Akhlaghi (2017)

Czechoslovak Mathematical Journal

Similarity:

Let G be a group and ω ( G ) be the set of element orders of G . Let k ω ( G ) and m k ( G ) be the number of elements of order k in G . Let nse ( G ) = { m k ( G ) : k ω ( G ) } . Assume r is a prime number and let G be a group such that nse ( G ) = nse ( S r ) , where S r is the symmetric group of degree r . In this paper we prove that G S r , if r divides the order of G and r 2 does not divide it. To get the conclusion we make use of some well-known results on the prime graphs of finite simple groups and their components.

Purity of level m stratifications

Marc-Hubert Nicole, Adrian Vasiu, Torsten Wedhorn (2010)

Annales scientifiques de l'École Normale Supérieure

Similarity:

Let k be a field of characteristic p > 0 . Let D m be a BT m over k (i.e., an m -truncated Barsotti–Tate group over k ). Let S be a k -scheme and let X be a BT m over S . Let S D m ( X ) be the subscheme of S which describes the locus where X is locally for the fppf topology isomorphic to D m . If p 5 , we show that S D m ( X ) is pure in S , i.e. the immersion S D m ( X ) S is affine. For p { 2 , 3 } , we prove purity if D m satisfies a certain technical property depending only on its p -torsion D m [ p ] . For p 5 , we apply the developed techniques to show that...

Generalized 3-edge-connectivity of Cartesian product graphs

Yuefang Sun (2015)

Czechoslovak Mathematical Journal

Similarity:

The generalized k -connectivity κ k ( G ) of a graph G was introduced by Chartrand et al. in 1984. As a natural counterpart of this concept, Li et al. in 2011 introduced the concept of generalized k -edge-connectivity which is defined as λ k ( G ) = min { λ ( S ) : S V ( G ) and | S | = k } , where λ ( S ) denotes the maximum number of pairwise edge-disjoint trees T 1 , T 2 , ... , T in G such that S V ( T i ) for 1 i . In this paper we prove that for any two connected graphs G and H we have λ 3 ( G H ) λ 3 ( G ) + λ 3 ( H ) , where G H is the Cartesian product of G and H . Moreover, the bound is sharp. We also...

On path-quasar Ramsey numbers

Binlong Li, Bo Ning (2014)

Annales Universitatis Mariae Curie-Sklodowska, sectio A – Mathematica

Similarity:

Let G 1 and G 2 be two given graphs. The Ramsey number R ( G 1 , G 2 ) is the least integer r such that for every graph G on r vertices, either G contains a G 1 or G ¯ contains a G 2 . Parsons gave a recursive formula to determine the values of R ( P n , K 1 , m ) , where P n is a path on n vertices and K 1 , m is a star on m + 1 vertices. In this note, we study the Ramsey numbers R ( P n , K 1 F m ) , where F m is a linear forest on m vertices. We determine the exact values of R ( P n , K 1 F m ) for the cases m n and m 2 n , and for the case that F m has no odd component. Moreover, we...

Maximum bipartite subgraphs in H -free graphs

Jing Lin (2022)

Czechoslovak Mathematical Journal

Similarity:

Given a graph G , let f ( G ) denote the maximum number of edges in a bipartite subgraph of G . Given a fixed graph H and a positive integer m , let f ( m , H ) denote the minimum possible cardinality of f ( G ) , as G ranges over all graphs on m edges that contain no copy of H . In this paper we prove that f ( m , θ k , s ) 1 2 m + Ω ( m ( 2 k + 1 ) / ( 2 k + 2 ) ) , which extends the results of N. Alon, M. Krivelevich, B. Sudakov. Write K k ' and K t , s ' for the subdivisions of K k and K t , s . We show that f ( m , K k ' ) 1 2 m + Ω ( m ( 5 k - 8 ) / ( 6 k - 10 ) ) and f ( m , K t , s ' ) 1 2 m + Ω ( m ( 5 t - 1 ) / ( 6 t - 2 ) ) , improving a result of Q. Zeng, J. Hou. We also give lower bounds on...

Sum-product theorems and incidence geometry

Mei-Chu Chang, Jozsef Solymosi (2007)

Journal of the European Mathematical Society

Similarity:

In this paper we prove the following theorems in incidence geometry. 1. There is δ > 0 such that for any P 1 , , P 4 , and Q 1 , , Q n 2 , if there are n ( 1 + δ ) / 2 many distinct lines between P i and Q j for all i , j , then P 1 , , P 4 are collinear. If the number of the distinct lines is < c n 1 / 2 then the cross ratio of the four points is algebraic. 2. Given c > 0 , there is δ > 0 such that for any P 1 , P 2 , P 3 2 noncollinear, and Q 1 , , Q n 2 , if there are c n 1 / 2 many distinct lines between P i and Q j for all i , j , then for any P 2 { P 1 , P 2 , P 3 } , we have δ n distinct lines between P and Q j . 3. Given...

The Ramsey numbers for some subgraphs of generalized wheels versus cycles and paths

Halina Bielak, Kinga Dąbrowska (2015)

Annales Universitatis Mariae Curie-Sklodowska, sectio A – Mathematica

Similarity:

The Ramsey number R ( G , H ) for a pair of graphs G and H is defined as the smallest integer n such that, for any graph F on n vertices, either F contains G or F ¯ contains H as a subgraph, where F ¯ denotes the complement of F . We study Ramsey numbers for some subgraphs of generalized wheels versus cycles and paths and determine these numbers for some cases. We extend many known results studied in [5, 14, 18, 19, 20]. In particular we count the numbers R ( K 1 + L n , P m ) and R ( K 1 + L n , C m ) for some integers m , n , where L n is...

Σ s -products revisited

Reynaldo Rojas-Hernández (2015)

Commentationes Mathematicae Universitatis Carolinae

Similarity:

We show that any Σ s -product of at most 𝔠 -many L Σ ( ω ) -spaces has the L Σ ( ω ) -property. This result generalizes some known results about L Σ ( ω ) -spaces. On the other hand, we prove that every Σ s -product of monotonically monolithic spaces is monotonically monolithic, and in a similar form, we show that every Σ s -product of Collins-Roscoe spaces has the Collins-Roscoe property. These results generalize some known results about the Collins-Roscoe spaces and answer some questions due to Tkachuk [Lifting the Collins-Roscoe...