More Like this

1. Character bounds for regular semisimple elements and asymptotic results on Thompson’s conjecture

   https://doi.org/10.1007/s00209-022-03193-3  

   Larsen, Michael; Taylor, Jay; Tiep, Pham Huu (February 2023, Mathematische Zeitschrift)

   Abstract For every integer k there exists a bound $$B=B(k)$$ B = B ( k ) such that if the characteristic polynomial of $$g\in \textrm{SL}_n(q)$$ g ∈ SL n ( q ) is the product of $$\le k$$ ≤ k pairwise distinct monic irreducible polynomials over $$\mathbb {F}_q$$ F q , then every element x of $$\textrm{SL}_n(q)$$ SL n ( q ) of support at least B is the product of two conjugates of g . We prove this and analogous results for the other classical groups over finite fields; in the orthogonal and symplectic cases, the result is slightly weaker. With finitely many exceptions ( p ,  q ), in the special case that $$n=p$$ n = p is prime, if g has order $$\frac{q^p-1}{q-1}$$ q p - 1 q - 1 , then every non-scalar element $$x \in \textrm{SL}_p(q)$$ x ∈ SL p ( q ) is the product of two conjugates of g . The proofs use the Frobenius formula together with upper bounds for values of unipotent and quadratic unipotent characters in finite classical groups. 

   more » « less
2. Large Monochromatic Components in Almost Complete Graphs and Bipartite Graphs

   https://doi.org/10.37236/9824  

   Füredi, Zoltán; Luo, Ruth (April 2021, The Electronic Journal of Combinatorics)

   Gyárfas proved that every coloring of the edges of $$K_n$$ with $t+1$ colors contains a monochromatic connected component of size at least $n/t$. Later, Gyárfás and Sárközy asked for which values of $$\gamma=\gamma(t)$$ does the following strengthening for almost complete graphs hold: if $$G$$ is an $$n$$-vertex graph with minimum degree at least $$(1-\gamma)n$$, then every $(t+1)$-edge coloring of $$G$$ contains a monochromatic component of size at least $n/t$. We show $$\gamma= 1/(6t^3)$$ suffices, improving a result of DeBiasio, Krueger, and Sárközy. 

   more » « less
3. The Implicit Graph Conjecture is False

   https://doi.org/10.1109/FOCS54457.2022.00109  

   Hatami, Hamed; Hatami, Pooya (October 2022, Annual Symposium on Foundations of Computer Science)

   An efficient implicit representation of an n-vertex graph G in a family F of graphs assigns to each vertex of G a binary code of length O(log n) so that the adjacency between every pair of vertices can be determined only as a function of their codes. This function can depend on the family but not on the individual graph. Every family of graphs admitting such a representation contains at most 2^O(n log(n)) graphs on n vertices, and thus has at most factorial speed of growth. The Implicit Graph Conjecture states that, conversely, every hereditary graph family with at most factorial speed of growth admits an efficient implicit representation. We refute this conjecture by establishing the existence of hereditary graph families with factorial speed of growth that require codes of length n^Ω(1). 

   more » « less
4. Pure Pairs. V. Excluding Some Long Subdivision

   https://doi.org/10.1007/s00493-023-00025-8  

   Scott, Alex; Seymour, Paul; Spirkl, Sophie (June 2023, Combinatorica)

   A “pure pair” in a graph G is a pair A, B of disjoint subsets of V(G) such that A is complete or anticomplete to B. Jacob Fox showed that for all ε>0, there is a comparability graph G with n vertices, where n is large, in which there is no pure pair A, B with |A|,|B|≥εn. He also proved that for all c>0 there exists ε>0 such that for every comparability graph G with n>1 vertices, there is a pure pair A, B with |A|,|B|≥εn1−c; and conjectured that the same holds for every perfect graph G. We prove this conjecture and strengthen it in several ways. In particular, we show that for all c>0, and all ℓ1,ℓ2≥4/c+9, there exists ε>0 such that, if G is an (n>1)-vertex graph with no hole of length exactly ℓ1 and no antihole of length exactly ℓ2, then there is a pure pair A, B in G with |A|≥εn and |B|≥εn1−c. This is further strengthened, replacing excluding a hole by excluding some “long” subdivision of a general graph. 

   more » « less
5. Universal minimal flows of extensions of and by compact groups

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

   BARTOŠOVÁ, DANA (August 2023, Ergodic Theory and Dynamical Systems)

   Abstract Every topological group G has, up to isomorphism, a unique minimal G -flow that maps onto every minimal G -flow, the universal minimal flow $M(G).$ We show that if G has a compact normal subgroup K that acts freely on $M(G)$ and there exists a uniformly continuous cross-section from $G/K$ to $G,$ then the phase space of $M(G)$ is homeomorphic to the product of the phase space of $M(G/K)$ with K . Moreover, if either the left and right uniformities on G coincide or G is isomorphic to a semidirect product $$G/K\ltimes K$$ , we also recover the action, in the latter case extending a result of Kechris and Sokić. As an application, we show that the phase space of $M(G)$ for any totally disconnected locally compact Polish group G with a normal open compact subgroup is homeomorphic to a finite set, the Cantor set $$2^{\mathbb {N}}$$ , $$M(\mathbb {Z})$$ , or $$M(\mathbb {Z})\times 2^{\mathbb {N}}.$$ 

   more » « less