Stability in the Erdős–Gallai Theorem on cycles and paths,II

The Erd?s–Gallai Theorem states that for $k\ge 3$, any $n$-vertex graph with no cycle of length at least $k$ has at most $\frac{1}{2}(k?1)(n?1)$ edges. A stronger version of the Erd?s–Gallai Theorem was given by Kopylov: If $G$ is a 2-connected $n$-vertex graph with no cycle of length at least $k$, then $e\left(G\right)\le max\{h(n,k,2),h(n,k,?\frac{k?1}{2}?)\}$, where $h(n,k,a)?\left(\genfrac{}{}{0ex}{}{k?a}{2}\right)+a(n?k+a)$. Furthermore, Kopylov presented the two possible extremal graphs, one with $h(n,k,2)$ edges and one with $h(n,k,?\frac{k?1}{2}?)$ edges.In this paper, we complete a stability theorem which strengthens Kopylov’s result. In particular, we show that for $k\ge 3$ odd and all $n\ge k$, every $n$-vertex 2-connected graph $G$ with no cycle of length at least $k$ is a subgraph of one of the two extremal graphs or $e\left(G\right)\le max\{h(n,k,3),h(n,k,\frac{k?3}{2})\}$. The upper bound for $e\left(G\right)$ here is tight.     

On hypergraphs without loose cycles

Recently, Mubayi and Wang showed that for $r\ge 4$ and $?\ge 3$, the number of $n$-vertex $r$-graphs that do not contain any loose cycle of length $?$ is at most $2^{O\left(n^{r?1}{(logn)}^{(r?3)∕(r?2)}\right)}$. We improve this bound to $2^{O(n^{r?1}loglogn)}$.     

Counting arithmetical structures on paths and cycles

Let $G$ be a finite, connected graph. An arithmetical structure on $G$ is a pair of positive integer vectors $\mathbf{d},\mathbf{r}$ such that $(diag\left(\mathbf{d}\right)?A)\mathbf{r}=0$, where $A$ is the adjacency matrix of $G$. We investigate the combinatorics of arithmetical structures on path and cycle graphs, as well as the associated critical groups (the torsion part of the cokernels of the matrices $(diag\left(\mathbf{d}\right)?A)$). For paths, we prove that arithmetical structures are enumerated by the Catalan numbers, and we obtain refined enumeration results related to ballot sequences. For cycles, we prove that arithmetical structures are enumerated by the binomial coefficients $\left(\genfrac{}{}{0ex}{}{2n?1}{n?1}\right)$, and we obtain refined enumeration results related to multisets. In addition, we determine the critical groups for all arithmetical structures on paths and cycles.     

On a conjecture of Füredi

Füredi conjectured that the Boolean lattice $2^{\left[n\right]}$ can be partitioned into $\left(\genfrac{}{}{00}{}{n}{\lfloor n/2\rfloor }\right)$ chains such that the size of any two differs in at most one. In this paper, we prove that there is an absolute constant $\alpha \approx 0.8482$ with the following property: for every $ϵ>0$, if $n$ is sufficiently large, the Boolean lattice $2^{\left[n\right]}$ has a chain partition into $\left(\genfrac{}{}{00}{}{n}{\lfloor n/2\rfloor }\right)$ chains, each of them of size between $(\alpha -ϵ)\sqrt{n}$ and $O(\sqrt{n}/ϵ)$.We deduce this result by looking at the more general setup of unimodal normalized matching posets. We prove that a unimodal normalized matching poset $P$ of width $w$ has a chain partition into $w$ chains, each of size at most $\frac{2\left|P\right|}{w}+5$, and it has a chain partition into $w$ chains, where each chain has size at least $\frac{\left|P\right|}{2w}-\frac{1}{2}$.     

Sharp well-posedness of the cauchy problem for the higher-order dispersive equation

This current paper is devoted to the Cauchy problem for higher order dispersive equation u_t+ ?_x~(2n+1)u = ?_x(u?_x~nu) + ?_x~(n-1)(u_x~2), n ≥ 2, n ∈ N~+.By using Besov-type spaces, we prove that the associated problem is locally well-posed in H~(-n/2+3/4,-1/(2n))(R). The new ingredient is that we establish some new dyadic bilinear estimates. When n is even, we also prove that the associated equation is ill-posed in H~(s,a)(R) with s -n/2+3/4 and all a∈R.     

4-labelings and grid embeddings of plane quadrangulations

A straight-line drawing of a planar graph $G$ is a closed rectangle-of-influence drawing if for each edge $uv$, the closed axis-parallel rectangle with opposite corners $u$ and $v$ contains no other vertices. We show that each quadrangulation on $n$ vertices has a closed rectangle-of-influence drawing on the $(n?3)\times (n?3)$ grid.The algorithm is based on angle labeling and simple face counting in regions. This answers the question of what would be a grid embedding of quadrangulations analogous to Schnyder’s classical algorithm for embedding triangulations and extends previous results on book embeddings for quadrangulations from Felsner, Huemer, Kappes, and Orden.A further compaction step yields a straight-line drawing of a quadrangulation on the $(?\frac{n}{2}??1)\times (?\frac{3n}{4}??1)$ grid. The advantage over other existing algorithms is that it is not necessary to add edges to the quadrangulation to make it $4$-connected.     

Dense uniform hypergraphs have high list chromatic number

The first author showed that the list chromatic number of every graph with average degree $d$ is at least $(0.5?o\left(1\right)){log}_{2}d$. We prove that for $r\ge 3$, every $r$-uniform hypergraph in which at least half of the $(r?1)$-vertex subsets are contained in at least $d$ edges has list chromatic number at least $\frac{lnd}{100r^3}$. When $r$ is fixed, this is sharp up to a constant factor.     

Turán numbers for odd wheels

The Turán number $\text{ex}(n,G)$ is the maximum number of edges in any $n$-vertex graph that does not contain a subgraph isomorphic to $G$. A wheel$W_n$ is a graph on $n$ vertices obtained from a $C_{n?1}$ by adding one vertex $w$ and making $w$ adjacent to all vertices of the $C_{n?1}$. We obtain two exact values for small wheels:

$\text{ex}(n,W_5)=?\frac{n^2}{4}+\frac{n}{2}?,$

$\text{ex}(n,W_7)=?\frac{n^2}{4}+\frac{n}{2}+1?.$

Given that $\text{ex}(n,W_6)$ is already known, this paper completes the spectrum for all wheels up to 7 vertices. In addition, we present the construction which gives us the lower bound $\text{ex}(n,W_{2k+1})>?\frac{n^2}{4}?+?\frac{n}{2}?$ in general case.     

Sparse graphs of girth at least five are packable

A graph is packable if it is a subgraph of its complement. The following statement was conjectured by Faudree, Rousseau, Schelp and Schuster in 1981: every non-star graph $G$ with girth at least $5$ is packable.The conjecture was proved by Faudree et al. with the additional condition that $G$ has at most $\frac{6}{5}n?2$ edges. In this paper, for each integer $k\ge 3$, we prove that every non-star graph with girth at least $5$ and at most $\frac{2k?1}{k}n?{\alpha }_k\left(n\right)$ edges is packable, where ${\alpha }_k\left(n\right)$ is $o\left(n\right)$ for every $k$. This implies that the conjecture is true for sufficiently large planar graphs.     

Online sum-paintability: The slow-coloring game

The slow-coloring game is played by Lister and Painter on a graph $G$. On each round, Lister marks a nonempty subset $M$ of the uncolored vertices, scoring $\left|M\right|$ points. Painter then gives a color to a subset of $M$ that is independent in $G$. The game ends when all vertices are colored. Painter and Lister want to minimize and maximize the total score, respectively. The best score that each player can guarantee is the sum-color cost of $G$, written $\stackrel{?}{s}\left(G\right)$. The game is an online variant of online sum list coloring.We prove $\frac{\left|V\left(G\right)\right|}{2\alpha \left(G\right)}+\frac{1}{2}\le \frac{\stackrel{?}{s}\left(G\right)}{\left|V\left(G\right)\right|}\le max\left\{\frac{\left|V\left(H\right)\right|}{\alpha \left(H\right)}:H?G\right\}$, where $\alpha \left(G\right)$ is the independence number, and we study when equality holds in the bounds. We compute $\stackrel{?}{s}\left(G\right)$ for graphs with $\alpha \left(G\right)=2$. Among $n$-vertex trees, we prove that $\stackrel{?}{s}$ is minimized by the star and maximized by the path. We also study $\stackrel{?}{s}\left(K_{r,s}\right)$.