More Like this

1. Graphs with no even holes and no sector wheels are the union of two chordal graphs

   https://doi.org/10.1016/j.ejc.2024.104035  

   Abrishami, Tara; Berger, Eli; Chudnovsky, Maria; Zerbib, Shira (December 2024, European Journal of Combinatorics)

   Sivaraman (2020) conjectured that if G is a graph with no induced even cycle then there exist sets X1,X2⊆V(G) satisfying V(G)=X1∪X2 such that the induced graphs G[X1] and G[X2] are both chordal. We prove this conjecture in the special case where G contains no sector wheel, namely, a pair (H,w) where H is an induced cycle of G and w is a vertex in V(G)∖V(H) such that N(w)∩H is either V(H) or a path with at least three vertices. 

   more » « less
2. THE CYCLIC GRAPH OF A Z -GROUP

   https://doi.org/10.1017/S0004972720001318  

   COSTANZO, DAVID G.; LEWIS, MARK L.; SCHMIDT, STEFANO; TSEGAYE, EYOB; UDELL, GABE (January 2020, Bulletin of the Australian Mathematical Society)

   null (Ed.)

   Abstract: For a group G, we define a graph Delta (G) by letting G^#=G\{1} be the set of vertices and by drawing an edge between distinct elements x,y in G^# if and only if the subgroup is cyclic. Recall that a Z-group is a group where every Sylow subgroup is cyclic. In this short note, we investigate Delta (G) for a Z-group G. 

   more » « less
3. Representations and Tensor Product Growth

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

   Larsen, Michael; Shalev, Aner; Tiep, Pham Huu (July 2022, International Mathematics Research Notices)

   Abstract The deep theory of approximate subgroups establishes three-step product growth for subsets of finite simple groups $$G$$ of Lie type of bounded rank. In this paper, we obtain two-step growth results for representations of such groups $$G$$ (including those of unbounded rank), where products of subsets are replaced by tensor products of representations. Let $$G$$ be a finite simple group of Lie type and $$\chi $$ a character of $$G$$. Let $$|\chi |$$ denote the sum of the squares of the degrees of all (distinct) irreducible characters of $$G$$ that are constituents of $$\chi $$. We show that for all $$\delta>0$$, there exists $$\epsilon>0$$, independent of $$G$$, such that if $$\chi $$ is an irreducible character of $$G$$ satisfying $$|\chi | \le |G|^{1-\delta }$$, then $$|\chi ^2| \ge |\chi |^{1+\epsilon }$$. We also obtain results for reducible characters and establish faster growth in the case where $$|\chi | \le |G|^{\delta }$$. In another direction, we explore covering phenomena, namely situations where every irreducible character of $$G$$ occurs as a constituent of certain products of characters. For example, we prove that if $$|\chi _1| \cdots |\chi _m|$$ is a high enough power of $|G|$, then every irreducible character of $$G$$ appears in $$\chi _1\cdots \chi _m$$. Finally, we obtain growth results for compact semisimple Lie groups. 

   more » « less
4. Efficient arithmetic regularity and removal lemmas for induced bipartite patterns.

   https://doi.org/10.19086/da  

   Alon, Noga; Fox, Jacob; Zhao, Yufei (April 2019, Discrete analysis)

   Let G be an abelian group of bounded exponent and A⊆G. We show that if the collection of translates of A has VC dimension at most d, then for every ϵ>0 there is a subgroup H of G of index at most ϵ^{−d−o(1)} such that one can add or delete at most ϵ|G| elements to/from A to make it a union of H-cosets. We also establish a removal lemma with polynomial bounds, with applications to property testing, for induced bipartite patterns in a finite abelian group with bounded exponent. 

   more » « less
5. Hyperbolic families and coloring graphs on surfaces

   https://doi.org/https://doi.org/10.1090/btran/26  

   Postle, Luke; Thomas, Robin (December 2018, Transactions of the American Mathematical Society. Series B)

   We develop a theory of linear isoperimetric inequalities for graphs on surfaces and apply it to coloring problems, as follows. Let $ G$ be a graph embedded in a fixed surface $$ \Sigma $$ of genus $ g$ and let $$ L=(L(v):v\in V(G))$$ be a collection of lists such that either each list has size at least five, or each list has size at least four and $ G$ is triangle-free, or each list has size at least three and $ G$ has no cycle of length four or less. An $ L$-coloring of $ G$ is a mapping $$ \phi $$ with domain $ V(G)$ such that $$ \phi (v)\in L(v)$$ for every $$ v\in V(G)$$ and $$ \phi (v)\ne \phi (u)$$ for every pair of adjacent vertices $$ u,v\in V(G)$$. We prove if every non-null-homotopic cycle in $ G$ has length $$ \Omega (\log g)$$, then $ G$ has an $ L$-coloring, if $ G$ does not have an $ L$-coloring, but every proper subgraph does (``$ L$-critical graph''), then $$ \vert V(G)\vert=O(g)$$, if every non-null-homotopic cycle in $ G$ has length $$ \Omega (g)$$, and a set $$ X\subseteq V(G)$$ of vertices that are pairwise at distance $$ \Omega (1)$$ is precolored from the corresponding lists, then the precoloring extends to an $ L$-coloring of $ G$, if every non-null-homotopic cycle in $ G$ has length $$ \Omega (g)$$, and the graph $ G$ is allowed to have crossings, but every two crossings are at distance $$ \Omega (1)$$, then $ G$ has an $ L$-coloring, if $ G$ has at least one $ L$-coloring, then it has at least $$ 2^{\Omega (\vert V(G)\vert)}$$ distinct $ L$-colorings. We show that the above assertions are consequences of certain isoperimetric inequalities satisfied by $ L$-critical graphs, and we study the structure of families of embedded graphs that satisfy those inequalities. It follows that the above assertions hold for other coloring problems, as long as the corresponding critical graphs satisfy the same inequalities. 

   more » « less