Abstract. We give an explicit procedure for \(5\)-list coloring a large class of toroidal \(6\)-regular triangulations in linear time. We also show that these graphs are not \(3\)-choosable.

MSC 2020: 05C15, 05C85, 05C10, 05C75 · Keywords: list coloring, toroidal graph, triangulation, regular graph, linear time algorithm

Abstract. Using the sunflower method, we show that if \(\theta \in (0,1) \cap \mathbb{Q}\) and \(\mathcal{F}\) is a \(O(n^{1/3})\)-bounded \(\theta\)-intersecting family over \([n]\), then \(\lvert \mathcal{F} \rvert = O(n)\), and that if \(\mathcal{F}\) is \(o(n^{1/3})\)-bounded, then \(\lvert \mathcal{F} \rvert \leq (\frac32 + o(1))n\). This partially solves a conjecture of Balachandran, Mathew and Mishra that any \(\theta\)-intersecting family over \([n]\) has size at most linear in \(n\), in the regime where we have no very large sets.

MSC 2020: 05D05, 03E05 · Keywords: sunflower method, intersecting families of set systems

Abstract. Let \(\mathbf{a} = (a_{i})_{i \geq 1}\) be a sequence in a field \(\mathbb{F}\), and \(f \colon \mathbb{F} \times \mathbb{F} \to \mathbb{F}\) be a function such that \(f(a_{i},a_{i}) \neq 0\) for all \(i \geq 1\). For any tournament \(T\) over \([n]\), consider the \(n \times n\) symmetric matrix \(M_{T}(f; \mathbf{a})\) with zero diagonal whose \((i,j)\)th entry (for \(i < j\)) is \(f(a_{i},a_{j})\) if \(i \to j\) in \(T\), and \(f(a_{j},a_{i})\) if \(j \to i\) in \(T\). It is known [see Balachandran et al., Linear Algebra Appl. 658 (2023), 310–318] that if \(T\) is a uniformly random tournament over \([n]\), then \(\operatorname{rank}(M_{T}(f; \mathbf{a})) \geq (\frac{1}{2}-o(1))n\) with high probability when \(\operatorname{char}(\mathbb{F}) \neq 2\) and \(f\) is a linear function.

In this paper, we investigate the other extremal question: how low can the ranks of such matrices be? We work with sequences \(\mathbf{a}\) that take only two distinct values, so the rank of any such \(n \times n\) matrix is at least \(n/2\). First, we show that the rank of any such matrix depends on whether an associated bipartite graph has certain eigenvalues of high multiplicity. Using this, we show that if \(f\) is linear, then there are \(n \times n\) real matrices \(M_{T}(f; \mathbf{a})\) of rank at most \(\frac{n}{2} + O(1)\). For rational matrices, we show that for each \(\varepsilon> 0\) we can find a sequence \(\mathbf{a}(\varepsilon)\) for which there are \(n \times n\) matrices \(M_{T}(f; \mathbf{a}(\varepsilon))\) of rank at most \((\frac{1}{2} + \varepsilon)n + O(1)\). These matrices are constructed from symmetric designs, and we also use them to produce bisection-closed families of size greater than \(\lfloor{3n/2\rfloor} - 2\) for \(n \leq 15\), which improves the previously best known bound given in [Balachandran et al., Electron. J. Combin. 26 (2019), no. 2, #P2.40].

MSC 2020: 05C50, 05B20, 05C20, 05B30, 05D05 05C35, 15B52 · Keywords: rank, tournament, symmetric design, bipartite graph, multiplicity

Abstract. Let \(\mathbb{F}\) be a field and suppose \(\mathbf{a} := (a_1, a_2, \dotsc)\) is a sequence of non-zero elements in \(\mathbb{F}\). For a tournament \(T\) on \([n]\), associate the \(n \times n\) symmetric matrix \(M_{T}(\mathbf{a})\) (resp. skew-symmetric matrix \(M_{T, \mathrm{skew}}(\mathbf{a})\)) with zero diagonal as follows: for \(i < j\), if the edge \(ij\) is directed as \(i \to j\) in \(T\), then set \(M_{T}(\mathbf{a})=a_i\) (resp. \(M_{T, \mathrm{skew}}(\mathbf{a})=a_i\)), else set \(M_{T}(\mathbf{a})=a_j\) (resp. \(M_{T, \mathrm{skew}}(\mathbf{a})=a_j\)). Let \(\mathcal{M}_{n}(\mathbf{a})\) (resp. \(\mathcal{M}_{n, \mathrm{skew}}(\mathbf{a})\)) be the family consisting of all the \(n \times n\) symmetric matrices \(M_{T}(\mathbf{a})\) (resp. skew-symmetric matrices \(M_{T, \mathrm{skew}}(\mathbf{a})\)) as \(T\) varies over all tournaments on \([n]\). We show that any matrix in \(\mathcal{M}_n(\mathbf{a})\) or \(\mathcal{M}_{n, \mathrm{skew}}(\mathbf{a})\) corresponding to a transitive tournament has rank at least \(n - 1\), and this is best possible. This settles in a strong form a conjecture posed in Balachandran et al. [An ensemble of high-rank matrices arising from tournaments; Linear Algebra Appl. 2023;658:310–318]. As a corollary, any matrix in these families has rank at least \(\lfloor \log_2(n) \rfloor\).

MSC 2020: 05C20, 15A03, 15A15, 05D99 05C50 · Keywords: minimum rank, symmetric matrix, skew-symmetric matrix, determinant, transitive tournament

Abstract. For a set \(L\) of positive proper fractions and a positive integer \(r \geq 2\), a fractional \(r\)-closed \(L\)-intersecting family is a collection \(\mathcal{F} \subset \mathcal{P}([n])\) with the property that for any \(2 \leq t \leq r\) and \(A_1, \dotsc, A_t \in \mathcal{F}\) there exists \(\theta \in L\) such that \(\lvert A_1 \cap \dotsb \cap A_t \rvert \in \{ \theta \lvert A_1 \rvert, \dotsc, \theta \lvert A_t \rvert\}\). In this paper we show that for \(r \geq 3\) and \(L = \{\theta\}\) any fractional \(r\)-closed \(\theta\)-intersecting family has size at most linear in \(n\), and this is best possible up to a constant factor. We also show that in the case \(\theta = 1/2\) we have a tight upper bound of \(\lfloor \frac{3n}{2} \rfloor - 2\) and that a maximal \(r\)-closed \((1/2)\)-intersecting family is determined uniquely up to isomorphism.

MSC 2020: 05D05, 05B99, 03E05 · Keywords: fractional intersecting family, sunflower, intersection theorem

Abstract. Suppose \(\mathbb{F}\) is a field and let \(\mathbf{a} := (a_1,a_2,\dotsc)\) be a sequence of non-zero elements in \(\mathbb{F}\). For \(\mathbf{a}_n := (a_1, \dotsc, a_n)\), we consider the family \(\mathcal{M}_n(\mathbf{a})\) of \(n\times n\) symmetric matrices \(M\) over \(\mathbb{F}\) with all diagonal entries zero and the \((i, j)\)th element of \(M\) either \(a_i\) or \(a_j\) for \(i < j\). In this short paper, we show that all matrices in a certain subclass of \(\mathcal{M}_n(\mathbf{a})\)—which can be naturally associated with transitive tournaments—have rank at least \(\lfloor 2n/3 \rfloor - 1\). We also show that if \(\operatorname{char}(\mathbb{F})\neq 2\) and \(M\) is a matrix chosen uniformly at random from \(\mathcal{M}_n(\mathbf{a})\), then with high probability \(\operatorname{rank}(M) \geq \bigl(\frac{1}{2} - o(1)\bigr)n\).

MSC 2020: 15B52, 05D99, 05C20, 15A03 05B20 · Keywords: rank, symmetric matrix, tournament, McDiarmid's inequality, bisection closed family

Abstract. Altshuler (Discrete Math 4(3):201–217, 1973) characterized the \(6\)-regular triangulations on the torus to be precisely those that are obtained from a regular triangulation of the \(r \times s\) toroidal grid where the vertices in the first and last column are connected by a shift of \(t\) vertices. Such a graph is denoted \(T(r, s, t)\). Collins and Hutchinson (Graph colouring and applications. CRM proceedings and lecture notes, vol 23. American Mathematical Society, Providence, pp 21–34, 1999) classified the \(4\)-colorable graphs \(T(r, s, t)\) with \(r, s \geq 3\). In this paper, we point out a gap in their classification and show how it can be fixed. Combined with the classification of the \(4\)-colorable graphs \(T(1, s, t)\) by Yeh and Zhu (Discrete Math 273(1–3):261–274, 2003), this completes the characterization of the colorability of all the \(6\)-regular triangulations on the torus.

MSC 2020: 05C15, 05C10, 05C75 · Keywords: chromatic number, colorings, toroidal graphs, triangulations, regular graphs

Abstract. We show that for loopless \(6\)-regular triangulations on the torus the gap between the choice number and chromatic number is at most \(2\). We also show that the largest gap for graphs embeddable in an orientable surface of genus \(g\) is of the order \(\Theta(\sqrt{g})\), and moreover for graphs with chromatic number of the order \(o(\sqrt{g}/\log_{2}(g))\) the largest gap is of the order \(o(\sqrt{g})\).

MSC 2020: 05C15, 05C10, 05C35, 05C75 · Keywords: list colorings, jump, toroidal graphs, triangulations, regular graphs

Abstract. Let \(F\) be a non-Archimedean local field and \(G = \mathrm{SL}(2,F)\). Let \((\pi, V)\) be an irreducible smooth Iwahori-spherical representation of \(G\). It is easy to see that such representations are always self-dual. The space \(V\) of \(\pi\) admits a non-degenerate \(G\)-invariant bilinear form \((\;,\;)\) which is unique up to scaling. It can be shown that the form \((\;,\;)\) is either symmetric or skew-symmetric and we set \(\varepsilon(\pi) = \pm 1\) accordingly. In this article, we use the Bernstein–Lusztig presentation of the Iwahori–Hecke algebra of \(G\) and show that \(\varepsilon(\pi) = 1\).

MSC 2020: 20G05, 22E50 20C08, 20G25 · Keywords: Iwahori subgroups, self-dual representations, signs

Abstract. A majority coloring (also called an unfriendly partition) of a graph \(G\) is a vertex coloring of \(G\) in which no vertex has more than half of its neighbors colored with its own color. The least number of colors required for a majority coloring of \(G\) is the majority chromatic number \(\mu(G)\). Lovász (1966) gave an elegant proof that \(\mu(G) = 2\) for every nonempty finite graph. The majority coloring game, introduced by Bosek–Grytczuk–Jakóbczak (2019), is a two-player Maker-Breaker-type game where the players alternately color vertices while maintaining the majority condition at each vertex; the least number of colors required for the first player to have a winning strategy on \(G\) is the majority game chromatic number \(\mu_g(G)\). In contrast with the static case, Bosek–Grytczuk–Jakóbczak show that \(\mu_g(G)\) is unbounded in general, while \(\mu_g(G)\le \mathrm{col}_g(G)\), where \(\mathrm{col}_g(G)\) is the game coloring number of \(G\).

It is known (cf. Faigle–Kern–Kierstead–Trotter (1993)) that, for any acyclic graph \(G\), \(\mathrm{col}_g(G) \leq 4\), so \(\mu_g(G) \leq 4\) as well. We improve this bound by showing that \(\mu_g(G) \leq 3\) for any acyclic graph \(G\) of maximum degree at most \(4\). We also show that \(\mu_g(G) = 2\) if \(G\) is a nonempty path, star, or complete graph, or a disjoint union of such graphs. These improve the results of Bosek–Grytczuk–Jakóbczak. We also initiate the study of the computational complexity of the pre-coloring extension problem for the static and game versions of majority coloring. We show that the Majority \(k\)-precoloring Extension problem is \(\mathsf{NP}\)-complete for each \(k \geq 2\). When \(k = 2\), it remains \(\mathsf{NP}\)-complete on the class of bipartite graphs where maximum degrees of each part are \(5\) and \(6\), and when \(k = 3\) it remains \(\mathsf{NP}\)-complete on the class of \(12\)-regular planar graphs. We show that the Majority Precoloring Extension Game problem is \(\mathsf{PSPACE}\)-complete, even when the number of colors is fixed to be the chromatic number of the input graph, and the Majority \(2\)-Precoloring Extension Game problem is \(\mathsf{PSPACE}\)-complete on the class of bipartite graphs in which one part has maximum degree equal to \(9\). The results on the game versions also hold for the variation where Bob starts the game.

MSC 2020: 05C57, 05C05, 05C15, 68Q15 · ACM CCS 2012: Mathematics of computing → Graph coloring; Theory of computation → Problems, reductions and completeness; Mathematics of computing → Combinatorics · Keywords: majority coloring game; NP-complete; PSPACE-complete; forest

Abstract. We give an explicit procedure for \(5\)-list coloring a large class of toroidal \(6\)-regular triangulations in linear time. We also show that these graphs are not \(3\)-choosable.

MSC 2020: 05C15, 05C10, 68WXX · Keywords: list coloring, toroidal graph, triangulation, regular graph, linear time algorithm

Abstract. This paper discusses two majority coloring games on graphs. A majority coloring of a graph \(G=(V,E)\) is a coloring of \(V(G)\) such that, for each vertex \(v\), the number of neighbors of \(v\) with the same color as \(v\) is at most \(\deg(v)/2\). A strong majority coloring is a coloring of \(V(G)\) such that, for each vertex \(v\), every monochromatic subset of \(N(v)\) has size at most \(\deg(v)/2\). The (strong) majority coloring game is a two-player Maker-Breaker-type game, in which two players Alice and Bob color the vertices of a graph \(G\) alternately, maintaining the (strong) majority condition. The least number of colors such that Alice has a winning strategy in such a game is called the (strong) majority game chromatic number of the graph \(G\), denoted \(\mu_g(G)\) (or \(\operatorname{Maj}_g(G)\) for the strong version).

For the majority coloring game, we prove that \(\mu_g(G) \leq 3\) under the following cases: \(G\) is a 2-caterpillar, \(G\) is a rooted tree with all leaves at depth \(k \leq 4\), and \(G\) is a subdivision of some graph. The latter resolves a problem posed by Bosek–Grytczuk–Jakóbczak (Discrete Applied Mathematics 255 (2025) 15–20), who also asked whether \(\mu_g(T) \leq 3\) for every tree \(T\). For the latter question, we discuss various difficulties that arise when natural strategies are attempted by Alice to win the majority coloring game on trees. We also include a comparison with the marking game and relaxed coloring game on trees, and with the majority coloring game on infinite locally finite acyclic graphs \(G\) with \(\delta(G) > 1\).

For the strong majority coloring game, we compute \(\operatorname{Maj}_g(C_n)\) exactly for each cycle \(C_n\), \(n \geq 3\). We also initiate the study of the computational complexity of the strong majority coloring game; specifically, we prove that the decision version of the Strong Majority Game Chromatic Number problem is PSPACE-complete. We also show that the Strong Majority 2-Coloring problem is NP-complete on Eulerian graphs.

MSC 2020: 05C57, 05C15, 05C05, 05C38, 05C07, 68Q17 · Keywords: majority coloring game, strong majority coloring game, caterpillar, subdivision, cycle, PSPACE-complete, NP-complete

Abstract. The \(\triangle\)-convexity space on a finite, simple graph \(G=(V,E)\) is the collection \(\mathcal{C}\) of subsets \(S \subseteq V(G)\) such that whenever \(x \in V(G)\) forms a triangle with two vertices in \(S\), we have \(x \in S\). The members of \(\mathcal{C}\) are called convex sets, and the convex hull of a set \(S \subseteq V(G)\), denoted \(\operatorname{Hull}(S)\), is the smallest member of \(\mathcal{C}\) that contains \(S\). A set \(S \subseteq V(G)\) is Carathéodory independent if \[ \operatorname{Hull}(S) \setminus \bigcup_{x \in S} \operatorname{Hull}(S \setminus \{x\}) \neq \varnothing, \] and it is exchange independent if \(|S|=1\) or there exists \(p \in S\) such that \[ \operatorname{Hull}(S \setminus \{p\}) \setminus \bigcup_{x \in S \setminus \{p\}} \operatorname{Hull}(S \setminus \{x\}) \neq \varnothing. \] The Carathéodory (resp., exchange) number, \(c_{\triangle}(G)\) (resp., \(e_{\triangle}(G)\)), is the size of a largest Carathéodory (resp., exchange) independent subset of \(V(G)\). It was shown by Anand–Anil–Changat–Narasimha-Shenoi–Ramla (JCMCC 126 (2025) 11–27) that \(c_{\triangle}(G) \leq t(G)+1\) and \(e_{\triangle}(G) \leq t(G)+2\), where \(t(G)\) is the number of triangles in \(G\), and that these bounds are tight. They also computed \(c_{\triangle}(G)\) and \(e_{\triangle}(G)\) for a block graph \(G\) in terms of the number and arrangement of non-\(K_2\) blocks in \(G\).

In this paper, we point out a gap in the proof in Anand et al. of the first inequality, \(c_{\triangle}(G) \leq t(G)+1\), which has consequences for the proof of the second inequality, \(e_{\triangle}(G) \leq t(G)+2\), as well. Moreover, the tightness results are inadvertently applied as characterizations of the extremal graphs, leading to incorrect computations of the Carathéodory and exchange numbers of block graphs in certain cases. We fix these gaps by giving a full proof of the first inequality via a different route from that in Anand et al. Together with the argument in Anand et al., this also completes the proof of the second inequality. Our proof also leads to a characterization of the extremal graphs for each bound, which we use to compute the Carathéodory and exchange numbers of block graphs and to identify the extremal block graphs. We also determine \(e_{\triangle}(G)\) exactly for \(k\)-trees for every \(k \geq 2\).

MSC 2020: 05C69, 05C35, 05C99, 52A01, 52A37 · Keywords: \(\triangle\)-convexity, Carathéodory number, exchange number, graph convexity, block graph, \(k\)-tree

Abstract. A path representation of a simple graph \(G\) is a simple graph \(H\) along with an edge partition \(\mathcal{P} = \{P_u : u \in V(G)\}\) of \(H\) into non-trivial paths such that \(\{u,v\} \in E(G)\) if and only if \(P_u\) and \(P_v\) intersect in \(H\). A path representation is proper if no two paths in \(\mathcal{P}\) can be concatenated into another path. The path representation number, \(\mathsf{prn}(G)\), of a graph \(G\) is the minimum number of vertices in any proper path representation of \(G\).

We give bounds on \(\mathsf{prn}(G)\) in terms of the order and size of \(G\), as well as other well-known graph parameters such as the clique cover number, \(\mathsf{cc}(G)\), the clique partition number, \(\mathsf{cp}(G)\), and the clique number, \(\omega(G)\). We investigate proper path representations of various classes of graphs, including complete bipartite graphs, complete graphs, the Erdős–Rényi random graph \(G(n,p)\), and triangle-free graphs, particularly trees.