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.     

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.     

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).     

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.     

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.     

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.     

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.     

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.     

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.     

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.     

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)$.     

A singular Liouville equation on planar domains

We show the existence of a solution for an equation where the nonlinearity is logarithmically singular at the origin, namely, $-\mathrm{\Delta }u=(\log u+f(u)){\chi }_{\{u>0\}}$ in $\mathrm{\Omega }\subset {\mathbb{R}}^2$ with Dirichlet boundary condition. The function f has exponential growth, which can be subcritical or critical with respect to the Trudinger–Moser inequality. We study the energy functional $I_{\epsilon }$ corresponding to the perturbed equation $-\mathrm{\Delta }u+g_{\epsilon }(u)=f(u)$, where $g_{\epsilon }$ is well defined at 0 and approximates $-\log u$. We show that $I_{\epsilon }$ has a critical point $u_{\epsilon }$ in $H_0^1(\mathrm{\Omega })$, which converges to a legitimate nontrivial nonnegative solution of the original problem as $\epsilon \to 0$. We also investigate the problem with $f(u)$ replaced by $\lambda f(u)$, when the parameter $\lambda >0$ is sufficiently large.     

Bounded sets structure of CpX and quasi‐(DF)‐spaces

For wide classes of locally convex spaces, in particular, for the space $C_p(X)$ of continuous real‐valued functions on a Tychonoff space X equipped with the pointwise topology, we characterize the existence of a fundamental bounded resolution (i.e., an increasing family of bounded sets indexed by the irrationals which swallows the bounded sets). These facts together with some results from Grothendieck's theory of $(DF)$‐spaces have led us to introduce quasi‐ $(DF)$‐spaces, a class of locally convex spaces containing $(DF)$‐spaces that preserves subspaces, countable direct sums and countable products. Regular $(LM)$‐spaces as well as their strong duals are quasi‐ $(DF)$‐spaces. Hence the space of distributions $D^{\prime }(\mathrm{\Omega })$ provides a concrete example of a quasi‐ $(DF)$‐space not being a $(DF)$‐space. We show that $C_p(X)$ has a fundamental bounded resolution if and only if $C_p(X)$ is a quasi‐ $(DF)$‐space if and only if the strong dual of $C_p(X)$ is a quasi‐ $(DF)$‐space if and only if X is countable. If X is metrizable, then $C_k(X)$ is a quasi‐ $(DF)$‐space if and only if X is a σ‐compact Polish space.     

Decomposition of Graphs into (k,r)‐Fans and Single Edges

Let $\phi (n,H)$ be the largest integer such that, for all graphs G on n vertices, the edge set $E(G)$ can be partitioned into at most $\phi (n,H)$ parts, of which every part either is a single edge or forms a graph isomorphic to H. Pikhurko and Sousa conjectured that $\phi (n,H)=\mathrm{ex}(n,H)$ for $\chi (H)⩾3$ and all sufficiently large n, where $\mathrm{ex}(n,H)$ denotes the maximum number of edges of graphs on n vertices that do not contain H as a subgraph. A $(k,r)$‐fan is a graph on $(r-1)k+1$ vertices consisting of k cliques of order r that intersect in exactly one common vertex. In this article, we verify Pikhurko and Sousa's conjecture for $(k,r)$‐fans. The result also generalizes a result of Liu and Sousa.     

Generalization of Hardy–Littlewood maximal inequality with variable exponent

Let $p(·)$ be a measurable function defined on ${\mathbb{R}}^d$ and $p_{-}:={inf}_{x\in {\mathbb{R}}^d}p(x)$. In this paper, we generalize the Hardy–Littlewood maximal operator. In the definition, instead of cubes or balls, we take the supremum over all rectangles the side lengths of which are in a cone-like set defined by a given function ψ. Moreover, instead of the integral means, we consider the $L_{q(·)}$-means. Let $p(·)$ and $q(·)$ satisfy the log-Hülder condition and $p(·)=q(·)r(·)$. Then, we prove that the maximal operator is bounded on $L_{p(·)}$ if and is bounded from $L_{p(·)}$ to the weak $L_{p(·)}$ if $1\le r_{-}\le \infty$. We generalize also the theorem about the Lebesgue points.     

Highly edge-connected regular graphs without large factorizable subgraphs

We construct highly edge-connected $r$-regular graphs of even order which do not contain $r?2$ pairwise disjoint perfect matchings. When $r$ is a multiple of 4, the result solves a problem of Thomassen [4].     

Degrees of categoricity of trees and the isomorphism problem

In this paper, we show that for any computable ordinal α, there exists a computable tree of rank $\alpha +1$ with strong degree of categoricity ${\mathbf{0}}^{(2\alpha )}$ if α is finite, and with strong degree of categoricity ${\mathbf{0}}^{(2\alpha +1)}$ if α is infinite. In fact, these are the greatest possible degrees of categoricity for such trees. For a computable limit ordinal α, we show that there is a computable tree of rank α with strong degree of categoricity ${\mathbf{0}}^{(\alpha )}$ (which equals ${\mathbf{0}}^{(2\alpha )}$). It follows from our proofs that, for every computable ordinal $\alpha >0$, the isomorphism problem for trees of rank α is ${\mathrm{\Pi }}_{2\alpha }^0$‐complete.