arXiv daily: Combinatorics (math.CO)

Authors:Daniele Bartoli, Alessandro Giannoni

Abstract: Scattered sequences are a generalization of scattered polynomials. So far, only scattered sequences of order one and two have been constructed. In this paper an infine family of scattered sequences of order three is obtained. Equivalence issues are also considered.

Authors:Yang Huang, Yuejian Peng

Abstract: Two families $\mathcal{A}$ and $\mathcal{B}$ are cross-intersecting if $A\cap B\ne \emptyset$ for any $A\in \mathcal{A}$ and $B\in \mathcal{B}$. We call $t$ families $\mathcal{A}_1, \mathcal{A}_2,\dots, \mathcal{A}_t$ pairwise cross-intersecting families if $\mathcal{A}_i$ and $\mathcal{A}_j$ are cross-intersecting when $1\le i<j \le t$. Additionally, if $\mathcal{A}_j\ne \emptyset$ for each $j\in [t]$, then we say that $\mathcal{A}_1, \mathcal{A}_2,\dots, \mathcal{A}_t$ are non-empty pairwise cross-intersecting. Let $\mathcal{A}_1\subset{[n]\choose k_1}, \mathcal{A}_2\subset{[n]\choose k_2}, \dots, \mathcal{A}_t\subset{[n]\choose k_t}$ be non-empty pairwise cross-intersecting families with $t\geq 2$, $k_1\geq k_2\geq \cdots \geq k_t$, and $n\geq k_1+k_2$, we determine the maximum value of $\sum_{i=1}^t{|\mathcal{A}_i|}$ and characterize all extremal families. This answers a question of Shi, Frankl and Qian [Combinatorica 42 (2022)] and unifies results of Frankl and Tokushige [J. Combin. Theory Ser. A 61 (1992)] and Shi, Frankl and Qian [Combinatorica 42 (2022)]. The key techniques in previous works cannot be extended to our situation. A result of Kruskal-Katona is applied to allow us to consider only families $\mathcal{A}_i$ whose elements are the first $|\mathcal{A}_i|$ elements in lexicographic order. We bound $\sum_{i=1}^t{|\mathcal{A}_i|}$ by a function $f(R)$ of the last element $R$ (in the lexicographic order) of $\mathcal{A}_1$, introduce the concepts `$c$-sequential' and `down-up family', and show that $f(R)$ has several types of local convexities.

Authors:Jiangdong Ai, Stefanie Gerke, Gregory Gutin, Shujing Wang, Anders Yeo, Yacong Zhou

Abstract: For a vertex $x$ of a digraph, $d^+(x)$ ($d^-(x)$, resp.) is the number of vertices at distance 1 from (to, resp.) $x$ and $d^{++}(x)$ is the number of vertices at distance 2 from $x$. In 1995, Seymour conjectured that for any oriented graph $D$ there exists a vertex $x$ such that $d^+(x)\leq d^{++}(x)$. In 2006, Sullivan conjectured that there exists a vertex $x$ in $D$ such that $d^-(x)\leq d^{++}(x)$. We give a sufficient condition in terms of the number of transitive triangles for an oriented graph to satisfy Sullivan's conjecture. In particular, this implies that Sullivan's conjecture holds for all orientations of planar graphs and of triangle-free graphs. An oriented graph $D$ is an oriented split graph if the vertices of $D$ can be partitioned into vertex sets $X$ and $Y$ such that $X$ is an independent set and $Y$ induces a tournament. We also show that the two conjectures hold for some families of oriented split graphs, in particular, when $Y$ induces a regular or an almost regular tournament.

Authors:Ravindra Pawar, Tarkeshwar Singh, Adarsh Handa, Aloysius Godinho

Abstract: Given a graph $G =(V,E)$, a bijection $f: E \rightarrow \{1, 2, \dots,|E|\}$ is called a local antimagic labeling of $G$ if the vertex weight $w(u) = \sum_{uv \in E} f(uv)$ is distinct for all adjacent vertices. The vertex weights under the local antimagic labeling of $G$ induce a proper vertex coloring of a graph $G$. The \textit{local antimagic chromatic number} of $G$ denoted by $\chi_{la}(G)$ is the minimum number of weights taken over all such local antimagic labelings of $G$. In this paper, we investigate the local antimagic chromatic numbers of the union of some families of graphs, corona product of graphs, and necklace graph and we construct infinitely many graphs satisfying $\chi_{la}(G) = \chi(G)$.

Authors:Yangyang Cheng, Katherine Staden

Abstract: Given graphs $G_1,\ldots,G_s$ all on the same vertex set and a graph $H$ with $e(H) \leq s$, a copy of $H$ is transversal or rainbow if it contains at most one edge from each $G_c$. When $s=e(H)$, such a copy contains exactly one edge from each $G_i$. We study the case when $H$ is spanning and explore how the regularity blow-up method, that has been so successful in the uncoloured setting, can be used to find transversals. We provide the analogues of the tools required to apply this method in the transversal setting. Our main result is a blow-up lemma for transversals that applies to separable bounded degree graphs $H$. Our proofs use weak regularity in the $3$-uniform hypergraph whose edges are those $xyc$ where $xy$ is an edge in the graph $G_c$. We apply our lemma to give a large class of spanning $3$-uniform linear hypergraphs $H$ such that any sufficiently large uniformly dense $n$-vertex $3$-uniform hypergraph with minimum vertex degree $\Omega(n^2)$ contains $H$ as a subhypergraph. This extends work of Lenz, Mubayi and Mycroft.

Authors:Ahmad Abdi, Dabeen Lee

Abstract: Take a prime power $q$, an integer $n\geq 2$, and a coordinate subspace $S\subseteq GF(q)^n$ over the Galois field $GF(q)$. One can associate with $S$ an $n$-partite $n$-uniform clutter $\mathcal{C}$, where every part has size $q$ and there is a bijection between the vectors in $S$ and the members of $\mathcal{C}$. In this paper, we determine when the clutter $\mathcal{C}$ is ideal, a property developed in connection to Packing and Covering problems in the areas of Integer Programming and Combinatorial Optimization. Interestingly, the characterization differs depending on whether $q$ is $2,4$, a higher power of $2$, or otherwise. Each characterization uses crucially that idealness is a minor-closed property: first the list of excluded minors is identified, and only then is the global structure determined. A key insight is that idealness of $\mathcal{C}$ depends solely on the underlying matroid of $S$. Our theorems also extend from idealness to the stronger max-flow min-cut property. As a consequence, we prove the Replication and $\tau=2$ Conjectures for this class of clutters.

Authors:Marcin Briański, Gwenaël Joret, Michał T. Seweryn

Abstract: The {\em circumference} of a graph $G$ with at least one cycle is the length of a longest cycle in $G$. A classic result of Birmel\'e (2003) states that the treewidth of $G$ is at most its circumference minus $1$. In case $G$ is $2$-connected, this upper bound also holds for the pathwidth of $G$; in fact, even the treedepth of $G$ is upper bounded by its circumference (Bria\'nski, Joret, Majewski, Micek, Seweryn, Sharma; 2023). In this paper, we study whether similar bounds hold when replacing the circumference of $G$ by its {\em cocircumference}, defined as the largest size of a {\em bond} in $G$, an inclusion-wise minimal set of edges $F$ such that $G-F$ has more components than $G$. In matroidal terms, the cocircumference of $G$ is the circumference of the bond matroid of $G$. Our first result is the following `dual' version of Birmel\'e's theorem: The treewidth of a graph $G$ is at most its cocircumference. Our second and main result is an upper bound of $3k-2$ on the pathwidth of a $2$-connected graph $G$ with cocircumference $k$. Contrary to circumference, no such bound holds for the treedepth of $G$. Our two upper bounds are best possible up to a constant factor.

Authors:Simon R. Blackburn, Tuvi Etzion

Abstract: Let $n$, $s$ and $k$ be positive integers. For distinct $i,j\in\mathbb{Z}_n$, define $||i,j||_n$ to be the distance between $i$ and $j$ when the elements of $\mathbb{Z}_n$ are written in a circle. So \[ ||i,j||_n=\min\{(i-j)\bmod n,(j-i)\bmod n\}. \] A permutation $\pi:\mathbb{Z}_n\rightarrow\mathbb {Z}_n$ is \emph{$(s,k)$-clash-free} if $||\pi(i),\pi(j)||_n\geq k$ whenever $||i,j||_n<s$. So an $(s,k)$-clash-free permutation moves every pair of close elements (at distance less than $s$) to a pair of elements at large distance (at distance at least $k$). The notion of an $(s,k)$-clash-free permutation can be reformulated in terms of certain packings of $s\times k$ rectangles on an $n\times n$ torus. For integers $n$ and $k$ with $1\leq k<n$, let $\sigma(n,k)$ be the largest value of $s$ such that an $(s,k)$-clash-free permutation of $\mathbb{Z}_n$ exists. Strengthening a recent paper of Blackburn, which proved a conjecture of Mammoliti and Simpson, we determine the value of $\sigma(n,k)$ in all cases.

Authors:Jason I. Brown, Isaac McMullin

Abstract: A common model of robustness of a graph against random failures has all vertices operational, but the edges independently operational with probability $p$. One can ask for the probability that all vertices can communicate ({\em all-terminal reliability}) or that two specific vertices (or {\em terminals}) can communicate with each other ({\em two-terminal reliability}). A relatively new measure is {\em split reliability}, where for two fixed vertices $s$ and $t$, we consider the probability that every vertex communicates with one of $s$ or $t$, but not both. In this paper, we explore the existence for fixed numbers $n \geq 2$ and $m \geq n-1$ of an {\em optimal} connected $(n,m)$-graph $G_{n,m}$ for split reliability, that is, a connected graph with $n$ vertices and $m$ edges for which for any other such graph $H$, the split reliability of $G_{n,m}$ is at least as large as that of $H$, for {\em all} values of $p \in [0,1]$. Unlike the similar problems for all-terminal and two-terminal reliability, where only partial results are known, we completely solve the issue for split reliability, where we show that there is an optimal $(n,m)$-graph for split reliability if and only if $n\leq 3$, $m=n-1$, or $n=m=4$.

Authors:Chuanan Wei

Abstract: Binomial coefficients and harmonic numbers are important in many branches of number theory. With the help of the operator method and several summation and transformation formulas for hypergeometric series, we prove eight conjectural series of Z.-W. Sun containing binomial coefficients and harmonic numbers in this paper.

Authors:Simone Costa, Stefano Della Fiore

Abstract: A subset $S$ of a group $G$ is $t$-weakly sequenceable if there is an ordering $(a_1, \ldots, a_k)$ of its elements such that the partial sums $(s_0, s_1, \ldots, s_k)$, given by $s_0 = 0$ and $s_i = \sum_{j=1}^i a_j$ for $1 \leq i \leq k$, are different whenever $i$ and $j$ are distinct and $|i-j|\leq t$. In [10] it was proved that if the order of a group is $pe$ then all sufficiently large subsets of the non-identity elements are $t$-weakly sequenceable when $p > 3$ is prime, $e \leq 3$ and $t \leq 6$. Inspired by this result, we show that, if $G$ is of the type $G = \mathbb{Z}_p \rtimes_{\varphi} \mathbb{Z}_2$ and the set $S$ is balanced (i.e. contains the same number of even elements which are those in the coset $\mathbb{Z}_p\rtimes_{\varphi} \{0\}$ and odd ones that are those in its complement) then $S$ admits, regardless of its size, an alternating parity $t$-weak sequencing whenever $p > 3$ is prime and $t \leq 8$. On the other hand, we have been able to prove also the following asymptotic result. Let us consider groups of type $G = H \rtimes_{\varphi} \mathbb{Z}_2$, then all sufficiently large balanced subsets of the non-identity elements admit an alternating parity $t$-weak sequencing. This result has been obtained using a hybrid approach that combines both Ramsey theory and the probabilistic method. The same procedure works also for studying the weak sequenceability for generic sufficiently large (not necessarily balanced) sets. Here we have been able to prove that, if the size of a subset $S$ of a group $G$ is large enough and if $S$ does not contain $0$, then $S$ is $t$-weakly sequenceable.

Authors:Ryoshun Oba, Shin-ichi Tanigawa

Abstract: Belk and Connelly introduced the realizable dimension $\textrm{rd}(G)$ of a finite graph $G$, which is the minimum nonnegative integer $d$ such that every framework $(G,p)$ in any dimension admits a framework in $\mathbb{R}^d$ with the same edge lengths. They characterized finite graphs with realizable dimension at most $1$, $2$, or $3$ in terms of forbidden minors. In this paper, we consider periodic frameworks and extend the notion to $\mathbb{Z}$-symmetric graphs. We give a forbidden minor characterization of $\mathbb{Z}$-symmetric graphs with realizable dimension at most $1$ or $2$, and show that the characterization can be checked in polynomial time for given quotient $\mathbb{Z}$-labelled graphs.

Authors:Fazal Hayat, Shou-Jun Xu, Bo Zhou

Abstract: For a given connected graph $G$, the edge Mostar index $Mo_e(G)$ is defined as $Mo_e(G)=\sum_{e=uv \in E(G)}|m_u(e|G) - m_v(e|G)|$, where $m_u(e|G)$ and $m_v(e|G)$ are respectively, the number of edges of $G$ lying closer to vertex $u$ than to vertex $v$ and the number of edges of $G$ lying closer to vertex $v$ than to vertex $u$. In this paper, we determine sharp upper bound for edge Mostar index on bicyclic graphs with fixed number of edges, also the graphs that achieve the bound are completely characterized, and thus disprove a conjecture on the edge Mostar index of bicyclic graph in [H. Liu, L. Song, Q. Xiao, Z. Tang, On edge Mostar index of graphs. Iranian J. Math. Chem. 11(2) (2020) 95--106].

Authors:Tianjiao Dai, Qiancheng Ouyang, François Pirot

Abstract: Given a graph $G$, a vertex-colouring $\sigma$ of $G$, and a subset $X\subseteq V(G)$, a colour $x \in \sigma(X)$ is said to be \emph{odd} for $X$ in $\sigma$ if it has an odd number of occurrences in $X$. We say that $\sigma$ is an \emph{odd colouring} of $G$ if it is proper and every (open) neighbourhood has an odd colour in $\sigma$. The odd chromatic number of a graph $G$, denoted by $\chi_o(G)$, is the minimum $k\in\mathbb{N}$ such that an odd colouring $\sigma \colon V(G)\to [k]$ exists. In a recent paper, Caro, Petru\v sevski and \v Skrekovski conjectured that every connected graph of maximum degree $\Delta\ge 3$ has odd-chromatic number at most $\Delta+1$. We prove that this conjecture holds asymptotically: for every connected graph $G$ with maximum degree $\Delta$, $\chi_o(G)\le\Delta+O(\ln\Delta)$ as $\Delta \to \infty$. We also prove that $\chi_o(G)\le\lfloor3\Delta/2\rfloor+2$ for every $\Delta$. If moreover the minimum degree $\delta$ of $G$ is sufficiently large, we have $\chi_o(G) \le \chi(G) + O(\Delta \ln \Delta/\delta)$ and $\chi_o(G) = O(\chi(G)\ln \Delta)$. Finally, given an integer $h\ge 1$, we study the generalisation of these results to $h$-odd colourings, where every vertex $v$ must have at least $\min \{\deg(v),h\}$ odd colours in its neighbourhood. Many of our results are tight up to some multiplicative constant.

Authors:Babak Samadi, Nasrin Soltankhah, Ismael G. Yero

Abstract: The problem of injective coloring in graphs can be revisited through two different approaches: coloring the two-step graphs and vertex partitioning of graphs into open packing sets, each of which is equivalent to the injective coloring problem itself. Taking these facts into account, we observe that the injective coloring lies between graph coloring and domination theory. We make use of these three points of view in this paper so as to investigate the injective coloring of some well-known graph products. We bound the injective chromatic number of direct and lexicographic product graphs from below and above. In particular, we completely determine this parameter for the direct product of two cycles. We also give a closed formula for the corona product of two graphs.

Authors:Deping Song, Shuang Li, Xiao Wang

Abstract: Let $G$ be a bridgeless graph, $C$ is a circuit of $G$. Fan proposed a conjecture that if $G/C$ admits a nowhere-zero 4-flow, then $G$ admits a 4-flow $(D,f)$ such that $E(G)-E(C)\subseteq$ supp$(f)$ and $|\textrm{supp}(f)\cap E(C)|>\frac{3}{4}|E(C)|$. The purpose of this conjecture is to find shorter circuit cover in bridgeless graphs. Fan showed that the conjecture holds for $|E(C)|\le19.$ Wang, Lu and Zhang showed that the conjecture holds for $|E(C)|\le 27$. In this paper, we prove that the conjecture holds for $|E(C)|\le 35.$

Authors:Matthew Kreitzer, Mihai Nica, Rajesh Pereira

Abstract: A de Bruijn torus is the two dimensional generalization of a de Bruijn sequence. While some methods exist to generate these tori, only a few methods of construction are known. We present a novel method to generate de Bruijn tori with rectangular windows by combining two variants de Bruijn sequences called `Alternating de Bruijn sequences' and `De Bruijn families'.

Authors:Saeid Alikhani, Nima Ghanbari, Michael A. Henning

Abstract: A set $D$ of vertices is a strong dominating set in a graph $G$, if for every vertex $x\in V(G) \setminus D$ there is a vertex $y\in D$ with $xy\in E(G)$ and $deg(x) \leq deg(y)$. The strong domination number $\gamma_{st}(G)$ of $G$ is the minimum cardinality of a strong dominating set in $G$. Let $G$ be a connected graph constructed from pairwise disjoint connected graphs $G_1,\ldots ,G_k$ by selecting a vertex of $G_1$, a vertex of $G_2$, and identifying these two vertices, and thereafter continuing in this manner inductively. The graphs $G_1,\ldots ,G_k$ are the primary subgraphs of $G$. In this paper, we study the strong domination number of $K_r$-gluing of two graphs and investigate the strong domination number for some particular cases of graphs from their primary subgraphs.

Authors:Milad Ahanjideh, István Kovács, Klavdija Kutnar

Abstract: A graph $\Gamma$ is said to be stable if for the direct product $\Gamma\times\mathbf{K}_2$, ${\rm Aut}(\Gamma \times \mathbf{K}_2)$ is isomorphic to ${\rm Aut}(\Gamma) \times \mathbb{Z}_2$; otherwise, it is called unstable. An unstable graph is called non-trivially unstable when it is not bipartite and no two vertices have the same neighborhood. Wilson described nine families of unstable Rose Window graphs and conjectured that these contain all non-trivially unstable Rose Window graphs (2008). In this paper we show that the conjecture is true.

Authors:Elena V. Konstantinova, Artem Kravchuk

Abstract: Transposition graph $T_n$ is defined as a Cayley graph over the symmetric group generated by all transpositions. It is known that all eigenvalues of $T_n$ are integers. Moreover, zero is its eigenvalue for any $n\geqslant 4$. But the exact distribution of the spectrum of the graph $T_n$ is unknown. In this paper we prove that integers from the interval $[-\frac{n-4}{2}, \frac{n-4}{2}]$ lie in the spectrum of $T_n$ if $n \geqslant 19$.

Authors:Dimitrios M. Thilikos, Sebastian Wiederrecht

Abstract: We introduce an annotated extension of treewidth that measures the contribution of a vertex set $X$ to the treewidth of a graph $G.$ This notion provides a graph distance measure to some graph property $\mathcal{P}$: A vertex set $X$ is a $k$-treewidth modulator of $G$ to $\mathcal{P}$ if the treewidth of $X$ in $G$ is at most $k$ and its removal gives a graph in $\mathcal{P}.$This notion allows for a version of the Graph Minors Structure Theorem (GMST) that has no need for apices and vortices: $K_k$-minor free graphs are those that admit tree-decompositions whose torsos have $c_{k}$-treewidth modulators to some surface of Euler-genus $c_{k}.$ This reveals that minor-exclusion is essentially tree-decomposability to a ``modulator-target scheme'' where the modulator is measured by its treewidth and the target is surface embeddability. We then fix the target condition by demanding that $\Sigma$ is some particular surface and define a ``surface extension'' of treewidth, where $\Sigma\mbox{-}\mathsf{tw}(G)$ is the minimum $k$ for which $G$ admits a tree-decomposition whose torsos have a $k$-treewidth modulator to being embeddable in $\Sigma.$We identify a finite collection $\mathfrak{D}_{\Sigma}$ of parametric graphs and prove that the minor-exclusion of the graphs in $\mathfrak{D}_{\Sigma}$ precisely determines the asymptotic behavior of ${\Sigma}\mbox{-}\mathsf{tw},$ for every surface $\Sigma.$ It follows that the collection $\mathfrak{D}_{\Sigma}$ bijectively corresponds to the ``surface obstructions'' for $\Sigma,$ i.e., surfaces that are minimally non-contained in $\Sigma.$

Authors:Lucas Aragão, Maurício Collares, Gabriel Dahia, João Pedro Marciano

Abstract: The $n$-dimensional random twisted hypercube $\mathbf{G}_n$ is constructed recursively by taking two instances of $\mathbf{G}_{n-1}$, with any joint distribution, and adding a random perfect matching between their vertex sets. Benjamini, Dikstein, Gross, and Zhukovskii showed that its diameter is $O(n\log \log \log n/\log \log n)$ with high probability and at least ${(n - 1)/ \log_2 n}$. We improve their upper bound by showing that $$\operatorname{diam}(\mathbf{G}_n) = \big(1 + o(1)\big) \frac{n}{\log_2 n}$$ with high probability.

Authors:Van Magnan, Cory Palmer, Ryan Wood

Abstract: Let $\mathcal{F}\subseteq \binom{[n]}{r}$ be an intersecting family of sets and let $\Delta(\mathcal{F})$ be the maximum degree in $\mathcal{F}$, i.e., the maximum number of edges of $\mathcal{F}$ containing a fixed vertex. The \emph{diversity} of $\mathcal{F}$ is defined as $d(\mathcal{F}) := |\mathcal{F}| - \Delta(\mathcal{F})$. Diversity can be viewed as a measure of distance from the `trivial' maximum-size intersecting family given by the Erd\H os-Ko-Rado Theorem. Indeed, the diversity of this family is $0$. Moreover, the diversity of the largest non-trivial intersecting family \`a la Hilton-Milner is $1$. It is known that the maximum possible diversity of an intersecting family $\mathcal{F}\subseteq \binom{[n]}{r}$ is $\binom{n-3}{r-2}$ as long as $n$ is large enough. We introduce a generalization called the \emph{$C$-weighted diversity} of $\mathcal{F}$ as $d_C(\mathcal{F}) := |\mathcal{F}| - C \cdot \Delta(\mathcal{F})$. We determine the maximum value of $d_C(\mathcal{F})$ for intersecting families $\mathcal{F} \subseteq \binom{[n]}{r}$ and characterize the maximal families for $C\in \left[0,\frac{7}{3}\right)$ as well as give general bounds for all $C$. Our results imply, for large $n$, a recent conjecture of Frankl and Wang concerning a related diversity-like measure. Our primary technique is a variant of Frankl's Delta-system method.

Authors:Sergey Goryainov, Chi Hoi Yip

Abstract: Let $q$ be a prime power. We study extremal Peisert-type graphs of order $q^2$ without the strict-EKR property, that is, Peisert-type graphs of order $q^2$ without the strict-EKR property and with the minimum number of edges. First, we determine this minimum number of edges for each value of $q$. If $q$ is a square, we show the uniqueness of extremal graph and its isomorphism with certain affine polar graph. Using the isomorphism, we conclude that there is no Hilton-Milner type result for this extremal graph. We also prove the tightness of the weight-distribution bound for both non-principal eigenvalues of this graph. If $q$ is a cube but not a square, we show the uniqueness of extremal graph and determine the number and the structure of non-canonical cliques. Finally, we show such uniqueness result does not extend to all $q$.

Authors:Takuya Inoue

Abstract: The alternating sign matrices-descending plane partitions (ASM-DPP) bijection problem is one of the most intriguing open problems in bijective combinatorics, which is also relevant to integrable combinatorics. The notion of a signed set and a signed bijection is used in [Fischer, I. \& Konvalinka, M., Electron. J. Comb., 27 (2020) 3-35.] to construct a bijection between $\text{ASM}_n \times \text{DPP}_{n-1}$ and $\text{DPP}_n \times \text{ASM}_{n-1}$. Here, we shall construct a more natural alternative to a signed bijection between alternating sign matrices and shifted Gelfand-Tsetlin patterns which is presented in that paper, based on the notion of compatibility which we introduce to measure the naturalness of a signed bijection. In addition, we give a bijective proof for the refined enumeration of an extension of alternating sign matrices with $n+3$ statistics, first proved in [Fischer, I. \& Schreier-Aigner, F., Advances in Mathematics 413 (2023) 108831.].

Authors:Rangel Hernández-Ortiz, Kolja Knauer, Luis Pedro Montejano

Abstract: We study the existence and the number of $k$-neighborly reorientations of an oriented matroid. This leads to $k$-variants of McMullen's problem and Roudneff's conjecture, the case $k=1$ being the original statements on complete cells in arrangements. Adding to results of Larman and Garc\'ia-Col\'in, we provide new bounds on the $k$-McMullen's problem and prove the conjecture for several ranks and $k$ by computer. Further, we show that $k$-Roudneff's conjecture for fixed rank and $k$ reduces to a finite case analyse. As a consequence we prove the conjecture for odd rank $r$ and $k=\frac{r-1}{2}$ as well as for rank $6$ and $k=2$ with the aid of the computer.

Authors:Ada Stelzer, Alexander Yong

Abstract: An algorithm is presented that generates sets of size equal to the degree of a given variety defined by a homogeneous ideal. This algorithm suggests a versatile framework to study various problems in combinatorial algebraic geometry and related fields.

Authors:W. T. Gowers, Thomas Karam

Abstract: Let $p$ be a prime, let $S$ be a non-empty subset of $\mathbb{F}_p$ and let $0<\epsilon\leq 1$. We show that there exists a constant $C=C(p, \epsilon)$ such that for every positive integer $k$, whenever $\phi_1, \dots, \phi_k: \mathbb{F}_p^n \rightarrow \mathbb{F}_p$ are linear forms and $E_1, \dots, E_k$ are subsets of $\mathbb{F}_p$, there exist linear forms $\psi_1, \dots, \psi_C: \mathbb{F}_p^n \rightarrow \mathbb{F}_p$ and subsets $F_1, \dots, F_C$ of $\mathbb{F}_p$ such that the set $U=\{x \in S^n: \psi_1(x) \in F_1, \dots, \psi_C(x) \in F_C\}$ is contained inside the set $V=\{x \in S^n: \phi_1(x) \in E_1, \dots, \phi_k(x) \in E_k\}$, and the difference $V \setminus U$ has density at most $\epsilon$ inside $S^n$. We then generalize this result to one where $\phi_1, \dots, \phi_k$ are replaced by homomorphisms $G^n \to H$ for some pair of finite Abelian groups $G$ and $H$, and to another where they are replaced by polynomial maps $\mathbb{F}_p^n \to \mathbb{F}_p$ of small degree.

Authors:Francisco Arrepol, Patricio Asenjo, Raúl Astete, Víctor Cartes, Anahí Gajardo, Valeria Henríquez, Catalina Opazo, Nicolás Sanhueza-Matamala, Christopher Thraves Caro

Abstract: For a graph $G$, an edge-separating (resp. vertex-separating) path system of $G$ is a family of paths in $G$ such that for any pair of edges $e_1, e_2$ (resp. pair of vertices $v_1, v_2$) of $G$ there is at least one path in the family that contains one of $e_1$ and $e_2$ (resp. $v_1$ and $v_2$) but not the other. We determine the size of a minimum edge-separating path system of an arbitrary tree $T$ as a function of its number of leaves and degree-two vertices. We obtain bounds for the size of a minimal vertex-separating path system for trees, which we show to be tight in many cases. We obtain similar results for a variation of the definition, where we require the path system to separate edges and vertices simultaneously. Finally, we investigate the size of a minimal vertex-separating path system in Erd\H{o}s--R\'enyi random graphs.

Authors:Allen Herman, Neha Joshi

Abstract: In this paper we determine all fusions of the association scheme $\mathcal{A} \otimes \mathcal{A}$, where $\mathcal{A}$ is the symmetric rank $3$ association scheme corresponding to a strongly regular graph. This includes both guaranteed fusions, which are fusions for all symmetric rank $3$ association schemes $\mathcal{A}$, and specific case fusions, which only exist under restrictions on the parameters of the association scheme. Along the way we will determine the fusions of wreath products of strongly regular graphs and the fusions of the tensor square of a symmetric rank $3$ table algebra. This extends recent work of the authors and Meagher, which solved the same problem for the generalized Hamming scheme $H(2,\mathcal{A})$ of the association scheme obtained from a strongly regular graph. The main results of this article show (1) the families of strongly regular graphs for which $\mathcal{A} \otimes \mathcal{A}$ has a special case fusion are the same families for which $H(2,\mathcal{A})$ has a special case fusion; and (2) the imprimitive strongly regular graphs are the only family of strongly regular graphs for which the wreath product $\mathcal{A} \wr \mathcal{A}$ has a special case fusion.

Authors:Thomas K. Waring

Abstract: Fill each box in a Young diagram with the number of paths from the bottom of its column to the end of its row, using steps north and east. Then, any square sub-matrix of this array starting on the south-east boundary has determinant one. We provide a - to our knowledge - new bijective argument for this result. Using the same ideas, we prove further identities involving these numbers which correspond to an integral orthonormal basis of the inner product space with Gram matrix given by the array in question. This provides an explicit answer to a question (listed as unsolved) raised in Exercise 6.27 c) of Stanley's Enumerative Combinatorics.

Authors:Ali Ghalavand, Sandi Klavžar, Mostafa Tavakoli

Abstract: The mixed metric dimension ${\rm mdim}(G)$ of a graph $G$ is the cardinality of a smallest set of vertices that (metrically) resolves each pair of elements from $V(G)\cup E(G)$. We say that $G$ is a max-mdim graph if ${\rm mdim}(G) = n(G)$. It is proved that a max-mdim graph $G$ with $n(G)\ge 7$ contains a vertex of degree at least $5$. Using the strong product of graphs and amalgamations large families of max-mdim graphs are constructed. The mixed metric dimension of graphs with at least one universal vertex is determined. The mixed metric dimension of graphs $G$ with cut vertices is bounded from the above and the mixed metric dimension of block graphs computed.

Authors:Brian Alspach, Primoz Sparl

Abstract: We investigate connected cubic vertex-transitive graphs whose edge sets admit a partition into a $2$-factor $\mathcal{C}$ and a $1$-factor that is invariant under a vertex-transitive subgroup of the automorphism group of the graph and where the quotient graph with respect to $\mathcal{C}$ is a cycle. There are two essentially different types of such cubic graphs. In this paper we focus on the examples of what we call the alternating type. We classify all such examples admitting a vertex-transitive subgroup of the automorphism group of the graph preserving the corresponding $2$-factor and also determine the ones for which the $2$-factor is invariant under the full automorphism group of the graph. In this way we introduce a new infinite family of cubic vertex-transitive graphs that is a natural generalization of the well-known generalized Petersen graphs as well as of the honeycomb toroidal graphs. The family contains an infinite subfamily of arc-regular examples and an infinite family of $2$-arc-regular examples.

Authors:Csilla Bujtás andMichael A. Henning, Sandi Klavžar

Abstract: For some $\alpha$ with $0 < \alpha \le 1$, a subset $X$ of vertices in a graph $G$ of order~$n$ is an $\alpha$-partial dominating set of $G$ if the set $X$ dominates at least $\alpha \times n$ vertices in $G$. The $\alpha$-partial domination number ${\rm pd}_{\alpha}(G)$ of $G$ is the minimum cardinality of an $\alpha$-partial dominating set of $G$. In this paper partial domination of graphs with minimum degree at least $3$ is studied. It is proved that if $G$ is a graph of order~$n$ and with $\delta(G)\ge 3$, then ${\rm pd}_{\frac{7}{8}}(G) \le \frac{1}{3}n$. If in addition $n\ge 60$, then ${\rm pd}_{\frac{9}{10}}(G) \le \frac{1}{3}n$, and if $G$ is a connected cubic graph of order $n\ge 28$, then ${\rm pd}_{\frac{13}{14}}(G) \le \frac{1}{3}n$. Along the way it is shown that there are exactly four connected cubic graphs of order $14$ with domination number $5$.

Authors:Jia Xu, Yong Yao

Abstract: Inequalities among symmetric functions are fundamental questions in mathematics and have various applications in science and engineering. In this paper, we tackle a conjecture about inequalities among the complete homogeneous symmetric function $H_{n,\lambda}$, that is, the inequality $H_{n,\lambda}\leq H_{n,\mu}$ implies majorization order $\lambda\preceq\mu$. This conjecture was proposed by Cuttler, Greene and Skandera in 2011. The conjecture is a close analogy with other known results on Muirhead-type inequalities. In 2021, Heaton and Shankar disproved the conjecture by showing a counterexample for degree $d=8$ and number of variables $n=3$. They then asked whether the conjecture is true when~ the number of variables, $n$, is large enough? In this paper, we answer the question by proving that the conjecture does not hold when $d\geq8$ and $n\geq2$. A crucial step of the proof relies on variables reduction. Inspired by this, we propose a new conjecture for $H_{n,\lambda}\leq H_{n,\mu}$.

Authors:Sjoerd de Vries

Abstract: Newton's identities provide a way to express elementary symmetric polynomials in terms of power polynomials over fields of characteristic zero. In this article we study symmetric polynomials in positive characteristic. Our main result shows that in this setting, one can recover the elementary symmetric polynomials as rational functions in the power polynomials.

Authors:Eng Keat Hng

Abstract: Garbe, Hladk\'y, \v{S}ileikis and Skerman recently introduced a general class of random graph processes called flip processes and proved that the typical evolution of these discrete-time random graph processes correspond to certain continuous-time deterministic graphon trajectories. We obtain a complete characterization of the equivalence classes of flip process rules with the same graphon trajectories. As an application, we characterize the flip process rules which are unique in their equivalence classes. These include several natural families of rules such as the complementing rules, the component completion rules, the extremist rules, and the clique removal rules.

Authors:Andrzej Grzesik, Justyna Jaworska, Bartłomiej Kielak, Aliaksandra Novik, Tomasz Ślusarczyk

Abstract: A classical Tur\'an problem asks for the maximum possible number of edges in a graph of a given order that does not contain a particular graph $H$ as a subgraph. It is well-known that the chromatic number of $H$ is the graph parameter which describes the asymptotic behavior of this maximum. Here, we consider an analogous problem for oriented graphs, where compressibility plays the role of the chromatic number. Since any oriented graph having a directed cycle is not contained in any transitive tournament, it makes sense to consider only acyclic oriented graphs as forbidden subgraphs. We provide basic properties of the compressibility, show that the compressibility of acyclic oriented graphs with out-degree at most 2 is polynomial with respect to the maximum length of a directed path, and that the same holds for a larger out-degree bound if the Erd\H{o}s-Hajnal conjecture is true. Additionally, generalizing previous results on powers of paths and arbitrary orientations of cycles, we determine the compressibility of acyclic oriented graphs with a restricted structure.

Authors:Colin Defant, Rachana Madhukara, Hugh Thomas

Abstract: The first author recently introduced toric promotion, an operator that acts on the labelings of a graph $G$ and serves as a cyclic analogue of Sch\"utzenberger's promotion operator. Toric promotion is defined as the composition of certain toggle operators, listed in a natural cyclic order. We consider more general permutoric promotion operators, which are defined as compositions of the same toggles, but in permuted orders. We settle a conjecture of the first author by determining the orders of all permutoric promotion operators when $G$ is a path graph. In fact, we completely characterize the orbit structures of these operators, showing that they satisfy the cyclic sieving phenomenon. The first half of our proof requires us to introduce and analyze new broken promotion operators, which can be interpreted via globs of liquid gliding on a path graph. For the latter half of our proof, we reformulate the dynamics of permutoric promotion via stones sliding along a cycle graph and coins colliding with each other on a path graph.

Authors:Eden Kuperwasser, Wojciech Samotij

Abstract: Given a family of graphs $\mathcal{F}$ and an integer $r$, we say that a graph is $r$-Ramsey for $\mathcal{F}$ if any $r$-colouring of its edges admits a monochromatic copy of a graph from $\mathcal{F}$. The threshold for the classic Ramsey property, where $\mathcal{F}$ consists of one graph, was located in the celebrated work of R\"odl and Ruci\'nski. In this paper, we offer a twofold generalisation to the R\"odl--Ruci\'nski theorem. First, we show that the list-colouring version of the property has the same threshold. Second, we extend this result to finite families $\mathcal{F}$, where the threshold statements might also diverge. This also confirms further special cases of the Kohayakawa--Kreuter conjecture. Along the way, we supply a short(-ish), self-contained proof of the $0$-statement of the R\"odl--Ruci\'nski theorem.

Authors:Riccardo W. Maffucci

Abstract: A $3$-polytope is a $3$-connected, planar graph. It is called unigraphic if it does not share its vertex degree sequence with any other $3$-polytope, up to graph isomorphism. The classification of unigraphic $3$-polytopes appears to be a difficult problem. In this paper we prove that, apart from pyramids, all unigraphic $3$-polytopes have no $n$-gonal faces for $n\geq 8$. Our method involves defining several planar graph transformations on a given $3$-polytope containing an $n$-gonal face with $n\geq 8$. The delicate part is to prove that, for every such $3$-polytope, at least one of these transformations both preserves $3$-connectivity, and is not an isomorphism.

Authors:Attila Joó

Abstract: L. Soukup formulated an abstract framework in his introductory paper for proving theorems about uncountable graphs by subdividing them by an increasing continuous chain of elementary submodels. The applicability of this method relies on the preservation of a certain property (that varies from problem to problem) by the subgraphs obtained by subdividing the graph by an elementary submodel. He calls the properties that are preserved ``well-reflecting''. The aim of this paper is to investigate the possibility of weakening of the assumption ``well-reflecting'' in L. Soukup's framework. Our motivation is to gain better understanding about a class of problems in infinite graph theory where a weaker form of well-reflection naturally occurs.

Authors:Igor Balla

Abstract: In 1930, Tammes posed the problem of determining $\rho(r, n)$, the minimum over all sets of $n$ unit vectors in $\mathbb{R}^r$ of their maximum pairwise inner product. In 1955, Rankin determined $\rho(r,n)$ whenever $n \leq 2r$ and in this paper we show that $\rho(r, 2r + k ) \geq \frac{\left(\frac{8}{27}k + 1\right)^{1/3} - 1}{2r + k}$, answering a question of Bukh and Cox. As a consequence, we conclude that the maximum size of a binary code with block length $r$ and minimum Hamming distance $(r-j)/2$ is at most $(2 + o(1))r$ when $j = o(r^{1/3})$, resolving a conjecture of Tiet\"av\"ainen from 1980 in a strong form. Furthermore, using a recently discovered connection to binary codes, this yields an analogous result for set-coloring Ramsey numbers of triangles.

Authors:János Barát, Zoltán L. Blázsik

Abstract: In an orientation $O$ of the graph $G$, an arc $e$ is deletable if and only if $O-e$ is strongly connected. For a $3$-edge-connected graph $G$, the Frank number is the minimum $k$ for which $G$ admits $k$ strongly connected orientations such that for every edge $e$ of $G$ the corresponding arc is deletable in at least one of the $k$ orientations. H\"orsch and Szigeti conjectured the Frank number is at most $3$ for every $3$-edge-connected graph $G$. We prove an upper bound of $5$, which improves the previous bound of $7$.

Authors:Olivier Bernardi, Éric Fusy, Shizhe Liang

Abstract: We define some Schnyder-type combinatorial structures on a class of planar triangulations of the pentagon which are closely related to 5-connected triangulations. The combinatorial structures have three incarnations defined in terms of orientations, corner-labelings, and woods respectively. The wood incarnation consists in 5 spanning trees crossing each other in an orderly fashion. Similarly as for Schnyder woods on triangulations, it induces, for each vertex, a partition of the inner triangles into face-connected regions (5~regions here). We show that the induced barycentric vertex-placement, where each vertex is at the barycenter of the 5 outer vertices with weights given by the number of faces in each region, yields a planar straight-line drawing.

Authors:Eric Katz, Max Kutler

Abstract: We make a systematic study of matroidal mixed Eulerian numbers which are certain intersection numbers in the matroid Chow ring generalizing the mixed Eulerian numbers introduced by Postnikov. These numbers are shown to be valuative and obey a log-concavity relation. We establish recursion formulas and use them to relate matroidal mixed Eulerian numbers to the characteristic and Tutte polynomials, reproving results of Huh-Katz and Berget-Spink-Tseng. Generalizing Postnikov, we show that these numbers are equal to certain weighted counts of binary trees. Lastly, we study these numbers for perfect matroid designs, proving that they generalize the remixed Eulerian numbers of Nadeau-Tewari.

Authors:Raphael Steiner

Abstract: A set $\mathcal{G}$ of planar graphs on the same number $n$ of vertices is called simultaneously embeddable if there exists a set $P$ of $n$ points in the plane such that every graph $G \in \mathcal{G}$ admits a (crossing-free) straight-line embedding with vertices placed at points of $P$. A well-known open problem from 2007 posed by Brass, Cenek, Duncan, Efrat, Erten, Ismailescu, Kobourov, Lubiw and Mitchell, asks whether for some $n$ there exists a set $\mathcal{G}$ consisting of two planar graphs on $n$ vertices that are not simultaneously embeddable. While this remains widely open, we give a short proof that for every $\varepsilon>0$ and sufficiently large $n$ there exists a collection of at most $(4+\varepsilon)\log_2(n)$ planar graphs on $n$ vertices which cannot be simultaneously embedded. This significantly improves the previous exponential bound of $O(n\cdot 4^{n/11})$ for the same problem which was recently established by Goenka, Semnani and Yip.

Authors:Yuta Watanabe

Abstract: The generalized wreath product of association schemes was introduced by R.~A.~Bailey in European Journal of Combinatorics 27 (2006) 428--435. It is known as a generalization of both wreath and direct products of association schemes. In this paper, we discuss the Terwilliger algebra of the generalized wreath product of commutative association schemes. I will describe its structure and its central primitive idempotents in terms of the parameters of each factors and their central primitive idempotents.

Authors:Martin Balko, Marian Poljak

Abstract: For graphs $G^<$ and $H^<$ with linearly ordered vertex sets, the \ordered Ramsey number $r_<(G^<,H^<)$ is the smallest positive integer $N$ such that any red-blue coloring of the edges of the complete ordered graph $K^<_N$ on $N$ vertices contains either a blue copy of $G^<$ or a red copy of $H^<$. Motivated by a problem of Conlon, Fox, Lee, and Sudakov (2017), we study the numbers $r_<(M^<,K^<_3)$ where $M^<$ is an ordered matching on $n$ vertices. We prove that almost all $n$-vertex ordered matchings $M^<$ with interval chromatic number 2 satisfy $r_<(M^<,K^<_3) \in \Omega((n/\log n)^{5/4})$ and $r_<(M^<,K^<_3) \in O(n^{7/4})$, improving a recent result by Rohatgi (2019). We also show that there are $n$-vertex ordered matchings $M^<$ with interval chromatic number at least 3 satisfying $r_<(M^<,K^<_3) \in \Omega((n/\log n)^{4/3})$, which asymptotically matches the best known lower bound on these off-diagonal ordered Ramsey numbers for general $n$-vertex ordered matchings.

Authors:Harshit Kumar Choudhary, I. Vinod Reddy

Abstract: A \emph{star coloring} of a graph $G$ is a proper vertex-coloring such that no path on four vertices is $2$-colored. The minimum number of colors required to obtain a star coloring of a graph $G$ is called star chromatic number and it is denoted by $\chi_s(G)$. A graph $G$ is called $k$-critical if $\chi_s(G)=k$ and $\chi_s(G -e) < \chi_s(G)$ for every edge $e \in E(G)$. In this paper, we give a characterization of 3-critical, $(n-1)$-critical and $(n-2)$-critical graphs with respect to star coloring, where $n$ denotes the number of vertices of $G$. We also give upper and lower bounds on the minimum number of edges in $(n-1)$-critical and $(n-2)$-critical graphs.

Authors:Nicanor Carrasco-Vargas

Abstract: In this paper we present a short proof of a theorem by Erd\H{o}s, Gr\"unwald and Weiszfeld on the characterization of infinite graphs which admit infinite Eulerian trails. In addition, we extend this result with a characterization of which finite trails can be extended to infinite Eulerian trails. Our proof is computable and yields an effective version of this theorem. This exhibits stark contrast with other classical results in the theory of infinite graphs which are not effective.

Authors:Georgios Kontogeorgiou, Alexandros Leivaditis, Kostas I. Psaromiligkos, Giannos Stamoulis, Dimitris Zoros

Abstract: A graph parameter is self-dual in some class of graphs embeddable in some surface if its value does not change in the dual graph by more than a constant factor. We prove that the branchwidth of connected hypergraphs without bridges and loops that are embeddable in some surface of Euler genus at most g is an (1,g)-self-dual parameter. This is the first proof that branchwidth is an additively self-dual width parameter.

Authors:Sophie Huczynska, Siaw-Lynn Ng

Abstract: Strong external difference families (SEDFs) are much-studied combinatorial objects motivated by an information security application. A well-known conjecture states that only one abelian SEDF with more than 2 sets exists. We show that if the disjointness condition is replaced by non-disjointness, then abelian SEDFs can be constructed with more than 2 sets (indeed any number of sets). We demonstrate that the non-disjoint analogue has striking differences to, and connections with, the classical SEDF and arises naturally via another coding application.

Authors:Samuele Giraudo

Abstract: Clones are generalizations of operads forming powerful instruments to describe varieties of algebras wherein repeating variables are allowed in their relations. They allow us in this way to realize and study a large range of algebraic structures. A functorial construction from the category of monoids to the category of clones is introduced. The obtained clones involve words on positive integers where letters are pigmented by elements of a monoid. By considering quotients of these structures, we construct a complete hierarchy of clones involving some families of combinatorial objects. This provides clone realizations of some known and some new special classes of monoids as among others the variety of left-regular bands, bounded semilattices, and regular band monoids.

Authors:Yanni Zhai, Xiying Yuan

Abstract: For a set of graphs $\mathcal{F}$, a graph is said to be $\mathcal{F}$-free if it does not contain any graph in $\mathcal{F}$ as a subgraph. Let Ex$_{sp}(n,\mathcal{F})$ denote the graphs with the maximum spectral radius among all $\mathcal{F}$-free graphs of order $n$. A linear forest is a graph whose connected component is a path. Denote by $\mathcal{L}_s$ the family of all linear forests with $s$ edges. In this paper the graphs in Ex$_{sp}(n,\{K_{k+1},\mathcal{L}_s\})$ will be completely characterized when $n$ is appropriately large.

Authors:Sizhong Zhou, Jiancheng Wu

Abstract: Let $\mathcal{A}$ be a set of connected graphs. Then a spanning subgraph $A$ of $G$ is called an $\mathcal{A}$-factor if each component of $A$ is isomorphic to some member of $\mathcal{A}$. Especially, when every graph in $\mathcal{A}$ is a path, $A$ is a path factor. For a positive integer $d\geq2$, we write $\mathcal{P}_{\geq d}=\{P_i|i\geq d\}$. Then a $\mathcal{P}_{\geq d}$-factor means a path factor in which every component admits at least $d$ vertices. A graph $G$ is called a $(\mathcal{P}_{\geq d},m)$-factor deleted graph if $G-E'$ admits a $\mathcal{P}_{\geq d}$-factor for any $E'\subseteq E(G)$ with $|E'|=m$. A graph $G$ is called a $(\mathcal{P}_{\geq d},k)$-factor critical graph if $G-Q$ has a $\mathcal{P}_{\geq d}$-factor for any $Q\subseteq V(G)$ with $|Q|=k$. In this paper, we present two degree conditions for graphs to be $(\mathcal{P}_{\geq3},m)$-factor deleted graphs and $(\mathcal{P}_{\geq3},k)$-factor critical graphs. Furthermore, we show that the two results are best possible in some sense.

Authors:Xinbu Cheng, Zixiang Xu

Abstract: The Euclidean Gallai-Ramsey problem, which investigates the existence of monochromatic or rainbow configurations in a colored $n$-dimensional Euclidean space $\mathbb{E}^{n}$, was introduced and studied recently. We further explore this problem for various configurations including triangles, squares, lines, and the structures with specific properties, such as rectangular and spherical configurations. Several of our new results provide refinements to the results presented in a recent work by Mao, Ozeki and Wang. One intriguing phenomenon evident on the Gallai-Ramsey results proven in this paper is that the dimensions of spaces are often independent of the number of colors. Our proofs primarily adopt a geometric perspective.

Authors:Igor Balla, Oliver Janzer, Benny Sudakov

Abstract: In this short note we prove a lower bound for the MaxCut of a graph in terms of the Lov\'asz theta function of its complement. We combine this with known bounds on the Lov\'asz theta function of complements of $H$-free graphs to recover many known results on the MaxCut of $H$-free graphs. In particular, we give a new, very short proof of a conjecture of Alon, Krivelevich and Sudakov about the MaxCut of graphs with no cycles of length $r$.

Authors:Alex Cohen, Cosmin Pohoata, Dmitrii Zakharov

Abstract: For sufficiently large $n$, we show that in every configuration of $n$ points chosen inside the unit square there exists a triangle of area less than $n^{-8/7-1/2000}$. This improves upon a result of Koml\'os, Pintz and Szemer\'edi from 1982. Our approach establishes new connections between the Heilbronn triangle problem and various themes in incidence geometry and projection theory which are closely related to the discretized sum-product phenomenon.

Authors:Ivan Damnjanović

Abstract: A nut graph is a non-trivial simple graph such that its adjacency matrix has a one-dimensional null space spanned by a full vector. It was recently shown by the authors that there exists a $d$-regular circulant nut graph of order $n$ if and only if $4 \mid d, \, 2 \mid n, \, d > 0$, together with $n \ge d + 4$ if $d \equiv_8 4$ and $n \ge d + 6$ if $8 \mid d$, as well as $(n, d) \neq (16, 8)$ [arXiv:2212.03026, 2022]. In this paper, we demonstrate the existence of a $d$-regular Cayley nut graph of order $n$ for each $4 \mid d, \, d > 0$ and $2 \mid n, \, n \ge d + 4$, thereby resolving the existence problem for Cayley nut graphs and vertex-transitive nut graphs whose degree is divisible by four.

Authors:Gwen McKinley, Sam Spiro

Abstract: Given a graph $F$, we define $\operatorname{ex}(G_{n,p},F)$ to be the maximum number of edges in an $F$-free subgraph of the random graph $G_{n,p}$. Very little is known about $\operatorname{ex}(G_{n,p},F)$ when $F$ is bipartite, with essentially tight bounds known only when $F$ is either $C_4, C_6, C_{10}$, or $K_{s,t}$ with $t$ sufficiently large in terms of $s$, due to work of F\"uredi and of Morris and Saxton. We extend this work by establishing essentially tight bounds when $F$ is a theta graph with sufficiently many paths. Our main innovation is in proving a balanced supersaturation result for vertices, which differs from the standard approach of proving balanced supersaturation for edges.

Authors:Seok Hyun Byun, Svetlana Poznanović

Abstract: Recently, Glasby and Paseman considered the following sequence of binomial sums $\{2^{-r}\sum_{i=0}^{r}\binom{m}{i}\}_{r=0} ^{m}$ and showed that this sequence is unimodal and attains its maximum value at $r=\lfloor\frac{m}{3}\rfloor+1$ for $m\in\mathbb{Z}_{\geq0}\setminus\{0,3,6,9,12\}$. They also analyzed the asymptotic behavior of the maximum value of the sequence as $m$ approaches infinity. In the present work, we generalize their results by considering the sequence $\{(1+a)^{-r}\sum_{i=0}^{r}\binom{m}{i}a^{i}\}_{r=0} ^{m}$ for positive integers $a$. We also consider a family of discrete probability distributions that naturally arises from this sequence.

Authors:Ritesh Goenka, Pardis Semnani, Chi Hoi Yip

Abstract: We show that there are $O(n \cdot 4^{n/11})$ planar graphs on $n$ vertices which do not admit a simultaneous straight-line embedding on any $n$-point set in the plane. In particular, this improves the best known bound $O(n!)$ significantly.

Authors:Flavien Mabilat LMR

Abstract: In this article, we study the classification of some natural numbers related to the combinatorics of congruence subgroups of the modular group. More precisely, we will focus here on the notion of minimal monomial solutions. These are the solutions of a matrix equation (also appearing in the study of Coxeter friezes), modulo an integer $N$, whose components are identical and minimal for this property. Our objective here is to study the integers $N$ for which the minimal monomial solutions satisfying some fixed conditions have an irreducibility property. In particular, we will classify the monomially irreducible integers which are the integers for which all the nonzero minimal monomial solutions are irreducible.

Authors:Jin Guo, Alexander L. Gavrilyuk, Ilia Ponomarenko

Abstract: It is proved that the Weisfeiler-Leman dimension of the class of permutation graphs is at most 18. Previously it was only known that this dimension is finite (Gru{\ss}ien, 2017).

Authors:Yetong Sha, Huan Xiong

Abstract: In 2016, Nath and Sellers proposed a conjecture regarding the precise largest size of ${(s,ms-1,ms+1)}$-core partitions. In this paper, we prove their conjecture. One of the key techniques in our proof is to introduce and study the properties of generalized-$\beta$-sets, which extend the concept of $\beta$-sets for core partitions. Our results can be interpreted as a generalization of the well-known result of Yang, Zhong, and Zhou concerning the largest size of $(s,s+1,s+2)$-core partitions.

Authors:Huan Qiu, Keng Li, Guoping Wang

Abstract: The least eigenvalue of a graph $G$ is the least eigenvalue of adjacency matrix of $G$. In this paper we determine the graphs which attain the minimum least eigenvalue among all complements of connected simple graphs with given connectivity.

Authors:Henry Förster, Michael Kaufmann, Laura Merker, Sergey Pupyrev, Chrysanthi Raftopoulou

Abstract: A linear layout of a graph $ G $ consists of a linear order $\prec$ of the vertices and a partition of the edges. A part is called a queue (stack) if no two edges nest (cross), that is, two edges $ (v,w) $ and $ (x,y) $ with $ v \prec x \prec y \prec w $ ($ v \prec x \prec w \prec y $) may not be in the same queue (stack). The best known lower and upper bounds for the number of queues needed for planar graphs are 4 [Alam et al., Algorithmica 2020] and 42 [Bekos et al., Algorithmica 2022], respectively. While queue layouts of special classes of planar graphs have received increased attention following the breakthrough result of [Dujmovi\'c et al., J. ACM 2020], the meaningful class of bipartite planar graphs has remained elusive so far, explicitly asked for by Bekos et al. In this paper we investigate bipartite planar graphs and give an improved upper bound of 28 by refining existing techniques. In contrast, we show that two queues or one queue together with one stack do not suffice; the latter answers an open question by Pupyrev [GD 2018]. We further investigate subclasses of bipartite planar graphs and give improved upper bounds; in particular we construct 5-queue layouts for 2-degenerate quadrangulations.

Authors:Junjie Wang, Yang Yu, Jianbiao Hu, Peng Wen

Abstract: Let $a,b$ be two positive integers such that $a \le b$ and $a \equiv b$ (mod $2$). We say that a graph $G$ has an $(a,b)$-parity factor if $G$ has a spanning subgraph $F$ such that $d_{F}(v) \equiv b$ (mod $2$) and $a \le d_{F}(v) \le b$ for all $v \in V (G)$. In this paper, we provide a tight spectral radius condition for a graph to have $(a,b)$-parity factors.

Authors:Tao Feng, Weicong Li, Qing Xiang

Abstract: In this paper, we construct a new family of $(q^4+1)$-tight sets in $Q(24,q)$ or $Q^-(25,q)$ according as $q=3^f$ or $q\equiv 2\pmod 3$. The novelty of the construction is the use of the action of the exceptional simple group $F_4(q)$ on its minimal module over $\F_q$.

Authors:Garrison Koch, Nathan Shank

Abstract: The Roman Dominating number is a widely studied variant of the dominating number on graphs. Given a graph $G=(V,E)$, the dominating number of a graph is the minimum size of a vertex set, $V' \subseteq V$, so that every vertex in the graph is either in $V'$ or is adjacent to a vertex in $V'$. A Roman Dominating function of $G$ is defined as $f:V \rightarrow \{0,1,2\}$ such that every vertex with a label of 0 in $G$ is adjacent to a vertex with a label of 2. The Roman Dominating number of a graph is the minimum total weight over all possible Roman Dominating functions. In this paper, we analyze a new variant: $n$-attack Roman Domination, particularly focusing on 2-attack Roman Domination $(n=2)$. An $n$-attack Roman Dominating function of $G$ is defined similarly to the Roman Dominating function with the additional condition that, for any $j\leq n$, any subset $S$ of $j$ vertices all with label 0 must have at least $j$ vertices with label 2 in the open neighborhood of $S$. The $n$-attack Roman Dominating number is the minimum total weight over all possible $n$-attack Roman Dominating functions. We introduce properties as well as an algorithm to find the 2-attack Roman Domination number. We also consider how to place dominating vertices if you are only allowed a finite number of them through the help of a python program. Finally, we discuss the 2-attack Roman Dominating number of infinite regular graphs that tile the plane. We conclude with open questions and possible ways to extend these results to the general $n$-attack case.

Authors:Tara Abrishami, Bogdan Alecu, Maria Chudnovsky, Sepehr Hajebi, Sophie Spirkl, Kristina Vušković

Abstract: The tree-independence number tree-$\alpha$, first defined and studied by Dallard, Milani\v{c} and \v{S}torgel, is a variant of treewidth tailored to solving the maximum independent set problem. Over a series of papers, Abrishami et al.\ developed the so-called central bag method to study induced obstructions to bounded treewidth. Among others, they showed that, in a certain superclass $\mathcal C$ of (even hole, diamond, pyramid)-free graphs, treewidth is bounded by a function of the clique number. In this paper, we relax the bounded clique number assumption, and show that $\mathcal C$ has bounded tree-$\alpha$. Via existing results, this yields a polynomial time algorithm for the maximum independent set problem in this class. Our result also corroborates, for this class of graphs, a conjecture of Dallard, Milani\v{c} and \v{S}torgel that in a hereditary graph class, tree-$\alpha$ is bounded if and only if the treewidth is bounded by a function of the clique number.

Authors:Mohan Ramu, Joseph Varghese Kureethara

Abstract: For a given graph $G$, let $f:V(G)\to \{1,2,\ldots,n\}$ be a bijective mapping. For a given edge $uv \in E(G)$, $\sigma(uv)=+$, if $f(u)$ and $f(v)$ have the same parity and $\sigma(uv)=-$, if $f(u)$ and $f(v)$ have opposite parity. The resultant signed graph is called a parity signed graph. Let us denote a parity signed graph $S=(G,\sigma)$ by $G_\sigma$. Let $E^-(G_\sigma)$ be a set of negative edges in a parity signed graph and let $Si(G)$ be the set of all parity signatures for the underlying graph $G$. We define the \emph{rna} number of $G$ as $\sigma^-(G)=\min\{p(E^-(G_\sigma)):\sigma \in Si(G)\}$. In this paper, we prove a non-trivial upper bound in the case of trees: $\sigma^-(T)\leq \left \lceil \frac{n}{2}\right \rceil$, where $T$ is a tree of order $n+1$. We have found families of trees whose \emph{rna} numbers are bounded above by $\left \lceil \frac{\Delta}{2}\right \rceil$ and also we have shown that for any $i\leq \left \lceil \frac{n}{2}\right \rceil$, there exists a tree $T$ (of order $n+1$) with $\sigma^-(T)=i$. This paper gives the characterizations of graphs with \emph{rna} number 1 in terms of its spanning trees and characterizations of graphs with \emph{rna} number 2.

Authors:Benedikt Stufler

Abstract: We present a new probabilistic proof of Otter's asymptotic formula for the number of unlabelled trees with a given number of vertices. We additionally prove a new approximation result, showing that the total variation distance between random P\'olya trees and random unlabelled trees tends to zero when the number of vertices tends to infinity. In order to demonstrate that our approach is not restricted to trees we extend our results to tree-like classes of graphs.

Authors:Alexander Clow, Neil McKay

Abstract: In this paper we consider ordinal sums of combinatorial games where each summand is a number, not necessarily in canonical form. In doing so we give formulas for the value of an ordinal sum of numbers where the literal form of the base has certain properties. These formulas include a closed form of the value of any ordinal sum of numbers where the base is in canonical form. Our work employs a recent result of Clow which gives a criteria for an ordinal sum G : K = H : K when G and H do not have the same literal form, as well as expanding this theory with the introduction of new notation, a novel ruleset, Teetering Towers, and a novel construction of the canonical forms of numbers in Teetering Towers. In doing so, we resolve the problem of determining the value of an ordinal sum of numbers in all but a few cases appearing in Conway's On Numbers and Games; thus generalizing a number of existing results and techniques including Berlekamp' sign rule, van Roode's signed binary number method, and recent work by Carvalho, Huggan, Nowakowski, and Pereira dos Santos. We conclude with a list of open problems related to our results.

Authors:Jinyoung Park, Michail Sarantis, Prasad Tetali

Abstract: We give a short and self-contained argument that shows that, for any positive integers $t$ and $n$ with $t =O\Bigl(\frac{n}{\log n}\Bigr)$, the number $\alpha([t]^n)$ of antichains of the poset $[t]^n$ is at most \[\exp_2\Bigl(1+O\Bigl(\Bigl(\frac{t\log^3 n}{n}\Bigr)^{1/2}\Bigr)\Bigr)N(t,n)\,,\] where $N(t,n)$ is the size of a largest level of $[t]^n$. This, in particular, says that if $t \ll n/\log^3 n$ as $n \rightarrow \infty$, then $\log\alpha([t]^n)=(1+o(1))N(t,n)$, giving a (partially) positive answer to a question of Moshkovitz and Shapira for $t, n$ in this range. Particularly for $t=3$, we prove a better upper bound: \[\log\alpha([3]^n)\le(1+4\log 3/n)N(3,n),\] which is the best known upper bound on the number of antichains of $[3]^n$.

Authors:Natalie Behague, Gabriel Crudele, Jonathan A. Noel, Lina M. Simbaqueba

Abstract: Given two non-empty graphs $H$ and $T$, write $H\succcurlyeq T$ to mean that $t(H,G)^{|E(T)|}\geq t(T,G)^{|E(H)|}$ for every graph $G$, where $t(\cdot,\cdot)$ is the homomorphism density function. We obtain various necessary and sufficient conditions for two trees $H$ and $T$ to satisfy $H\succcurlyeq T$ and determine all such pairs on at most 8 vertices. This extends results of Leontovich and Sidorenko from the 1980s and 90s. Our approach applies an information-theoretic technique of Kopparty and Rossman to reduce the problem of showing that $H\succcurlyeq T$ for two forests $H$ and $T$ to solving a particular linear program. We also characterize trees $H$ which satisfy $H\succcurlyeq S_k$ or $H\succcurlyeq P_4$, where $S_k$ is the $k$-vertex star and $P_4$ is the $4$-vertex path.

Authors:Riccardo W. Maffucci

Abstract: We consider the graph degree sequences such that every realisation is a polyhedron. It turns out that there are exactly eight of them. All of these are unigraphic, in the sense that each is realised by exactly one polyhedron. This is a revisitation of a Theorem of Rao about sequences that are realised by only planar graphs. Our proof yields additional geometrical insight on this problem. Moreover, our proof is constructive: for each graph degree sequence that is not forcibly polyhedral, we construct a non-polyhedral realisation.

Authors:Felix Joos, Jonathan Schrodt

Abstract: Let $T$ be an oriented tree on $n$ vertices with maximum degree at most $e^{o(\sqrt{\log n})}$. If $G$ is a digraph on $n$ vertices with minimum semidegree $\delta^0(G)\geq(\frac12+o(1))n$, then $G$ contains $T$ as a spanning tree, as recently shown by Kathapurkar and Montgomery (in fact, they only require maximum degree $o(n/\log n)$). This generalizes the corresponding result by Koml\'os, S\'ark\"ozy and Szemer\'edi for graphs. We investigate the natural question how many copies of $T$ the digraph $G$ contains. Our main result states that every such $G$ contains at least $|Aut(T)|^{-1}(\frac12-o(1))^nn!$ copies of $T$, which is optimal. This implies the analogous result in the undirected case.

Authors:Kazuo Murota, Akihisa Tamura

Abstract: The Shapley-Folkman theorem is a statement about the Minkowski sum of (non-convex) sets, expressing the closeness of the Minkowski sum to convexity in a quantitative manner. This paper establishes similar theorems for integrally convex sets and M-natural-convex sets, which are major classes of discrete convex sets in discrete convex analysis.

Authors:Takatora Suzuki, Han Guo, Momoko Hayamizu

Abstract: Phylogenetic networks are a flexible model of evolution that can represent reticulate evolution and handle complex data. Tree-based networks, which are phylogenetic networks that have a spanning tree with the same root and leaf-set as the network itself, have been well studied. However, not all networks are tree-based. Francis-Semple-Steel (2018) thus introduced several indices to measure the deviation of rooted binary phylogenetic networks $N$ from being tree-based, such as the minimum number $\delta^\ast(N)$ of additional leaves needed to make $N$ tree-based, and the minimum difference $\eta^\ast(N)$ between the number of vertices of $N$ and the number of vertices of a subtree of $N$ that shares the root and leaf set with $N$. Hayamizu (2021) has established a canonical decomposition of almost-binary phylogenetic networks of $N$, called the maximal zig-zag trail decomposition, which has many implications including a linear time algorithm for computing $\delta^\ast(N)$. The Maximum Covering Subtree Problem (MCSP) is the problem of computing $\eta^\ast(N)$, and Davidov et al. (2022) showed that this can be solved in polynomial time (in cubic time when $N$ is binary) by an algorithm for the minimum cost flow problem. In this paper, under the assumption that $N$ is almost-binary (i.e. each internal vertex has in-degree and out-degree at most two), we show that $\delta^\ast(N)\leq \eta^\ast (N)$ holds, which is tight, and give a characterisation of such phylogenetic networks $N$ that satisfy $\delta^\ast(N)=\eta^\ast(N)$. Our approach uses the canonical decomposition of $N$ and focuses on how the maximal W-fences (i.e. the forbidden subgraphs of tree-based networks) are connected to maximal M-fences in the network $N$. Our results introduce a new class of phylogenetic networks for which MCSP can be solved in linear time, which can be seen as a generalisation of tree-based networks.

Authors:Katie Ansaldi, Gabriel Cowley, Eric Green, Kihyun Kim, JT Rapp

Abstract: An exact r-coloring of a set $S$ is a surjective function $c:S \rightarrow \{1, 2, \ldots,r\}$. A rainbow solution to an equation over $S$ is a solution such that all components are a different color. We prove that every 3-coloring of $\mathbb{N}$ with an upper density greater than $(4^s-1)/(3 \cdot 4^s)$ contains a rainbow solution to $x-y=z^k$. The rainbow number for an equation in the set $S$ is the smallest integer $r$ such that every exact $r$-coloring has a rainbow solution. We compute the rainbow numbers of $\mathbb{Z}_p$ for the equation $x-y=z^k$, where $p$ is prime and $k\geq 2$.

Authors:Pepijn Wissing, Edwin R. van Dam

Abstract: Complex unit gain graphs may exhibit various kinds of symmetry. In this work, we explore structural symmetry, spectral symmetry and sign-symmetry in gain graphs, and their respective relations to one-another. Our main result is a construction that transforms an arbitrary gain graph into infinitely many switching-distinct gain graphs whose spectral symmetry does not imply sign-symmetry. This provides a more general answer to the gain graph analogue of an existence question that was recently treated in the context of signed graphs.

Authors:Noga Alon, Anurag Bishnoi, Shagnik Das, Alessandro Neri

Abstract: A strong blocking set in a finite projective space is a set of points that intersects each hyperplane in a spanning set. We provide a new graph theoretic construction of such sets: combining constant-degree expanders with asymptotically good codes, we explicitly construct strong blocking sets in the $(k-1)$-dimensional projective space over $\mathbb{F}_q$ that have size $O( q k )$. Since strong blocking sets have recently been shown to be equivalent to minimal linear codes, our construction gives the first explicit construction of $\mathbb{F}_q$-linear minimal codes of length $n$ and dimension $k$, for every prime power $q$, for which $n = O (q k)$. This solves one of the main open problems on minimal codes.

Authors:Hieu T. Ngo

Abstract: We study a matrix analog of the Erd\H{o}s-Falconer distance problems in vector spaces over finite fields. There arises an interesting analysis of certain quadratic matrix Gauss sums.

Authors:Élisabeth Remy, Paul Ruet

Abstract: Nested canalization (NC) is a property of Boolean functions which has been recently extended to multivalued functions. We study the effect of the Van Ham mapping (from multivalued to Boolean functions) on this property. We introduce the class of softly nested canalizing (SNC) multivalued functions, and prove that the Van Ham mapping sends SNC multivalued functions to NC Boolean functions. Since NC multivalued functions are SNC, this preservation property holds for NC multivalued functions as well. We also study the relevance of SNC functions in the context of gene regulatory network modelling.

Authors:Eyal Ackerman, Balázs Keszegh

Abstract: Let $\cal C$ be a set of curves in the plane such that no three curves in $\cal C$ intersect at a single point and every pair of curves in $\cal C$ intersect at exactly one point which is either a crossing or a touching point. According to a conjecture of J\'anos Pach the number of pairs of curves in $\cal C$ that touch each other is $O(|{\cal C}|)$. We prove this conjecture for $x$-monotone curves.

Authors:Oliver Lorscheid, Koen Thas

Abstract: This text is dedicated to Jacques Tits's ideas on geometry over F1, the field with one element. In a first part, we explain how thin Tits geometries surface as rational point sets over the Krasner hyperfield, which links these ideas to combinatorial flag varieties in the sense of Borovik, Gelfand and White and F1-geometry in the sense of Connes and Consani. A completely novel feature is our approach to algebraic groups over F1 in terms of an alteration of the very concept of a group. In the second part, we study an incidence-geometrical counterpart of (epimorphisms to) thin Tits geometries; we introduce and classify all F1-structures on 3-dimensional projective spaces over finite fields. This extends recent work of Thas and Thas on epimorphisms of projective planes (and other rank 2 buildings) to thin planes.

Authors:Francesco Pavese

Abstract: A $4$-general set in ${\rm PG}(n,q)$ is a set of points of ${\rm PG}(n,q)$ spanning the whole ${\rm PG}(n,q)$ and such that no four of them are on a plane. Such a pointset is said to be complete if it is not contained in a larger $4$-general set of ${\rm PG}(n, q)$. In this paper upper and lower bounds for the size of the largest and the smallest complete $4$-general set in ${\rm PG}(n,q)$, respectively, are investigated. Complete $4$-general sets in ${\rm PG}(n,q)$, $q \in \{3,4\}$, whose size is close to the theoretical upper bound are provided. Further results are also presented, including a description of the complete $4$-general sets in projective spaces of small dimension over small fields and the construction of a transitive $4$-general set of size $3(q + 1)$ in ${\rm PG}(5, q)$, $q \equiv 1 \pmod{3}$.

Authors:Niccolò Di Marco, Andrea Frosini, Christophe Picouleau

Abstract: Given a 3-uniform hypergraph H, its 2-intersection graph G has for vertex set the hyperedges of H and ee' is an edge of G whenever e and e' have exactly two common vertices in H. Di Marco et al. prove that deciding wether a graph G is the 2-intersection graph of a 3-uniform hypergraph is NP-complete. The main problems we study concern the class of claw-free graphs. We show that the recognition problem remains NP-complete when G is claw-free graphs but becomes polynomial if in addition G is triangulated.

Authors:Thilo Krill, Max Pitz

Abstract: Two graphs are of the same topological type if they can be mutually embedded into each other topologically. We show that there are exactly $\aleph_1$ distinct topological types of countable trees. In general, for any infinite cardinal $\kappa$ there are exactly $\kappa^+$ distinct topological types of trees of size $\kappa$. This solves a problem of van der Holst from 2005.

Authors:Guilherme Zeus Dantas e Moura, Tibor Jordán, Corwin Silverman

Abstract: A $d$-dimensional bar-and-joint framework $(G,p)$ with underlying graph $G$ is called universally rigid if all realizations of $G$ with the same edge lengths, in all dimensions, are congruent to $(G,p)$. A graph $G$ is said to be generically universally rigid in $\mathbb{R}^d$ if every $d$-dimensional generic framework $(G,p)$ is universally rigid. In this paper we focus on the case $d=1$. We give counterexamples to a conjectured characterization of generically universally rigid graphs from R. Connelly (2011). We also introduce two new operations that preserve the universal rigidity of generic frameworks, and the property of being not universally rigid, respectively. One of these operations is used in the analysis of one of our examples, while the other operation is applied to obtain a lower bound on the size of generically universally rigid graphs. This bound gives a partial answer to a question from T. Jord\'an and V-H. Nguyen (2015).

Authors:Warren Singh, Timothy Sun

Abstract: A graph is said to be nearly complete bipartite if it can be obtained by deleting a set of independent edges from a complete bipartite graph. The nonorientable genus of such graphs is known except in a few cases where the sizes of the partite classes differ by at most one, and a maximum matching is deleted. We resolve these missing cases using three classic tools for constructing genus embeddings of the complete bipartite graphs: current graphs, diamond sums, and the direct rotation systems of Ringel.

Authors:Kirsten Hogenson, Dan Johnston, Suzanne O'Hara

Abstract: A graph $G$ is equitably $k$-choosable if, for every $k$-uniform list assignment $L$, $G$ is $L$-colorable and each color appears on at most $\left\lceil |V(G)|/k\right\rceil$ vertices. Equitable list-coloring was introduced by Kostochka, Pelsmajer, and West in 2003. They conjectured that a connected graph $G$ with $\Delta(G)\geq 3$ is equitably $\Delta(G)$-choosable, as long as $G$ is not complete or $K_{d,d}$ for odd $d$. In this paper, we use a discharging argument to prove their conjecture for the infinite family of prism graphs.

Authors:Vance Faber, Noah Streib

Abstract: This paper concerns all-to-all network routing on regular digraphs. In previous work we focused on efficient routing in highly symmetric digraphs with low diameter for fixed degree. Here, we show that every connected regular digraph has an all-to-all routing scheme and associated schedule with no waiting. In fact, this routing scheme becomes more efficient as the diameter goes down with respect to the degree and number of vertices. Lastly, we examine the simple scheduling algorithm called ``farthest-distance-first'' and prove that it yields optimal schedules for all-to-all communication in networks of interest, including Kautz graphs.

Authors:David Conlon, Jacob Fox, Huy Tuan Pham, Yufei Zhao

Abstract: For positive integers $n,r,s$ with $r > s$, the set-coloring Ramsey number $R(n;r,s)$ is the minimum $N$ such that if every edge of the complete graph $K_N$ receives a set of $s$ colors from a palette of $r$ colors, then there is a subset of $n$ vertices where all of the edges between them receive a common color. If $n$ is fixed and $\frac{s}{r}$ is less than and bounded away from $1-\frac{1}{n-1}$, then $R(n;r,s)$ is known to grow exponentially in $r$, while if $\frac{s}{r}$ is greater than and bounded away from $1-\frac{1}{n-1}$, then $R(n;r,s)$ is bounded. Here we prove bounds for $R(n;r,s)$ in the intermediate range where $\frac{s}{r}$ is close to $1 - \frac{1}{n-1}$ by establishing a connection to the maximum size of error-correcting codes near the zero-rate threshold.

Authors:Qianghui Guo, Yinglie Jin, Lisa H. Sun, Shina Xu

Abstract: Combinatorial enumeration of various RNA secondary structures and protein contact maps, is of great interest for both combinatorists and computational biologists. Enumeration of protein contact maps has considerable difficulties due to the significant higher vertex degree than that of RNA secondary structures. The state of art maximum vertex degree in previous works is two. This paper proposes a solution for counting stacks in protein contact maps with arbitrary vertex degree upper bound. By establishing bijection between such general stacks and $m$-regular $\Lambda$-avoiding $DLU$ paths, and counting the paths using theories of pattern avoiding lattice paths, we obtain a unified system of equations for generating functions of general stacks. We also show that previous enumeration results for RNA secondary structures and protein contact maps can be derived from the unified equation system as special cases.

Authors:Gábor Hegedüs

Abstract: Let $A_1, \ldots ,A_m$ and $B_1, \ldots ,B_m$ be subsets of $[n]$ and let $t$ be a non-negative integer with the following property: $|A_i \cap B_i|\leq t$ for each $i$ and $|A_i\cap B_j|>t$ whenever $i< j$. Then $m\leq 2^{n-t}$. Our proof uses Lov\'asz' tensor product method. We prove the following skew version of Bollob\'as' Theorem. Let $A_1, \ldots ,A_m$ and $B_1, \ldots ,B_m$ be finite sets of $[n]$ satisfying the conditions $A_i \cap B_i =\emptyset$ for each $i$ and $A_i\cap B_j\ne \emptyset$ for each $i< j$. Then $$ \sum_{i=1}^m \frac{1}{{|A_i|+|B_i| \choose |A_i|}}\leq n+1. $$ Both upper bounds are sharp.

Authors:Ada Chan, Peter Sin

Abstract: In a continuous-time quantum walk on a network of qubits, pretty good state transfer is the phenomenon of state transfer between two vertices with fidelity arbitrarily close to 1. We construct families of graphs to demonstrate that there is no bound on the size of a set of vertices that admit pretty good state transfer between any two vertices of the set.

Authors:Victor Falgas-Ravry, Klas Markström, Eero Räty

Abstract: Let $\mathbf{G}:=(G_1, G_2, G_3)$ be a triple of graphs on a common vertex set $V$ of size $n$. A rainbow triangle in $\mathbf{G}$ is a triple of edges $(e_1, e_2, e_3)$ with $e_i\in G_i$ for each $i$ and $\{e_1, e_2, e_3\}$ forming a triangle in $V$. In this paper we consider the following question: what triples of minimum degree conditions $(\delta(G_1), \delta(G_2), \delta(G_3))$ guarantee the existence of a rainbow triangle? This may be seen as a minimum degree version of a problem of Aharoni, DeVos, de la Maza, Montejanos and \v{S}\'amal on density conditions for rainbow triangles, which was recently resolved by the authors. We establish that the extremal behaviour in the minimum degree setting differs strikingly from that seen in the density setting, with discrete jumps as opposed to continuous transitions. Our work leaves a number of natural questions open, which we discuss.

Authors:Attila Joó

Abstract: Aharoni and Ziv conjectured that if $ M $ and $ N $ are finitary matroids on $ E $, then a certain ``Hall-like'' condition is sufficient to guarantee the existence of an $ M $-independent spanning set of $ N $. We show that their condition ensures that every finite subset of $ E $ is $ N $-spanned by an $ M $-independent set.

Authors:Alexandr Valyuzhenich

Abstract: In this work, we prove a general version of the reduction lemmas for eigenfunctions of graphs admitting involutive automorphisms of a special type.

Authors:Raphael Steck

Abstract: I show that walls of size at least $6 \times 4$ do not have the edge-Erd\H{o}s-P\'{o}sa property.

Authors:Ali Azimi, R. B. Bapat, Mohammad Farrokhi Derakhshandeh Ghouchan

Abstract: We present explicit formulas for Moore-Penrose inverses of some families of set inclusion matrices arising from sets, vector spaces, and designs.

Authors:W. C. Shiu, G. C. Lau, R. X. Zhang

Abstract: Let $G=(V, E)$ be a connected graph. A bijection $f: E\to \{1, \ldots, |E|\}$ is called a local antimagic labeling if for any two adjacent vertices $x$ and $y$, $f^+(x)\neq f^+(y)$, where $f^+(x)=\sum_{e\in E(x)}f(e)$ and $E(x)$ is the set of edges incident to $x$. Thus a local antimagic labeling induces a proper vertex coloring of $G$, where the vertex $x$ is assigned the color $f^+(x)$. The local antimagic chromatic number $\chi_{la}(G)$ is the minimum number of colors taken over all colorings induced by local antimagic labelings of $G$. In this paper, we present some families of bridge graphs with $\chi_{la}(G)=3$ and give several ways to construct bridge graphs with $\chi_{la}(G)=3$.

Authors:Alexander L. Gavrilyuk, Sho Suda

Abstract: It follows from Delsarte theory that the Witt $4$-$(11,5,1)$ design gives rise to a $Q$-polynomial association scheme $\mathcal{W}$ defined on the set of its blocks. In this note we show that $\mathcal{W}$ is unique, i.e., defined up to isomorphism by its parameters.

Authors:Y. H. Chen, Thomas Y. He, F. Tang, J. J. Wei

Abstract: In this paper, we investigate partitions with parts separated by parity introduced by Andrews with the aid of separation integer partition classes. we also extend separable integer partition classes with modulus $1$ introduced by Andrews to overpartitions, called separable overpartition classes. We investigate overpartition and the overpartition analogue of Rogers-Ramanujan indentities, which are separable overpartition classes.

Authors:Sounaka Mishra, Rohini S, Sagar S. Sawant

Abstract: It is currently an unsolved problem to determine whether a $\triangle$-free planar graph $G$ contains an independent set $A$ such that $G[V_G\setminus A]$ is $2$-choosable. However, in this paper, we take a slightly different approach by relaxing the planarity condition. We prove the $\mathbb{NP}$-completeness of the above decision problem when the graph is $\triangle$-free, $4$-colorable, and of diameter $3$. Building upon this notion, we examine the computational complexity of two optimization problems: minimum near $3$-choosability and minimum $2$-choosable deletion. In the former problem, the goal is to find an independent set $A$ of minimum size in a given graph $G$, such that the induced subgraph $G[V_G \setminus A]$ is $2$-choosable. We establish that this problem is $\mathbb{NP}$-hard to approximate within a factor of $|V_G|^{1-\epsilon}$ for any $\epsilon > 0$, even for planar bipartite graphs. On the other hand, the problem of minimum $2$-choosable deletion involves determining a vertex set $A \subseteq V_G$ of minimum cardinality such that the induced subgraph $G[V_G \setminus A]$ is $2$-choosable. We prove that this problem is $\mathbb{NP}$-complete, but can be approximated within a factor of $O(\log |V_G|)$.

Authors:Prajnanaswaroop S

Abstract: Cayley graphs are graphs on algebraic structures, typically groups or group-like structures. In this paper, we have obtained a few results on Cayley graphs on Cyclic groups, typically powers of cycles, some colorings of powers of cycles, Cayley graphs on some non-abelian groups, and Cayley graphs on gyrogroups.

Authors:Xiaona Fang, Lihua You

Abstract: The Tur\'an number of a graph $F$, denoted $ex(n, F)$, is the maximum number of edges in an $F$-free graph on $n$ vertices. Let $P_{\ell}$, $S_{\ell}$ denote the path and star on $\ell$ vertices, respectively. A linear forest is a forest whose connected components are paths. In 2013, Lidick\'y et al. considered the Tur\'an number of linear forest and $k_1P_4 \bigcup k_2 S_3$ for sufficiently large $n$. Recently, Fang and Yuan determine the Tur\'an numbers of $P_{\ell} \bigcup kS_{\ell-1}$, $k_1P_{2\ell} \bigcup k_2 S_{2\ell-1}$, $2P_5 \bigcup kS_4$ for $n$ appropriately large and characterized the corresponding extremal graphs. In this paper, We determine $ex(n, P_9 \bigcup P_7)$ for all $n\geq 16$ and characterize all extremal graphs, which partially confirms a conjecture proposed by Yuan and Zhang [L.T. Yuan, X.D. Zhang, J. Graph. Theory 98(3) (2021) 499--524]. And we determine the Tur\'an numbers of $\bigcup\limits _{i=1}^{k_1} P_{\ell _i} \bigcup\limits _{j=1}^{k_2} S_{a _j}$ for $n$ appropriately large, where $a_j\leq 2k_2+2 \sum\limits_{i=1}^{k_1} \lfloor\frac{\ell_i}{2}\rfloor-2j$ for any $j\in [k_2]$, which generalizes the results of Fang and Yuan. The corresponding extremal graphs are also completely characterized

Authors:Ted Dobson

Abstract: We introduce a new class of transitive permutation groups which properly contains the automorphism groups of vertex-transitive graphs and digraphs. We then give a sufficient condition for a quotient of this family to remain in the family, showing that relatively straightforward induction arguments may possibly be used to solve problems in this family, and consequently for symmetry questions about vertex-transitive digraphs. As an example of this, for $p$ an odd prime, we use induction to determine the Sylow $p$-subgroups of transitive groups of degree $p^n$ that contain a regular cyclic subgroup in this family. This is enough information to determine the automorphism groups of circulant digraphs of order $p^n$.

Authors:Seamus P. Albion, Ilse Fischer, Hans Höngesberg, Florian Schreier-Aigner

Abstract: The skew Schur functions admit many determinantal expressions. Chief among them are the (dual) Jacobi-Trudi formula and Lascoux-Pragacz formula, which is a skew analogue of the Giambelli identity. Comparatively, the skew characters of the symplectic and orthogonal groups, also known as the skew symplectic and orthogonal Schur functions, have received very little attention in this direction. We establish analogues of the dual Jacobi-Trudi and Lascoux-Pragacz formulae for these characters. Our approach is entirely combinatorial, being based on lattice path descriptions of the tableaux models of Koike and Terada.

Authors:Jorge Blanco, Stephanie Einstein, Caleb Hostetler, Jurgen Kritschgau, Daniel Ogbe

Abstract: The zero forcing number was introduced as a combinatorial bound on the maximum nullity taken over the set of real symmetric matrices that respect the pattern of an underlying graph. The $Z_q$-forcing game is an analog to the standard zero forcing game which incorporates inertia restrictions on the set of matrices associated with a graph. This work proves an upper bound on the $Z_q$-forcing number for trees. Furthermore, we consider the $Z_q$-forcing number for caterpillar cycles on $n$ vertices. We focus on developing game theoretic proofs of upper and lower bounds.

Authors:Hao Li, Hao Lin, Guanghui Wang, Wenling Zhou

Abstract: The uniform Tur\'an density $\pi_{1}(F)$ of a $3$-uniform hypergraph $F$ is the supremum over all $d$ for which there is an $F$-free hypergraph with the property that every linearly sized subhypergraph with density at least $d$. Determining $\pi_{1}(F)$ for given hypergraphs $F$ was suggested by Erd\H{o}s and S\'os in 1980s. In particular, they raised the questions of determining $\pi_{1}(K_4^{(3)-})$ and $\pi_{1}(K_4^{(3)})$. The former question was solved recently in [Israel J. Math. 211 (2016), 349-366] and [J. Eur. Math. Soc. 20 (2018), 1139-1159], while the latter is still a major open problem. In addition to $K_4^{(3)-}$, there are very few hypergraphs whose uniform Tur\'an density has been determined. In this paper, we give a sufficient condition for $3$-uniform hypergraphs $F$ satisfying $\pi_{1}(F)=1/4$. In particular, currently all known $3$-uniform hypergraphs whose uniform Tur\'an density is $1/4$, such as $K_4^{(3)-}$ and the $3$-uniform hypergraphs $F^{\star}_5$ studied in [arXiv:2211.12747], satisfy this condition. Moreover, we find some intriguing $3$-uniform hypergraphs whose uniform Tur\'an density is also $1/4$.

Authors:Athmakoori Prashant, S. Francis Raj, M. Gokulnath

Abstract: Finding families that admit a linear $\chi$-binding function is a problem that has interested researchers for a long time. Recently, the question of finding linear subfamilies of $2K_2$-free graphs has garnered much attention. In this paper, we are interested in finding a linear subfamily of a specific superclass of $2K_2$-free graphs, namely $(P_3\cup P_2)$-free graphs. We show that the class of $\{P_3\cup P_2,gem\}$-free graphs admits $f=2\omega$ as a linear $\chi$-binding function. Furthermore, we give examples to show that the optimal $\chi$-binding function $f^*\geq \left\lceil\frac{5\omega(G)}{4}\right\rceil$ for the class of $\{P_3\cup P_2, gem\}$-free graphs and that the $\chi$-binding function $f=2\omega$ is tight when $\omega=2$ and $3$.

Authors:Bruce Olberding, Elaine A. Walker

Abstract: Working over a field of characteristic other than $2$, we examine a relationship between quadrilaterals and the pencil of conics passing through their vertices. Asymptotically, such a pencil of conics is what we call a bisector field, a set ${\mathbb{B}}$ of paired lines such that each line $\ell$ in ${\mathbb{B}}$ simultaneously bisects each pair in ${\mathbb{B}}$ in the sense that $\ell$ crosses the pairs of lines in ${\mathbb{B}}$ in pairs of points that all share the same midpoint. We show that a quadrilateral induces a geometry on the affine plane via an inner product, under which we examine pencils of conics and pairs of bisectors of a quadrilateral. We show also how bisectors give a new interpretation of some classically studied features of quadrangles, such as the nine-point conic.

Authors:Daniel W. Cranston, Gexin Yu

Abstract: Hocquard, Kim, and Pierron constructed, for every even integer $D\ge 2$, a 2-degenerate graph $G_D$ with maximum degree $D$ such that $\omega(G_D^2)=\frac52D$. They asked whether (a) there exists $D_0$ such that every 2-degenerate graph $G$ with maximum degree $D\ge D_0$ satisfies $\chi(G^2)\le \frac52D$ and (b) whether this result holds more generally for every graph $G$ with mad(G)<4. In this direction, we prove upper bounds on the clique number $\omega(G^2)$ of $G^2$ that match the lower bound given by this construction, up to small additive constants. We show that if $G$ is 2-degenerate with maximum degree $D$, then $\omega(G^2)\le \frac52D+72$ (with $\omega(G^2)\le \frac52D+60$ when $D$ is sufficiently large). And if $G$ has mad(G)<4 and maximum degree $D$, then $\omega(G^2)\le \frac52D+532$. Thus, the construction of Hocquard et al. is essentially best possible.

Authors:Jesse Campion Loth, Michael Levet, Kevin Liu, Sheila Sundaram, Mei Yin

Abstract: In this paper, we consider the moments of permutation statistics on conjugacy classes of colored permutation groups. We first show that when the cycle lengths are sufficiently large, the moments of arbitrary permutation statistics are independent of the conjugacy class. For permutation statistics that can be realized via $\textit{symmetric}$ constraints, we show that for a fixed number of colors, each moment is a polynomial in the degree $n$ of the $r$-colored permutation group $\mathfrak{S}_{n,r}$. Hamaker & Rhoades (arXiv 2022) established analogous results for the symmetric group as part of their far-reaching representation-theoretic framework. Independently, Campion Loth, Levet, Liu, Stucky, Sundaram, & Yin (arXiv, 2023) arrived at independence and polynomiality results for the symmetric group using instead an elementary combinatorial framework. Our techniques in this paper build on this latter elementary approach.

Authors:Gabe Cunningham Wentworth Institute of Technology, Elías Mochán Northeastern University, Antonio Montero University of Ljubljana

Abstract: A map on a surface whose automorphism group has a subgroup acting regularly on its vertices is called a Cayley map. Here we generalize that notion to maniplexes and polytopes. We define $\mathcal{M}$ to be a \emph{Cayley extension} of $\mathcal{K}$ if the facets of $\mathcal{M}$ are isomorphic to $\mathcal{K}$ and if some subgroup of the automorphism group of $\mathcal{M}$ acts regularly on the facets of $\mathcal{M}$. We show that many natural extensions in the literature on maniplexes and polytopes are in fact Cayley extensions. We also describe several universal Cayley extensions. Finally, we examine the automorphism group and symmetry type graph of Cayley extensions.

Authors:Ted Dobson

Abstract: We introduce two refinements of the class of $5/2$-groups, inspired by the classes of automorphism groups of configurations and automorphism groups of unit circulant digraphs. We show that both of these classes have the property that any two regular cyclic subgroups of a group $G$ in either of these classes are conjugate in $G$. This generalizes two results in the literature (and simplifies their proofs) that show that symmetric configurations and unit circulant digraphs are isomorphic if and only if they are isomorphic by a group automorphism of ${\mathbb Z}_n$.

Authors:Giulio Cerbai

Abstract: In 2011, Duncan and Steingr\'imsson conjectured that modified ascent sequences avoiding any of the patterns 212, 1212, 2132, 2213, 2231 and 2321 are counted by the Bell numbers. Furthermore, the distribution of the number of ascents is the reverse of the distribution of blocks on set partitions. We solve the conjecture for all the patterns except 2321. We describe the corresponding sets of Fishburn permutations by pattern avoidance, and leave some open questions for future work.

Authors:Günter Rote

Abstract: We survey a few strengthenings and generalizations of the Combinatorial Nullstellensatz of Alon and the Schwartz-Zippel Lemma. These lemmas guarantee the existence of (a certain number of) nonzeros of a multivariate polynomial when the variables run independently through sufficiently large ranges.

Authors:Leo Versteegen

Abstract: A graph $H$ is called strongly common if for every coloring $\phi$ of $K_n$ with two colors, the number of monochromatic copies of $H$ is at least the number of monochromatic copies of $H$ in a random coloring of $K_n$ with the same density of color classes as $\phi$. In this note we prove that if a graph has odd girth but is not a cycle, then it is not strongly common. This answers a question of Chen and Ma.

Authors:Nikolay Terekhov, Maksim Zhukovskii

Abstract: The weak saturation number $\mathrm{wsat}(n,F)$ is the minimum number of edges in a graph on $n$ vertices such that all the missing edges can be activated sequentially so that each new edge creates a copy of $F$. A usual approach to prove a lower bound for the weak saturation number is algebraic: if it is possible to embed edges of $K_n$ in a vector space in a certain way (depending on $F$), then the dimension of the subspace spanned by the images of the edges of $K_n$ is a lower bound for the weak saturation number. In this paper, we present a new combinatorial approach to prove lower bounds for weak saturation numbers that allows to establish worst-case tight (up to constant additive terms) general lower bounds as well as to get exact values of the weak saturation numbers for certain graph families. It is known (Alon, 1985) that, for every $F$, there exists $c_F$ such that $\mathrm{wsat}(n,F)=c_Fn(1+o(1))$. Our lower bounds imply that all values in the interval $\left[\frac{\delta}{2}-\frac{1}{\delta+1},\delta-1\right]$ with step size $\frac{1}{\delta+1}$ are achievable by $c_F$ (while any value outside this interval is not achievable).

Authors:Federico Glaudo, Noah Kravitz

Abstract: For a finite multiset $A$ of an abelian group $G$, let $\text{FS}(A)$ denote the multiset of the $2^{|A|}$ subset sums of $A$. It is natural to ask to what extent $A$ can be reconstructed from $\text{FS}(A)$. We fully solve this problem for $2$-torsion-free groups $G$ by giving characterizations, both algebraic and combinatorial, of the fibers of $\text{FS}$. Equivalently, we characterize all pairs of multisets $A,B$ with $\text{FS}(A)=\text{FS}(B)$. Our results build on recent work of Ciprietti and the first author.

Authors:Thomas Karam

Abstract: Let $p$ be a prime, let $1 \le t < d < p$ be integers, and let $S$ be a non-empty subset of $\mathbb{F}_p$. We establish that if a polynomial $P:\mathbb{F}_p^n \to \mathbb{F}_p$ with degree $d$ is such that the image $P(S^n)$ does not contain the full image $A(\mathbb{F}_p)$ of any non-constant polynomial $A: \mathbb{F}_p \to \mathbb{F}_p$ with degree at most $t$, then $P$ coincides on $S^n$ with a polynomial that in particular has bounded degree-$\lfloor d/(t+1) \rfloor$-rank in the sense of Green and Tao. Similarly, we prove that if the assumption holds even for $t=d$, then $P$ coincides on $S^n$ with a polynomial determined by a bounded number of coordinates.

Authors:Sela Fried, Toufik Mansour

Abstract: Recently, we initiated the study of random walk labelings of graphs. These are graph labelings that are obtainable by performing a random walk on the graph, such that each vertex is labeled upon its first visit. In this work, we calculate the number of random walk labelings of several natural graph families: The wheel, fan, barbell, lollipop, tadpole, friendship, and snake graphs. Additionally, we prove several combinatorial identities that emerged during the calculations.

Authors:Shengxiang Lv

Abstract: $G_{m,n,k}$ is a subgraph of the complete bipartite graph $K_{m,n}$ with a $k$-matching removed. By a new method based on the embeddings of some $G_{m,n,k}$ with small $m,n,k$ and bipartite joins with small bipartite graphs, we construct the nonorientable genus embedding of $G_{m,n,k}$ for all $m,n\geq 3$ with $(m,n,k)\neq (5,4,4), (4,5,4),(5,5,5)$. Hence, we solve the cases $G_{n+1,n,n}$($n$ is even) and $G_{n,n,n}$, with the values of $n$ that have not been previously solved, i.e., $n\geq 6$. This completes previous work on the nonorientable genus of $G_{m,n,k}$.

Authors:Gilad Chase, Yuval Filmus

Abstract: We determine all $m$-ary Boolean functions $f_0,\ldots,f_m$ and $n$-ary Boolean functions $g_0,\ldots,g_n$ satisfying the equation \[ f_0(g_1(z_{11},\ldots,z_{1m}),\ldots,g_n(z_{n1},\ldots,z_{nm})) = g_0(f_1(z_{11},\ldots,z_{n1}),\ldots,f_m(z_{1m},\ldots,z_{nm})), \] for all Boolean inputs $\{ z_{ij} : i \in [n], j \in [m] \}$. This extends characterizations by Dokow and Holzman (who considered the case $g_0 = \cdots = g_n$) and by Chase, Filmus, Minzer, Mossel and Saurabh (who considered the case $g_1 = \cdots = g_n$).

Authors:Terrence George

Abstract: We construct an electrical-network version of the twist map for the positive Grassmannian, and use it to solve the inverse problem of recovering conductances from the response matrix. Each conductance is expressed as a biratio of Pfaffians as in the inverse map of Kenyon and Wilson; however, our Pfaffians are the more canonical $B$ variables instead of their tripod variables, and are coordinates on the positive orthogonal Grassmannian studied by Henriques and Speyer.

Authors:Oriol Serra, Lluís Vena

Abstract: In \cite[Serra, Vena, Extremal families for the Kruskal-Katona theorem]{sv21}, the authors have shown a characterization of the extremal families for the Kruskal-Katona Theorem. We further develop some of the arguments given in \cite{sv21} and give additional properties of these extremal families. F\"uredi-Griggs/M\"ors theorem from 1986/85 \cite{furgri86,mors85} claims that, for some cardinalities, the initial segment of the colexicographical is the unique extremal family; we extend their result as follows: the number of (non-isomorphic) extremal families strictly grows with the gap between the last two coefficients of the $k$-binomial decomposition. We also show that every family is an induced subfamily of an extremal family, and that, somewhat going in the opposite direction, every extremal family is close to being the inital segment of the colex order; namely, if the family is extremal, then after performing $t$ lower shadows, with $t=O(\log(\log n))$, we obtain the initial segment of the colexicographical order. We also give a ``fast'' algorithm to determine whether, for a given $t$ and $m$, there exists an extremal family of size $m$ for which its $t$-th lower shadow is not yet the initial segment in the colexicographical order. As a byproduct of these arguments, we give yet another characterization of the families of $k$-sets satisfying equality in the Kruskal--Katona theorem. Such characterization is, at first glance, less appealing than the one in \cite{sv21}, since the additional information that it provides is indirect. However, the arguments used to prove such characterization provide additional insight on the structure of the extremal families themselves.

Authors:Shunsuke Maeda, Yusuke Kaneko, Hideaki Muramatsu, Yukihiro Murakami, Momoko Hayamizu

Abstract: Phylogenetic networks are used to represent the evolutionary history of species. They are versatile when compared to traditional phylogenetic trees, as they capture more complex evolutionary events such as hybridization and horizontal gene transfer. Distance-based methods such as the Neighbor-Net algorithm are widely used to compute phylogenetic networks from data. However, the output is necessarily an undirected graph, posing a great challenge to deduce the direction of genetic flow in order to infer the true evolutionary history. Recently, Huber et al. investigated two different computational problems relevant to orienting undirected phylogenetic networks into directed ones. In this paper, we consider the problem of orienting an undirected binary network into a tree-child network. We give some necessary conditions for determining the tree-child orientability, such as a tight upper bound on the size of tree-child orientable graphs, as well as many interesting examples. In addition, we introduce new families of undirected phylogenetic networks, the jellyfish graphs and ladder graphs, that are orientable but not tree-child orientable. We also prove that any ladder graph can be made tree-child orientable by adding extra leaves, and describe a simple algorithm for orienting a ladder graph to a tree-child network with the minimum number of extra leaves. We pose many open problems as well.

Authors:Joseph A. Thas, Koen Thas

Abstract: This is the second part of our study of epimorphisms with source a thick generalized $m$-gon and target a thin generalized $m$-gon. We classify the case $m = 8$ when the polygons are finite (in the first part [15] we handled the cases $m = 3, 4$ and $6$). Then we show that the infinite case is very different, and construct examples which strongly differ from the finite case. A number of general structure theorems are also obtained, and we also take a look at the infinite case for general gonality.

Authors:Gabriel Coutinho, Emanuel Juliano, Thomás Jung Spier

Abstract: We prove that the only trees that admit perfect state transfer according to the adjacency matrix model are $P_2$ and $P_3$. This answers a question first asked by Godsil in 2012 and proves a conjecture by Coutinho and Liu from 2015.

Authors:Takuro Abe

Abstract: We prove the addition-deletion theorems for the Solomon-Terao polynomials, which have two important specializations. Namely, one is to the characteristic polynomials of hyperplane arangements, and the other to the Poincar\`{e} polynomials of the regular nilpotent Hessenberg varieties. One of the main tools to show them is the free surjection theorem which confirms the right exactness of several important exact sequences among logarithmic modules. Moreover, we introduce a generalized polynomial $B$-theory to the higher order logarithmic modules, whose origin was due to Terao.

Authors:Lele Liu, Bo Ning

Abstract: Spectral graph theory is a captivating area of graph theory that employs the eigenvalues and eigenvectors of matrices associated with graphs to study them. In this paper, we present a collection of $20$ topics in spectral graph theory, covering a range of open problems and conjectures. Our focus is primarily on the adjacency matrix of graphs, and for each topic, we provide a brief historical overview.

Authors:Nathan Bowler, Florian Gut, Meike Hatzel, Ken-ichi Kawarabayashi, Irene Muzi, Florian Reich

Abstract: We introduce torsoids, a canonical structure in matching covered graphs, corresponding to the bricks and braces of the graph. This allows a more fine-grained understanding of the structure of finite and infinite directed graphs with respect to their 1-separations.

Authors:Eli Bagno, Yisca Kares

Abstract: We find the range of the major index on the various conjugacy classes of involutions in the symmetric group $S_n$. In addition to indicating the minimum and the maximum values, we show that except for the case of involutions without fixed points, all the values in the range are attained. For the conjugacy classes of involutions without fixed points, we show that the only missing values are one more than the minimum and one less than the maximum.

Authors:Gabriel Coutinho, Emanuel Juliano, Thomás Jung Spier

Abstract: The main result of this paper states that in a rooted product of a path with rooted graphs which are disposed in a somewhat mirror-symmetric fashion, there are distinct eigenvalues supported in the end vertices of the path which are too close to each other: their difference is smaller than the square root of two in the even distance case, and smaller than one in the odd distance case. As a first application, we show that these end vertices cannot be involved in a quantum walk phenomenon known as perfect state transfer, significantly strengthening a recent result by two of the authors along with Godsil and van Bommel. For a second application, we show that there is no balanced integral tree of odd diameter bigger than three, answering a question raised by H\'{i}c and Nedela in 1998. Our main technique involves manipulating ratios of characteristic polynomials of graphs and subgraphs into continued fractions, and exploring in detail their analytic properties. We will also make use of a result due to P\'{o}lya and Szeg\"{o} about functions that preserve the Lebesgue measure, which as far as we know is a novel application to combinatorics. In the end, we connect our machinery to a recently introduced algorithm to locate eigenvalues of trees, and with our approach we show that any graph which contains two vertices separated by a unique path that is the subdivision of a bridge with at least six inner vertices cannot be integral. As a minor corollary this implies that most trees are not integral, but we believe no one thought otherwise.

Authors:Clemens Heuberger, Sarah J. Selkirk, Stephan Wagner

Abstract: The protection number of a vertex $v$ in a tree is the length of the shortest path from $v$ to any leaf contained in the maximal subtree where $v$ is the root. In this paper, we determine the distribution of the maximum protection number of a vertex in simply generated trees, thereby refining a recent result of Devroye, Goh and Zhao. Two different cases can be observed: if the given family of trees allows vertices of outdegree $1$, then the maximum protection number is on average logarithmic in the tree size, with a discrete double-exponential limiting distribution. If no such vertices are allowed, the maximum protection number is doubly logarithmic in the tree size and concentrated on at most two values. These results are obtained by studying the singular behaviour of the generating functions of trees with bounded protection number. While a general distributional result by Prodinger and Wagner can be used in the first case, we prove a variant of that result in the second case.

Authors:Anders Claesson, Atli Fannar Franklín, Einar Steingrímsson

Abstract: A curious generating function $S_0(x)$ for permutations of $[n]$ with exactly $n$ inversions is presented. Moreover, $(xC(x))^iS_0(x)$ is shown to be the generating function for permutations of $[n]$ with exactly $n-i$ inversions, where $C(x)$ is the generating function for the Catalan numbers.

Authors:Klavdija Kutnar, Dragan Marušič, Andriaherimanana Sarobidy Razafimahatratra

Abstract: Given a graph $X$ with a Hamilton cycle $C$, the {\em compression factor $\kappa(X,C)$ of $C$} is the order of the largest cyclic subgroup of $\operatorname{Aut}(C)\cap\operatorname{Aut}(X)$, and the {\em Hamilton compression $\kappa(X)$ of $X$ } is the maximum of $\kappa(X,C)$ where $C$ runs over all Hamilton cycles in $X$. Generalizing the well-known open problem regarding the existence of vertex-transitive graphs without Hamilton paths/cycles, it was asked by Gregor, Merino and M\"utze in [``The Hamilton compression of highly symmetric graphs'', {\em arXiv preprint} arXiv: 2205.08126v1 (2022)] whether for every positive integer $k$ there exists infinitely many vertex-transitive graphs (Cayley graphs) with Hamilton compression equal to $k$. Since an infinite family of Cayley graphs with Hamilton compression equal to $1$ was given there, the question is completely resolved in this paper in the case of Cayley graphs with a construction of Cayley graphs of semidirect products $\mathbb{Z}_p\rtimes\mathbb{Z}_k$ where $p$ is a prime and $k \geq 2$ a divisor of $p-1$. Further, infinite families of non-Cayley vertex-transitive graphs with Hamilton compression equal to $1$ are given. All of these graphs being metacirculants, some additional results on Hamilton compression of metacirculants of specific orders are also given.

Authors:Shahram Mohsenipour

Abstract: We prove an infinitary version of the Brauer-Schur theorem.

Authors:Michael Krivelevich

Abstract: A crown with $k$ spikes is an edge-disjoint union of a cycle $C$ and a matching $M$ of size $k$ such that each edge of $M$ has exactly one vertex in common with $C$. We prove that if $G$ is an $(n,d,\lambda)$-graph with $\lambda/d\le 0.001$ and $d$ is large enough, then $G$ contains a crown on $n$ vertices with $\lfloor n/2\rfloor$ spikes. As a consequence, such $G$ contains a Hamilton cycle in its square $G^2$.

Authors:Vincent Pilaud, Francisco Santos, Günter M. Ziegler

Abstract: We survey Jean-Louis Loday's vertex description of the associahedron, and its far reaching influence in combinatorics, discrete geometry and algebra. We present in particular four topics were it plays a central role: lattice congruences of the weak order and their quotientopes, cluster algebras and their generalized associahedra, nested complexes and their nestohedra, and operads and the associahedron diagonal.

Authors:Mark Pankov, Krzysztof Petelczyc, Mariusz Zynel

Abstract: We investigate point-line geometries whose singular subspaces correspond to binary equidistant codes. The main result is a description of automorphisms of these geometries. In some important cases, automorphisms induced by non-monomial linear automorphisms surprisingly arise.

Authors:Alexandru Pascadi

Abstract: We introduce a regularity method for sparse graphs, with new regularity and counting lemmas which use the Schatten-von-Neumann norms to measure uniformity. This leads to $k$-cycle removal lemmas in subgraphs of mildly-pseudorandom graphs, and also in graphs lacking a quasi-smooth family of bipartite subgraphs, extending results of Conlon, Fox, Sudakov and Zhao. We give some applications in additive combinatorics: one about translation-invariant linear equations in subsets of mildly-pseudorandom sets, one about such equations in generalized Sidon sets, and one about polygonal patterns in subsets of $\mathbf{Z}^2$ with few parallelograms (giving a two-dimensional analogue for a result of Prendiville). Separately, our regularity lemma implies a dense graph removal lemma with mild constant dependencies, in graphs whose spectral $L^{2-\varepsilon}$ norms are small.

Authors:Gang Chen, Jiawei He, Zhiman Wu

Abstract: Schur rings over the infinite dihedral group $\mathcal{Z}\rtimes\mathcal{Z}_2$ are studied according to properties of Schur rings over infinite groups and the classification of Schur rings over infinite cyclic groups. Schur rings over $\mathcal{Z}\rtimes{\mathcal{Z}}_2$ are classified under the assumption that $\mathcal{Z}$ is an $\mathcal{A}$-subgroup. Those Schur rings are proved to be traditional.

Authors:Yulai Ma, Davide Mattiolo, Eckhard Steffen, Isaak H. Wolf

Abstract: An $r$-regular graph is an $r$-graph, if every odd set of vertices is connected to its complement by at least $r$ edges. Let $G$ and $H$ be $r$-graphs. An $H$-coloring of $G$ is a mapping $f\colon E(G) \to E(H)$ such that each $r$ adjacent edges of $G$ are mapped to $r$ adjacent edges of $H$. For every $r\geq 3$, let $\mathcal{H}_r$ be an inclusion-wise minimal set of connected $r$-graphs, such that for every connected $r$-graph $G$ there is an $H \in \mathcal{H}_r$ which colors $G$. We show that $\mathcal{H}_r$ is unique and characterize $\mathcal{H}_r$ by showing that $G \in \mathcal{H}_r$ if and only if the only connected $r$-graph coloring $G$ is $G$ itself. The Petersen Coloring Conjecture states that the Petersen graph $P$ colors every bridgeless cubic graph. We show that if true, this is a very exclusive situation. Indeed, either $\mathcal{H}_3 = \{P\}$ or $\mathcal{H}_3$ is an infinite set and if $r \geq 4$, then $\mathcal{H}_r$ is an infinite set. Similar results hold for the restriction on simple $r$-graphs. By definition, $r$-graphs of class $1$ (i.e. those having edge-chromatic number equal to $r$) can be colored with any $r$-graph. Hence, our study will focus on those $r$-graphs whose edge-chromatic number is bigger than $r$, also called $r$-graphs of class $2$. We determine the set of smallest $r$-graphs of class 2 and show that it is a subset of $\mathcal{H}_r$.

Authors:Florian Hörsch

Abstract: For a given digraph $D$ and distinct $u,v \in V(D)$, we denote by $\lambda_D(u,v)$ the local arc-connectivity from $u$ to $v$. Further, we define the total arc connectivity $tac(D)$ of $D$ to be $\sum_{\{u,v\}\subseteq V(D)}\lambda_D(u,v)+\lambda_D(v,u)$. We show that, given a graph $G$ and an integer $k$, it is NP-complete to decide whether $G$ has an orientation $\vec{G}$ satisfying $tac(\vec{G})\geq k$. This answers a question of Pekec. On the positive side, we show that the corresponding maximization problem admits a $\frac{2}{3}$-approximation algorithm.

Authors:Minho Cho, Jinha Kim

Abstract: A stacked $d$-sphere $S$ is the boundary complex of a stacked $(d+1)$-ball, which is obtained by taking cone over a free $d$-face repeatedly from a $(d+1)$-simplex. A stacked sphere $S$ is called linear if every cone is taken over a face added in the previous step. In this paper, we study the transversal number of facets of stacked $d$-spheres, denoted by $\tau(S)$, which is the minimum number of vertices intersecting with all facets. Briggs, Dobbins and Lee showed that the transversal ratio of a stacked $d$-sphere is bounded above by $\frac{2}{d+2}+o(1)$ and can be as large as $\frac{2}{d+3}$. We improve the lower bound by constructing linear stacked $d$-spheres with transversal ratio $\frac{6}{3d+8}$ and general stacked $d$-spheres with transversal ratio $\frac{2d+3}{(d+2)^2}$. Finally, we show that $\frac{6}{3d+8}$ is optimal for linear stacked $2$-spheres, that is, the transversal ratio is at most $\frac{3}{7} + o(1)$ for linear stacked $2$-spheres.

Authors:Igor Araujo, Simón Piga, Andrew Treglown, Zimu Xiang

Abstract: Given graphs $F$ and $G$, a perfect $F$-tiling in $G$ is a collection of vertex-disjoint copies of $F$ in $G$ that together cover all the vertices in $G$. The study of the minimum degree threshold forcing a perfect $F$-tiling in a graph $G$ has a long history, culminating in the K\"uhn--Osthus theorem [Combinatorica 2009] which resolves this problem, up to an additive constant, for all graphs $F$. In this paper we initiate the study of the analogous question for edge-ordered graphs. In particular, we characterize for which edge-ordered graphs $F$ this problem is well-defined. We also apply the absorbing method to asymptotically determine the minimum degree threshold for forcing a perfect $P$-tiling in an edge-ordered graph, where $P$ is any fixed monotone path.

Authors:David Dolžan

Abstract: We calculate the Wiener index of the zero-divisor graph of a finite semisimple ring. We also calculate the Wiener complexity of the zero-divisor graph of a finite simple ring and find an upper bound for the Wiener complexity in the semisimple case.

Authors:Agelos Georgakopoulos, Panos Papasoglu

Abstract: We present problems and results that combine graph-minors and coarse geometry. For example, we ask whether every geodesic metric space (or graph) without a fat $H$ minor is quasi-isometric to a graph with no $H$ minor, for an arbitrary finite graph $H$. We answer this affirmatively for a few small $H$. We also present a metric analogue of Menger's theorem and Konig's ray theorem. We conjecture metric analogues of the Erdos--Posa Theorem and Halin's grid theorem.

Authors:Alexandr Polyanskii, Rinat Sadykov

Abstract: The unraveled ball of radius $r$ centered at a vertex $v$ in a weighted graph $G$ is the ball of radius $r$ centered at $v$ in the universal cover of $G$. We present a general bound on the maximum spectral radius of unraveled balls of fixed radius in a weighted graph. The weighted degree of a vertex in a weighted graph is the sum of weights of edges incident to the vertex. A weighted graph is called regular if the weighted degrees of its vertices are the same. Using the result on unraveled balls, we prove a variation of the Alon-Boppana theorem for regular weighted graphs.

Authors:Gianira N. Alfarano, Eimear Byrne

Abstract: The Critical Theorem, due to Henry Crapo and Gian-Carlo Rota, has been extended and generalised in many ways. In this paper, we describe properties of the characteristic polynomial of a weighted lattice showing that it has a recursive description. We use this to obtain results on critical exponents of $q$-polymatroids. We prove a Critical Theorem for representable $q$-polymatroids and we provide a lower bound on the critical exponent. We show that certain families of rank-metric codes attain this lower bound.

Authors:Joannes Vermant, Klara Stokes

Abstract: In structural rigidity, one studies frameworks of bars and joints in Euclidean space. Such a framework is an articulated structure consisting of rigid bars, joined together at joints around which the bars may rotate. In this paper, we will describe articulated motions of realisations of incidence geometries that uses the terminology of graph of groups, and describe the motions of such a framework using group theory. Our approach allows to model a variety of situations, such as parallel redrawings, scenes, polytopes, realisations of graphs on surfaces, and even unique colourability of graphs. This approach allows a concise description of various dualities in rigidity theory. We also provide a lower bound on the dimension of the infinitesimal motions of such a framework in the special case when the underlying group is a Lie group.

Authors:Sara C. Billey, Joshua P. Swanson

Abstract: It is a remarkable fact that for many statistics on finite sets of combinatorial objects, the roots of the corresponding generating function are each either a complex root of unity or zero. We call such polynomials \textbf{cyclotomic generating functions} (CGF's). Previous work studied the support and asymptotic distribution of the coefficients of several families of CGF's arising from tableau and forest combinatorics. In this paper, we continue these explorations by studying general CGF's from algebraic, analytic, and asymptotic perspectives. We review some of the many known examples of CGF's; describe their coefficients, moments, cumulants, and characteristic functions; and give a variety of necessary and sufficient conditions for their existence arising from probability, commutative algebra, and invariant theory. We further show that CGF's are ``generically'' asymptotically normal, generalizing a result of Diaconis. We include several open problems concerning CGF's.

Authors:Colin Defant, Michael Joseph, Matthew Macauley, Alex McDonough

Abstract: Much of dynamical algebraic combinatorics focuses on global dynamical systems defined via maps that are compositions of local toggle operators. The second author and Roby studied such maps that result from toggling independent sets of a path graph. We investigate a "toric" analogue of this work by analyzing the dynamics arising from toggling independent sets of a cycle graph. Each orbit in the dynamical system can be encoded via a grid of 0s and 1s; two commuting bijections on the set of 1s in this grid produce torsors for what we call the infinite snake group and the finite ouroboros groups. By studying related covering maps, we deduce precise combinatorial properties of the orbits. Because the snake and ouroboros groups are abelian, they define tilings of cylinders and tori by parallelograms, which we also characterize. Many of the ideas developed here should be adaptable both to other toggle actions in combinatorics and to other cellular automata.

Authors:Taikei Fujii, Takahiko Nobukawa, Tatsushi Shimazaki

Abstract: The set-valued tableaux are combinatorial objects introduced by Buch for expressing the tableaux-sum formula of the stable Grothendieck polynomials. Not much is known about the set-valued tableaux compared to the usual case of the semi-standard tableaux. In this paper, we show the odd property for the number of set-valued tableaux.

Authors:S. Huczynska, L. M. Johnson

Abstract: Recently, new combinatorial structures called disjoint partial difference families (DPDFs) and external partial difference families (EPDFs) were introduced, which simultaneously generalize partial difference sets, disjoint difference families and external difference families, and have applications in information security. So far, all known construction methods have used cyclotomy in finite fields. We present the first non-cyclotomic infinite families of DPDFs which are also EPDFs, in structures other than finite fields (in particular cyclic groups and non-abelian groups). As well as direct constructions, we present an approach to constructing DPDFs/EPDFs using relative difference sets (RDSs); as part of this, we demonstrate how the well-known RDS result of Bose extends to a very natural construction for DPDFs and EPDFs.

Authors:Recep Altar Çiçeksiz, Zhihan Jin, Eero Räty, István Tomon

Abstract: In 1993, Fishburn and Graham established the following qualitative extension of the classical Erd\H{o}s-Szekeres theorem. If $N$ is sufficiently large with respect to $n$, then any $N\times N$ real matrix contains an $n\times n$ submatrix in which every row and every column is monotone. We prove that the smallest such $N$ is at most $2^{n^{4+o(1)}}$, greatly improving the previously best known double-exponential upper bound, and getting close to the best known lower bound $n^{n/2}$. In particular, we prove the following surprising sharp transition in the asymmetric setting. On one hand, every $8n^2\times 2^{n^{4+o(1)}}$ matrix contains an $n\times n$ submatrix, in which every row is mononote. On the other hand, there exist $n^{2}/6\times 2^{2^{n^{1-o(1)}}}$ matrices containing no such submatrix .

Authors:Jelena Sedlar, Riste Škrekovski

Abstract: In a (proper) edge-coloring of a bridgeless cubic graph G an edge e is rich (resp. poor) if the number of colors of all edges incident to end-vertices of e is 5 (resp. 3). An edge-coloring of G is is normal if every edge of G is either rich or poor. In this paper we consider snarks ~G obtained by a simple superposition of edges and vertices of a cycle C in a snark G: For an even cycle C we show that a normal coloring of G can be extended to a normal coloring of ~G without changing colors of edges outside C in G: An interesting remark is that this is in general impossible for odd cycles, since the normal coloring of a Petersen graph P10 cannot be extended to a superposition of P10 on a 5-cycle without changing colors outside the 5-cycle. On the other hand, as our colorings of the superpositioned snarks introduce 18 or more poor edges, we are inclined to believe that every bridgeless cubic graph istinct from P10 has a normal coloring with at least one poor edge and possibly with at least 6 if we also exclude the Petersen graph with one vertex truncated.

Authors:Ying Wang, Zihao Zhang

Abstract: By using Sulanke-Xin continued fractions method, Xin proposed a recursion system to solve the Somos 4 Hankel determinant conjecture. We find Xin's recursion system indeed give a sufficient condition for $(\alpha, \beta)$ Somos $4$ sequences. This allows us to prove 4 conjectures of Barry on $(\alpha, \beta)$ Somos $4$ sequences in a unified way.

Authors:Primoz Potocnik, Alejandra Ramos-Rivera, Micael Toledo, Stephen Wilson

Abstract: A corner in a map is an edge-vertex-edge triple consisting of two distinct edges incident to the same vertex. A corneration is a set of corners that covers every arc of the map exactly once. Cornerations in a dart-transitive map generalize the notion of a cycle structure in a symmetric graph. In this paper, we study the cornerations (and associated structures) that are preserved by a vertex-transitive group of automorphisms of the map.

Authors:Gábor Hegedüs

Abstract: The vertices of the permutohedron can be covered by one hyperplane in the $n$ dimensional affine space. We prove here that any set of hyperplanes that covers all the vertices of the permutohedron but one contains at least ${n\choose 2}$ hyperplanes. Our proof is based on a new variant of the Combinatorial Nullstellensatz.

Authors:António Girão, Robert Hancock

Abstract: Recently, Dragani\'c, Munh\'a Correia, Sudakov and Yuster showed that every tournament on $(2+o(1))k^2$ vertices contains a $1$-subdivision of a transitive tournament on $k$ vertices, which is tight up to a constant factor. We prove a counterpart of their result for immersions. Let $f(k)$ be the smallest integer such that any tournament on at least $f(k)$ vertices must contain a $1$-immersion of a transitive tournament on $k$ vertices. We show that $f(k)=O(k)$, which is clearly tight up to a multiplicative factor. If one insists in finding an immersion of a complete directed graph on $k$ vertices then an extra condition on the tournament is necessary. Indeed, we show that every tournament with minimum out-degree at least $Ck$ must contain a $2$-immersion of a complete digraph on $k$ vertices. This is again tight up to the value of $C$ and tight on the order of the paths in the immersion.

Authors:Thomas Jenrich

Abstract: In 1933, Karol Borsuk asked whether each bounded set in the $n$-dimensional Euclidean space can be divided into $n$+1 parts of smaller diameter. Because it would not make sense otherwise, one usually assumes that he just forgot to require that the whole set contains at least two points. The hypothesis that the answer to that question is positive became famous under the name \emph{Borsuk's conjecture}. Counterexamples are known for any $n\ge 64$, since 2013. Let $\Lambda$ the (original, unscaled) Leech lattice, a now very well-known infinite discrete vector set in the 24-dimensional Euclidean space. The smallest norm of nonzero vectors in $\Lambda$ is $\sqrt{32}$. Let $M$ the set of the 196560 vectors in $\Lambda$ having this norm. For each $x \in M$, $-x$ is in $M$. Let $H$ the set of all subsets of $M$ that for each $x$ in $M$ contain either $x$ or $-x$. Each element of $H$ has the same diameter $d = \sqrt{96}$. For dimensions $n<24$ one can analogously construct respective $M_n$ and $H_n$ from laminated $n$-dimensional sublattices of $\Lambda$. For uniformity, let $\Lambda_{24}=\Lambda$, $M_{24} = M$ and $H_{24} = H$. If $M_n$ is divisible into at most $n+1$ parts of diameter below $d$ then this applies to all elements of $H_n$, too. On the other hand, the more the minimum number of parts of diameter below $d$ that $M_n$ can be divided into exceeds $n+1$, the more likely $H_n$ contains a counterexample to Borsuk's conjecture. For dimensions $n$ from 22 to 24, I could not divide $M_n$ into less than 28, 32 and 39 parts of diameter below $d$, resp. (I did not find any applicable result by others).

Authors:Jan De Beule, Jonathan Mannaert, Valentino Smaldore

Abstract: In this paper we develop non-existence results for $m$-ovoids in the classical polar spaces $Q^-(2r+1,q), W(2r-1,q)$ and $H(2r,q^2)$ for $r>2$. In [4] a lower bound on $m$ for the existence of $m$-ovoids of $H(4,q^2)$ is found by using the connection between $m$-ovoids, two-character sets, and strongly regular graphs. This approach is generalized in [3] for the polar spaces $Q^-(2r+1,q), W(2r-1,q)$ and $H(2r,q^2)$, $r>2$. In [1] an improvement for the particular case $H(4,q^2)$ is obtained by exploiting the algebraic structure of the collinearity graph, and using the characterization of an $m$-ovoid as an intruiging set. In this paper, we use an approach based on geometrical and combinatorial arguments, inspired by the results from [10], to improve the bounds from [3].

Authors:Patrizio Bifulco, Joachim Kerner

Abstract: In this note we elaborate on some notions of surface area for discrete graphs which are closely related to the inverse degree. These notions then naturally lead to an associated connectivity measure of graphs and to the definition of a special class of large graphs, called social graphs, that might prove interesting for applications, among others, in computer science.

Authors:Bartłomiej Pawelski

Abstract: We provide the first-ever calculation of the number of inequivalent monotone Boolean functions of 9 variables, which is equal to 789,204,635,842,035,040,527,740,846,300,252,680.

Authors:Seog-Jin Kim, Xiaopan Lian

Abstract: The square of a graph $G$, denoted $G^2$, has the same vertex set as $G$ and has an edge between two vertices if the distance between them in $G$ is at most $2$. Thomassen (2018) and Hartke, Jahanbekam and Thomas (2016) proved that $\chi(G^2) \leq 7$ if $G$ is a subcubic planar graph. A natural question is whether $\chi_{\ell}(G^2) \leq 7$ or not if $G$ is a subcubic planar graph. Cranston and Kim (2008) showed that $\chi_{\ell}(G^2) \leq 7$ if $G$ is a subcubic planar graph of girth at least 7. We prove that $\chi_{\ell}(G^2) \leq 7$ if $G$ is a subcubic planar graph of girth at least 6.

Authors:Svante Linusson, Petter Restadh

Abstract: The purpose of this paper is twofold. We investigate a simple necessary condition, called the rhombus criterion, for two vertices in a polytope not to form an edge and show that in many examples of $0/1$-polytopes it is also sufficient. We explain how also when this is not the case, the criterion can give a good algorithm for determining the edges of high-dimenional polytopes. In particular we study the Chordal graph polytope, which arises in the theory of causality and is an important example of a characteristic imset polytope. We prove that, asymptotically, for almost all pairs of vertices the rhombus criterion holds. We conjecture it to hold for all pairs of vertices.

Authors:Freddie Illingworth, Lukas Michel, Alex Scott

Abstract: The free semigroup $\mathcal{F}$ over a finite alphabet $\mathcal{A}$ is the set of all finite words with letters from $\mathcal{A}$ equipped with the operation of concatenation. A subset $S$ of $\mathcal{F}$ is $k$-product-free if no element of $S$ can be obtained by concatenating $k$ words from $S$, and strongly $k$-product-free if no element of $S$ is a (non-trivial) concatenation of at most $k$ words from $S$. We prove that a $k$-product-free subset of $\mathcal{F}$ has upper Banach density at most $1/\rho(k)$, where $\rho(k) = \min\{\ell \colon \ell \nmid k - 1\}$. This confirms a conjecture of Ortega, Ru\'{e}, and Serra. We also determine the structure of the extremal $k$-product-free subsets for all $k \notin \{3, 5, 7, 13\}$; a special case of this proves a conjecture of Leader, Letzter, Narayanan, and Walters. We further determine the structure of all strongly $k$-product-free sets with maximum density.

Authors:Susana Furtado, Charles Johnson

Abstract: Efficient vectors are the natural set from which to choose a cardinal ranking vector for a reciprocal matrix. Such vectors are the key to certain business project selection models. Many ways to construct specific efficient vectors have been proposed. Yet, no previous method to produce all efficient vectors was known. Here, using some graph theoretic ideas, as well as a numerical extension technique, we show how to generate all efficient vectors for any given reciprocal matrix. We apply this method to give explicitly all efficient vectors for a 4-by-4 reciprocal matrix. Several examples are provided.

Authors:Agnijo Banerjee

Abstract: A family $\mathcal{F} \subset \mathcal{P}(n)$ is $r$-wise $k$-intersecting if $|A_1 \cap \dots \cap A_r| \geq k$ for any $A_1, \dots, A_r \in \mathcal{F}$. It is easily seen that if $\mathcal{F}$ is $r$-wise $k$-intersecting for $r \geq 2$, $k \geq 1$ then $|\mathcal{F}| \leq 2^{n-1}$. The problem of determining the maximal size of a family $\mathcal{F}$ that is both $r_1$-wise $k_1$-intersecting and $r_2$-wise $k_2$-intersecting was raised in 2019 by Frankl and Kupavskii [1]. They proved the surprising result that, for $(r_1,k_1) = (3,1)$ and $(r_2,k_2) = (2,32)$ then this maximum is at most $2^{n-2}$, and conjectured the same holds if $k_2$ is replaced by $3$. In this paper we shall not only prove this conjecture but we shall also determine the exact maximum for $(r_1,k_1) = (3,1)$ and $(r_2,k_2) = (2,3)$ for all $n$.

Authors:Lior Gishboliner, Nick Kushnir, Asaf Shapira

Abstract: A distance estimator for a graph property $\mathcal{P}$ is an algorithm that given $G$ and $\alpha, \varepsilon >0$ distinguishes between the case that $G$ is $(\alpha-\varepsilon)$-close to $\mathcal{P}$ and the case that $G$ is $\alpha$-far from $\mathcal{P}$ (in edit distance). We say that $\mathcal{P}$ is estimable if it has a distance estimator whose query complexity depends only on $\varepsilon$. Every estimable property is also testable, since testing corresponds to estimating with $\alpha=\varepsilon$. A central result in the area of property testing, the Fischer--Newman theorem, gives an inverse statement: every testable property is in fact estimable. The proof of Fischer and Newman was highly ineffective, since it incurred a tower-type loss when transforming a testing algorithm for $\mathcal{P}$ into a distance estimator. This raised the natural problem, studied recently by Fiat--Ron and by Hoppen--Kohayakawa--Lang--Lefmann--Stagni, whether one can find a transformation with a polynomial loss. We obtain the following results. 1. If $\mathcal{P}$ is hereditary, then one can turn a tester for $\mathcal{P}$ into a distance estimator with an exponential loss. This is an exponential improvement over the result of Hoppen et. al., who obtained a transformation with a double exponential loss. 2. For every $\mathcal{P}$, one can turn a testing algorithm for $\mathcal{P}$ into a distance estimator with a double exponential loss. This improves over the transformation of Fischer--Newman that incurred a tower-type loss. Our main conceptual contribution in this work is that we manage to turn the approach of Fischer--Newman, which was inherently ineffective, into an efficient one. On the technical level, our main contribution is in establishing certain properties of Frieze--Kannan Weak Regular partitions that are of independent interest.

Authors:Fernando Sancho de Salas, Alejandro Torres Sancho

Abstract: We develop Grothendieck's theory of dualizing complexes on finite posets, and its subsequent theory of Cohen-Macaulayness.

Authors:Benedek Kovács, Zoltán Lóránt Nagy

Abstract: We study the set of intersection sizes of a $k$-dimensional affine subspace and a point set of size $m \in [0, 2^n]$ of the $n$-dimensional binary affine space $AG(n,2)$. Following the theme of Erd\H{o}s, F\"uredi, Rothschild and T. S\'os, we partially determine which local densities in $k$-dimensional affine subspaces are unavoidable in all $m$-element point sets in the $n$-dimensional affine space.\\ We also show constructions of point sets for which the intersection sizes with $k$-dimensional affine subspaces takes values from a set of a small size compared to $2^k$. These are built up from affine subspaces and so-called subspace evasive sets. Meanwhile, we improve the best known upper bounds on subspace evasive sets and apply results concerning the canonical signed-digit (CSD) representation of numbers.

Authors:A. Lourdusamy, I. Dhivviyanandam, Lian Mathew

Abstract: Let $G$ be a connected graph. A pebbling move is defined as taking two pebbles from one vertex and placing one pebble to an adjacent vertex and throwing away the other pebble. The non-split domination cover pebbling number, $\psi_{ns}(G)$, of a graph $G$ is the minimum of pebbles that must be placed on $V(G)$ such that after a sequence of pebbling moves, the set of vertices with a pebble forms a non-split dominating set of $G$, regardless of the initial configuration of pebbles. We discuss some basic results, NP-completeness of non-split domination number, and determine $\psi_{ns}$ for some families of Middle graphs.

Authors:Rizwan Jahangir, Dharm Veer

Abstract: We characterize Cohen-Macaulay posets of dimension two; they are precisely the shellable and strongly connected posets of dimension two. We also give a combinatorial description of these posets. Using the fact that co-comparability graph of a 2-dimensional poset is a permutation graph, we characterize Cohen-Macaulay permutation graphs.

Authors:Dominique Désérable, Rolf Hoffmann, Franciszek Seredyński

Abstract: "Dominos" are special entities consisting of a hard dimer-like kernel surrounded by a soft hull and governed by local interactions. "Soft hull" and "hard kernel" mean that the hulls can overlap while the kernel acts under a repulsive potential. Unlike the dimer problem in statistical physics, which lists the number of all possible configurations for a given n x n lattice, the more modest goal herein is to provide lower and upper bounds for the maximum allowed number of dominos in the diamond. In this NP problem, a deterministic construction rule is proposed and leads to a suboptimal solution {\psi}_n as a lower bound. A certain disorder is then injected and leads to an upper bound {\psi}_n_upper reachable or not. In some cases, the lower and upper bounds coincide, so {\psi}_n = {\psi}_n_upper becomes the exact number of dominos for a maximum configuration.

Authors:Batmend Horoldagva, Chunlei Xu

Abstract: Recently, Gutman defined a new vertex-degree-based graph invariant, named the Sombor index $SO$ of a graph $G$, and is defined by $$SO(G)=\sum_{uv\in E(G)}\sqrt{d_G(u)^2+d_G(v)^2},$$ where $d_G(v)$ is the degree of the vertex $v$ of $G$. In this paper, we obtain the sharp lower and upper bounds on $SO(G)$ of a connected graph, and characterize graphs for which these bounds are attained.

Authors:Michela Ascolese, Andrea Frosini

Abstract: In [2], while studying a relevant class of polyominoes that tile the plane by translation, i.e., double square polyominoes, the authors found that their boundary words, encoded by the Freeman chain coding on a four letters alphabet, have specific interesting properties that involve notions of combinatorics on words such as palindromicity, periodicity and symmetry. Furthermore, they defined a notion of reducibility on double squares using homologous morphisms, so leading to a set of irreducible tile elements called prime double squares. The authors, by inspecting the boundary words of the smallest prime double squares, conjectured the strong property that no runs of two (or more) consecutive equal letters are present there. In this paper, we prove such a conjecture using combinatorics on words tools, and setting the path to the definition of a fast generation algorithm and to the possibility of enumerating the elements of this class w.r.t. standard parameters, as perimeter and area.

Authors:Hui Qin, Guowei Dai, Yuan Chen, Ting Jin, Yuan Yuan

Abstract: A spanning subgraph $H$ of a graph $G$ is called a $P_{\geq k}$-factor of $G$ if every component of $H$ is isomorphic to a path of order at least $k$, where $k\geq2$ is an integer. A graph $G$ is called a $(P_{\geq k},l)$-factor critical graph if $G-V'$ contains a $P_{\geq k}$-factor for any $V'\subseteq V(G)$ with $|V'|=l$. A graph $G$ is called a $(P_{\geq k},m)$-factor deleted graph if $G-E'$ has a $P_{\geq k}$-factor for any $E'\subseteq E(G)$ with $|E'|=m$. Intuitively, if a graph is dense enough, it will have a $P_{\geq 3}$-factor. In this paper, we give some sufficient conditions for a graph to be a $(P_{\geq 3},l)$-factor critical graph or a $(P_{\geq 3},m)$-factor deleted graph. In this paper, we demonstrate that (i) $G$ is a $(P_{\geq 3},l)$-factor critical graph if its sun toughness $s(G)>\frac{l+1}{3}$ and $\kappa(G)\geq l+2$. (ii) $G$ is a $(P_{\geq 3},l)$-factor critical graph if its degree sum $\sigma_3(G)\geq n+2l$ and $\kappa(G)\geq l+1$. (iii) $G$ is a $(P_{\geq 3},m)$-factor deleted graph if its sun toughness $s(G)\geq \frac{m+1}{m+2}$ and $\kappa(G)\geq 2m+1$. (iv) $G$ is a $(P_{\geq 3},m)$-factor deleted graph if its degree sum $\sigma_3(G)\geq n+2m$ and $\kappa(G)\geq 2m+1$.

Authors:Sandra Albrechtsen, Tony Huynh, Raphael W. Jacobs, Paul Knappe, Paul Wollan

Abstract: We give an approximate Menger-type theorem for when a graph $G$ contains two $X-Y$ paths $P_1$ and $P_2$ such that $P_1 \cup P_2$ is an induced subgraph of $G$. More generally, we prove that there exists a function $f(d) \in O(d)$, such that for every graph $G$ and $X,Y \subseteq V(G)$, either there exist two $X-Y$ paths $P_1$ and $P_2$ such that the distance between $P_1$ and $P_2$ is at least $d$, or there exists $v \in V(G)$ such that the ball of radius $f(d)$ centered at $v$ intersects every $X-Y$ path.

Authors:Erlang Surya, Lutz Warnke, Emily Zhu

Abstract: We consider two variants of the induced subgraph isomorphism problem for two independent binomial random graphs with constant edge-probabilities p_1,p_2. We resolve several open problems of Chatterjee and Diaconis, and also confirm simulation-based predictions of McCreesh, Prosser, Solnon and Trimble: (i) we prove a sharp threshold result for the appearance of G_{n,p_1} as an induced subgraph of G_{N,p_2}, (ii) we show two-point concentration of the maximum common induced subgraph of G_{N, p_1} and G_{N,p_2}, and (iii) we show that the number of induced copies of G_{n,p_1} in G_{N,p_2} has an unusual limiting distribution.

Authors:Jeremy M. Dover

Abstract: A blocking semioval is a set of points in a projective plane that is both a blocking set (i.e., every line meets the set, but the set contains no line) and a semioval (i.e., there is a unique tangent line at each point). The smallest size of a blocking semioval is known for all finite projective planes of order less than 11; we investigate the situation in PG(2,11).

Authors:Reina Ishikawa

Abstract: In the present paper, we give proofs of the existence of a 3-design in the extended ternary quadratic residue code of length 14 and the extended quaternary quadratic residue code of length 18.

Authors:Flor Aguilar, Gabriela Araujo-Pardo, Leah Bermann

Abstract: An \emph{$(3,m;g)$ semicubic graph} is a graph in which all vertices have degrees either $3$ or $m$ and fixed girth $g$. In this paper, we construct families of semicubic graphs of even girth and small order using two different techniques. The first technique generalizes a previous construction which glues cubic cages of girth $g$ together at remote vertices (vertices at distance at least $g/2$). The second technique, the main content of this paper, produces bipartite semicubic $(3,m; g)$-graphs with fixed even girth $g = 4t$ or $4t+2$ using voltage graphs over $\mathbb{Z}_{m}$. When $g = 4t+2$, the graphs have two vertices of degree $m$, while when $g = 4t$ they have exactly three vertices of degree $m$ (the remaining vertices are of degree $3$ in both cases). Specifically, we describe infinite families of semicubic graphs $(3,m; g)$ for $g = \{6, 8, 10, 12\}$ for infinitely many values of $m$. The cases $g = \{6,8\}$ include the unique $6$-cage and the unique $8$-cage when $m = 3$. The families obtained in this paper for girth $g=\{10,12\}$ include examples with the best known bounds for semicubic graphs $(3,m; g)$

Authors:Giusy Monzillo, Tim Penttila, Alessandro Siciliano

Abstract: Brown et al. provide a representation of a spread of the Tits quadrangle $T_2(\mathcal O)$, $\mathcal O$ an oval of $\mathrm PG(2,q)$, $q$ even, in terms of a certain family of $q$ ovals of $\mathrm PG(2,q)$. By combining this representation with the Vandendriessche classification of hyperovals in $\mathrm PG(2,64)$ and the classification of flocks of the quadratic cone in $\mathrm PG(3,64)$, recently given by the authors, in this paper, we classify all the spreads of $T_2(\mathcal O)$, $\mathcal O$ an oval of $\mathrm PG(2,64)$, up to equivalence. These complete the classification of spreads of $T_2(\mathcal O)$ for $q\le 64$.

Authors:Dániel Garamvölgyi, Tibor Jordán

Abstract: A $d$-dimensional framework is a pair $(G,p)$, where $G$ is a graph and $p$ maps the vertices of $G$ to points in $\mathbb{R}^d$. The edges of $G$ are mapped to the corresponding line segments. A graph $G$ is said to be globally rigid in $\mathbb{R}^d$ if every generic $d$-dimensional framework $(G,p)$ is determined, up to congruence, by its edge lengths. A finer property is global linkedness: we say that a vertex pair $\{u,v\}$ of $G$ is globally linked in $G$ in $\mathbb{R}^d$ if in every generic $d$-dimensional framework $(G,p)$ the distance of $u$ and $v$ is uniquely determined by the edge lengths. In this paper we investigate globally linked pairs in graphs in $\mathbb{R}^d$. We give several characterizations of those rigid graphs $G$ in which a pair $\{u,v\}$ is globally linked if and only if there exist $d+1$ internally disjoint paths from $u$ to $v$ in $G$. We call these graphs $d$-joined. Among others, we show that $G$ is $d$-joined if and only if for each pair of generic frameworks of $G$ with the same edge lengths, one can be obtained from the other by a sequence of partial reflections along hyperplanes determined by $d$-separators of $G$. We also show that the family of $d$-joined graphs is closed under edge addition, as well as under gluing along $d$ or more vertices. As a key ingredient to our main results, we prove that rigid graphs in $\mathbb{R}^d$ contain no crossing $d$-separators. Our results give rise to new families of graphs for which global linkedness (and global rigidity) in $\mathbb{R}^d$ can be tested in polynomial time.

Authors:G. Ravindra, Sanghita Ghosh, Abraham V. M

Abstract: For a graph $G$ with the vertex set $V(G)$ and the edge set $E(G)$ and a star subgraph $S$ of $G$, let $\alpha_S(G)$ be the maximum number of vertices in $G$ such that no two of them are in the same star subgraph $S$ and $\theta_S(G)$ be the minimum number of star subgraph $S$ that cover the vertices of $G$. A graph $G$ is called $S$-perfect if for every induced subgraph $H$ of $G$, $\alpha_S(H)=\theta_S(H)$. Motivated by perfect graphs discovered by Berge, Ravindra introduced $S$-perfect graphs. In this paper we prove that a triangulated graph is $S$-perfect if and only if $G$ is odd sun-free. This result leads to a conjecture which if proved is a structural characterization of $S$-perfect graphs in terms of forbidden subgraphs.

Authors:Rafik Sahbi, Wissam Boumalha, Asmaa Issad

Abstract: A partition $\pi=\{V_{1},V_{2},...,V_{k}\}$ of the vertex set $V$ of a graph $G$ into $k$ color classes $V_{i}$, with $1\leq i\leq k$ is called a quorum coloring of $G$ if for every vertex $v\in V$, at least half of the vertices in the closed neighborhood $N[v]$ of $v$ have the same color as $v$. The maximum cardinality of a quorum coloring of $G$ is called the quorum coloring number of $G$ and is denoted by $\psi_{q}(G)$. A quorum coloring of order $\psi_{q}(G)$ is a $\psi_{q}$-coloring. The determination of the quorum coloring number or design a linear-time algorithm computing it in a perfect $N$-ary tree has been posed recently as an open problem by Sahbi. In this paper, we answer this problem by designing a linear-time algorithm for finding both a $\psi_{q}$-coloring and the quorum coloring number for every perfect tree whose the vertices at the same depth have the same degree.

Authors:Jan Hladký, Gopal Viswanathan

Abstract: Each graphon $W:\Omega^2\rightarrow[0,1]$ yields an inhomogeneous random graph model $G(n,W)$. We show that $G(n,W)$ is asymptotically almost surely connected if and only if (i) $W$ is a connected graphon and (ii) the measure of elements of $\Omega$ of $W$-degree less than $\alpha$ is $o(\alpha)$ as $\alpha\rightarrow 0$. These two conditions encapsulate the absence of several linear-sized components, and of isolated vertices, respectively. We study in bigger detail the limit probability of the property that $G(n,W)$ contains an isolated vertex, and, more generally, the limit distribution of the minimum degree of $G(n,W)$.

Authors:Ferdinand Ihringer

Abstract: A minimum storage regenerating (MSR) subspace family of $\mathbb{F}_q^{2m}$ is a set $\mathcal{S}$ of $m$-spaces in $\mathbb{F}_q^{2m}$ such that for any $m$-space $S$ in $\mathcal{S}$ there exists an element in $\mathrm{PGL}(2m, q)$ which maps $S$ to itself and fixes $\mathcal{S} \setminus \{ S \}$ pointwise. We show that an MSR subspace family of $2$-spaces in $\mathbb{F}_q^4$ has at most size $6$ with equality if and only if it is a particular subset of a Segre variety. This implies that an $(n, n-2, 4)$-MSR code has $n \leq 9$.

Authors:Lauren Snider, Catherine Yan

Abstract: Graphical parking functions, or $G$-parking functions, are a generalization of classical parking functions which depend on a connected multigraph $G$ having a distinguished root vertex. Gaydarov and Hopkins characterized the relationship between $G$-parking functions and another vector-dependent generalization of parking functions, the $\boldsymbol{u}$-parking functions. The crucial component of their result was their classification of all graphs $G$ whose $G$-parking functions are invariant under action by the symmetric group $\mathfrak{S}_n$, where $n+1$ is the order of $G$. In this work, we present a 2-dimensional analogue of Gaydarov and Hopkins' results by characterizing the overlap between $G$-parking functions and 2-dimensional $\boldsymbol{U}$-parking functions, i.e., pairs of integer sequences whose order statistics are bounded by certain weights along lattice paths in the plane. Our key result is a total classification of all $G$ whose set of $G$-parking functions is $(\mathfrak{S}_p \times \mathfrak{S}_q)$-invariant, where $p+q+1$ is the order of $G$.

Authors:Greta Panova

Abstract: Kostka, Littlewood-Richardson, Kronecker, and plethysm coefficients are fundamental quantities in algebraic combinatorics, yet many natural questions about them stay unanswered for more than 80 years. Kronecker and plethysm coefficients lack ``nice formulas'', a notion that can be formalized using computational complexity theory. Beyond formulas and combinatorial interpretations, we can attempt to understand their asymptotic behavior in various regimes, and inequalities they could satisfy. Understanding these quantities has applications beyond combinatorics. On the one hand, the asymptotics of structure constants is closely related to understanding the [limit] behavior of vertex and tiling models in statistical mechanics. More recently, these structure constants have been involved in establishing computational complexity lower bounds and separation of complexity classes like VP vs VNP, the algebraic analogs of P vs NP in arithmetic complexity theory. Here we discuss the outstanding problems related to asymptotics, positivity, and complexity of structure constants focusing mostly on the Kronecker coefficients of the symmetric group and, less so, on the plethysm coefficients. This expository paper is based on the talk presented at the Open Problems in Algebraic Combinatorics coneference in May 2022.

Authors:Shiwali Gupta, Subrahmanyam Kalyanasundaram, Rogers Mathew

Abstract: A conflict-free open neighborhood coloring of a graph is an assignment of colors to the vertices such that for every vertex there is a color that appears exactly once in its open neighborhood. For a graph G, the smallest number of colors required for such a coloring is called the conflict-free open neighborhood (CFON) chromatic number and is denoted by \chi_{ON}(G). Analogously, we define conflict-free closed neighborhood (CFCN) coloring, and CFCN chromatic number (denoted by \chi_{CN}(G)). First studied in 2002, this problem has received considerable attention. We study the CFON and CFCN coloring problems and show the following results. In what follows, \Delta denotes the maximum degree of the graph. 1. For a K_{1, k}-free graph G, we show that \chi_{ON}(G) = O(k \ln\Delta). This improves the bound of O(k^2 \ln \Delta) from [Bhyravarapu, Kalyanasundaram, Mathew, MFCS 2022]. Since \chi_{CN}(G) \leq 2\chi_{ON}(G), our result implies an upper bound on \chi_{CN}(G) as well. It is known that there exist separate classes of graphs with \chi_{ON}(G) = \Omega(\ln\Delta) and \chi_{ON}(G) = \Omega(k). 2. Let f(\delta) be defined as follows: f(\delta) = max {\chi_{CN} (G) : G is a graph with minimum degree \delta}. It is easy to see that f(\delta') \geq f(\delta) when \delta' < \delta. It is known [Debski and Przybylo, JGT 2021] that f(c \Delta) = \Theta(\log \Delta), for any positive constant c. In this paper, we show that f(c\Delta^{1 - \epsilon}) = \Omega (\ln^2 \Delta), where c, \epsilon are positive constants such that \epsilon < 0.75. Together with the known upper bound \chi_{CN}(G) = O(\ln^2 \Delta), this implies that f(c\Delta^{1 - \epsilon}) = \Theta (\ln^2 \Delta). 3. For a K_{1, k}-free graph G on n vertices, we show that \chi_{CN}(G) = O(\ln k \ln n). This bound is asymptotically tight.

Authors:Gi-Sang Cheon, Bumtle Kang, Suh-Ryung Kim, Homoon Ryu

Abstract: In this paper, we study row graphs of Toeplitz matrices. The notion of row graphs was introduced by Greenberg et al. in 1984 and is closely related to the notion of competition graphs, which has been extensively studied since Cohen had introduced it in 1968. To understand the structure of the row graphs of Toeplitz matrices, which seem to be quite complicated, we have begun with Toeplitz matrices whose row graphs are triangle-free. We could show that if the row graph G of a Toeplitz matrix T is triangle-free, then T has the maximum row sum at most 2. Furthermore, it turns out that G is a disjoint union of paths and cycles whose lengths cannot vary that much in such a case. Then we study (0, 1)-Toeplitz matrices whose row graphs have only path components, only cycle components, and a cycle component of specific length, respectively. In particular, we completely characterize a (0, 1)-Toeplitz matrix whose row graph is a cycle.

Authors:Yahav Alon, Patrick Morris, Wojciech Samotij

Abstract: Motivated by the investigation of sharpness of thresholds for Ramsey properties in random graphs, Friedgut, Kohayakawa, R\"odl, Ruci\'nski and Tetali introduced two variants of a single-player game whose goal is to colour the edges of a~random graph, in an online fashion, so as not to create a monochromatic triangle. In the two-round variant of the game, the player is first asked to find a triangle-free colouring of the edges of a random graph $G_1$ and then extend this colouring to a triangle-free colouring of the union of $G_1$ and another (independent) random graph $G_2$, which is disclosed to the player only after they have coloured $G_1$. Friedgut et al.\ analysed this variant of the online Ramsey game in two instances: when $G_1$ has $\Theta(n^{4/3})$ edges and when the number of edges of $G_1$ is just below the threshold above which a random graph typically no longer admits a triangle-free colouring, which is located at $\Theta(n^{3/2})$. The two-round Ramsey game has been recently revisited by Conlon, Das, Lee and M\'esz\'aros, who generalised the result of Friedgut at al.\ from triangles to all strictly $2$-balanced graphs. We extend the work of Friedgut et al.\ in an orthogonal direction and analyse the triangle case of the two-round Ramsey game at all intermediate densities. More precisely, for every $n^{-4/3} \ll p \ll n^{-1/2}$, with the exception of $p = \Theta(n^{-3/5})$, we determine the threshold density $q$ at which it becomes impossible to extend any triangle-free colouring of a typical $G_1 \sim G_{n,p}$ to a triangle-free colouring of the union of $G_1$ and $G_2 \sim G_{n,q}$. An interesting aspect of our result is that this threshold density $q$ `jumps' by a polynomial quantity as $p$ crosses a `critical' window around $n^{-3/5}$.

Authors:Minjia Shi, Xiaoxiao Li, Denis S. Krotov, Ferruh Özbudak

Abstract: The Galois ring GR$(4^\Delta)$ is the residue ring $Z_4[x]/(h(x))$, where $h(x)$ is a basic primitive polynomial of degree $\Delta$ over $Z_4$. For any odd $\Delta$ larger than $1$, we construct a partition of GR$(4^\Delta) \backslash \{0\}$ into $6$-subsets of type $\{a,b,-a-b,-a,-b,a+b\}$ and $3$-subsets of type $\{c,-c,2c\}$ such that the partition is invariant under the multiplication by a nonzero element of the Teichmuller set in GR$(4^\Delta)$ and, if $\Delta$ is not a multiple of $3$, under the action of the automorphism group of GR$(4^\Delta)$. As a corollary, this implies the existence of quasi-cyclic additive $1$-perfect codes of index $(2^\Delta-1)$ in $D((2^\Delta-1)(2^\Delta-2)/{6}, 2^\Delta-1 )$ where $D(m,n)$ is the Doob metric scheme on $Z^{2m+n}$.

Authors:Xiaoli Yuan, Yuejian Peng

Abstract: Erd\H{o}s and Simonovits asked the following question: For an integer $r\geq 2$ and a family of non-bipartite graphs $\mathcal{H}$, what is the tight bound of $\alpha$ such that any $\mathcal{H}$-free $n$-vertex graph with minimum degree at least $\alpha n$ has chromatic number at most $r$? We answer this question for $r=2$ and any family of odd cycles. Let $l\le k$ and $n\ge 1000k^{8}$ be positive integers. Let ${\mathcal C}$ be a family of odd cycles, $C_{2l+1}$ be the shortest odd cycle not in ${\mathcal C}$, and $C_{2k+1}$ be the longest odd cycle in ${\mathcal C}$. Let $BC_{2l+1}(n)$ denote the graph obtained by taking $2l+1$ vertex-disjoint copies of $K_{\frac{n}{2(2l+1)},\frac{n}{2(2l+1)}}$ and selecting a vertex in each of them such that these vertices form a cycle of length $2l+1$. Let $C_{2k+3}({n \over 2k+3})$ denote the balanced blow up of $C_{2k+3}$ with $n$ vertices. Note that both $BC_{2l+1}(n)$ and $C_{2k+3}({n \over 2k+3})$ are $n$-vertex ${\mathcal C}$-free non-bipartite graphs. We show that if $G$ is an $n$-vertex ${\mathcal C}$-free graph with $\delta(G)>\max\{ \frac{n}{2(2l+1)}, \frac{2}{2k+3}n\}$, then $G$ is bipartite. The bound is tight evident by $BC_{2l+1}(n)$ and $C_{2k+3}({n \over 2k+3})$. Moreover, the only $n$-vertex ${\mathcal C}$-free non-bipartite graph with minimum degree $\max\{ \frac{n}{2(2l+1)}, \frac{2}{2k+3}n\}=\frac{n}{2(2l+1)}$ is $BC_{2l+1}(n)$, and the the only $n$-vertex ${\mathcal C}$-free non-bipartite graph with minimum degree $\max\{ \frac{n}{2(2l+1)}, \frac{2}{2k+3}n\}=\frac{2}{2k+3}n$ is $C_{2k+3}({n \over 2k+3})$. Our result also unifies stability results of Andr\'{a}sfai, Erd\H{o}s and S\'{o}s, H\"{a}ggkvist and Yuan and Peng for large $n$.

Authors:Max Wakefield

Abstract: The Tutte polynomial and Derksen's $\mathcal{G}$-invariant are the universal deletion/contraction and valuative matroid and polymatroid invariants, respectively. There are only a handful of well known invariants (like the matroid Kazhdan-Lusztig polynomials) between (in terms of roughness/fineness) the Tutte polynomial and Derksen's $\mathcal{G}$-invariant. The aim of this study is to define a spectrum of generalized Tutte polynomials to fill the gap between the Tutte polynomial and Derksen's $\mathcal{G}$-invariant. These polynomials are built by taking repeated convolution products of universal Tutte characters studied by Dupont, Fink, and Moci and using the framework of Ardila and Sanchez for studying valuative invariants. We develop foundational aspects of these polynomials by showing they are valuative on generalized permutahedra and present a generalized deletion/contraction formula. We apply these results on chain Tutte polynomials to obtain new formulas for the M\"obius polynomial, the opposite characteristic polynomial, a generalized M\"obius polynomial, Ford's expected codimension of a matroid variety, and Derksen's $\mathcal{G}$-invariant.

Authors:Sean Mandrick, Vincent Vatter

Abstract: We investigate lettericity in graphs, in particular the question of the greatest lettericity of a graph on $n$ vertices. We show that all graphs on $n$ vertices have lettericity at most $n-(1/2)\log_2 n$ and that almost all graphs on $n$ vertices have lettericity at least $n-(2\log_2 n + 2\log_2\log_2 n)$.

Authors:Kevin Ivan Piterman

Abstract: For a symplectic space $V$ of dimension $2n$ over $\mathbb{F}_{q}$, we compute the eigenvalues of its orthogonality graph. This is the simple graph with vertices the $2$-dimensional non-degenerate subspaces of $V$ and edges between orthogonal vertices. As a consequence of Garland's method, we obtain vanishing results on the homology groups of the frame complex of $V$, which is the clique complex of this graph. We conclude that if $n < q+3$ then the poset of frames of size $\neq 0,n-1$, which is homotopy equivalent to the frame complex, is Cohen-Macaulay over a field of characteristic $0$. However, we also show that this poset is not Cohen-Macaulay if the dimension is big enough.

Authors:Tahir Shamsher, Mir Riyaz ul Rashid, S. Pirzada

Abstract: A signed graph $S=(G, \sigma)$ is a pair in which $G$ is an underlying graph and $\sigma$ is a function from the edge set to $\{\pm1\}$. For signed graphs $S_{1}$ and $S_{2}$ on $n_{1}$ and $n_{2}$ vertices, respectively, the signed neighbourhood corona $S_{1} \star_s S_{2}$ (in short s-neighbourhood corona) of $S_{1}$ and $S_{2}$ is the signed graph obtained by taking one copy of $S_{1}$ and $n_{1}$ copies of $S_{2}$ and joining every neighbour of the $i$th vertex of $S_{1}$ with the same sign as the sign of incident edge to every vertex in the $i$th copy of $S_{2}$. In this paper, we investigate the adjacency, Laplacian and net Laplacian spectrum of $S_{1} \star_s S_{2}$ in terms of the corresponding spectrum of $ S_{1}$ and $ S_{2}$. We determine $(i)$ the adjacency spectrum of $S_{1} \star_s S_{2}$ for arbitrary $S_{1} $ and net regular $ S_{2}$, $(ii)$ the Laplacian spectrum for regular $S_{1} $ and regular and net regular $ S_{2}$ and $(iii)$ the net Laplacian spectrum for net regular $S_{1} $ and arbitrary $ S_{2}$. As a consequence, we obtain the signed graphs with $4$ and $5$ distinct adjacency, Laplacian and net Laplacian eigenvalues. Finally, we show that the signed neighbourhood corona of two signed graphs is not determined by its adjacency (resp., Laplacian, net Laplacian) spectrum.

Authors:Anupam Mondal, Sajal Mukherjee, Kuldeep Saha

Abstract: We denote the matching complex of the complete graph of order $n$ by $M_n$. The topology of $M_n$ is an interesting topic in combinatorial topology and discrete geometry. Bouc initiated the homotopical study of $M_n$. A key step was Bouc's homology computation for the first non-trivial $M_n$, viz., $M_7$, by hand. In the present article, we look into the topology of $M_7$ in the light of discrete Morse theory as developed by Forman. Discrete Morse theory gives a combinatorial generalization of the classical notion of a smooth gradient vector field, called (discrete) gradient vector field on a simplicial complex. Similar to the smooth case, the critical simplices with respect to a gradient vector field captures the topology of the complex. We apply discrete Morse theoretic techniques to present an algorithmic computation of the Morse homology groups of $M_7$ by constructing an efficient (near-optimal) gradient vector field on $M_7$. Moreover, we augment this near-optimal gradient vector field to an optimal one (i.e., one with the least number of critical simplices). To our knowledge, this is the first example of an optimal gradient vector field on $M_7$.

Authors:Johannes Lengler, Anders Martinsson, Kalina Petrova, Patrick Schnider, Raphael Steiner, Simon Weber, Emo Welzl

Abstract: For any positive edge density $p$, a random graph in the Erd\H{o}s-Renyi $G_{n,p}$ model is connected with non-zero probability, since all edges are mutually independent. We consider random graph models in which edges that do not share endpoints are independent while incident edges may be dependent and ask: what is the minimum probability $\rho(n)$, such that for any distribution $\mathcal{G}$ (in this model) on graphs with $n$ vertices in which each potential edge has a marginal probability of being present at least $\rho(n)$, a graph drawn from $\mathcal{G}$ is connected with non-zero probability? As it turns out, the condition ``edges that do not share endpoints are independent" needs to be clarified and the answer to the question above is sensitive to the specification. In fact, we formalize this intuitive description into a strict hierarchy of five independence conditions, which we show to have at least three different behaviors for the threshold $\rho(n)$. For each condition, we provide upper and lower bounds for $\rho(n)$. In the strongest condition, the coloring model (which includes, e.g., random geometric graphs), we prove that $\rho(n)\rightarrow 2-\phi\approx 0.38$ for $n\rightarrow\infty$. This separates it from the weaker independence conditions we consider, as there we prove that $\rho(n)>0.5-o(n)$. In stark contrast to the coloring model, for our weakest independence condition -- pairwise independence of non-adjacent edges -- we show that $\rho(n)$ lies within $O(1/n^2)$ of the threshold for completely arbitrary distributions ($1-2/n$).

Authors:Christian Ikenmeyer, Greta Panova

Abstract: We settle the question of where exactly the reduced Kronecker coefficients lie on the spectrum between the Littlewood-Richardson and Kronecker coefficients by showing that every Kronecker coefficient of the symmetric group is equal to a reduced Kronecker coefficient by an explicit construction. This implies the equivalence of a question by Stanley from 2000 and a question by Kirillov from 2004 about combinatorial interpretations of these two families of coefficients. Moreover, as a corollary, we deduce that deciding the positivity of reduced Kronecker coefficients is $NP$-hard, and computing them is $\#P$-hard under parsimonious many-one reductions.

Authors:Davi Castro-Silva

Abstract: We study the interplay between notions of quasirandomness for additive sets and for hypergraphs. In particular, we show a strong connection between the notions of Gowers uniformity in the additive setting and discrepancy-type measures of quasirandomness in the hypergraph setting. Exploiting this connection, we provide a long list of disparate quasirandom properties regarding both additive sets and Cayley-type hypergraphs constructed from such sets, and show that these properties are all equivalent (in the sense of Chung, Graham and Wilson) with polynomial bounds on their interdependences.

Authors:Jin Sun

Abstract: The Ramsey's theorem says that a graph with sufficiently many vertices contains a clique or stable set with many vertices. Now we attach some parameter to every vertex, such as degree. Consider the case a graph with sufficiently many vertices of large degree, we can get the realted Ramsey-type result. The Ramsey's theorem of connected version says that every connected graph with sufficiently many vertices contains an induced path, clique or star with many vertices. Now we require the vertex is non-trivial, i.e. the parameter of this vertex is non-trivial, such as $\operatorname{deg}(v)\not =1$. A connected graph with sufficiently many non-trivial vertices must contain some special induced subgraph. We also get the non-connected version of this Ramsey-type result as a corollary.

Authors:Balázs Patkós, Zsolt Tuza, Máté Vizer

Abstract: A $q$-graph $H$ on $n$ vertices is a set of vectors of length $n$ with all entries from $\{0,1,\dots,q\}$ and every vector (that we call a $q$-edge) having exactly two non-zero entries. The support of a $q$-edge $\mathbf{x}$ is the pair $S_{\mathbf{x}}$ of indices of non-zero entries. We say that $H$ is an $s$-copy of an ordinary graph $F$ if $|H|=|E(F)|$, $F$ is isomorphic to the graph with edge set $\{S_{\mathbf{x}}:\mathbf{x}\in H\}$, and whenever $v\in e,e'\in E(F)$, the entries with index corresponding to $v$ in the $q$-edges corresponding to $e$ and $e'$ sum up to at least $s$. E.g., the $q$-edges $(1,3,0,0,0), (0,1,0,0,3)$, and $(3,0,0,0,1)$ form a 4-triangle. The Tur\'an number $\mathrm{ex}(n,F,q,s)$ is the maximum number of $q$-edges that a $q$-graph $H$ on $n$ vertices can have if it does not contain any $s$-copies of $F$. In the present paper, we determine the asymptotics of $\mathrm{ex}(n,F,q,q+1)$ for many graphs $F$.

Authors:Gábot Bacsó, Balázs Patkós, Zsolt Tuza, Máté Vizer

Abstract: A 1-removed subgraph $G_f$ of a graph $G=(V,E)$ is obtained by $(i)$ selecting at most one edge $f(v)$ for each vertex $v\in V$, such that $v\in f(v)\in E$ (the mapping $f:V\to E \cup \{\varnothing\}$ is allowed to be non-injective), and $(ii)$ deleting all the selected edges $f(v)$ from the edge set $E$ of $G$. Proper vertex colorings of 1-removed subgraphs proved to be a useful tool for earlier research on some Tur\'an-type problems. In this paper, we introduce a systematic investigation of the graph invariant 1-robust chromatic number, denoted as $\omega_1(G)$. This invariant is defined as the minimum chromatic number $\chi(G_f)$ among all 1-removed subgraphs $G_f$ of $G$. We also examine other standard graph invariants in a similar manner.

Authors:Gábor Bacsó, Csilla Bujtás, Balázs Patkós, Zsolt Tuza, Máté Vizer

Abstract: A 1-selection $f$ of a graph $G$ is a function $f: V(G)\rightarrow E(G)$ such that $f(v)$ is incident to $v$ for every vertex $v$. The 1-removed $G_f$ is the graph $(V(G),E(G)\setminus f[V(G)])$. The (1-)robust chromatic number $\chi_1(G)$ is the minimum of $\chi(G_f)$ over all 1-selections $f$ of $G$. We determine the robust chromatic number of complete multipartite graphs and Kneser graphs and prove tight lower and upper bounds on the robust chromatic number of chordal graphs and some of their extensively studied subclasses, with respect to their ordinary chromatic number.

Authors:Nevil Anto, Manu Basavaraju, Suresh Manjanath Hegde, Shashanka Kulamarva

Abstract: An acyclic edge coloring of a graph is a proper edge coloring without any bichromatic cycles. The acyclic chromatic index of a graph $G$ denoted by $a'(G)$, is the minimum $k$ such that $G$ has an acyclic edge coloring with $k$ colors. Fiam\v{c}\'{\i}k conjectured that $a'(G) \le \Delta+2$ for any graph $G$ with maximum degree $\Delta$. A graph $G$ is said to be $k$-degenerate if every subgraph of $G$ has a vertex of degree at most $k$. Basavaraju and Chandran proved that the conjecture is true for $2$-degenerate graphs. We prove that for a $3$-degenerate graph $G$, $a'(G) \le \Delta+5$, thereby bringing the upper bound closer to the conjectured bound. We also consider $k$-degenerate graphs with $k \ge 4$ and give an upper bound for the acyclic chromatic index of the same.

Authors:Jan Goedgebeur, Edita Máčajová, Jarne Renders

Abstract: An edge $e$ of a graph $G$ is called deletable for some orientation $o$ if the restriction of $o$ to $G-e$ is a strong orientation. In 2021, H\"orsch and Szigeti proposed a new parameter for $3$-edge-connected graphs, called the Frank number, which refines $k$-edge-connectivity. The Frank number is defined as the minimum number of orientations of $G$ for which every edge of $G$ is deletable in at least one of them. They showed that every $3$-edge-connected graph has Frank number at most $7$ and that in case these graphs are also $3$-edge-colourable graphs the parameter is at most $3$. Here we strengthen the latter result by showing that such graphs have Frank number $2$, which also confirms a conjecture by Bar\'at and Bl\'aszik. Furthermore, we prove two sufficient conditions for cubic graphs to have Frank number $2$ and use them in an algorithm to computationally show that the Petersen graph is the only cyclically $4$-edge-connected cubic graph up to $36$ vertices having Frank number greater than $2$.

Authors:Zhen Chen, Jianfeng Wang, Maurizio Brunetti, Francesco Belardo

Abstract: A graph $G$ is divisible by a graph $H$ if the characteristic polynomial of $G$ is divisible by that of $H$. In this paper, a necessary and sufficient condition for recursive graphs to be divisible by a path is used to show that the H-shape graph $P_{2,2;n-4}^{2,n-7}$, known to be (for $n$ large enough) the minimizer of the spectral radius among the graphs of order $n$ and diameter $n-5$, is determined by its adjacency spectrum if and only if $n \neq 10,13,15$.

Authors:Geoffroy Caillat-Grenier

Abstract: In this paper we discuss potentially practical ways to produce expander graphs with good spectral properties and a compact description. We focus on several classes of uniform and bipartite expander graphs defined as random Schreier graphs of the general linear group over the finite field of size two. We perform numerical experiments and show that such constructions produce spectral expanders that can be useful for practical applications. To find a theoretical explanation of the observed experimental results, we used the method of moments to prove upper bounds for the expected second largest eigenvalue of the random Schreier graphs used in our constructions. We focus on bounds for which it is difficult to study the asymptotic behaviour but it is possible to compute non-trivial conclusions for relatively small graphs with parameters from our numerical experiments (e.g., with less than 2^200 vertices and degree at least logarithmic in the number of vertices).

Authors:Niklas Christoph Affolter

Abstract: In this PhD thesis we develop the frame work of triple crossing diagram maps (TCD maps), which describes constrained configurations of points in projective spaces and discrete dynamics on these configurations. We are able to capture the constraints and dynamics of a large list of examples that occur in discrete differential geometry (DDG), discrete integrable systems and exactly solvable models. We explain how to apply various geometric operations to TCD maps, including projections, intersections with hyperplanes and projective dualization. In fact, we show how many examples in the literature are related by the aforementioned operations. Moreover, we introduce a hierarchy of cluster structures on TCD maps, thus answering the open question how objects of DDG relate to cluster structures. At the same time, the general cluster structure reproduces cluster structures known for the pentagram map, T-graphs and t-embeddings. We also explain how the cluster structures behave under geometric operations. Via the cluster structures, the TCD maps are also related to the probabilistic dimer model. The spanning tree model and the Ising model can be obtained as special cases of the dimer model, and we investigate how these special cases relate to geometry. This also leads to two new incidence theorems in relation to quadrics and null-polarities in $\mathbb C \mathrm P^3$. Finally, we also show how TCD maps relate to the Fock-Goncharov moduli spaces of projective flag configurations.

Authors:Cesar Ceballos, Clément Chenevière

Abstract: Given a lattice path $\nu$, the $\nu$-Tamari lattice and the $\nu$-Dyck lattice are two natural examples of partial order structures on the set of lattice paths that lie weakly above $\nu$. In this paper, we introduce a more general family of lattices, called alt $\nu$-Tamari lattices, which contains these two examples as particular cases. Unexpectedly, we show that all these lattices have the same number of linear intervals.

Authors:Hao Lin, Guanghui Wang, Wenling Zhou

Abstract: A $k$-graph (or $k$-uniform hypergraph) $H$ is uniformly dense if the edge distribution of $H$ is uniformly dense with respect to every large collection of $k$-vertex cliques induced by sets of $(k-2)$-tuples. Reiher, R\"odl and Schacht [Int. Math. Res. Not., 2018] proposed the study of the uniform Tur\'an density $\pi_{k-2}(F)$ for given $k$-graphs $F$ in uniformly dense $k$-graphs. Meanwhile, they [J. London Math. Soc., 2018] characterized $k$-graphs $F$ satisfying $\pi_{k-2}(F)=0$ and showed that $\pi_{k-2}(\cdot)$ ``jumps" from 0 to at least $k^{-k}$. In particular, they asked whether there exist $3$-graphs $F$ with $\pi_{1}(F)$ equal or arbitrarily close to $1/27$. Recently, Garbe, Kr\'al' and Lamaison [arXiv:2105.09883] constructed some $3$-graphs with $\pi_{1}(F)=1/27$. In this paper, for any $k$-graph $F$, we give a lower bound of $\pi_{k-2}(F)$ based on a probabilistic framework, and provide a general theorem that reduces proving an upper bound on $\pi_{k-2}(F)$ to embedding $F$ in reduced $k$-graphs of the same density using the regularity method for $k$-graphs. By using this result and Ramsey theorem for multicolored hypergraphs, we extend the results of Garbe, Kr\'al' and Lamaison to $k\ge 3$. In other words, we give a sufficient condition for $k$-graphs $F$ satisfying $\pi_{k-2}(F)=k^{-k}$. Additionally, we also construct an infinite family of $k$-graphs with $\pi_{k-2}(F)=k^{-k}$.

Authors:Balázs Patkós, Zsolt Tuza, Máté Vizer

Abstract: We introduce the following generalization of set intersection via characteristic vectors: for $n,q,s, t \ge 1$ a family $\mathcal{F}\subseteq \{0,1,\dots,q\}^n$ of vectors is said to be \emph{$s$-sum $t$-intersecting} if for any distinct $\mathbf{x},\mathbf{y}\in \mathcal{F}$ there exist at least $t$ coordinates, where the entries of $\mathbf{x}$ and $\mathbf{y}$ sum up to at least $s$, i.e.\ $|\{i:x_i+y_i\ge s\}|\ge t$. The original set intersection corresponds to the case $q=1,s=2$. We address analogs of several variants of classical results in this setting: the Erd\H{o}s--Ko--Rado theorem and the theorem of Bollob\'as on intersecting set pairs.

Authors:Fabienne Chouraqui

Abstract: Given two linear transformations, with representing matrices $A$ and $B$ with respect to some bases, it is not clear, in general, whether the Tracy-Singh product of the matrices $A$ and $B$ corresponds to a particular operation on the linear transformations. Nevertheless, it is not hard to show that in the particular case that each matrix is a square matrix of order of the form $n^2$, $n>1$, and is partitioned into $n^2$ square blocks of order $n$, then their Tracy-Singh product, $A \boxtimes B$, is similar to $A \otimes B$, and the change of basis matrix is a permutation matrix. In this note, we prove that in the special case of linear operators induced from set-theoretic solutions of the Yang-Baxter equation, the Tracy-Singh product of their representing matrices is the representing matrix of the linear operator obtained from the direct product of the set-theoretic solutions.

Authors:John Bamberg, Jesse Lansdown, Geertrui Van de Voorde

Abstract: It is known that a Bruen chain of the three-dimensional projective space $\mathrm{PG}(3,q)$ exists for every odd prime power $q$ at most $37$, except for $q=29$. It was shown by Cardinali et. al (2005) that Bruen chains do not exist for $41\le q\leq 49$. We develop a model, based on finite fields, which allows us to extend this result to $41\leqslant q \leqslant 97$, thereby adding more evidence to the conjecture that Bruen chains do not exist for $q>37$. Furthermore, we show that Bruen chains can be realised precisely as the $(q+1)/2$-cliques of a two related, yet distinct, undirected simple graphs.

Authors:Dimitri Leemans, Micael Toledo

Abstract: Maniplexes are coloured graphs that generalise maps on surfaces and abstract polytopes. Each maniplex uniquely defines a partially ordered set that encodes information about its structure. When this poset is an abstract polytope, we say that the associated maniplex is polytopal. Maniplexes that have two properties, called faithfulness and thinness, are completely determined by their associated poset, which is often an abstract polytope. We show that all faithful thin maniplexes of rank three are polytopal. So far only one example, of rank four, of a thin maniplex that is not polytopal was known. We construct the first infinite family of maniplexes that are faithful and thin but are non-polytopal for all ranks greater than three.

Authors:Pierre Hoppenot, Zoltán Szigeti

Abstract: We show that if the arc-connectivity of a directed graph $D$ is at most $\lfloor\frac{k+1}{2}\rfloor$ and the reorientation of an arc set $F$ in $D$ results in a $k$-arc-connected directed graph then we can reorient one arc of $F$ without decreasing the arc-connectivity of $D.$ This improves a result of Fukuda, Prodon, Sakuma and one of Ito et al. for $k\in\{2,3\}$.

Authors:O-joung Kwon, Xiaopan Lian

Abstract: We introduce the vertex-arboricity of group-labelled graphs. For an abelian group $\Gamma$, a $\Gamma$-labelled graph is a graph whose edges are labelled by elements of $\Gamma$. For an abelian group $\Gamma$ and $A\subseteq \Gamma$, the $(\Gamma, A)$-vertex-arboricity of a $\Gamma$-labelled graph is the minimum integer $k$ such that its vertex set can be partitioned into $k$ parts where each part induces a subgraph having no cycle of value in $A$. We prove that for every positive integer $\omega$, there is a function $f_{\omega}:\mathbb{N}\times\mathbb{N}\to \mathbb{R}$ such that if $|\Gamma\setminus A|\le \omega$, then every $\Gamma$-labelled graph with $(\Gamma, A)$-vertex-arboricity at least $f_{\omega}(t,d)$ contains a subdivision of $K_t$ where all branching paths are of value in $A$ and of length at least $d$. This extends a well-known result that every graph of sufficiently large chromatic number contains a subdivision of $K_t$, in various directions.

Authors:Maria Axenovich, Domagoj Bradač, Lior Gishboliner, Dhruv Mubayi, Lea Weber

Abstract: The well-known Erd\H{o}s-Hajnal conjecture states that for any graph $F$, there exists $\epsilon>0$ such that every $n$-vertex graph $G$ that contains no induced copy of $F$ has a homogeneous set of size at least $n^{\epsilon}$. We consider a variant of the Erd\H{o}s-Hajnal problem for hypergraphs where we forbid a family of hypergraphs described by their orders and sizes. For graphs, we observe that if we forbid induced subgraphs on $m$ vertices and $f$ edges for any positive $m$ and $0\leq f \leq \binom{m}{2}$, then we obtain large homogeneous sets. For triple systems, in the first nontrivial case $m=4$, for every $S \subseteq \{0,1,2,3,4\}$, we give bounds on the minimum size of a homogeneous set in a triple system where the number of edges spanned by every four vertices is not in $S$. In most cases the bounds are essentially tight. We also determine, for all $S$, whether the growth rate is polynomial or polylogarithmic. Some open problems remain.

Authors:Georg Grasegger, Jan Legerský

Abstract: A framework, which is a (possibly infinite) graph with a realization of its vertices in the plane, is called flexible if it can be continuously deformed while preserving the edge lengths. We focus on flexibility of frameworks in which 4-cycles form parallelograms. For the class of frameworks considered in this paper (allowing triangles), we prove that the following are equivalent: flexibility, infinitesimal flexibility, the existence of at least two classes of an equivalence relation based on 3- and 4-cycles and being a non-trivial subgraph of the Cartesian product of graphs. We study the algorithmic aspects and the rotationally symmetric version of the problem. The results are illustrated on frameworks obtained from tessellations by regular polygons.

Authors:Dmitrii Taletskii

Abstract: We show that the number of independent sets in every outerplanar graph is greater than the number of its 4-dominating sets.

Authors:Hans L. Bodlaender, Matthew Johnson, Barnaby Martin, Jelle J. Oostveen, Sukanya Pandey, Daniel Paulusma, Siani Smith, Erik Jan van Leeuwen

Abstract: We study Steiner Forest on $H$-subgraph-free graphs, that is, graphs that do not contain some fixed graph $H$ as a (not necessarily induced) subgraph. We are motivated by a recent framework that completely characterizes the complexity of many problems on $H$-subgraph-free graphs. However, in contrast to e.g. the related Steiner Tree problem, Steiner Forest falls outside this framework. Hence, the complexity of Steiner Forest on $H$-subgraph-free graphs remained tantalizingly open. In this paper, we make significant progress towards determining the complexity of Steiner Forest on $H$-subgraph-free graphs. Our main results are four novel polynomial-time algorithms for different excluded graphs $H$ that are central to further understand its complexity. Along the way, we study the complexity of Steiner Forest for graphs with a small $c$-deletion set, that is, a small set $S$ of vertices such that each component of $G-S$ has size at most $c$. Using this parameter, we give two noteworthy algorithms that we later employ as subroutines. First, we prove Steiner Forest is FPT parameterized by $|S|$ when $c=1$ (i.e. the vertex cover number). Second, we prove Steiner Forest is polynomial-time solvable for graphs with a 2-deletion set of size at most 2. The latter result is tight, as the problem is NP-complete for graphs with a 3-deletion set of size 2.

Authors:Eiichi Bannai, Hirotake Kurihara, Da Zhao, Yan Zhu

Abstract: The classification problem of $P$- and $Q$-polynomial association schemes has been one of the central problems in algebraic combinatorics. Generalizing the concept of $P$- and $Q$-polynomial association schemes to multivariate cases, namely to consider higher rank $P$- and $Q$-polynomial association schemes, has been tried by some authors, but it seems that so far there were neither very well-established definition nor results. Very recently, Bernard, Cramp\'{e}, d'Andecy, Vinet, and Zaimi [arXiv:2212.10824], defined bivariate $P$-polynomial association schemes, as well as bivariate $Q$-polynomial association schemes. In this paper, we study these concepts and propose a new modified definition concerning a general monomial order, which is more general and more natural and also easy to handle. We prove that there are many interesting families of examples of multivariate $P$- and/or $Q$-polynomial association schemes.

Authors:Anurag Bishnoi, Simona Boyadzhiyska, Shagnik Das, Yvonne den Bakker

Abstract: Given a finite grid in $\mathbb{R}^2$, how many lines are needed to cover all but one point at least $k$ times? Problems of this nature have been studied for decades, with a general lower bound having been established by Ball and Serra. We solve this problem for various types of grids, in particular showing the tightness of the Ball--Serra bound when one side is much larger than the other. In other cases, we prove new lower bounds that improve upon Ball--Serra and provide an asymptotic answer for almost all grids. For the standard grid $\{0,\ldots,n-1\} \times \{0,\ldots,n-1\}$, we prove nontrivial upper and lower bounds on the number of lines needed. To prove our results, we combine linear programming duality with some combinatorial arguments.

Authors:Alan Frieze, Wesley Pegden

Abstract: We discuss the existence of Hamilton cycles in the random graph $G_{n,p}$ where there are restrictions caused by (i) coloring sequences, (ii) a subset of vertices must occur in a specific order and (iii) there is a bound on the number of inversions in the associated permutation.

Authors:Alexandre Rok, Andras Szenes

Abstract: We give a short proof of the chromatic e-positivity conjecture of Stanley for length-2 partitions.

Authors:Reza Rastegar

Abstract: We derive linear recurrences for avoiding non-overlapping consecutive patterns in both permutations and words and identify a necessary condition for establishing c-Wilf-equivalence between two non-overlapping patterns. Furthermore, we offer alternative, elementary proofs for several known results in consecutive pattern containment that were previously demonstrated using ideas from cluster algebra and analytical combinatorics. Lastly, we establish new general bounds on the growth rates of consecutive pattern avoidance in permutations.

Authors:Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Shun-ichi Maezawa, Yuta Nozaki, Yoshio Okamoto

Abstract: We prove that the computation of a combinatorial shortest path between two vertices of a graph associahedron, introduced by Carr and Devadoss, is NP-hard. This resolves an open problem raised by Cardinal. A graph associahedron is a generalization of the well-known associahedron. The associahedron is obtained as the graph associahedron of a path. It is a tantalizing and important open problem in theoretical computer science whether the computation of a combinatorial shortest path between two vertices of the associahedron can be done in polynomial time, which is identical to the computation of the flip distance between two triangulations of a convex polygon, and the rotation distance between two rooted binary trees. Our result shows that a certain generalized approach to tackling this open problem is not promising. As a corollary of our theorem, we prove that the computation of a combinatorial shortest path between two vertices of a polymatroid base polytope cannot be done in polynomial time unless P = NP. Since a combinatorial shortest path on the matroid base polytope can be computed in polynomial time, our result reveals an unexpected contrast between matroids and polymatroids.

Authors:Moritz Mühlenthaler, Benjamin Peyrille, Zoltán Szigeti

Abstract: The orientation theorem of Nash-Williams states that an undirected graph admits a $k$-arc-connected orientation if and only if it is $2k$-edge-connected. Recently, Ito et al. showed that any orientation of an undirected $2k$-edge-connected graph can be transformed into a $k$-arc-connected orientation by reorienting one arc at a time without decreasing the arc-connectivity at any step, thus providing an algorithmic proof of Nash-Williams' theorem. We generalize their result to hypergraphs and therefore provide an algorithmic proof of the characterization of hypergraphs with a $k$-hyperarc-connected orientation originally given by Frank et al. We prove that any orientation of an undirected $(k,k)$-partition-connected hypergraph can be transformed into a $k$-hyperarc-connected orientation by reorienting one hyperarc at a time without decreasing the hyperarc-connectivity in any step. Furthermore, we provide a simple combinatorial algorithm for computing such a transformation in polynomial time.

Authors:Dhruv Mubayi, Liana Yepremyan

Abstract: Given two $r$-uniform hypergraphs $G$ and $H$ the Tur\'an number $\rm{ex}(G, H)$ is the maximum number of edges in an $H$-free subgraph of $G$. We study the typical value of $\rm{ex}(G, H)$ when $G=G_{n,p}^{(r)}$, the Erd\H{o}s-R\'enyi random $r$-uniform hypergraph, and $H=C_{2\ell}^{(r)}$, the $r$-uniform linear cycle of length $2\ell$. The case of graphs ($r=2$) is a longstanding open problem that has been investigated by many researchers. We determine the order of magnitude of $\rm{ex}\left(G_{n,p}^{(r)}, C_{2\ell}^{(r)}\right)$ for all $r\geq 4$ and all $\ell\geq 2$ up to polylogarithmic factors for all values of $p=p(n)$. Our proof is based on the container method and uses a balanced supersaturation result for linear even cycles which improves upon previous such results by Ferber-Mckinley-Samotij and Balogh-Narayanan-Skokan.

Authors:Amritanshu Prasad, Samrith Ram

Abstract: We express the number of anti-invariant subspaces for a linear operator on a finite vector space in terms of the number of its invariant subspaces. When the operator is diagonalizable with distinct eigenvalues, our formula gives a finite-field interpretation for the entries of the $q$-Hermite Catalan matrix. We also obtain an interesting new proof of Touchard's formula for these entries.

Authors:Aniruddha Biswas, Palash Sarkar

Abstract: For $n\leq 6$, we provide the number of $n$-variable unate and monotone Boolean functions under various restrictions. Additionally, we provide the number of balanced 7-variable monotone Boolean functions.

Authors:Aaron Berger, Nitya Mani

Abstract: We study the following natural arithmetic question regarding intersecting families: how large can a family of subsets of integers from $\{1, \ldots n\}$ be such that, for every pair of subsets in the family, the intersection contains a sum $x + y = z$? We conjecture that any such sum-intersecting family must have size at most $\frac14 \cdot 2^{n}$ (which would be tight if correct). Towards this conjecture, we show that every sum-intersecting family has at most $0.32 \cdot 2^n$ subsets.

Authors:Yuping Gao, Songling Shan, Gexin Yu

Abstract: The study of existence of hamiltonian cycles and factors in graphs in terms of toughness was initiated by Chv\'atal in 1973 and has been a popular topic since then. The study of Berge cycles and factor in hypergraphs has attracted quite a bit attention in recent years and much progress has been made in terms of conditions such as degrees. In this article, we propose to study toughness conditions for a hypergraph to have a Berge $k$-factor. Our main result is that every $k$-tough hypergraph $H$ has a Berge $k$-factor if $k\cdot |V(H)|$ is even and $|V(H)|\ge k+1$ for integer $k\ge 1$. This extends a similar result on graphs from 1985 by Enomoto, Jackson, Keterinis, and Saito.

Authors:Davide Mattiolo, Giuseppe Mazzuoccolo, Jozef Rajník, Gloria Tabarelli

Abstract: A $d$-dimensional nowhere-zero $r$-flow on a graph $G$, an $(r,d)$-NZF from now on, is a flow where the value on each edge is an element of $\mathbb{R}^d$ whose (Euclidean) norm lies in the interval $[1,r-1]$. Such a notion is a natural generalization of the well-known concept of circular nowhere-zero $r$-flow (i.e.\ $d=1$). For every bridgeless graph $G$, the $5$-flow Conjecture claims that $\phi_1(G)\leq 5$, while a conjecture by Jain suggests that $\phi_d(G)=1$, for all $d \geq 3$. Here, we address the problem of finding a possible upper-bound also for the remaining case $d=2$. We show that, for all bridgeless graphs, $\phi_2(G) \le 1 + \sqrt{5}$ and that the oriented $5$-cycle double cover Conjecture implies $\phi_2(G)\leq \tau^2$, where $\tau$ is the Golden Ratio. Moreover, we propose a geometric method to describe an $(r,2)$-NZF of a cubic graph in a compact way, and we apply it in some instances. Our results and some computational evidence suggest that $\tau^2$ could be a promising upper bound for the parameter $\phi_2(G)$ for an arbitrary bridgeless graph $G$. We leave that as a relevant open problem which represents an analogous of the $5$-flow Conjecture in the $2$-dimensional case (i.e. complex case).

Authors:Marie-Charlotte Brandenburg, Jesús A. De Loera, Chiara Meroni

Abstract: We study the structure of the set of all possible affine hyperplane sections of a convex polytope. We present two different cell decompositions of this set, induced by hyperplane arrangements. Using our decomposition, we bound the number of possible combinatorial types of sections and craft algorithms that compute optimal sections of the polytope according to various combinatorial and metric criteria, including sections that maximize the number of $k$-dimensional faces, maximize the volume, and maximize the integral of a polynomial. Our optimization algorithms run in polynomial time in fixed dimension, but the same problems show hardness otherwise. Our tools can be extended to intersection with halfspaces and projections onto hyperplanes. Finally, we present several experiments illustrating our theorems and algorithms on famous polytopes.

Authors:Agelos Georgakopoulos, Alex Wendland

Abstract: We prove that every recurrent graph $G$ quasi-isometric to $\mathbb{R}$ admits an essentially unique Lipschitz harmonic function $h$. If $G$ is vertex-transitive, then the action of $Aut(G)$ preserves $\partial h$ up to a sign, a fact that we exploit to prove various combinatorial results about $G$. As a consequence, we prove the 2-ended case of the conjecture of Grimmett & Li that the connective constant of a non-degenerate vertex-transitive graph is at least the golden mean. Moreover, answering a question of Watkins from 1990, we construct a cubic, 2-ended, vertex-transitive graph which is not a Cayley graph.

Authors:Guoce Xin, Yingrui Zhang, ZiHao Zhang

Abstract: The Todd polynomials $td_k=td_k(b_1,b_2,\dots,b_m)$ are defined by their generating functions $$\sum_{k\ge 0} td_k s^k = \prod_{i=1}^m \frac{b_i s}{e^{b_i s}-1}.$$ It appears as a basic block in Todd class of a toric variety, which is important in the theory of lattice polytopes and in number theory. We find generalized Todd polynomials arise naturally in MacMahon's partition analysis, especially in Erhart series computation.We give fast evaluation of generalized Todd polynomials for numerical $b_i$'s. In order to do so, we develop fast operations in the quotient ring $\mathbb{Z}_p[[x]]$ modulo $s^d$ for large prime $p$. As applications, i) we recompute the Ehrhart series of magic squares of order 6, which was first solved by the first named author. The running time is reduced from 70 days to about 1 day; ii) we give a polynomial time algorithm for Integer Linear Programming when the dimension is fixed, with a good performance.

Authors:Norihide Tokushige

Abstract: Let $\mathcal G$ be a family of subsets of an $n$-element set. The family $\mathcal G$ is called $3$-wise $t$-intersecting if the intersection of any three subsets in $\mathcal G$ is of size at least $t$. For a real number $p\in(0,1)$ we define the measure of the family by the sum of $p^{|G|}(1-p)^{n-|G|}$ over all $G\in\mathcal G$. For example, if $\mathcal G$ consists of all subsets containing a fixed $t$-element set, then it is a $3$-wise $t$-intersecting family with the measure $p^t$. For a given $\delta>0$, by choosing $t$ sufficiently large, the following holds for all $p$ with $0<p\leq 2/(\sqrt{4t+9}-1)$. If $\mathcal G$ is a $3$-wise $t$-intersecting family with the measure at least $(\frac12+\delta)p^t$, then $\mathcal G$ satisfies one of (i) and (ii): (i) every subset in $\mathcal G$ contains a fixed $t$-element set, (ii) every subset in $\mathcal G$ contains at least $t+2$ elements from a fixed $(t+3)$-element set.

Authors:Margaret Bayer, Mark Denker, Marija Jelić Milutinović, Rowan Rowlands, Sheila Sundaram, Lei Xue

Abstract: We define the $k$-cut complex of a graph $G$ with vertex set $V(G)$ to be the simplicial complex whose facets are the complements of sets of size $k$ in $V(G)$ inducing disconnected subgraphs of $G$. This generalizes the Alexander dual of a graph complex studied by Fr\"oberg (1990), and Eagon and Reiner (1998). We describe the effect of various graph operations on the cut complex, and study its shellability, homotopy type and homology for various families of graphs, including trees, cycles, complete multipartite graphs, and the prism $K_n \times K_2$, using techniques from algebraic topology, discrete Morse theory and equivariant poset topology.

Authors:Nimisha Pahuja

Abstract: Ayyer and Linusson studied correlations in the multispecies TASEP on a ring (Trans AMS, 2017) using a combinatorial analysis of the multiline queues construction defined by Ferrari and Martin (AOP, 2008). It is natural to explore whether an analogous application of appropriate multiline queues could give similar results for the partially asymmetric case. In this paper, we solve this problem of correlations of adjacent particles on the first two sites in the multispecies PASEP on a finite ring. We use the multiline processes defined by Martin (EJP, 2020), the dynamics of which also depend on the asymmetry parameter $q$, to compute the correlations.

Authors:Tamás Róbert Mezei

Abstract: We solve the $r$-star covering problem in simple orthogonal polygons, also known as the point guard problem in simple orthogonal polygons with rectangular vision, in quadratic time.

Authors:Sergey Norin, Jérémie Turcotte

Abstract: Motivated by Hadwiger's conjecture, Seymour asked which graphs $H$ have the property that every non-null graph $G$ with no $H$ minor has a vertex of degree at most $|V(H)|-2$. We show that for every monotone graph family $\mathcal{F}$ with strongly sublinear separators, all sufficiently large bipartite graphs $H \in \mathcal{F}$ with bounded maximum degree have this property. None of the conditions that $H$ belongs to $\mathcal{F}$, that $H$ is bipartite and that $H$ has bounded maximum degree can be omitted.

Authors:Alen Vegi Kalamar Department of Mathematics and Computer Science, University of Maribor, Maribor, Slovenia Comtrade Gaming, Maribor, Slovenia

Abstract: In this paper we extend counting of traversing Hamiltonian cycles from 2-tiled graphs to generalized tiled graphs. We further show that, for a fixed finite set of tiles, counting traversing Hamiltonian cycles can be done in linear time with respect to the size of such graph, implying counting Hamiltonian cycles in tiled graphs is fixed-parameter tractable.

Authors:Eckhard Steffen, Isaak H. Wolf

Abstract: We study rotation $r$-graphs and show that for every $r$-graph $G$ of odd regularity there is a simple rotation $r$-graph $G'$ such that $G$ can be obtained form $G'$ by a finite number of $2$-cut reductions. As a consequence, some hard conjectures as the (generalized) Berge-Fulkerson Conjecture and Tutte's 3- and 5-flow conjecture can be reduced to rotation $r$-graphs.

Authors:Alexandru Chirvasitu, Thomas W. Cusick

Abstract: Let $(0, a_1, \ldots, a_{d-1})_n$ denote the function $f_n(x_0, x_1, \ldots, x_{n-1})$ of degree $d$ in $n$ variables generated by the monomial $x_0x_{a_1} \cdots x_{a_{d-1}}$ and having the property that $f_n$ is invariant under cyclic permutations of the variables. Such a function $f_n$ is called monomial rotation symmetric (MRS). Much of this paper extends the work on quadratic MRS functions in a $2020$ paper of the authors to the case of binomial RS functions, that is sums of two quadratic MRS functions. There are also some results for the sum of any number of quadratic MRS functions.

Authors:Aida Abiad, Carme Alvarez, Arnau Messegué

Abstract: A graph $G$ of order $n$ is said to be a sum basic equilibrium if and only if for every edge $uv$ from $G$ and any node $v'$ from $G$, when performing the swap of the edge $uv$ for the edge $uv'$, the sum of the distances from $u$ to all the other nodes is not strictly reduced. This concept lies in the heart of the so-called network creation games, where the central problem is to understand the structure of the resulting equilibrium graphs, and in particular, how well they globally minimize the diameter. It was shown in [Alon, Demaine, Hajiaghayi, Leighton, SIAM J. Discrete Math. 27(2), 2013] that the diameter of sum basic equilibria is $2^{O(\sqrt{\log n})}$ in general, and at most $2$ for trees. In this paper we show that the upper bound of $2$ can be extended to bipartite graphs, and that it also holds for some nonbipartite classes like block graphs and cactus graphs.

Authors:Igor Grzelec, Monika Pilśniak, Mariusz Woźniak

Abstract: Let $C_{n_1}\cup C_{n_2}\cup \ldots \cup C_{n_k}$ be a 2-factor i.e. a vertex-disjoint union of cycles. In this note we completely characterize those 2-factors that are uniquely embeddeble in their complement.

Authors:Jeffrey Cheng, Ian Malcolm Johnson McInnis, Matthew Yee

Abstract: A weighted graph $\phi G$ encodes a finite metric space $D_{\phi G}$. When is $D$ totally decomposable? When does it embed in $\ell_1$ space? When does its representing matrix have $\leq 1$ positive eigenvalue? We give useful lemmata and prove that these questions can be answered without examining $\phi$ if and only if $G$ has no $K_{2,3}$ minor. We also prove results toward the following conjecture. $D_{\phi G}$ has $\leq n$ positive eigenvalues for all $\phi$, if and only if $G$ has no $K_{2,3,...,3}$ minor, with $n$ threes.

Authors:Jeffrey Cheng, Ian Malcolm Johnson McInnis, Matthew Yee

Abstract: We study the inertia of distance matrices of weighted graphs. Our novel congruence-based proof of the inertia of weighted trees extends to a proof for the inertia of weighted unicyclic graphs whose cycle is a triangle. Partial results are given on the inertia of other rationally weighted unicylic graphs.

Authors:Dániel Keliger, László Lovász, Tamás Móri, Gergely Ódor

Abstract: We study SIR type epidemics on graphs in two scenarios: (i) when the initial infections start from a well connected central region, (ii) when initial infections are distributed uniformly. Previously, \'Odor et al. demonstrated on a few random graph models that the expectation of the total number of infections undergoes a switchover phenomenon; the central region is more dangerous for small infection rates, while for large rates, the uniform seeding is expected to infect more nodes. We rigorously prove this claim under mild, deterministic assumptions on the underlying graph. If we further assume that the central region has a large enough expansion, the second moment of the degree distribution is bounded and the number of initial infections is comparable to the number of vertices, the difference between the two scenarios is shown to be macroscopic.

Authors:Tan Nhat Tran, Shuhei Tsujie

Abstract: The Shi arrangement due to Shi (1986) and the Ish arrangement due to Armstrong (2013) are deformations of the type $A$ Coxeter arrangement that share many common properties. Motivated by a question of Armstrong and Rhoades since 2012 to seek for Ish arrangements of other types, in this paper we introduce an Ish arrangement of type $B$. We study this Ish arrangement through various aspects similar to as known in type $A$ with a main emphasis on freeness and supersolvability. Our method is based on the concept of $\psi$-digraphic arrangements recently introduced due to Abe and the authors with a type $B$ extension.

Authors:Jing Lou, Ruifang Liu, Guoyan Ao

Abstract: A fractional matching of a graph $G$ is a function $f:E(G)\rightarrow [0, 1]$ such that for any $v\in V(G)$, $\sum_{e\in E_{G}(v)}f(e)\leq1$, where $E_{G}(v)=\{e\in E(G): e~ \mbox{is incident with} ~v~\mbox{in}~G\}$.The fractional matching number of $G$ is $\mu_{f}(G)=\mathrm{max}\{\sum_{e\in E(G)}f(e):f$ is a fractional matching of $G\}$. Let $k\in (0,n)$ is an integer. In this paper, we prove a tight lower bound of the spectral radius to guarantee $\mu_{f}(G)>\frac{n-k}{2}$ in a graph with minimum degree $\delta,$ which implies the result on the fractional perfect matching due to Fan et al. [Discrete Math. 345 (2022) 112892]. For a set $\{A, B, C, \ldots\}$ of graphs, an $\{A, B, C, \ldots\}$-factor of a graph $G$ is defined to be a spanning subgraph of $G$ each component of which is isomorphic to one of $\{A, B, C, \ldots\}$.We present a tight sufficient condition in terms of the spectral radius for the existence of a $\{K_2, \{C_k\}\}$-factor in a graph with minimum degree $\delta,$ where $k\geq 3$ is an integer. Moreover, we also provide a tight spectral radius condition for the existence of a $\{K_{1, 1}, K_{1, 2}, \ldots , K_{1, k}\}$-factor with $k\geq2$ in a graph with minimum degree $\delta,$ which generalizes the result of Miao et al. [Discrete Appl. Math. 326 (2023) 17-32].

Authors:Paweł Obszarski, Krzysztof Turowski, Hubert Zięba

Abstract: In this paper we investigate the game chromatic number for complete multipartite graphs. We devise several strategies for Alice, and one strategy for Bob, and we prove their optimality in all complete multipartite graphs with no singletons. All the strategies presented are computable in linear time, and the values of the game chromatic number depend directly only on the number and the sizes of sets in the partition.

Authors:Sandra Albrechtsen

Abstract: We combine the two fundamental fixed-order tangle theorems of Robertson and Seymour into a single theorem that implies both, in a best possible way. We show that, for every $k \in \mathbb{N}$, every tree-decomposition of a graph $G$ which efficiently distinguishes all its $k$-tangles can be refined to a tree-decomposition whose parts are either too small to be home to a $k$-tangle, or as small as possible while being home to a $k$-tangle.

Authors:Matteo Pegoraro

Abstract: In this work we define a novel edit distance for graphs considered with some weights on the edges. The metric is driven by the idea of considering graphs as topological summaries in the context of persistence and topological data analysis. In case the graphs are trees, the metric can be computed with a dynamical integer linear programming approach. This framework is applied and further studied in other works focused on merge trees, where stability properties are also assessed.

Authors:Tomislav Došlić, Luka Podrug

Abstract: We consider two division problems on narrow strips of square and hexagonal lattices. In both cases we compute the bivariate enumerating sequences and the corresponding generating functions, which allowed us to determine the asymptotic behavior of the total number of such subdivisions and the expected number of parts. For the square lattice we extend results of two recent references by establishing polynomiality of enumerating sequences forming columns and diagonals of the triangular enumerating sequence. In the hexagonal case, we find a number of new combinatorial interpretations of the Fibonacci numbers and find combinatorial proofs of some Fibonacci related identities. We also show how both cases could be treated via the transfer matrix method and discuss some directions for future research.

Authors:Mercè Claverol, Andrea de las Heras-Parrilla, David Flores-Peñaloza, Clemens Huemer, David Orden

Abstract: Three polynomials are defined for given sets $S$ of $n$ points in general position in the plane: The Voronoi polynomial with coefficients the numbers of vertices of the order-$k$ Voronoi diagrams of~$S$, the circle polynomial with coefficients the numbers of circles through three points of $S$ enclosing $k$ points of $S$, and the $E_{\leq k}$ polynomial with coefficients the numbers of (at most $k$)-edges of~$S$. We present several formulas for the rectilinear crossing number of $S$ in terms of these polynomials and their roots. We also prove that the roots of the Voronoi polynomial lie on the unit circle if, and only if, $S$ is in convex position. Further, we present bounds on the location of the roots of these polynomials.

Authors:Barnabás Janzer, Oliver Janzer

Abstract: Given a graph $H$, let $g(n,H)$ denote the smallest $k$ for which the following holds. We can assign a $k$-colouring $f_v$ of the edge set of $K_n$ to each vertex $v$ in $K_n$ with the property that for any copy $T$ of $H$ in $K_n$, there is some $u\in V(T)$ such that every edge in $T$ has a different colour in $f_u$. The study of this function was initiated by Alon and Ben-Eliezer. They characterized the family of graphs $H$ for which $g(n,H)$ is bounded and asked whether it is true that for every other graph $g(n,H)$ is polynomial. We show that this is not the case and characterize the family of connected graphs $H$ for which $g(n,H)$ grows polynomially. Answering another question of theirs, we also prove that for every $\varepsilon>0$, there is some $r=r(\varepsilon)$ such that $g(n,K_r)\geq n^{1-\varepsilon}$ for all sufficiently large $n$. Finally, we show that the above problem is connected to the Erd\H{o}s-Gy\'arf\'as function in Ramsey Theory, and prove a family of special cases of a conjecture of Conlon, Fox, Lee and Sudakov by showing that for each fixed $r$ the complete $r$-uniform hypergraph $K_n^{(r)}$ can be edge-coloured using a subpolynomial number of colours in such a way that at least $r$ colours appear among any $r+1$ vertices.

Authors:Anitha G, P Vanchinathan

Abstract: For a finite field of odd number of elements we construct families of permutation binomials and permutation trinomials with one fixed-point (namely zero) and remaining elements being permuted as disjoint cycles of same length. Binomials and trinomials providing permutations with cycles of many lengths with certain frequency are also constructed.

Authors:Borys Kuca

Abstract: We examine multidimensional polynomial progressions involving linearly independent polynomials in finite fields, proving power saving bounds for sets lacking such configurations. This jointly generalises earlier results of Peluse (for the single dimensional case) and the author (for distinct degree polynomials). In contrast to the cases studied in the aforementioned two papers, a usual PET induction argument does not give Gowers norm control over multidimensional progressions that involve polynomials of the same degrees. The main challenge is therefore to obtain Gowers norm control, and we accomplish this for all multidimensional polynomial progressions with pairwise independent polynomials. The key inputs are: (1) a quantitative version of a PET induction scheme developed in ergodic theory by Donoso, Koutsogiannis, Ferr\'e-Moragues and Sun, (2) a quantitative concatenation result for Gowers box norms in arbitrary finite abelian groups, motivated by earlier results of Tao, Ziegler, Peluse and Prendiville; (3) an adaptation to combinatorics of the box norm smoothing technique, recently developed in the ergodic setting by the author and Frantzikinakis; and (4) a new version of the multidimensional degree lowering argument.

Authors:A. Alochukwu, M. Dorfling, E. Jonck

Abstract: An $i$-packing in a graph $G$ is a set of vertices that are pairwise distance more than $i$ apart. A \emph{packing colouring} of $G$ is a partition $X=\{X_{1},X_{2},\ldots,X_{k}\}$ of $V(G)$ such that each colour class $X_{i}$ is an $i$-packing. The minimum order $k$ of a packing colouring is called the packing chromatic number of $G$, denoted by $\chi_{\rho}(G)$. In this paper we investigate the existence of trees $T$ for which there is only one packing colouring using $\chi_\rho(T)$ colours. For the case $\chi_\rho(T)=3$, we completely characterise all such trees. As a by-product we obtain sets of uniquely $3$-$\chi_\rho$-packable trees with monotone $\chi_{\rho}$-coloring and non-monotone $\chi_{\rho}$-coloring respectively.

Authors:Thang Pham

Abstract: In this paper we prove a sharp condition to guarantee of having a positive proportion of all congruence classes of triangles in given sets in $\mathbb{F}_q^2$. More precisely, for $A, B, C\subset \mathbb{F}_q^2$, if $|A||B||C|^{1/2}\gg q^4$, then for any $\lambda\in \mathbb{F}_q\setminus \{0\}$, the number of congruence classes of triangles with vertices in $A\times B\times C$ and one side-length $\lambda$ is at least $\gg q^2$. As a consequence, the number of congruence classes of triangles with vertices in $A\times B\times C$ is at least $\gg q^3$. The main ingredients in our proof are a recent incidence bound between points and rigid motions due to the author and Semin Yoo (2023) and a result on a Furstenberg type problem. When three sets are the same, we give a unified and new proof for all the best current results due to Bennett, Hart, Iosevich, Pakianathan, and Rudnev (2017) and McDonald (2020). The novelty of this approach is to present an application of results on the number of $k$-rich rigid motions in studying the distribution of simplex. A number of related questions will be also addressed in this paper.

Authors:Philip Mummert

Abstract: Austrian Solitaire is a variation of Bulgarian Solitaire. It may be described as a card game, a method of asset inventory management, or a discrete dynamical system on integer partitions. We prove that the limit cycles in Austrian Solitaire do not depend on the initial configuration. We show that a full Farey sequence completely characterizes these unique (and balanced) cycles.

Authors:Ivailo Hartarsky, Lyuben Lichev, Fabio Toninelli

Abstract: We consider local dynamics of the dimer model (perfect matchings) on hypercubic boxes $[n]^d$. These consist of successively switching the dimers along alternating cycles of prescribed (small) lengths. We study the connectivity properties of the dimer configuration space equipped with these transitions. Answering a question of Freire, Klivans, Milet and Saldanha, we show that in three dimensions any configuration admits an alternating cycle of length at most 6. We further establish that any configuration on $[n]^d$ features order $n^{d-2}$ alternating cycles of length at most $4d-2$. We also prove that the dynamics of dimer configurations on the unit hypercube of dimension $d$ is ergodic when switching alternating cycles of length at most $4d-4$. Finally, in the planar but non-bipartite case, we show that parallelogram-shaped boxes in the triangular lattice are ergodic for switching alternating cycles of lengths 4 and 6 only, thus improving a result of Kenyon and R\'emila, which also uses 8-cycles. None of our proofs make reference to height functions.

Authors:Payal Vasoya, Devsi Bantva

Abstract: A radio labeling of a graph $G$ is a function $f : V(G) \rightarrow \{0,1,2,\ldots\}$ such that $|f(u)-f(v)| \geq diam(G) + 1 - d(u,v)$ for every pair of distinct vertices $u,v$ of $G$. The radio number of $G$, denoted by $rn(G)$, is the smallest number $k$ such that $G$ has radio labeling $f$ with max$\{f(v):v \in V(G)\} = k$. In this paper, we give a lower bound for the radio number for the Cartesian product of the generalized Petersen graph and tree. We present two necessary and sufficient conditions, and three other sufficient conditions to achieve the lower bound. Using these results, we determine the radio number for the Cartesian product of the Peterson graph and stars.

Authors:Roy Gotlib, Tali Kaufman

Abstract: "No Where to go but in" is a well known statement of Osho. Osho meant to say that the answers to all our questions should be obtained by looking into ourselves. In a paraphrase to Osho's statement we say "No Where to go but high". This meant to demonstrate that for various seemingly unrelated topics and questions the only way to get significant progress is via the prism of a new philosophy (new field) called high dimensional expansion. In this note we give an introduction \footnote{This introduction reflects the authors' interests and by no mean claim to represent the field in a through way} to the high dimensional expansion philosophy, and how it has been useful recently in obtaining progress in various questions in seemingly unrelated fields. This exposition is dedicated to the memory of my mother, Sarah Kaufman, who was always trying to understand the reason why things behave in a certain way. It is also dedicated to the memory of my father Eliezer Kaufman.

Authors:Sandi Klavžar, Elif Tan

Abstract: A set of edges $X\subseteq E(G)$ of a graph $G$ is an edge general position set if no three edges from $X$ lie on a common shortest path in $G$. The cardinality of a largest edge general position set of $G$ is the edge general position number of $G$. In this paper edge general position sets are investigated in partial cubes. In particular it is proved that the union of two largest $\Theta$-classes of a Fibonacci cube or a Lucas cube is a maximal edge general position set.

Authors:Vsevolod Voronov

Abstract: The work is devoted to to one of the variations of the Hadwiger--Nelson problem on the chromatic number of the plane. In this formulation one needs to find for arbitrarily small $\varepsilon$ the least possible number of colors needed to color the Euclidean plane in such a way that any two points, the distance between which belongs to the interval $[1-\varepsilon, 1+\varepsilon]$, are colored differently. The hypothesis proposed by G. Exoo in 2004, states that for arbitrary positive $\varepsilon$ at least 7 colors are required. Also, with a sufficiently small $\varepsilon$ the number of colors is exactly 7. The main result of this paper is the proof of this hypothesis.

Authors:Minho Kim

Abstract: We characterized the combinatorial structure of the Voronoi cell of the $A_n$ lattice in arbitrary dimensions. Based on the well-known fact that the Voronoi cell is the disjoint union of $(n+1)!$ congruent simplices, we show that it is the disjoint union of $(n+1)$ congruent hyper-rhombi, which are the generalized rhombi or trigonal trapezohedra. The explicit structure of the faces is investigated, including the fact that all the $k$-dimensional faces, $2\le k\le n-1$, are hyper-rhombi. We show it to be the vertex-first orthogonal projection of the $(n+1)$-dimensional unit cube. Hence the Voronoi cell is a zonotope. We prove that in low dimensions ($n\le 3$) the Voronoi cell can be understood as the section of that of the $D_{n+1}$ lattice with the hyperplane orthogonal to the diagonal direction. We provide all the explicit coordinates and transformation matrices associated with our analysis. Most of our analysis is algebraic and easily accessible to those less familiar with the Coxeter-Dynkin diagrams.

Authors:Jiangdong Ai, Stefanie Gerke, Gregory Gutin, Anders Yeo, Yacong Zhou

Abstract: We obtain lower and upper bounds for the maximum weight of a directed cut in the classes of weighted digraphs and weighted acyclic digraphs as well as in some of their subclasses. We compare our results with those obtained for the maximum size of a directed cut in unweighted digraphs. In particular, we show that a lower bound obtained by Alon, Bollobas, Gyafas, Lehel and Scott (J Graph Th 55(1) (2007)) for unweighted acyclic digraphs can be extended to weighted digraphs with the maximum length of a cycle being bounded by a constant and the weight of every arc being at least one. We state a number of open problems.

Authors:Marcin Stawiski

Abstract: Karo\'nski, {\L}uczak and Thomason conjectured in 2004 that for every finite graph without isolated edge, the edges can be assigned weights from $\{1,2,3\}$ in such a way that the endvertices of each edge have different sums of incident edge weights. This is known as the 1-2-3 Conjecture, and it was only recently proved by Keusch. We extend this result to infinite graphs in the following way. If $G$ is a graph without isolated edge, then the edges can be assigned weights from $\{1,2,3\}$ is such a way that the endvertices of each edge have different sum of incident edge weights, or these endvertices have both the same infinite degree. We also investigate the extensions of theorems about total and list versions of 1-2-3 Conjecture to infinite graphs.

Authors:Chiara Cappello, Reza Naserasr, Eckhard Steffen, Zhouningxin Wang

Abstract: Extending the notion of maxcut, the study of the frustration index of signed graphs is one of the basic questions in the theory of signed graphs. Recently two of the authors initiated the study of critically frustrated signed graphs. That is a signed graph whose frustration index decreases with the removal of any edge. The main focus of this study is on critical signed graphs which are not edge-disjoint unions of critically frustrated signed graphs (namely non-decomposable signed graphs) and which are not built from other critically frustrated signed graphs by subdivision. We conjecture that for any given $k$ there are only finitely many critically $k$-frustrated signed graphs of this kind. Providing support for this conjecture we show that there are only two of such critically $3$-frustrated signed graphs where there is no pair of edge-disjoint negative cycles. Similarly, we show that there are exactly ten critically $3$-frustrated signed planar graphs that are neither decomposable nor subdivisions of other critically frustrated signed graphs. We present a method for building non-decomposable critically frustrated signed graphs based on two given such signed graphs. We also show that the condition of being non-decomposable is necessary for our conjecture.

Authors:Stéphane Bessy, Johannes Rauch, Dieter Rautenbach, Uéverton S. Souza

Abstract: We show that every graph $G$ of maximum degree $\Delta$ and sufficiently large order has a vertex cutset $S$ of order at most $\Delta$ that induces a subgraph $G[S]$ of maximum degree at most $\Delta-3$. For $\Delta\in \{ 4,5\}$, we refine this result by considering also the average degree of $G[S]$. If $G$ has no $K_{r,r}$ subgraph, then we show the existence of a vertex cutset that induces a subgraph of maximum degree at most $\left(1-\frac{1}{{r\choose 2}}\right)\Delta+O(1)$.

Authors:Ira M. Gessel, Ishan Kar

Abstract: The binomial convolution of two sequences $\{a_n\}$ and $\{b_n\}$ is the sequence whose $n$th term is $\sum_{k=0}^{n} \binom{n}{k} a_k b_{n-k}$. If $\{a_n\}$ and $\{b_n\}$ have rational generating functions then so does their binomial convolution. We discuss an efficient method, using resultants, for computing this rational generating function and give several examples involving Fibonacci and tribonacci numbers and related sequences. We then describe a similar method for computing Hadamard products of rational generating functions. Finally we describe two additional methods for computing binomial convolutions and Hadamard products of rational power series, one using symmetric functions and one using partial fractions.

Authors:Radel Ben-Av, Giora Dula, Assaf Goldberger, Yoseph Strassler

Abstract: In this paper we describe an algorithm for generating all the possible $PIW(m,n,k)$ - integer $m\times n$ Weighing matrices of weight $k$ up to Hadamard equivalence. Our method is efficient on a personal computer for small size matrices, up to $m\le n=12$, and $k\le 50$. As a by product we also improved the \textit{\textbf{nsoks}} \cite{riel2006nsoks} algorithm to find all possible representations of an integer $k$ as a sum of $n$ integer squares. We have implemented our algorithm in \texttt{Sagemath} and as an example we provide a complete classification for \ $n=m=7$ and $k=25$. Our list of $IW(7,25)$ can serve as a step towards finding the open classical weighing matrix $W(35,25)$.

Authors:Warren Singh, Timothy Sun

Abstract: For each nonorientable surface of genus at least 3, we construct a face-simple minimal quadrangulation, i.e., a simple quadrangulation on the fewest number of vertices possible whose dual is also a simple graph. This answers a question of Liu, Ellingham, and Ye, and also provides a simpler proof of part of their main result. The inductive construction is based on an earlier idea for finding near-quadrangular embeddings of the complete graphs using the diamond sum operation.

Authors:Oscar Defrain, Jean-Florent Raymond

Abstract: Graphs of bounded degeneracy are known to contain induced paths of order $\Omega(\log \log n)$ when they contain a path of order $n$, as proved by Ne\v{s}et\v{r}il and Ossona de Mendez (2012). In 2016 Esperet, Lemoine, and Maffray conjectured that this bound could be improved to $\Omega((\log n)^c)$ for some constant $c>0$ depending on the degeneracy. We disprove this conjecture by constructing, for arbitrarily large values of $n$, a graph that is 2-degenerate, has a path of order $n$, and where all induced paths have order $O((\log \log n)^2)$. We also show that the graphs we construct have linearly bounded coloring numbers.

Authors:Valentin Bouquet, François Delbot, Christophe Picouleau, Stéphane Rovedakis

Abstract: A set $S\subseteq V$ of a graph $G=(V,E)$ is a dominating set if each vertex has a neighbor in $S$ or belongs to $S$. Dominating Set is the problem of deciding, given a graph $G$ and an integer $k\geq 1$, if $G$ has a dominating set of size at most $k$. It is well known that this problem is $\mathsf{NP}$-complete even for claw-free graphs. We give a complexity dichotomy for Dominating Set for the class of claw-free graphs with diameter $d$. We show that the problem is $\mathsf{NP}$-complete for every fixed $d\ge 3$ and polynomial time solvable for $d\le 2$. To prove the case $d=2$, we show that Minimum Maximal Matching can be solved in polynomial time for $2K_2$-free graphs.

Authors:Ryoh Fuji-Hara, Ying Miao

Abstract: An ideal secret sharing scheme is a method of sharing a secret key in some key space among a finite set of participants in such a way that only the authorized subsets of participants can reconstruct the secret key from their shares which are of the same length as that of the secret key. The set of all authorized subsets of participants is the access structure of the secret sharing scheme. In this paper, we derive several properties and restate the combinatorial characterization of an ideal secret sharing scheme in Brickell-Stinson model in terms of orthogonality of its representative array. We propose two practical models, namely the parallel and hierarchical models, for access structures, and then, by the restated characterization, we discuss sufficient conditions on finite geometries for ideal secret sharing schemes to realize these access structure models. Several series of ideal secret sharing schemes realizing special parallel or hierarchical access structure model are constructed from finite projective planes.

Authors:Sizhong Zhou, Jiancheng Wu

Abstract: Let $k\geq2$ be an integer. A tree $T$ is called a $k$-tree if $d_T(v)\leq k$ for each $v\in V(T)$, that is, the maximum degree of a $k$-tree is at most $k$. Let $\lambda_1(D(G))$ denote the distance spectral radius in $G$, where $D(G)$ denotes the distance matrix of $G$. In this paper, we verify a upper bound for $\lambda_1(D(G))$ in a connected graph $G$ to guarantee the existence of a spanning $k$-tree in $G$.

Authors:Gunnar Brinkmann

Abstract: We give constructive proofs for the existence of uniquely hamiltonian graphs for various sets of degrees. We give constructions for all sets with minimum 2 (a trivial case), all sets with minimum 3 that contain an even number (for sets without an even number it is known that no uniquely hamiltonian graphs exist), and all sets with at least two elements and minimum 4 where all other elements are at least 10. For minimum degree 3 and 4, the constructions also give 3-connected graphs.

Authors:Feihu Liu, Guoce Xin, Suting Ye, Jingjing Yin

Abstract: Given relative prime positive integers $A=(a_1, a_2, ..., a_n)$, the Frobenius number $g(A)$ is the largest integer not representable as a linear combination of the $a_i$'s with nonnegative integer coefficients. We find the ``Stable" property introduced for the square sequence $A=(a,a+1,a+2^2,\dots, a+k^2)$ naturally extends for $A(a)=(a,ha+d,ha+b_2d,...,ha+b_kd)$. This gives a parallel characterization of $g(A(a))$ as a ``congruence class function" modulo $b_k$ when $a$ is large enough. For orderly sequence $B=(1,b_2,\dots,b_k)$, we find good bound for $a$. In particular we calculate $g(a,ha+dB)$ for $B=(1,2,b,b+1,2b)$, $B=(1,b,2b-1)$ and $B=(1,2,...,k,K)$.

Authors:Haiying Shan, Muhuo Liu

Abstract: Let $P(n)$ denote the set of all partitions of $n$, whose elements are nondecreasing sequences of positive integers whose sum is $n$. For ${\bf a}=( n_{1}, n_{2},\ldots, n_{d}) \in P(n)$, let $G({\bf a},v)$ denote the graph obtained from connected graph $G$ appending $d$ paths with lengths $n_{1},n_{2},\ldots,n_{d}$ on vertex $v$ of $G$. We show that the ordering of graphs in $G_{n}(v)=\{ G({\bf a},v) \mid {\bf a} \in P(n) \}$ by $A_\alpha$-spectral radii coincides with the shortlex ordering of $P(n)$.

Authors:Kyriakos Katsamaktsis, Shoham Letzter

Abstract: We investigate the existence of a rainbow Hamilton cycle in a uniformly edge-coloured randomly perturbed graph. We show that for every $\delta \in (0,1)$ there exists $C = C(\delta) > 0$ such that the following holds. Let $G_0$ be an $n$-vertex graph with minimum degree at least $\delta n$ and suppose that each edge of the union of $G_0$, with the random graph $G(n, p)$ on the same vertex set, gets a colour in $[n]$ independently and uniformly at random. Then, with high probability, $G_0 \cup G(n, p)$ has a rainbow Hamilton cycle. This improves a result of Aigner-Horev and Hefetz, who proved the same when the edges are coloured uniformly in a set of $(1 + \epsilon)n$ colours.

Authors:Houshan Fu, Chunming Tang, Suijie Wang

Abstract: We show that an adjoint of a loopless matroid is connected if and only if it itself is connected. Our first goal is to study the adjoint of modular matroids. We prove that a modular matroid has only one adjoint (up to isomorphism) which can be given by its opposite lattice, and proceed to present some alternative characterizations of modular matroids associated to adjoints and opposite lattices. The other purpose is to investigate the adjoint sequence $ad^0M,adM,ad^2M,\ldots$ of a connected matroid $M$. We classify such adjoint sequences into three types: finite, cyclic and convergent. For the first two types, the adjoint sequences eventually stabilize at the finite projective geometries except for free matroids. For the last type, the infinite non-repeating adjoint sequences are convergent to the infinite projective geometries.

Authors:Yiran Zhang, Yuejian Peng, Zhidan Luo

Abstract: For graphs $G_0$, $G_1$ and $G_2$, write $G_0\longmapsto(G_1, G_2)$ if each red-blue-edge-coloring of $G_0$ yields a red $G_1$ or a blue $G_2$. The Ramsey number $r(G_1, G_2)$ is the minimum number $n$ such that the complete graph $K_n\longmapsto(G_1, G_2)$. In [Discrete Math. 312(2012)], Schelp formulated the following question: for which graphs $H$ there is a constant $0<c<1$ such that for any graph $G$ of order at least $r(H, H)$ with $\delta(G)>c|V(G)|$, $G\longmapsto(H, H)$. In this paper, we prove that for any $m>n$, if $G$ is a balanced bipartite graph of order $2(m+n-1)$ with $\delta(G)>\frac{3}{4}(m+n-1)$, then $G\longmapsto(CM_m, CM_n)$, where $CM_i$ is a matching with $i$ edges contained in a connected component. By Szem\'{e}redi's Regularity Lemma, using a similar idea as introduced by [J. Combin. Theory Ser. B 75(1999)], we show that for every $\eta>0$, there is an integer $N_0>0$ such that for any $N>N_0$ the following holds: Let $\alpha_1>\alpha_2>0$ such that $\alpha_1+\alpha_2=1$. Let $G[X, Y]$ be a balanced bipartite graph on $2(N-1)$ vertices with $\delta(G)>(\frac{3}{4}+3\eta)(N-1)$. Then for each red-blue-edge-coloring of $G$, either there exist red even cycles of each length in $\{4, 6, 8, \ldots, (2-3\eta^2)\alpha_1N\}$, or there exist blue even cycles of each length in $\{4, 6, 8, \ldots, (2-3\eta^2)\alpha_2N\}$. Furthermore, the bound $\delta(G)\geq(\frac{3}{4}+3\eta)(N-1)$ is asymptotically tight. Previous studies on Schelp's question on cycles are on diagonal case, we obtain an asymptotic result of Schelp's question for all non-diagonal cases.

Authors:Thang Pham, Semin Yoo

Abstract: Let $A$ and $B$ be sets in a finite vector space. In this paper, we study the magnitude of the set $A\cap f(B)$, where $f$ runs through a set of transformations. More precisely, we will focus on the cases that the set of transformations is given by orthogonal matrices or orthogonal projections. One of the most important contributions of this paper is to show that if $A, B\subset \mathbb{F}_q^d$ satisfy some natural conditions then, for almost every $g\in O(d)$, there are at least $\gg q^d$ elements $z\in \mathbb{F}_q^d$ such that \[|A\cap (g(B)+z)| \sim \frac{|A||B|}{q^d}.\] This infers that $|A-gB|\gg q^d$ for almost every $g\in O(d)$. In the flavor of expanding functions, with $|A|\le |B|$, we also show that the image $A-gB$ grows exponentially. In two dimensions, the result simply says that if $|A|=q^x$ and $|B|=q^y$, as long as $0<x\le y<2$, then for almost every $g\in O(2)$, we can always find $\epsilon=\epsilon(x, y)>0$ such that $|A-gB|\gg |B|^{1+\epsilon}$. To prove these results, we need to develop a new and robust incidence bound between points and rigid motions by using a number of techniques including algebraic methods and discrete Fourier analysis. Our results are essentially sharp in odd dimensions.

Authors:Jędrzej Hodor, William T. Trotter

Abstract: Over the past 10 years, there has been considerable interest in exploring questions connecting dimension for posets with graph theoretic properties of their cover graphs and order diagrams, especially with the concepts of planarity and treewidth. Joret and Micek conjectured that if $P$ is a poset with a planar cover graph, then the dimension of $P$ is bounded in terms of the number of minimal elements of $P$ and the treewidth of the cover graph of $P$. We settle this conjecture in the affirmative by strengthening a recent breakthrough result [14] by Blake, Micek, and Trotter, who proved that for each poset $P$ admitting a planar cover graph and a unique minimal element we have $\mathrm{dim}(P) \leq 2 \mathrm{se}(P) + 2$, namely, we prove that $\mathrm{dim}(P) \leq 2 \mathrm{wheel}(P) + 2$.

Authors:Roberto Pagaria, Maddalena Pismataro, Tan Nhat Tran, Lorenzo Vecchi

Abstract: We call a poset factorable if its characteristic polynomial has all positive integer roots. Inspired by inductive and divisional freeness of a central hyperplane arrangement, we introduce and study the notion of inductive posets and their superclass of divisional posets. It then motivates us to define the so-called inductive and divisional abelian (Lie group) arrangements, whose posets of layers serve as the main examples of our posets. Our first main result is that every divisional poset is factorable. Our second main result shows that the class of inductive posets contains strictly supersolvable posets, the notion recently introduced due to Bibby and Delucchi (2022). This result can be regarded as an extension of a classical result due to Jambu and Terao (1984), which asserts that every supersolvable hyperplane arrangement is inductively free. Our third main result is an application to toric arrangements, which states that the toric arrangement defined by an arbitrary ideal of a root system of type $A$, $B$ or $C$ with respect to the root lattice is inductive.

Authors:Seid Kassaw Muhie Woldia University, Woldia, Ethiopia, Daniele Ettore Otera Vilnius University, Vilnius, Lithuania, Francesco G. Russo University of Cape Town, Cape Town, South Africa

Abstract: The factorization number $F_2(G)$ of a finite group $G$ is the number of all possible factorizations of $G=HK$ as product of its subgroups $H$ and $K$, while the subgroup commutativity degree $\mathrm{sd}(G)$ of $G$ is the probability of finding two commuting subgroups in $G$ at random. It is known that $\mathrm{sd}(G)$ can be expressed in terms of $F_2(G)$. Denoting by $\mathrm{L}(G)$ the subgroups lattice of $G$, the non--permutability graph of subgroups $\Gamma_{\mathrm{L}(G)}$ of $G$ is the graph with vertices in $\mathrm{L}(G) \setminus \mathfrak{C}_{\mathrm{L}(G)}(\mathrm{L}(G))$, where $\mathfrak{C}_{\mathrm{L}(G)}(\mathrm{L}(G))$ is the smallest sublattice of $\mathrm{L}(G)$ containing all permutable subgroups of $G$, and edges obtained by joining two vertices $X,Y$ such that $XY\neq YX$. The spectral properties of $\Gamma_{\mathrm{L}(G)}$ have been recently investigated in connection with $F_2(G)$ and $\mathrm{sd}(G)$. Here we show a new combinatorial formula, which allows us to express $F_2(G)$, and so $\mathrm{sd}(G)$, in terms of adjacency and Laplacian matrices of $\Gamma_{\mathrm{L}(G)}$.

Authors:I. Cardinali, L. Giuzzi

Abstract: Consider the point line-geometry ${\mathcal P}_t(n,k)$ having as points all the $[n,k]$-linear codes having minimum dual distance at least $t+1$ and where two points $X$ and $Y$ are collinear whenever $X\cap Y$ is a $[n,k-1]$-linear code having minimum dual distance at least $t+1$. We are interested in the collinearity graph $\Lambda_t(n,k)$ of ${\mathcal P}_t(n,k).$ The graph $\Lambda_t(n,k)$ is a subgraph of the Grassmann graph and also a subgraph of the graph $\Delta_t(n,k)$ of the linear codes having minimum dual distance at least $t+1$ introduced in~[M. Kwiatkowski, M. Pankov, On the distance between linear codes, Finite Fields Appl. 39 (2016), 251--263, doi:10.1016/j.ffa.2016.02.004, arXiv:1506.00215]. We shall study the structure of $\Lambda_t(n,k)$ in relation to that of $\Delta_t(n,k)$ and we will characterize the set of its isolated vertices. We will then focus on $\Lambda_1(n,k)$ and $\Lambda_2(n,k)$ providing necessary and sufficient conditions for them to be connected.

Authors:Julius Ross, Hendrik Süß, Thomas Wannerer

Abstract: We introduce and study a notion of dually Lorentzian polynomials, and show that if $s$ is non-zero and dually Lorentzian then the operator \[s(\partial_{x_1},\ldots,\partial_{x_n}):\mathbb R[x_1,\ldots,x_n] \to \mathbb R[x_1,\ldots,x_n]\] preserves (strictly) Lorentzian polynomials. From this we conclude that any theory that admits a mixed Alexandrov-Fenchel inequality also admits a generalized Alexandrov-Fenchel inequality involving dually Lorentzian polynomials. As such we deduce generalized Alexandrov-Fenchel inequalities for mixed discriminants, for integrals of K\"ahler classes, for mixed volumes, and in the theory of valuations.

Authors:Chong Zheng

Abstract: In this paper, we study some properties of persistent pairs in a discrete Morse function on a simplicial complex. As a simple corollary we improve discrete Morse inequalities. By using the properties, we explore the correlation between the number of strongly connected critical simplices between two distinct discrete Morse functions and the Betti number of a simple graph. This result gives an answer to the problem recently posed by King et al.

Authors:Longfei Fang, Huiqiu Lin, Yongtang Shi

Abstract: Given a planar graph family $\mathcal{F}$, let ${\rm ex}_{\mathcal{P}}(n,\mathcal{F})$ and ${\rm spex}_{\mathcal{P}}(n,\mathcal{F})$ be the maximum size and maximum spectral radius over all $n$-vertex $\mathcal{F}$-free planar graphs, respectively. Let $tC_k$ be the disjoint union of $t$ copies of $k$-cycles, and $t\mathcal{C}$ be the family of $t$ vertex-disjoint cycles without length restriction. Tait and Tobin [Three conjectures in extremal spectral graph theory, J. Combin. Theory Ser. B 126 (2017) 137--161] determined that $K_2+P_{n-2}$ is the extremal spectral graph among all planar graphs with sufficiently large order $n$, which implies the extreme graphs of $spex_{\mathcal{P}}(n,tC_{\ell})$ and $spex_{\mathcal{P}}(n,t\mathcal{C})$ for $t\geq 3$ are $K_2+P_{n-2}$. In this paper, we first determine $spex_{\mathcal{P}}(n,tC_{\ell})$ and $spex_{\mathcal{P}}(n,t\mathcal{C})$ and characterize the unique extremal graph for $1\leq t\leq 2$, $\ell\geq 3$ and sufficiently large $n$. Secondly, we obtain the exact values of ${\rm ex}_{\mathcal{P}}(n,2C_4)$ and ${\rm ex}_{\mathcal{P}}(n,2\mathcal{C})$, which answers a conjecture of Li [Planar Tur\'an number of disjoint union of $C_3$ and $C_4$, arxiv:2212.12751v1 (2022)]. These present a new exploration of approaches and tools to investigate extremal problems of planar graphs.

Authors:Daniel Neuen

Abstract: Two graphs are homomorphism indistinguishable over a graph class $\mathcal{F}$, denoted by $G \equiv_{\mathcal{F}} H$, if $\operatorname{hom}(F,G) = \operatorname{hom}(F,H)$ for all $F \in \mathcal{F}$ where $\operatorname{hom}(F,G)$ denotes the number of homomorphisms from $F$ to $G$. A classical result of Lov\'{a}sz shows that isomorphism between graphs is equivalent to homomorphism indistinguishability over the class of all graphs. More recently, there has been a series of works giving natural algebraic and/or logical characterizations for homomorphism indistinguishability over certain restricted graph classes. A class of graphs $\mathcal{F}$ is homomorphism-distinguishing closed if, for every $F \notin \mathcal{F}$, there are graphs $G$ and $H$ such that $G \equiv_{\mathcal{F}} H$ and $\operatorname{hom}(F,G) \neq \operatorname{hom}(F,H)$. Roberson conjectured that every class closed under taking minors and disjoint unions is homomorphism-distinguishing closed which implies that every such class defines a distinct equivalence relation between graphs. In this note, we confirm this conjecture for the classes $\mathcal{T}_k$, $k \geq 1$, containing all graphs of tree-width at most $k$.

Authors:Robert F. Bailey, Keenan B. Nicholson

Abstract: We consider twisted permutation codes, a class of frequency permutation arrays obtained from finite groups with multiple permutation representations of the same degree, introduced by Gillespie, Praeger and Spiga (and later studied by Akbari, Gillespie and Praeger), and develop a decoding algorithm for such codes based on earlier work of the first author for permutation group codes. In particular, we show how to implement this algorithm for an infinite family of groups considered by Akbari, Gillespie and Praeger.

Authors:Aleksandr D. Krotov, Denis S. Krotov

Abstract: We discuss the problem of existence of latin squares without a substructure consisting of six elements $(r_1,c_2,l_3)$, $(r_2,c_3,l_1)$, $(r_3,c_1,l_2)$, $(r_2,c_1,l_3)$, $(r_3,c_2,l_1)$, $(r_1,c_3,l_2)$. Equivalently, the corresponding latin square graph does not have an induced subgraph isomorphic to $K_{3,3}$. The exhaustive search [Brouwer, Wanless. Universally noncommutative loops. 2011] says that there are no such latin squares of order from $3$ to $11$, and there are only two $K_{3,3}$-free latin squares of order $8$, up to equivalence. We repeat the search, establishing also the number of latin $m$-by-$n$ rectangles for each $m$ and $n$ less or equal to $11$. As a switched combination of two orthogonal latin squares of order $8$, we construct a $K_{3,3}$-free (universally noncommutative) latin square of order $16$. Keywords: latin square; transversal; trade; pattern avoiding; eigenfunction; universally noncommutative loops.

Authors:Aida Abiad, Carlos A. Alfaro, Ralihe R. Villagrán

Abstract: The search for a highly discriminating and easily computable invariant to distinguish graphs remains a challenging research topic. Here we focus on cospectral graphs whose complements are also cospectral (generalized cospectral), and on coinvariant graphs (same Smith normal form) whose complements are also coinvariant (generalized coinvariant). We show a new characterization of generalized cospectral graphs in terms of codeterminantal graphs. We also establish the Smith normal form of some graph classes for certain associated matrices, and as an application, we prove that the Smith normal form can be used to uniquely determine star graphs. Finally, for graphs up to 10 vertices, we present enumeration results on the number of generalized cospectral graphs and generalized coinvariant graphs with respect to several associated matrices.

Authors:Jinwon Choi, Jooyeon Park

Abstract: In this paper, we determine the graphs which have the minimal spectral radius among all the connected graphs of order $n$ and the independence number $\lceil\frac{n}{2}\rceil-1.$

Authors:Helen W. J. Zhang, Ying Zhong

Abstract: In this paper, we obtain asymptotic formulas for $k$-crank of $k$-colored partitions. Let $M_k(a, c; n)$ denote the number of $k$-colored partitions of $n$ with a $k$-crank congruent to $a$ mod $c$. For the cases $k=2,3,4$, Fu and Tang derived several inequality relations for $M_k(a, c; n)$ using generating functions. We employ the Hardy-Ramanujan Circle Method to extend the results of Fu and Tang. Furthermore, additional inequality relations for $M_k(a, c; n)$ have been established, such as logarithmic concavity and logarithmic subadditivity.

Authors:Justus Bruckamp, Markus Chimani, Martina Juhnke-Kubitzke

Abstract: In this paper, we study the connected blocks polytope, which, apart from its own merits, can be seen as the generalization of certain connectivity based or Eulerian subgraph polytopes. We provide a complete facet description of this polytope, characterize its edges and show that it is Hirsch. We also show that connected blocks polytopes admit a regular unimodular triangulation by constructing a squarefree Gr\"obner basis. In addition, we prove that the polytope is Gorenstein of index $2$ and that its $h^\ast$-vector is unimodal.

Authors:Juan Jia, Yinhuo Zhang

Abstract: In this paper we use the Lyndon-shirshov basis to study the shuffle type polynomials. We give a free noncommutative binomial (or multinomial) theorem in terms of the Lyndon-Shirshov basis. Another noncommutative binomial theorem given by the shuffle type polynomials with respect to an adjoint derivation is established. As a result, the Bell differential polynomials and the $q$-Bell differential polynomials can be derived from the second binomial theorem. The relation between the shuffle type polynomials and the Bell differential polynomials is established. Finally, we give some applications of the free noncommutative binomial theorem including application of the shuffle type polynomials to bialgebras and Hopf algebras.

Authors:Marc Hellmuth, Sandhya Thekkumpadan Puthiyaveedu

Abstract: Median graphs are connected graphs in which for all three vertices there is a unique vertex that belongs to shortest paths between each pair of these three vertices. To be more formal, a graph $G$ is a median graph if, for all $\mu, u,v\in V(G)$, it holds that $|I(\mu,u)\cap I(\mu,v)\cap I(u,v)|=1$ where $I(x,y)$ denotes the set of all vertices that lie on shortest paths connecting $x$ and $y$. In this paper we are interested in a natural generalization of median graphs, called $k$-median graphs. A graph $G$ is a $k$-median graph, if there are $k$ vertices $\mu_1,\dots,\mu_k\in V(G)$ such that, for all $u,v\in V(G)$, it holds that $|I(\mu_i,u)\cap I(\mu_i,v)\cap I(u,v)|=1$, $1\leq i\leq k$. By definition, every median graph with $n$ vertices is an $n$-median graph. We provide several characterizations of $k$-median graphs that, in turn, are used to provide many novel characterizations of median graphs.

Authors:V. Gurvich, D. Martynov, V. Maximchuk, M. Vyalyi

Abstract: Given integer $n$ and $k$ such that $0 < k \leq n$ and $n$ piles of stones, two player alternate turns. By one move it is allowed to choose any $k$ piles and remove exactly one stone from each. The player who has to move but cannot is the loser. Cases $k=1$ and $k = n$ are trivial. For $k=2$ the game was solved for $n \leq 6$. For $n \leq 4$ the Sprague-Grundy function was efficiently computed (for both the normal and mis\`ere versions). For $n = 5,6$ a polynomial algorithm computing P-positions was obtained. Here we consider the case $2 \leq k = n-1$ and compute Smith's remoteness function, whose even values define the P-positions. In fact, an optimal move is always defined by the following simple rule: if all piles are odd, keep a largest one and reduce all other; if there exist even piles, keep a smallest one of them and reduce all other. Such strategy is optimal for both players, moreover, it allows to win as fast as possible from an N-position and to resist as long as possible from a P-position.

Authors:Bishal Deb, Alan D. Sokal

Abstract: A permutation is said to be cycle-alternating if it has no cycle double rises, cycle double falls or fixed points; thus each index $i$ is either a cycle valley ($\sigma^{-1}(i)>i<\sigma(i)$) or a cycle peak ($\sigma^{-1}(i)<i>\sigma(i)$). We find Stieltjes-type continued fractions for some multivariate polynomials that enumerate cycle-alternating permutations with respect to a large (sometimes infinite) number of simultaneous statistics that measure cycle status, record status, crossings and nestings along with the parity of the indices. Our continued fractions are specializations of more general continued fractions of Sokal and Zeng. We then introduce alternating Laguerre digraphs, which are generalization of cycle-alternating permutations, and find exponential generating functions for some polynomials enumerating them. We interpret the Stieltjes--Rogers and Jacobi--Rogers matrices associated to some of our continued fractions in terms of alternating Laguerre digraphs.

Authors:Archit Karandikar, Akashnil Dutta

Abstract: The Queen's Domination problem, studied for over 160 years, poses the following question: What is the least number of queens that can be arranged on a $m \times n$ chessboard so that they either attack or occupy every cell? We propose a novel relaxation of the Queen's Domination problem and show that it is exactly solvable on both square and rectangular chessboards. As a consequence, we improve on the best known lower bound for rectangular chessboards in $\approx 12.5\%$ of the non-trivial cases. As another consequence, we simplify and generalize the proofs for the best known lower-bounds for Queen's Domination of square $n \times n$ chessboards for $n \equiv \{0,1,2\} \mod 4$ using an elegant idea based on a convex hull. Finally, we show some results and make some conjectures towards the goal of simplifying the long complicated proof for the best known lower-bound for square boards when $n \equiv 3 \mod 4$ (and $n > 11$). These simple-to-state conjectures may also be of independent interest.

Authors:Nathan Lindzey

Abstract: For each integer partition $\lambda \vdash n$ we give a simple combinatorial expression for the sum of the Jack character $\theta^\lambda_\alpha$ over the integer partitions of $n$ with no singleton parts. For $\alpha = 1,2$ this gives closed forms for the eigenvalues of the permutation and perfect matching derangement graphs, resolving an open question in algebraic graph theory. A byproduct of the latter is a simple combinatorial formula for the immanants of the matrix $J-I$ where $J$ is the all-ones matrix, which might be of independent interest. Our proofs center around a Jack analogue of a hook product related to Cayley's $\Omega$--process in classical invariant theory, which we call the principal lower hook product.

Authors:Guantao Chen, Songling Shan

Abstract: Let $G$ be a multigraph. A subset $F$ of $E(G)$ is an edge cover of $G$ if every vertex of $G$ is incident to an edge of $F$. The cover index, $\xi(G)$, is the largest number of edge covers into which the edges of $G$ can be partitioned. Clearly $\xi(G) \le \delta(G)$, the minimum degree of $G$. For $U\subseteq V(G)$, denote by $E^+(U)$ the set of edges incident to a vertex of $U$. When $|U|$ is odd, to cover all the vertices of $U$, any edge cover needs to contain at least $(|U|+1)/2$ edges from $E^+(U)$, indicating $ \xi(G) \le |E^+(U)|/ (|U|+1)/2$. Let $\rho_c(G)$, the co-density of $G$, be defined as the minimum of $|E^+(U)|/((|U|+1)/2)$ ranging over all $U\subseteq V(G)$ with $|U| $ odd and at least 3. Then $\rho_c(G)$ provides another upper bound on $\xi(G)$. Thus $\xi(G) \le \min\{\delta(G), \lfloor \rho_c(G) \rfloor \}$. For a lower bound on $\xi(G)$, in 1967, Gupta conjectured that $\xi(G) \ge \min\{\delta(G)-1, \lfloor \rho_c(G) \rfloor \}$. Gupta showed that the conjecture is true when $G$ is simple, and Cao et al. verified this conjecture when $\rho_c(G)$ is not an integer. In this note, we confirm the conjecture when the maximum multiplicity of $G$ is at most two or $ \min\{\delta(G)-1, \lfloor \rho_c(G) \rfloor \} \le 6$.

Authors:Sela Fried, Toufik Mansour

Abstract: We initiate the study of what we refer to as random walk labelings of graphs. These are graph labelings that are obtainable by performing a random walk on the graph, such that the labeling occurs increasingly whenever an unlabeled vertex is encountered. Some of the results we obtain involve sums of inverses of binomial coefficients, for which we obtain new identities. In particular, we prove that $\sum_{k=0}^{n-1}2^{k}(2k+1)^{-1}\binom{2k}{k}^{-1}\binom{n+k}{k}=\binom{2n}{n}2^{-n}\sum_{k=0}^{n-1}2^{k}(2k+1)^{-1}\binom{2k}{k}^{-1}$, thus confirming a conjecture of Bala.

Authors:Andrey Kupavskii, Elizaveta Popova

Abstract: In this paper, we study tilings of $\mathbb Z$, that is, coverings of $\mathbb Z$ by disjoint sets (tiles). Let $T=\{d_1,\ldots, d_s\}$ be a given multiset of distances. Is it always possible to tile $\mathbb Z$ by tiles, for which the multiset of distances between consecutive points is equal to $T$? In this paper, we give a sufficient condition that such a tiling exists. Our result allows multisets of distances to have arbitrarily many distinct values. Our result generalizes most of the previously known results, all of which dealt with the cases of $2$ or $3$ distinct distances.

Authors:Oriol Serra, Lluís Vena

Abstract: Given a family $S$ of $k$--subsets of $[n]$, its lower shadow $\Delta(S)$ is the family of $(k-1)$--subsets which are contained in at least one set in $S$. The celebrated Kruskal--Katona theorem gives the minimum cardinality of $\Delta(S)$ in terms of the cardinality of $S$. F\"uredi and Griggs (and M\"ors) showed that the extremal families for this shadow minimization problem in the Boolean lattice are unique for some cardinalities and asked for a general characterization of these extremal families. In this paper we prove a new combinatorial inequality from which yet another simple proof of the Kruskal--Katona theorem can be derived. The inequality can be used to obtain a characterization of the extremal families for this minimization problem, giving an answer to the question of F\"uredi and Griggs. Some known and new additional properties of extremal families can also be easily derived from the inequality.

Authors:Udrea Păun

Abstract: The $G^{+}$ method is a new method, a powerful one, for the study of (homogeneous and nonhomogeneous) products of nonnegative matrices -- for problems on the products of nonnegative matrices. To study such products, new classes of matrices are introduced: that of the sum-positive matrices, that of the $\left[ \Delta \right] $-positive matrices on partitions (of the column index sets), that of the $g_{k}^{+}$-matrices... On the other hand, the $g_{k}^{+}$-matrices lead to necessary and sufficient conditions for the $k$-connected graphs. Using the $G^{+}$ method, we prove old and new results (Wielandt Theorem and a generalization of it, etc.) on the products of nonnegative matrices -- mainly, sum-positive, $\left[ \Delta \right] $-positive on partitions, irreducible, primitive, reducible, fully indecomposable, scrambling, or Sarymsakov matrices, in some cases the matrices being, moreover, $g_{k}^{+}$-matrices (not only irreducible).

Authors:Saieed Akbari, Hussah Al Menderj, Miin Huey Ang, Johnny Lim, Zhen Chuan Ng

Abstract: Let $G_S$ be a graph with loops obtained from a graph $G$ of order $n$ and loops at $S \subseteq V(G)$. In this paper, we establish a neccesary and sufficient condition on the bipartititeness of a connected graph $G$ and the spectrum Spec($G_S$) and Spec($G_{V(G)\backslash S}$). We also prove that for every $S \subseteq V(G)$, $E(G_S) \geq E(G)$ when $G$ is bipartite. Moreover, we provide an identification of the spectrum of complete graphs $K_n$ and complete bipartite graphs $K_{m,n}$ with loops. We characterize any graphs with loops of order n whose eigenvalues are all positive or non-negative, and also any graphs with a few distinct eigenvalues. Finally, we provide some bounds related to $G_S$.

Authors:Nathan R. T. Lesnevich

Abstract: We consider the Schur-positivity of monomial immanants of Jacobi-Trudi matrices, in particular whether a non-negative coefficient of the trivial Schur function implies non-negative coefficients for other Schur functions in said immanants. We prove that this true for hook-shape Schur functions using combinatorial methods in a representation theory setting. Our main theorem proves that hook-shape immanant characters can be written as finite non-negative integer sums of Stanley-Stembridge characters, and provides an explicit combinatorial formula for these sums. This resolves a special case of a longstanding conjecture of Stanley and Stembridge that posits such a sum exists for all immanant characters. We also provide several simplifications for computing immanant characters, and several corollaries applying the main result to cases where the coefficient of the trivial Schur function in monomial immanants of Jacobi-Trudi matrices is known to be non-negative.

Authors:Erik Panzer, Karen Yeats

Abstract: For every regular graph, we define a sequence of integers, using the recursion of the Martin polynomial. This sequence counts spanning tree partitions and constitutes the diagonal coefficients of powers of the Kirchhoff polynomial. We prove that this sequence respects all known symmetries of Feynman period integrals in quantum field theory. We show that other quantities with this property, the $c_2$ invariant and the extended graph permanent, are essentially determined by our new sequence. This proves the completion conjecture for the $c_2$ invariant at all primes, and also that it is fixed under twists. We conjecture that our invariant is perfect: Two Feynman periods are equal, if and only if, their Martin sequences are equal.

Authors:Alexander E. Black, Kevin Liu, Alex Mcdonough, Garrett Nelson, Michael C. Wigal, Mei Yin, Youngho Yoo

Abstract: A tanglegram consists of two rooted binary trees and a perfect matching between their leaves, and a planar tanglegram is one that admits a layout with no crossings. We show that the problem of generating planar tanglegrams uniformly at random reduces to the corresponding problem for irreducible planar tanglegram layouts, which are known to be in bijection with pairs of disjoint triangulations of a convex polygon. We extend the flip operation on a single triangulation to a flip operation on pairs of disjoint triangulations. Interestingly, the resulting flip graph is both connected and regular, and hence a random walk on this graph converges to the uniform distribution. We also show that the restriction of the flip graph to the pairs with a fixed triangulation in either coordinate is connected, and give diameter bounds that are near optimal. Our results furthermore yield new insight into the flip graph of triangulations of a convex $n$-gon with a geometric interpretation on the associahedron.

Authors:J. Pascal Gollin, Sebastian Wiederrecht

Abstract: Given a graph class~$\mathcal{C}$, the $\mathcal{C}$-blind-treewidth of a graph~$G$ is the smallest integer~$k$ such that~$G$ has a tree-decomposition where every bag whose torso does not belong to~$\mathcal{C}$ has size at most~$k$. In this paper we focus on the class~$\mathcal{B}$ of bipartite graphs and the class~$\mathcal{P}$ of planar graphs together with the odd-minor relation. For each of the two parameters, $\mathcal{B}$-blind-treewidth and ${(\mathcal{B}\cup\mathcal{P})}$-blind-treewidth, we prove an analogue of the celebrated Grid Theorem under the odd-minor relation. As a consequence we obtain FPT-approximation algorithms for both parameters. We then provide FPT-algorithms for \textsc{Maximum Independent Set} on graphs of bounded $\mathcal{B}$-blind-treewidth and \textsc{Maximum Cut} on graphs of bounded ${(\mathcal{B}\cup\mathcal{P})}$-blind-treewidth.

Authors:Dimitrios M. Thilikos, Sebastian Wiederrecht

Abstract: The \textsl{branchwidth} of a graph has been introduced by Roberson and Seymour as a measure of the tree-decomposability of a graph, alternative to treewidth. Branchwidth is polynomially computable on planar graphs by the celebrated ``Ratcatcher''-algorithm of Seymour and Thomas. We investigate an extension of this algorithm to minor-closed graph classes, further than planar graphs as follows: Let $H_{0}$ be a graph embeddedable in the projective plane and $H_{1}$ be a graph embeddedable in the torus. We prove that every $\{H_{0},H_{1}\}$-minor free graph $G$ contains a subgraph $G'$ where the difference between the branchwidth of $G$ and the branchwidth of $G'$ is bounded by some constant, depending only on $H_{0}$ and $H_{1}$. Moreover, the graph $G'$ admits a tree decomposition where all torsos are planar. This decomposition can be used for deriving an EPTAS for branchwidth: For $\{H_{0},H_{1}\}$-minor free graphs, there is a function $f\colon\mathbb{N}\to\mathbb{N}$ and a $(1+\epsilon)$-approximation algorithm for branchwidth, running in time $\mathcal{O}(n^3+f(\frac{1}{\epsilon})\cdot n),$ for every $\epsilon>0$.

Authors:Prajnanaswaroopa S

Abstract: The Alon-Tarsi number of a polynomial is a parameter related to the exponents of its monomials. For graphs, their Alon-Tarsi number is the Alon-Tarsi number of their graph polynomials. As such, it provides an upper bound on their choice and online choice numbers. In this paper, we obtain the Alon-Tarsi number of some complete multipartite graphs and line graphs of some complete graphs of even order.

Authors:Sen-Peng Eu, Louis Kao

Abstract: The Springer numbers, introduced by Arnold, are generalizations of Euler numbers in the sense of Coxeter groups. They appear as the row sums of a double triangular array $(v_{n,k})$ of integers, $1\leq|k|\leq n$, defined recursively by a boustrophedon algorithm. We say a sequence of combinatorial objects $(X_{n,k})$ is an Arnold family if $X_{n,k}$ is counted by $v_{n,k}$. A polynomial refinement $V_{n,k}(t)$ of $v_{n,k}$, together with the combinatorial interpretations in several combinatorial structures was introduced by Eu and Fu recently. In this paper, we provide three new Arnold families of combinatorial objects, namely the cycle-up-down permutations, the valley signed permutations and Knuth's flip equivalences on permutations. We shall find corresponding statistics to realize the refined polynomial arrays.

Authors:Hao Chen, Jie Ma

Abstract: A graph $H$ is called common and respectively, strongly common if the number of monochromatic copies of $H$ in a 2-edge-coloring $\phi$ of a large clique is asymptotically minimised by the random coloring with an equal proportion of each color and respectively, by the random coloring with the same proportion of each color as in $\phi$. A well-known theorem of Jagger, {\v S}t'ov{\' i}{\v c}ek and Thomason states that every graph containing a $K_4$ is not common. Here we prove an analogous result that every graph containing a $K_3$ and with at least four edges is not strongly common.

Authors:Pierre Aboulker, Guillaume Aubian, Pierre Charbit

Abstract: The dichromatic number $\vec\chi(D)$ of a digraph $D$ is the minimum size of a partition of its vertices into acyclic induced subgraphs. We denote by $\lambda(D)$ the maximum local edge connectivity of a digraph $D$. Neumann-Lara proved that for every digraph $D$, $\vec\chi(D) \leq \lambda(D) + 1$. In this paper, we characterize the digraphs $D$ for which $\vec\chi(D) = \lambda(D) + 1$. This generalizes an analogue result for undirected graph proved by Stiebitz and Toft as well as the directed version of Brooks' Theorem proved by Mohar. Along the way, we introduce a generalization of Haj\'os join that gives a new way to construct families of dicritical digraphs that is of independent interest.

Authors:James Cruickshank, Bill Jackson, Shinichi Tanigawa

Abstract: We show that, if $\Gamma$ is a point group of $\mathbb{R}^{k+1}$ of order two for some $k\geq 2$ and $\mathcal S$ is a $k$-pseudomanifold which has a free automorphism of order two, then either $\mathcal S$ has a $\Gamma$-symmetric infinitesimally rigid realisation in $\mathbb{R}^{k+1}$ or $k=2$ and $\Gamma$ is a half-turn rotation group.This verifies a conjecture made by Klee, Nevo, Novik and Zhang for the case when $\Gamma$ is a point-inversion group. Our result implies that Stanley's lower bound theorem for centrally symmetric polytopes extends to pseudomanifolds with a free simplicial involution, thus verifying (the inequality part) of another conjecture of Klee, Nevo, Novik and Zheng. Both results actually apply to a much larger class of simplicial complexes, namely the circuits of the simplicial matroid. The proof of our rigidity result adapts earlier ideas of Fogelsanger to the setting of symmetric simplicial complexes.

Authors:Sanath K. Devalapurkar, Max L. Misterka

Abstract: The goal of this article is to study some basic algebraic and combinatorial properties of "generalized $n$-series" over a commutative ring $R$, which are functions $s: \mathbf{Z}_{\geq 0} \to R$ satisfying a mild condition. A special example of generalized $n$-series is given by the $q$-integers $\frac{q^n-1}{q-1} \in \mathbf{Z}[\![q-1]\!]$. Given a generalized $n$-series $s$, one can define $s$-analogues of factorials (via $n!_s = \prod_{i=1}^n s(n)$) and binomial coefficients. We prove that Pascal's identity, the binomial identity, Lucas' theorem, and the Vandermonde identity admit $s$-analogues; each of these specialize to their appropriate $q$-analogue in the case of the $q$-integer generalized $n$-series. We also study the growth rates of generalized $n$-series defined over the integers. Finally, we define an $s$-analogue of the ($q$-)derivative, and prove $s$-analogues of the Poincar\'e lemma and the Cartier isomorphism for the affine line, as well as a pullback square due to Bhatt-Lurie.

Authors:Connor Donovan, Danielle Paulson, Pablo Soberón

Abstract: Krasnosselsky's art gallery theorem gives a combinatorial characterization of star-shaped sets in Euclidean spaces, similar to Helly's characterization of finite families of convex sets with non-empty intersection. We study colorful and quantitative variations of Krasnosselsky's result. In particular, we are interested in conditions on a set $K$ that guarantee there exists a measurably large set $K'$ such that every point in $K'$ can see every point in $K$. We prove results guaranteeing the existence of $K'$ with large volume or large diameter.

Authors:Dhruv Mubayi, Jacques Verstraete

Abstract: We consider the maximum chromatic number of hypergraphs consisting of cliques that have pairwise small intersections. Designs of the appropriate parameters produce optimal constructions, but these are known to exist only when the number of cliques is exponential in the clique size. We construct near designs where the number of cliques is polynomial in the clique size, and show that they have large chromatic number. The case when the cliques have pairwise intersections of size at most one seems particularly challenging. Here we give lower bounds by analyzing a random greedy hypergraph process. We also consider the related question of determining the maximum number of caps in a finite projective/affine plane and obtain nontrivial upper and lower bounds.