More Like this

1. Polynomial-time algorithm for Maximum Independent Set in bounded-degree graphs with no long induced claws

   Chudnovsky, M. with (January 2022, 2022 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA))

   For graphs G and H, we say that G is H-free if it does not contain H as an induced subgraph. Already in the early 1980s Alekseev observed that if H is connected, then the Max Weight Independent Set problem (MWIS) remains NP-hard in H-free graphs, unless H is a path or a subdivided claw, i.e., a graph obtained from the three-leaf star by subdividing each edge some number of times (possibly zero). Since then determining the complexity of MWIS in these remaining cases is one of the most important problems in algorithmic graph theory. A general belief is that the problem is polynomial-time solvable, which is witnessed by algorithmic results for graphs excluding some small paths or subdivided claws. A more conclusive evidence was given by the recent breakthrough result by Gartland and Lokshtanov [FOCS 2020]: They proved that MWIS can be solved in quasipolynomial time in H-free graphs, where H is any fixed path. If H is an arbitrary subdivided claw, we know much less: The problem admits a QPTAS and a subexponential-time algorithm [Chudnovsky et al., SODA 2019]. In this paper we make an important step towards solving the problem by showing that for any subdivided claw H, MWIS is polynomial-time solvable in H-free graphs of bounded degree. 

   more » « less
2. 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
3. TEMPERED HOMOGENEOUS SPACES IV

   https://doi.org/10.1017/s1474748022000287  

   Benoist, Yves; Kobayashi, Toshiyuki (June 2022, Journal of the Institute of Mathematics of Jussieu)

   Let 𝐺 be a complex semisimple Lie group and 𝘏 a complex closed connected subgroup. Let g and h be their Lie algebras. We prove that the regular representation of 𝐺 in 𝐿²(𝐺/𝘏) is tempered if and only if the orthogonal of h in g contains regular elements by showing simultaneously the equivalence to other striking conditions, such as h has a solvable limit algebra. 

   more » « less
4. The spread of a finite group

   https://doi.org/doi.org/10.4007/annals.2021.193.2.5  

   Burness, Tim; Guralnick, Robert; Harper, Scott (January 2021, Annals of mathematics)

   null (Ed.)

   A group G is said to be 3/2-generated if every nontrivial element belongs to a generating pair. It is easy to see that if G has this property, then every proper quotient of G is cyclic. In this paper we prove that the converse is true for finite groups, which settles a conjecture of Breuer, Guralnick and Kantor from 2008. In fact, we prove a much stronger result, which solves a problem posed by Brenner and Wiegold in 1975. Namely, if G is a finite group and every proper quotient of G is cyclic, then for any pair of nontrivial elements x1, x2 ϵ G, there exists y ϵ G such that G = ⟨x1, y⟩ = ⟨x2, y⟩. In other words, s(G) ⩾ 2, where s(G) is the spread of G. Moreover, if u(G) denotes the more restrictive uniform spread of G, then we can completely characterise the finite groups G with u(G) = 0 and u(G) = 1. To prove these results, we first establish a reduction to almost simple groups. For simple groups, the result was proved by Guralnick and Kantor in 2000 using probabilistic methods, and since then the almost simple groups have been the subject of several papers. By combining our reduction theorem and this earlier work, it remains to handle the groups with socle an exceptional group of Lie type, and this is the case we treat in this paper. 

   more » « less
5. A Unified Proof of Conjectures on Cycle Lengths in Graphs

   https://doi.org/10.1093/imrn/rnaa324  

   Gao, Jun; Huo, Qingyi; Liu, Chun-Hung; Ma, Jie (January 2021, International Mathematics Research Notices)

   null (Ed.)

   Abstract In this paper, we prove a tight minimum degree condition in general graphs for the existence of paths between two given endpoints whose lengths form a long arithmetic progression with common difference one or two. This allows us to obtain a number of exact and optimal results on cycle lengths in graphs of given minimum degree, connectivity or chromatic number. More precisely, we prove the following statements by a unified approach: 1. Every graph $$G$$ with minimum degree at least $k+1$ contains cycles of all even lengths modulo $$k$$; in addition, if $$G$$ is $$2$$-connected and non-bipartite, then it contains cycles of all lengths modulo $$k$$. 2. For all $$k\geq 3$$, every $$k$$-connected graph contains a cycle of length zero modulo $$k$$. 3. Every $$3$$-connected non-bipartite graph with minimum degree at least $k+1$ contains $$k$$ cycles of consecutive lengths. 4. Every graph with chromatic number at least $k+2$ contains $$k$$ cycles of consecutive lengths. The 1st statement is a conjecture of Thomassen, the 2nd is a conjecture of Dean, the 3rd is a tight answer to a question of Bondy and Vince, and the 4th is a conjecture of Sudakov and Verstraëte. All of the above results are best possible. 

   more » « less