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.     

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.     

Extremal results on feedback arc sets in digraphs

For an oriented graph $G$, let $\beta (G)$ denote the size of a minimum feedback arc set, a smallest edge subset whose deletion leaves an acyclic subgraph. Berger and Shor proved that any $m$-edge oriented graph $G$ satisfies $\beta (G)=m/2-\mathrm{\Omega }(m^{3/4})$. We observe that if an oriented graph $G$ has a fixed forbidden subgraph $B$, the bound $\beta (G)=m/2-\mathrm{\Omega }(m^{3/4})$ is sharp as a function of $m$ if $B$ is not bipartite, but the exponent $3/4$ in the lower order term can be improved if $B$ is bipartite. Using a result of Bukh and Conlon on Turán numbers, we prove that any rational number in $[3/4,1]$ is optimal as an exponent for some finite family of forbidden subgraphs. Our upper bounds come equipped with randomized linear-time algorithms that construct feedback arc sets achieving those bounds. We also characterize directed quasirandomness via minimum feedback arc sets.     

A Ramsey–Turán theory for tilings in graphs

For a $k$-vertex graph $F$ and an $n$-vertex graph $G$, an $F$-tiling in $G$ is a collection of vertex-disjoint copies of $F$ in $G$. For $r\in \mathbb{N}$, the $r$-independence number of $G$, denoted ${\alpha }_r(G)$, is the largest size of a $K_r$-free set of vertices in $G$. In this article, we discuss Ramsey–Turán-type theorems for tilings where one is interested in minimum degree and independence number conditions (and the interaction between the two) that guarantee the existence of optimal $F$-tilings. Our results unify and generalise previous results of Balogh–Molla–Sharifzadeh [Random Struct. Algoritm. 49 (2016), no. 4, 669–693], Nenadov–Pehova [SIAM J. Discret. Math. 34 (2020), no. 2, 1001–1010] and Balogh–McDowell–Molla–Mycroft [Comb. Probab. Comput. 27 (2018), no. 4, 449–474] on the subject.     

Packing list-colorings

List coloring is an influential and classic topic in graph theory. We initiate the study of a natural strengthening of this problem, where instead of one list-coloring, we seek many in parallel. Our explorations have uncovered a potentially rich seam of interesting problems spanning chromatic graph theory. Given a $k$-list-assignment $L$ of a graph $G$, which is the assignment of a list $L(v)$ of $k$ colors to each vertex $v\in V(G)$, we study the existence of $k$ pairwise-disjoint proper colorings of $G$ using colors from these lists. We may refer to this as a list-packing. Using a mix of combinatorial and probabilistic methods, we set out some basic upper bounds on the smallest $k$ for which such a list-packing is always guaranteed, in terms of the number of vertices, the degeneracy, the maximum degree, or the (list) chromatic number of $G$. (The reader might already find it interesting that such a minimal $k$ is well defined.) We also pursue a more focused study of the case when $G$ is a bipartite graph. Our results do not yet rule out the tantalising prospect that the minimal $k$ above is not too much larger than the list chromatic number. Our study has taken inspiration from study of the strong chromatic number, and we also explore generalizations of the problem above in the same spirit.     

Random perfect matchings in regular graphs

We prove that in all regular robust expanders $G$, every edge is asymptotically equally likely contained in a uniformly chosen perfect matching $M$. We also show that given any fixed matching or spanning regular graph $N$ in $G$, the random variable $|M\cap E(N)|$ is approximately Poisson distributed. This in particular confirms a conjecture and a question due to Spiro and Surya, and complements results due to Kahn and Kim who proved that in a regular graph every vertex is asymptotically equally likely contained in a uniformly chosen matching. Our proofs rely on the switching method and the fact that simple random walks mix rapidly in robust expanders.     

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.     

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

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.     

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

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.     

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.     

Totally real flat minimal surfaces in the hyperquadric

In this paper, we study geometry of totally real minimal surfaces in the complex hyperquadric $Q_{N-2}$, and obtain some characterizations of the harmonic sequence generated by these minimal immersions. For totally real flat surfaces that are minimal immersed in both $Q_{N-2}$ and $\mathbb{C}{P}^{N-1}$, we determine them for $N=4,5,6$, and give a classification theorem when they are Clifford solutions.     

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.     

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.     

On blowups of vorticity for the homogeneous Euler equation

Blowups of vorticity for the three- and two-dimensional homogeneous Euler equations are studied. Two regimes of approaching a blow-up point, respectively, with variable or fixed time are analyzed. It is shown that in the n-dimensional ( $n=2,3$) generic case the blowups of degrees $1,\cdots ,n$ at the variable time regime and of degrees $1/2,\cdots ,(n+1)/(n+2)$ at the fixed time regime may exist. Particular situations when the vorticity blows while the direction of the vorticity vector is concentrated in one or two directions are realizable.