Papers

Let $G=(V,E)$ be a finite simple graph with Laplacian eigenvalues $\lambda_1(L(G))\ge\cdots\ge\lambda_{|V|}(L(G))$, and define \[ \eps_k(G)= \sum_{j=1}^{\min\{k,|V|\}}\lambda_j(L(G))-|E|. \] Let $\nu(G)$ be the matching number of $G$, and let $n(G)$ be the number of non-isolated vertices of $G$. Lew proved that \(\eps_k(G)\le k\nu(G)+\lfloor k/2\rfloor\), and conjectured that the additive term can be removed in the non-endpoint range. We prove this conjecture: \[ \eps_k(G)\le k\nu(G) \qquad (1\le k\le n(G)-2). \] We also characterize all equality cases. Up to isolated vertices, equality holds precisely for stars, for \(K_1\vee(K_k\cup\overline{K_{n-k-1}})\) with \(k\) odd, and for \(K_n-E(K_{1,t})\) with \(n\) odd, \(k=n-2\), and \(1\le t\le n-2\). We also analyze the endpoint range \(k\ge n(G)-1\), where \(\eps_k(G)=|E|\), and determine the specific cases where the inequality \(\varepsilon_k(G)\le k\nu(G)\) fails or holds with equality.

We prove a coarse analogue of the classic fact that every graph can be decomposed along its cut-vertices into $2$-connected components. Precisely, we prove that for every graph $G$ and a positive integer $d$, $G$ admits a tree decomposition whose adhesion sets have weak diameter at most $3d+2$ so that no two vertices $u,v$ lying in the same bag can be separated by a set of weak diameter at most $d$ whose distance from $u$ and $v$ is more than $d$. By the Coarse Menger's Theorem for two paths, this condition admits also a dual formulation, phrased in terms of the existence of two paths that are far from each other and connect the vicinity of $u$ with the vicinity of $v$.

A set of vertices $S$ of a directed graph $G$ is geodetic if every vertex of $G$ lies on a shortest path from a vertex of $S$ to a vertex of $S$. A directed graph is geodetic if there is at most one shortest path from every vertex of $G$ to every vertex of $G$. We prove the NP-completeness of the following decision problem. Given a directed acyclic planar geodetic graph $G$ and an integer $k$, does $G$ have a geodetic set with at most $k$ vertices? This implies that the question of whether $G$ has a strong or a monitoring geodetic set with at most $k$ vertices is also NP-complete for directed acyclic planar geodetic graphs. Furthermore, we prove that the number of vertices in a minimum geodetic set and the number of vertices in a minimum edge geodetic set can be computed in linear time for directed acyclic series-parallel graphs.

This paper introduces the weak augmented Zarankiewicz number $z_{wA}(m,n)$ and the weak limited augmented Zarankiewicz number $z_{wL}(m,n)$, which are combinatorial extensions of the classical Zarankiewicz number obtained by relaxing the original admissibility conditions for augmented bipartite graphs. We show that the resulting weak framework still guarantees irreducibility of the associated doubly simple biquadratic forms, with SOS rank equal to the total number of edges. This yields the inequality chain \[ \mathrm{BSR}(m,n) \geq z_{wA}(m,n) \geq z_{wL}(m,n) \geq z_L(m,n) \geq z(m,n). \] We provide three complementary constructions demonstrating the power of the weak framework. First, a $5\times 3$ construction using degenerate 2-edges yields $z_{wL}(5,3)\ge 10>9=z_L(5,3)$, giving $\mathrm{BSR}(5,3)\ge 10$. Second, a $15\times 6$ construction on the incidence graph of $K_6$ with 14 nondegenerate 2-edges gives $z_{wL}(15,6)\ge 44>43$, improving the previously known bound. Third, a critical $6\times 3$ construction with complementary 2-cycles gives $z_{wL}(6,3)\ge 12>11=z_L(6,3)$, yielding $\mathrm{BSR}(6,3)\ge 12$ and demonstrating that complementary 2-cycles are safe.

Moon and Moser proved a sharp edge-extremal theorem for Hamilton cycles in balanced bipartite graphs with minimum degree at least $k$. Li and Ning obtained spectral analogues for Hamiltonicity in balanced bipartite graphs of order $2n$ and for traceability in nearly balanced bipartite graphs with part sizes $n$ and $n-1$, under the assumption $n\ge (k+1)^2$. We show that their sharp spectral thresholds remain valid in the linear ranges $n\ge 2k$ and $n\ge 2k+1$, respectively. More precisely, we determine the extremal values of the adjacency spectral radius and the signless Laplacian spectral radius for non-Hamiltonian balanced bipartite graphs with minimum degree $\delta(G)\ge k$, and for non-traceable nearly balanced bipartite graphs with $\delta(G)\ge k$. In each case, the extremal graph is unique up to isomorphism. Our proof is based on feasible graph parameters: parameters that increase under edge addition and are nondecreasing under Kelmans operations. This yields Moon–Moser type extremal theorems for a general class of parameters, from which the spectral results follow.

We obtain a coarse version of the block-cutvertex tree-decomposition of a connected graph.

Given any $\varepsilon > 0$, let $M(n)$ be a random $n \times (n+u)$ matrix over $\mathbb{Z}_p$, with all entries independent and $\varepsilon$-balanced (lying in each residue class mod $p$ with probability at most $1-\varepsilon$). Wood proved that as $n \to \infty$ the distribution of $\mathrm{cok}(M(n))$ approaches Cohen and Lenstra's conjectured distribution of class groups. Given $\alpha,\beta >0$ such that $\alpha + \beta <1$, we prove that the distribution of $\mathrm{cok}(M(n))$ still approaches the Cohen–Lenstra distribution even if we weaken the hypothesis by allowing up to $\alpha n$ entries per column and up to $\beta n$ entries per row of $M(n)$ to not be $\varepsilon$-balanced. We also weaken the independence condition by allowing certain types of dependence between the entries of each column. In addition, we prove that, for any $\delta > 0$, the cokernels of random band matrices of width $\log(n)^{1+\delta}$ with $\varepsilon$-balanced entries in the band and arbitrary entries outside of it will also approach the Cohen–Lenstra distribution, which answers a question of Kang–Lee–Yu.

Let $p$ be a prime number. We introduce a sparseness condition on the supports of $p$-adic Hahn series, and prove that this condition implies transcendence over $\breve{\mathbf Q}_p$, the completed maximal unramified extension of $\mathbf{Q}_p$. As an application, we prove the order-type conjecture of $\mathbf{Q}_p$-algebraic $p$-adic Hahn series with bounded support under the condition that the support has only finitely many accumulation points. All results in this paper have been fully formalized in the Lean theorem prover (v 4.31.0), building over Mathlib.

The dichromatic number of a digraph is the minimum number of colors needed to partition its vertex set into acyclic subdigraphs. A biclique is a set of vertices inducing all possible pairs of opposite arcs. For a digraph $D$, define $\Delta(D) = \max_{v\in V(D)} \sqrt{d^+(v) \cdot d^-(v)}$. We prove that, for every fixed integer $b\in\mathbb{N}$, every digraph $D$ with $\Delta(D) = \Delta$ being sufficiently large with respect to $b$ either contains a biclique whose size exceeds $\Delta-2b$ or has dichromatic number at most $\Delta-b$. This extends a classical result of Reed to the directed setting and supports a conjecture of the present authors. Furthermore, the theorem is tight, as for all integers $b$ and $\Delta\geq 3b$ there exists a digraph $D$ with $\Delta(D)= \Delta$, dichromatic number $\Delta-b+1$, and whose largest biclique has size $\Delta-2b+1$.

The paper aims to provide a categorification of the Brenti–Welker identity involving Eulerian numbers in (Adv. Appl. Math. 42 (2009): 545–556) by lifting it from an enumerative equality to an isomorphism of symmetric group representations. To do so, we study the decomposition of the tensor product of $(\mathbb{C}^r)^{\otimes n}$ and modules affording Foulkes characters as modules of the symmetric group. The main ingredient of the proof is a combinatorial identity which may be of independent interest.

Let \(G\) be a graph admitting a perfect matching. An edge is called a {\it \(k\)-matching edge} if it belongs to exactly \(k\) perfect matchings, and a {\it \(k^{+}\)-matching edge} if it belongs to at least \(k\) perfect matchings. Thus, an admissible edge is a \(1^{+}\)-matching edge, and a connected graph is matching covered if every edge is admissible. We call a connected graph {\it \(k\)-matching covered} if every edge is a \(k\)-matching edge; in particular, a \(2\)-matching covered graph is called matching double covered. Motivated by matching-covered graph theory and the Berge–Fulkerson conjecture (1970s), we introduce the class \(\mathfrak{B}\) of connected graphs in which every edge is either a \(1\)-matching edge or a \(2\)-matching edge, and no perfect matching contains edges of both types. In particular, every matching double covered graph belongs to \(\mathfrak{B}\). Using ear decompositions and tight-cut decompositions, we establish a complete structural characterization of graphs in \(\mathfrak{B}\). These characterizations reveal how restrictions on the number of perfect matchings containing each edge determine the global structure of the corresponding matching-covered graphs.

We show that for every $k \in \mathbb{N}$, every graph $G$ contains $k$ vertex-disjoint cycles of different lengths, or there exists a set $X \subseteq V(G)$ with $|X| \in \mathcal{O}(k^6\mathsf{polylog}(k))$ such that $G-X$ has at most $k-1$ cycle lengths. We also prove analogous results for facial lengths of embedded graphs. Let $G$ be a graph with a closed 2-cell embedding $\psi$ on a surface $\Sigma$ of Euler genus $g$, let $c$ be a colouring of the faces $\mathcal{F}(\psi)$ of $\psi$, and let $R(G,\psi)$ be the radial graph of $(G, \psi)$. Then there exist $k$ faces $F_1, \ldots , F_k \in \mathcal{F}(\psi)$ that are given pairwise distinct colours by $c$ and are pairwise at distance at least $d$ in $\psi$, or there exists a set $X \subseteq V(G)$ of order at most $\mathcal{O}(k^2dg)$ such that $|\{ c(F) \mid F \in \mathcal{F}(\psi) \text{ and } V(F) \cap \bigcup_{x \in X} N^d_{R(G,\psi)}(x) = \emptyset \}| \leq k(k+2)$. Finally, using a result from additive combinatorics, we show that there are subdivided ladders with only a small number of cycle lengths. This suggests that it may be difficult to improve our bounds.

Throughout, all graphs are simple, finite and have vertex sets of the form $\{ 0, 1, 2, \ldots, n - 1 \}$ for some $n \in \mathbb{N}$. For graphs $G$ and $H$, and a permutation group $\Gamma$ on the vertex set of $H$, we say that $H$ is $\Gamma$-embeddable in $G$ if there exists a graph homomorphism from $H$ to $G$ of the form $\psi \circ \varphi$, where $\varphi \in \Gamma$ and $\psi$ is an increasing injection. Recently, standard and ordered Ramsey numbers of graphs were unified through the introduction of permutational Ramsey numbers, defined as follows. For graphs $H_1, H_2, \ldots, H_k$ and permutation groups $\Gamma_1, \Gamma_2, \ldots, \Gamma_k$ on their respective vertex sets, the permutational Ramsey number $R(H_1^{\Gamma_1}, H_2^{\Gamma_2}, \ldots, H_k^{\Gamma_k})$ is the minimum $n \in \mathbb{N}$ such that for every $k$-edge-coloring of a complete graph on $n$ vertices, there exists some $j \in \{1, 2, \ldots, k\}$ for which $H_j$ is $\Gamma_j$-embeddable in the spanning subgraph of the complete graph comprising the edges of color $j$. Here, we consider reflective (resp. dihedral) Ramsey numbers, which are a specific class of permutational Ramsey numbers in which each group $\Gamma_j$ is the reflection group (resp. dihedral group) on the naturally ordered vertex set of $H_j$. Focusing on the two-color case, we apply the SAT-based approach originally proposed by Poljak for ordered Ramsey numbers and recently extended to cyclic Ramsey numbers. We utilize the Kissat SAT solver to obtain exact values and lower bounds for small reflective and dihedral Ramsey numbers whose two arguments belong to the following graph classes: monotone and alternating paths, monotone cycles, start-central stars, complete graphs and nested matchings. We also derive several general results and formulate conjectures based on the computational findings.

In this article, we study the edge-to-edge dihedral tilings of the sphere by kites and regular $m$-gons with $m\ge 4$. All such tilings have been identified and fully classified, using various combinatorial and geometric tools. New phenomena are observed among the tilings.

We resolve a conjecture of de Saint Germain: all Y-friezes arise from $\mathrm{SL}_2$-friezes. Additionally, we give a threefold characterisation of those $\mathrm{SL}_2$-friezes that give rise to the same Y-frieze: an elementary characterisation using quiddities, a combinatorial characterisation using triangulated polygons, and a geometrical characterisation using chains of horocycles.

We lift a product rule in the Cartan subalgebra of quantum $\mathfrak{sl}_2$ to a filtration of the plethystic representation $\Delta^{(n,m)}\mathrm{Sym}^d E$ of the affine group scheme of the algebraic group $\mathrm{SL}_2$, where $E$ is the natural representation and $\Delta^{(n,m)}$ the Weyl functor. This is a significant step towards a categorification of quantum $\mathfrak{sl}_2$. Our filtration is an addition to a growing family of field-independent isomorphisms of $\mathrm{SL}_2$ representations that include Hermite reciprocity and the Wronskian isomorphism. It is the first such field-independent result requiring multiple filtration layers. It is proved by combinatorial techniques using the authors' symmetric functions model for Weyl modules.

We give a new proof of the celebrated theorem of Knutson and Tao that the spectra of triples $A, B, A+B$ of Hermitian matrices exactly correspond to positions of boundary rays of honeycombs. Most importantly, our proof gives new insights into why honeycombs are related to Hermitian matrices in the first place. Our proof is axiomatic: We distill four essential properties shared by honeycombs and spectra of Hermitian triples, and show that any two objects sharing these four properties must be equivalent. In this way, we argue that honeycombs are `model organisms' for Hermitian triples: they are families of objects satisfying the same defining properties, but in more obvious ways.

Let $\operatorname{Cyc}(G)$ denote the number of cyclic subsets in a graph $G$, which are subsets that induce a Hamiltonian subgraph. Draganić, Keevash and Müyesser recently proved that every regular Dirac graph has $\Omega(2^n)$ cyclic subsets, resolving a problem of Erdős and Faudree. We determine the sharp asymptotic lower bound throughout the linear range below Dirac's threshold. Let $G$ be an $n$-vertex $d$-regular graph with $d=\Omega(n)$ and $d<n/2$, then $$ \operatorname{Cyc}(G)\ge (q-o(1))2^{n/q}, \quad \text{where } \quad q=\left\lfloor \frac{n}{d+1}\right\rfloor \ge 2. $$ This bound is asymptotically best possible, including the leading coefficient $q$, as witnessed at the staircase levels by the disjoint union of $q$ equal cliques. Consequently, the optimal exponential rate changes by discrete jumps as $d$ crosses the thresholds $n/k$, rather than varying smoothly with $d$. We also prove the optimal exponential rate at the Dirac boundary: every $n$-vertex $n/2$-regular graph satisfies $\operatorname{Cyc}(G)\ge 2^{(1-o(1))n},$ which is sharp up to a subexponential factor by $K_{n/2,n/2}$.

Reiher's clique density theorem determines the sharp lower envelope for the density of $K_r$ at fixed edge density. We prove a higher-order version in which the prescribed quantity is itself a clique density. For every $3\le s<r$, we determine the minimum possible $K_r$-density among graphons with prescribed $K_s$-density. For $s\ge3$ the constraint is genuinely nonlinear and leaves the edge density undetermined; nevertheless, on the positive range the sharp lower boundary is the classical multipartite edge-to-clique profile, reparametrised by $K_s$-density. We also prove stability on the positive branches of this profile: at every interior point, near extremality forces cut-distance closeness to the corresponding extremal family at the induced edge density.

The Vietoris-Rips filtration $\mathcal{VR}(-)$ is a standard tool for analyzing the shape of data within topological data analysis. Beginning with seminal work of Sheehy, a substantial amount of research has centered on constructing linear-size sparse approximations to $\mathcal{VR}(-)$ and related filtrations for metric spaces of bounded doubling dimension. We show that this geometric assumption is necessary in a precise sense. Working in the framework of homotopy interleavings, we show that for any fixed $c \in [1, \sqrt{2})$, there exists a family of finite metric spaces for which any finitely presented $c$-approximation to $\mathcal{VR}(-)$ has exponential size. We also show that for any fixed $c \geq 1$, there exists a family of finite metric spaces for which any finitely presented $c$-approximation to $\mathcal{VR}(-)$ has superlinear size, yielding an obstruction to linear-size approximations for any fixed approximation factor. Both results extend to the intrinsic Čech filtration and to any bifiltration containing $\mathcal{VR}(-)$ as a $1$-parameter slice, including the function-Rips, degree-Rips, and subdivision-Rips bifiltrations.

For integers $1\le \ell<k$, let $\Pi^k_\ell$ denote the single-forbidden $\ell$-degree Turán spectrum of $k$-uniform hypergraphs. We introduce transfer functions for this spectrum: explicit functions $f$ such that, for every $F$, there is another single $k$-graph $F^*$ with $\pi_\ell(F^*)=f(\pi_\ell(F))$. This gives a mechanism for producing new single-forbidden densities while retaining full control of the resulting value. Our transfer functions are realized by a new family of suspension-type operations, called tree suspensions. From these operations we obtain three explicit maps: one acting on $\Pi^k_\ell$ for every $1\le\ell<k$, a second acting when $\ell\ge k/2$, and a third acting in the ordinary Turán case $\ell=1$. The common feature is a robust tree structure which gives the lower bound by a two-part construction and, in the regimes above, admits a matching embedding or Lagrangian upper bound. As a first application, the universal transfer function propagates accumulation points. Using the recent zero-accumulation results for $\ell\ge2$ together with the ordinary Turán accumulation result of Conlon and Schülke, we prove that $\Pi^k_\ell$ has infinitely many accumulation points for every $k\ge3$ and every $1\le\ell<k$. This recovers, in particular, the known infinitude of accumulation points in the ordinary and codegree spectra. As a second application, combining two independent transfer functions forces algebraic degrees to grow. For every $k\ge3$ and every $\ell\in\{1,\lceil k/2\rceil,\ldots,k-2\}$, the spectrum $\Pi^k_\ell$ contains algebraic numbers of arbitrarily large degree over $\mathbb Q$. Thus the arithmetic complexity previously known for finite forbidden families already occurs in the single-forbidden spectrum, both for ordinary Turán density and for a broad range of degree Turán densities.

The red-blue vertex partitions now known as crumby colorings originate in a conjecture of Thomassen related to Wegner's conjecture on squares of planar graphs. In such a coloring, the blue vertices induce a graph of maximum degree at most one, while the red vertices induce a graph with no isolated vertices and no simple path with three edges. Barát, Blázsik and Damásdi proved that every 2-connected outerplanar graph of maximum degree at most three admits a crumby coloring, and conjectured that the 2-connectivity assumption can be removed. We prove this conjecture: every finite simple subcubic outerplanar graph admits a crumby coloring. To prove the conjecture, we introduce a rooted grammar for subcubic outerplanar graphs. The grammar describes such graphs recursively using rooted branches and two-terminal path fragments; cyclic blocks are handled by deleting the root to obtain a path fragment. We correspondingly extend crumby colorings to crumby-admissible colorings: in a rooted branch the root, and in a path fragment the two terminals, are allowed to be temporary isolated red vertices. This relaxation makes induction along the grammar possible while retaining only finite boundary information. The induction reduces to verifying an explicit finite family of lower certificates, namely nonempty sets of boundary types and root states. The required verification has two parts: the family must be closed under all steps of the decomposition, and every certified completed branch must contain a final-legal root state, so that the temporary defect disappears and the resulting coloring is a genuine crumby coloring. This final step is computer-assisted: a stand-alone certificate checker, supplied with the paper, verifies the stated closure and crumby conditions for the supplied certificate. All structural reductions and the certificate-induction principle are proved by hand.

Let $J_{\ge s}(n,k)$ be the graph whose vertices are the $k$-subsets of $[n]$, with two distinct vertices adjacent whenever their intersection has size at least $s$. Equivalently, $J_{\ge s}(n,k)$ is the complement of a threshold Kneser graph. We determine both the symmetric minimum rank over an arbitrary infinite field and the real positive semidefinite minimum rank of this family. Specifically, for $k\ge2$, $1\le s\le k-1$, and $n\ge2k-s$, we prove $$ \operatorname{mr}^{\mathbb F}\left(J_{\ge s}(n,k)\right) = \binom{n-2(k-s)}{s} $$ for every infinite field $\mathbb F$, and $$ \operatorname{mr}_{+}^{\mathbb R}\left(J_{\ge s}(n,k)\right) = \binom{n-2(k-s)}{s}. $$ The lower bound follows from a diagonal submatrix indexed by two carefully chosen families of $k$-subsets. For the upper bound, we construct a symmetric matrix using an exterior power of a bilinear form, a Lagrange interpolation identity, and a generic nonvanishing argument. Over $\mathbb R$, an interlacing choice of parameters makes the bilinear form positive definite and yields a positive semidefinite matrix attaining the required upper bound. As consequences, we answer a question from an American Institute of Mathematics workshop, determine the real faithful orthogonality dimension of all graphs $J_{\ge s}(n,k)$ in the stated range, and recover the known minimum-rank formula for Johnson graphs.

A conjecture of Alon and Wei states that, for any $d$-regular graph $G$ with $n$ vertices, there exists a spanning subgraph $H$ such that for all $0\le i\le d$, we have $m(H, i)$, the number of vertices in $H$ with degree $i$, is between $\frac{n}{d+1}-2$ and $\frac{n}{d+1}+2$. We prove the conjecture for all fixed $d$ when $n$ is sufficiently large. More precisely, if $q=(q_0,\ldots,q_d)$ satisfies $$ \sum_{i=0}^d q_i=n,\qquad \sum_{i=0}^d i q_i\equiv 0\pmod 2,\qquad \left|q_i-\frac{n}{d+1}\right|\le 1 \quad (0\le i\le d), $$ then there is a spanning subgraph $H\subseteq G$ such that $$ m(H,i)=q_i \qquad (0\le i\le d). $$

In this paper, we investigate the generalized spectral closedness of graph classes defined by a family $\mathcal{F}$ of forbidden induced subgraphs. To systematically study this property, we introduce a novel combinatorial concept of patterned closed walks (or $\beta$-closed walks), which naturally interlaces the edges of a graph with those of its complement. By establishing the induced-subgraph expansion of these $\beta$-closed walk counts, we obtain an algebraic sufficient condition for generalized spectral closedness based on the existence of a walk-realizable $\mathcal{F}$-supporter. Crucially, the search for such a walk-realizable supporter is reduced to a linear programming feasibility problem. As primary applications of this computational framework, we prove that the classes of threshold graphs and chain graphs are generalized spectrally closed.

We study solution discovery in the token-sliding model from a logical and cost-value optimization perspective. In solution discovery, we are given a graph, an initial placement of $k$ tokens, and a movement budget $b$. The task is to find a reachable target configuration satisfying a prescribed condition. Our results are inspired by Partial Vertex Cover Discovery, where the condition is that the~$k$ tokens cover at least $t$ edges of the input graph. This objective is not merely a sum of independent occupied vertex contributions: each selected vertex contributes its degree, but edges with both endpoints selected have to be subtracted once. To capture this phenomenon, we introduce FO Value Discovery, an optimization problem in which the value of a selected tuple is given by unary vertex weights together with first-order definable correction terms. We further generalize the setting to FO Cost-Value Decision, where vertices carry both costs and values, and the task is to decide whether there is a tuple whose first-order value expression reaches a prescribed value threshold while respecting a cost bound. Finally, we study the parameterized complexity of Partial Vertex Cover Discovery and Vertex Cover Discovery. As a consequence of the logical meta-theorems, we obtain fixed-parameter tractability of Partial Vertex Cover Discovery on several graph classes, including classes of locally bounded cliquewidth. We also show that Partial Vertex Cover Discovery is W[1]-hard parameterized by $k+b$ and fixed-parameter tractable on $d$-degenerate graphs parameterized by $k+d$. For Vertex Cover Discovery, we prove NP-hardness on planar graphs, W[1]-hardness parameterized by the clique cover number, even when a clique cover is supplied with the input, and W[1]-hardness with respect to parameter cutwidth.

Subdivisions of complete graphs play a central role in combinatorics, having deep connections to structural, extremal, and topological aspects of graph theory. A celebrated conjecture of Mader, proved independently by Bollobás and Thomason and by Komlós and Szemerédi, states that every graph of average degree of order $h^2$ contains a subdivision of $K_h$. In this paper, we consider the induced variant of this problem. A theorem of Kühn and Osthus implies that, for every fixed graph $H$ and every $s\ge 1$, graphs of sufficiently large average degree contain either a copy of $K_{s,s}$ or an induced subdivision of $H$. However, even for $H=K_h$, the best previous quantitative bounds were far from optimal. We prove nearly tight bounds for forcing induced subdivisions of $K_h$. We show that every $K_{s,t}$-free graph of average degree $\Omega_{s,t}(h^{2(s-1)}\log^{7(s-1)} h)$ contains an induced subdivision of $K_h$, and that every $C_{2k}$-free graph with $k \geq 3$ and average degree $\Omega_k(h\log^5 h)$ contains an induced subdivision of $K_h$. These bounds substantially improve the previously known results and are nearly optimal in both settings. They also hold if $K_h$ is replaced by any other graph on $h$ vertices.

Recently, Frankl and Wang considered a product version of the classical Hilton-Milner theorem. They conjectured that, if $\mathcal{F} \subset \binom{[n]}{k}$ and $\mathcal{G} \subset \binom{[n]}{\ell}$ are non-trivial cross-intersecting families with $n \geq 2k > 2\ell \geq 4$, the maximum of $|\mathcal{F}||\mathcal{G}|$ is attained by the natural Hilton-Milner-type configurations. In this paper, we present two main results concerning this conjecture. Firstly, we show that the conjecture does not hold in general. By introducing a two-center construction, we prove that for every fixed integer $\ell \geq 3$ and all sufficiently large $k$, the conjecture is false in a linear range $2k+1 \leq n \leq (c_\ell - \epsilon)k$ for any $0 < \epsilon < c_\ell - 2$, where $c_\ell > 2$ is an explicit constant. Secondly, we prove that the conjecture holds when $n > 100\ell k^2$ and $3 \leq \ell < k$, and we completely characterize the extremal families. Our proofs rely on the size of minimal covers and analyzing the structural properties of $2$-cover graphs.

If $G$ and $H$ are two cubic multi-graphs, then an $H$-coloring of $G$ is a mapping $f: E(G)\rightarrow E(H)$, such that for every $v\in V(G)$ there is a vertex $x\in V(H)$, such that $f(\partial_G(v))=\partial_H(x)$. If $G$ admits an $H$-coloring then it is common to write $H\prec G$. The Petersen coloring conjecture predicts that for any bridgeless cubic graph $G$ one has $P_{10}\prec G$. Here $P_{10}$ is the Petersen graph. Let $f: E(G)\rightarrow E(H)$ be any mapping. Define: $V(f)=\{v\in V(G):\exists x\in V(H), f(\partial_G(v))=\partial_H(x)\}$. Let $S_{10}$ be the smallest cubic multi-graph that has no perfect matching. It has ten vertices. Define $S_{12}$ as the cubic graph that is obtained from $S_{10}$, by replacing its unique vertex $z$ adjacent to three bridges with a triangle. In this paper we show that (1) for every cubic multi-graph $G$ with a perfect matching, there is a mapping $f:E(G)\rightarrow E(S_{12})$, such that $|V(f)|\geq \frac{4}{5}\cdot |V(G)|$, and (2) for every cubic multi-graph $G$, there is a mapping $f:E(G)\rightarrow E(S_{10})$, such that $|V(f)|\geq \frac{5}{6}\cdot |V(G)|$. Our second result improves the $\frac{4}{5}$-bound by Hakobyan and the second author from 2018.

The Petrie symmetric function $G(k,n)$, introduced by Grinberg, is defined as the sum of monomial symmetric functions $m_\lambda$ indexed by partitions $\lambda\vdash n$ satisfying $\lambda_1<k$. This article demonstrates that the Schur positivity pattern of $\nabla^r G(k,n)$ for all $r\geq 1$ depends exclusively on whether $k$ divides $n$, thus answering an open problem of Bergeron noted in Grinberg's work.