Chromatic number is Ramsey distinguishing

A graph $G$ is Ramsey for a graph $H$ if every colouring of the edges of $G$ in two colours contains a monochromatic copy of $H$. Two graphs $H_1$ and $H_2$ are Ramsey equivalent if any graph $G$ is Ramsey for $H_1$ if and only if it is Ramsey for $H_2$. A graph parameter $s$ is Ramsey distinguishing if $s(H_1)\ne s(H_2)$ implies that $H_1$ and $H_2$ are not Ramsey equivalent. In this paper we show that the chromatic number is a Ramsey distinguishing parameter. We also extend this to the multicolour case and use a similar idea to find another graph parameter which is Ramsey distinguishing.     

The extremal function for K9= minors

We prove the extremal function for $K_9^{=}$ minors, where $K_9^{=}$ denotes the complete graph $K_9$ with two edges removed. In particular, we show that any graph with $n\ge 8$ vertices and at least $6n-20$ edges either contains a $K_9^{=}$ minor or is isomorphic to a graph obtained from disjoint copies of $K_8$ and $K_{2,2,2,2,2}$ by identifying cliques of size 5. We utilize computer assistance to prove one of our lemmas.     

Enumerative problems for arborescences and monotone paths on polytope graphs

Every generic linear functional $f$ on a convex polytope $P$ induces an orientation on the graph of $P$. From the resulting directed graph one can define a notion of $f$-arborescence and $f$-monotone path on $P$, as well as a natural graph structure on the vertex set of $f$-monotone paths. These concepts are important in geometric combinatorics and optimization. This paper bounds the number of $f$-arborescences, the number of $f$-monotone paths, and the diameter of the graph of $f$-monotone paths for polytopes $P$ in terms of their dimension and number of vertices or facets.     

Orientations of graphs avoiding given lists on out-degrees

Let $G$ be a graph and $F:V\left(G\right)\to 2^{\mathbb{N}}$ be a mapping. The graph $G$ is said to be $F$- avoiding if there exists an orientation $O$ of $G$ such that $d_O^{+}\left(v\right)\notin F\left(v\right)$ for every $v\in V\left(G\right)$, where $d_O^{+}\left(v\right)$ denotes the out-degree of $v$ in the directed graph $G$ with respect to $O$. In this paper it is shown that if $G$ is bipartite and $\mid F\left(v\right)\mid \le d_G\left(v\right)/2$ for every $v\in V\left(G\right)$, then $G$ is $F$-avoiding. The bound $\mid F\left(v\right)\mid \le d_G\left(v\right)/2$ is best possible. For every graph $G$, we conjecture that if $\mid F\left(v\right)\mid \le \frac{1}{2}\left(d_G\left(v\right)-1\right)$ for every $v\in V\left(G\right)$, then $G$ is $F$-avoiding. We also argue about this conjecture for the best possibility of the conditions and also show some partial solutions.     

Degree sum conditions for the existence of homeomorphically irreducible spanning trees

In 1990, Albertson, Berman, Hutchinson, and Thomassen proved a theorem which gives a minimum degree condition for the existence of a spanning tree with no vertices of degree 2. Such a spanning tree is called a homeomorphically irreducible spanning tree (HIST). In this paper, we prove that every graph of order $n$ ($n\ge 8$) contains a HIST if $d(u)+d(v)\ge n?1$ for any nonadjacent vertices $u$ and $v$. The degree sum condition is best possible.     

Independent set and matching permutations

Let $G$ be a graph $G$ whose largest independent set has size $m$. A permutation $\pi$ of $\left\{1,\text{…},m\right\}$ is an independent set permutation of $G$ if $$a_{\pi \left(1\right)}\left(G\right)\le a_{\pi \left(2\right)}\left(G\right)\le \mathrm{?}\le a_{\pi \left(m\right)}\left(G\right),$$ where $a_k\left(G\right)$ is the number of independent sets of size $k$ in $G$. In 1987 Alavi, Malde, Schwenk, and Erd?s proved that every permutation of $\left\{1,\text{…},m\right\}$ is an independent set permutation of some graph with $\alpha \left(G\right)=m$, that is, with the largest independent set having size $m$. They raised the question of determining, for each $m$, the smallest number $f\left(m\right)$ such that every permutation of $\left\{1,\text{…},m\right\}$ is an independent set permutation of some graph with $\alpha \left(G\right)=m$ and with at most $f\left(m\right)$ vertices, and they gave an upper bound on $f\left(m\right)$ of roughly $m^{2m}$. Here we settle the question, determining $f\left(m\right)=m^m$, and make progress on a related question, that of determining the smallest order such that every permutation of $\left\{1,\text{…},m\right\}$ is the unique independent set permutation of some graph of at most that order. More generally we consider an extension of independent set permutations to weak orders, and extend Alavi et al.'s main result to show that every weak order on $\left\{1,\text{…},m\right\}$ can be realized by the independent set sequence of some graph with $\alpha \left(G\right)=m$ and with at most $m^{m+2}$ vertices. Alavi et al. also considered matching permutations, defined analogously to independent set permutations. They observed that not every permutation of $\left\{1,\text{…},m\right\}$ is a matching permutation of some graph with the largest matching having size $m$, putting an upper bound of $2^{m?1}$ on the number of matching permutations of $\left\{1,\text{…},m\right\}$. Confirming their speculation that this upper bound is not tight, we improve it to $O\left(2^m∕\sqrt{m}\right)$.     

On induced subgraphs of the Hamming graph

In connection with his solution of the Sensitivity Conjecture, Hao Huang (arXiv: 1907.00847, 2019) asked the following question: Given a graph $G$ with high symmetry, what can we say about the smallest maximum degree of induced subgraphs of $G$ with $\alpha \left(G\right)+1$ vertices, where $\alpha \left(G\right)$ denotes the size of the largest independent set in $G$? We study this question for $H\left(n,k\right)$, the $n$‐dimensional Hamming graph over an alphabet of size $k$. Generalizing a construction by Chung et al. (JCT‐A, 1988), we prove that $H\left(n,k\right)$ has an induced subgraph with more than $\alpha \left(H\left(n,k\right)\right)$ vertices and maximum degree at most $?\sqrt{n}?$. Chung et al. proved this statement for $k=2$ (the $n$‐dimensional cube).     

Triangles in C 5-free graphs and hypergraphs of girth six

We introduce a new approach and prove that the maximum number of triangles in a $C_5$-free graph on $n$ vertices is at most $$\left(1+o\left(1\right)\right)\frac{1}{3\sqrt{2}}{n}^{3∕2}.$$ We show a connection to $r$-uniform hypergraphs without (Berge) cycles of length less than six, and estimate their maximum possible size. Using our approach, we also (slightly) improve the previous estimate on the maximum size of an induced-$C_4$-free and $C_5$-free graph.     

Bounding the mim-width of hereditary graph classes

A large number of $\mathsf{NP}$-hard graph problems are solvable in $\mathsf{XP}$ time when parameterized by some width parameter. Hence, when solving problems on special graph classes, it is helpful to know if the graph class under consideration has bounded width. In this paper we consider maximum-induced matching width (mim-width), a particularly general width parameter that has a number of algorithmic applications whenever a decomposition is “quickly computable” for the graph class under consideration. We start by extending the toolkit for proving (un)boundedness of mim-width of graph classes. By combining our new techniques with known ones we then initiate a systematic study into bounding mim-width from the perspective of hereditary graph classes, and make a comparison with clique-width, a more restrictive width parameter that has been well studied. We prove that for a given graph $H$, the class of $H$-free graphs has bounded mim-width if and only if it has bounded clique-width. We show that the same is not true for $(H_1,H_2)$-free graphs. We identify several general classes of $(H_1,H_2)$-free graphs having unbounded clique-width, but bounded mim-width; moreover, we show that a branch decomposition of constant mim-width can be found in polynomial time for these classes. Hence, these results have algorithmic implications: when the input is restricted to such a class of $(H_1,H_2)$-free graphs, many problems become polynomial-time solvable, including classical problems, such as $k$- Colouring and Independent Set , domination-type problems known as Locally Checkable Vertex Subset and Vertex Partitioning (LC-VSVP) problems, and distance versions of LC-VSVP problems, to name just a few. We also prove a number of new results showing that, for certain $H_1$ and $H_2$, the class of $(H_1,H_2)$-free graphs has unbounded mim-width. Boundedness of clique-width implies boundedness of mim-width. By combining our results with the known bounded cases for clique-width, we present summary theorems of the current state of the art for the boundedness of mim-width for $(H_1,H_2)$-free graphs. In particular, we classify the mim-width of $(H_1,H_2)$-free graphs for all pairs $(H_1,H_2)$ with $\mid V(H_1)\mid +\mid V(H_2)\mid \le 8$. When $H_1$ and $H_2$ are connected graphs, we classify all pairs $(H_1,H_2)$ except for one remaining infinite family and a few isolated cases.     

Sparse halves in K 4-free graphs

A conjecture of Chung and Graham states that every $K_4$-free graph on $n$ vertices contains a vertex set of size $?n∕2?$ that spans at most $n^2∕18$ edges. We make the first step toward this conjecture by showing that it holds for all regular graphs.     

Order plus size of τ‐critical graphs

Let $G=\left(V,E\right)$ be a $\tau$‐critical graph with $\tau \left(G\right)=t$. Erd?s and Gallai proved that $\mid V\mid \le 2t$ and the bound $\mid E\mid \le \left(\genfrac{}{}{0ex}{}{t+1}{2}\right)$ was obtained by Erd?s, Hajnal, and Moon. We give here the sharp combined bound $\mid E\mid +\mid V\mid \le \left(\genfrac{}{}{0ex}{}{t+2}{2}\right)$ and find all graphs with equality.     

Even cycle creating paths

We say that two graphs $H_1,H_2$ on the same vertex set are $G$-creating if the union of the two graphs contains $G$ as a subgraph. Let $H\left(n,k\right)$ be the maximum number of pairwise $C_k$-creating Hamiltonian paths of the complete graph $K_n$. The behavior of $H\left(n,2k+1\right)$ is much better understood than the behavior of $H\left(n,2k\right)$, the former is an exponential function of $n$ whereas the latter is larger than exponential, for every fixed $k$. We study $H\left(n,k\right)$ for fixed $k$ and $n$ tending to infinity. The only nontrivial upper bound on $H\left(n,2k\right)$ was proved by Cohen, Fachini, and Körner in the case of $k=2$: $$n^{(1/2)n-o\left(n\right)}\le H\left(n,4\right)\le n^{\left(1-1/4\right)n-o\left(n\right)}\mathrm{.}$$ In this paper, we generalize their method to prove that for every $k\ge 2$, $$n^{(1/k)n-o\left(n\right)}\le H\left(n,2k\right)\le n^{\left(1-2/(3k^2-2k)\right)n-o\left(n\right)}$$ and a similar, slightly better upper bound holds when $k$ is odd. Our proof uses constructions of bipartite, regular, $C_{2k}$-free graphs with many edges given in papers by Reiman, Benson, Lazebnik, Ustimenko, and Woldar.     

Finding any given 2‐factor in sparse pseudorandom graphs efficiently

Given an $n$‐vertex pseudorandom graph $G$ and an $n$‐vertex graph $H$ with maximum degree at most two, we wish to find a copy of $H$ in $G$, that is, an embedding $\phi :V\left(H\right)\to V\left(G\right)$ so that $\phi \left(u\right)\phi \left(v\right)\in E\left(G\right)$ for all $uv\in E\left(H\right)$. Particular instances of this problem include finding a triangle‐factor and finding a Hamilton cycle in $G$. Here, we provide a deterministic polynomial time algorithm that finds a given $H$ in any suitably pseudorandom graph $G$. The pseudorandom graphs we consider are $\left(p,\lambda \right)$‐bijumbled graphs of minimum degree which is a constant proportion of the average degree, that is, $\mathrm{\Omega }\left(pn\right)$. A $\left(p,\lambda \right)$‐bijumbled graph is characterised through the discrepancy property: $|e\left(A,B\right)?p|A||B||<\lambda \sqrt{|A||B|}$ for any two sets of vertices $A$ and $B$. Our condition $\lambda =O(p^{2}n/\log n)$ on bijumbledness is within a log factor from being tight and provides a positive answer to a recent question of Nenadov. We combine novel variants of the absorption‐reservoir method, a powerful tool from extremal graph theory and random graphs. Our approach builds on our previous work, incorporating the work of Nenadov, together with additional ideas and simplifications.     

Partitions of hypergraphs under variable degeneracy constraints

The paper deals with partitions of hypergraphs into induced subhypergraphs satisfying constraints on their degeneracy. Our hypergraphs may have multiple edges, but no loops. Given a hypergraph $H$ and a sequence $f=\left(f_1,f_2,\text{…},f_p\right)$ of $p\ge 1$ vertex functions $f_i:V\left(H\right)\to {\mathbb{N}}_0$ such that $f_1\left(v\right)+f_2\left(v\right)+\mathrm{?}+f_p\left(v\right)\ge d_H\left(v\right)$ for all $v\in V\left(H\right)$, we want to find a sequence $\left(H_1,H_2,\text{…},H_p\right)$ of vertex disjoint induced subhypergraphs containing all vertices of $H$ such that each hypergraph $H_i$ is strictly $f_i$‐degenerate, that is, for every nonempty subhypergraph $H\prime ?H_i$ there is a vertex $v\in V\left(H\prime \right)$ such that $d_{H\prime }\left(v\right)<f_i\left(v\right)$. Our main result in this paper says that such a sequence of hypergraphs exists if and only if $\left(H,f\right)$ is not a so‐called hard pair. Hard pairs form a recursively defined family of configurations, obtained from three basic types of configurations by the operation of merging a vertex. Our main result has several interesting applications related to generalized hypergraph coloring problems.     

The number of the non‐full‐rank Steiner triple systems

The $p$‐rank of a Steiner triple system (STS) $B$ is the dimension of the linear span of the set of characteristic vectors of blocks of $B$, over GF $\left(p\right)$. We derive a formula for the number of different STSs of order $v$ and given $2$‐rank $r_2$, $r_2<v$, and a formula for the number of STSs of order $v$ and given $3$‐rank $r_3$, $r_3<v?1$. Also, we prove that there are no STSs of $2$‐rank smaller than $v$ and, at the same time, $3$‐rank smaller than $v?1$. Our results extend previous study on enumerating STSs according to the rank of their codes, mainly by Tonchev, V.A. Zinoviev, and D.V. Zinoviev for the binary case and by Jungnickel and Tonchev for the ternary case.     

Generalized pentagonal geometries

A pentagonal geometry PENT($k,r$) is a partial linear space, where every line is incident with $k$ points, every point is incident with $r$ lines, and for each point $x$, there is a line incident with precisely those points that are not collinear with $x$. Here we generalize the concept by allowing the points not collinear with $x$ to form the point set of a Steiner system $S\left(2,k,w\right)$ whose blocks are lines of the geometry.     

On the maximum number of copies of H in graphs with given size and order

We study the maximum number $ex\left(n,e,H\right)$ of copies of a graph $H$ in graphs with a given number of vertices and edges. We show that for any fixed graph $H,ex\left(n,e,H\right)$ is asymptotically realized by the quasi‐clique provided that the edge density is sufficiently large. We also investigate a variant of this problem, when the host graph is bipartite.