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.     

Classification of Regular Embeddings of Complete Multipartite Graphs

A 2‐cell embedding of a graph Γ into a closed (orientable or nonorientable) surface is called regular if its automorphism group acts regularly on the flags. In this article, we classify the regular embeddings of the complete multipartite graph $K_{n,\dots ,n}$. We show that if the number of partite sets is greater than 3, there exists no such embedding; and if the number of partite sets is 3, for any n, there exist one orientable regular embedding and one nonorientable regular embedding of $K_{n,n,n}$ up to isomorphism.     

Uniformly 3-connected graphs

Let $k$ be a positive integer. A graph is said to be uniformly $k$-connected if between any pair of vertices the maximum number of independent paths is exactly $k$. Dawes showed that all minimally 3-connected graphs can be constructed from $K_4$ such that every graph in each intermediate step is also minimally 3-connected. In this paper, we generalize Dawes' result to uniformly 3-connected graphs. We give a constructive characterization of the class of uniformly 3-connected graphs which differs from the characterization provided by Göring et al., where their characterization requires the set of all 3-connected and 3-regular graphs as a starting set, the new characterization requires only the graph $K_4$. Eventually, we obtain a tight bound on the number of edges in uniformly 3-connected graphs.     

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.     

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.     

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.     

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.     

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

On infinite‐dimensional Banach spaces and weak forms of the axiom of choice

We study theorems from Functional Analysis with regard to their relationship with various weak choice principles and prove several results about them: “Every infinite‐dimensional Banach space has a well‐orderable Hamel basis” is equivalent to $\mathsf{AC}$; “ $\mathbb{R}$ can be well‐ordered” implies “no infinite‐dimensional Banach space has a Hamel basis of cardinality $<2^{{\aleph }_0}$”, thus the latter statement is true in every Fraenkel‐Mostowski model of $\mathsf{ZFA}$; “No infinite‐dimensional Banach space has a Hamel basis of cardinality $<2^{{\aleph }_0}$” is not provable in $\mathsf{ZF}$; “No infinite‐dimensional Banach space has a well‐orderable Hamel basis of cardinality $<2^{{\aleph }_0}$” is provable in $\mathsf{ZF}$; ${\mathsf{AC}}_{\mathsf{fin}}^{{\aleph }_{\mathsf{0}}}$ (the Axiom of Choice for denumerable families of non‐empty finite sets) is equivalent to “no infinite‐dimensional Banach space has a Hamel basis which can be written as a denumerable union of finite sets”; Mazur's Lemma (“If X is an infinite‐dimensional Banach space, Y is a finite‐dimensional vector subspace of X , and $\epsilon >0$, then there is a unit vector $x\in X$ such that $||y||\le (1+\epsilon )||y+\alpha x||$ for all $y\in Y$ and all scalars α”) is provable in $\mathsf{ZF}$; “A real normed vector space X is finite‐dimensional if and only if its closed unit ball $B_X=\{x\in X:||x||\le 1\}$ is compact” is provable in $\mathsf{ZF}$; $\mathsf{DC}$ (Principle of Dependent Choices) + “ $\mathbb{R}$ can be well‐ordered” does not imply the Hahn‐Banach Theorem ( $\mathsf{HB}$) in $\mathsf{ZF}$; $\mathsf{HB}$ and “no infinite‐dimensional Banach space has a Hamel basis of cardinality $<2^{{\aleph }_0}$” are independent from each other in $\mathsf{ZF}$; “No infinite‐dimensional Banach space can be written as a denumerable union of finite‐dimensional subspaces” lies in strength between ${\mathsf{AC}}^{{\aleph }_0}$ (the Axiom of Countable Choice) and ${\mathsf{AC}}_{\mathsf{fin}}^{{\aleph }_{\mathsf{0}}}$; $\mathsf{DC}$ implies “No infinite‐dimensional Banach space can be written as a denumerable union of closed proper subspaces” which in turn implies ${\mathsf{AC}}^{{\aleph }_0}$; “Every infinite‐dimensional Banach space has a denumerable linearly independent subset” is a theorem of $\mathsf{ZF}+{\mathsf{AC}}^{{\aleph }_0}$, but not a theorem of $\mathsf{ZF}$; and “Every infinite‐dimensional Banach space has a linearly independent subset of cardinality $\ge 2^{{\aleph }_0}$” implies “every Dedekind‐finite set is finite”.     

Minimal energy problems for strongly singular Riesz kernels

We study minimal energy problems for strongly singular Riesz kernels ${|\mathbf{x}-\mathbf{y}|}^{\alpha -n}$, where $n\ge 2$ and $\alpha \in (-1,1)$, considered for compact $(n-1)$‐dimensional $C^{\infty }$‐manifolds Γ immersed into ${\mathbb{R}}^n$. Based on the spatial energy of harmonic double layer potentials, we are motivated to formulate the natural regularization of such minimization problems by switching to Hadamard's partie finie integral operator which defines a strongly elliptic pseudodifferential operator of order $\beta =1-\alpha$ on Γ. The measures with finite energy are shown to be elements from the Sobolev space $H^{\beta /2}(\mathrm{\Gamma })$, $0<\beta <2$, and the corresponding minimal energy problem admits a unique solution. We relate our continuous approach also to the discrete one, which has been worked out earlier by D. P. Hardin and E. B. Saff.     

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

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.     

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.     

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.