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.     

On vertex-disjoint cycles and degree sum conditions

This paper considers a degree sum condition sufficient to imply the existence of $k$ vertex-disjoint cycles in a graph $G$. For an integer $t\ge 1$, let ${\sigma }_t\left(G\right)$ be the smallest sum of degrees of $t$ independent vertices of $G$. We prove that if $G$ has order at least $7k+1$ and ${\sigma }_4\left(G\right)\ge 8k?3$, with $k\ge 2$, then $G$ contains $k$ vertex-disjoint cycles. We also show that the degree sum condition on ${\sigma }_4\left(G\right)$ is sharp and conjecture a degree sum condition on ${\sigma }_t\left(G\right)$ sufficient to imply $G$ contains $k$ vertex-disjoint cycles for $k\ge 2$.     

Explicit solutions for one-dimensional two-phase free boundary problems with either shrinkage or expansion

We consider a one-dimensional solidification of a pure substance which is initially in liquid state in a bounded interval $[0,l]$. Initially, the liquid is above the freezing temperature, and cooling is applied at $x=0$ while the other end $x=l$ is kept adiabatic. At the time $t=0$, the temperature of the liquid at $x=0$ comes down to the freezing point and solidification begins, where $x=s\left(t\right)$ is the position of the solid–liquid interface. As the liquid solidifies, it shrinks ($0<r<1$) or expands ($r<0$) and appears a region between $x=0$ and $x=rs\left(t\right)$, with $r<1$. Temperature distributions of the solid and liquid phases and the position of the two free boundaries ($x=rs\left(t\right)$ and $x=s\left(t\right)$) in the solidification process are studied. For three different cases, changing the condition on the free boundary $x=rs\left(t\right)$ (temperature boundary condition, heat flux boundary condition and convective boundary condition) an explicit solution is obtained. Moreover, the solution of each problem is given as a function of a parameter which is the unique solution of a transcendental equation and for two of the three cases a condition on the parameter must be verified by data of the problem in order to have an instantaneous phase-change process. In all the cases, the explicit solution is given by a representation of the similarity type.     

Distant sum distinguishing index of graphs

Consider a positive integer $r$ and a graph $G=(V,E)$ with maximum degree $\Delta$ and without isolated edges. The least $k$ so that a proper edge colouring $c:E\to \{1,2,\dots ,k\}$ exists such that ${\sum }_{e?u}c\left(e\right)\ne {\sum }_{e?v}c\left(e\right)$ for every pair of distinct vertices $u,v$ at distance at most $r$ in $G$ is denoted by ${\chi }_{\Sigma ,r}^{\prime }\left(G\right)$. For $r=1$, it has been proved that ${\chi }_{\Sigma ,1}^{\prime }\left(G\right)=(1+o\left(1\right))\Delta$. For any $r\ge 2$ in turn an infinite family of graphs is known with ${\chi }_{\Sigma ,r}^{\prime }\left(G\right)=\Omega \left({\Delta }^{r?1}\right)$. We prove that, on the other hand, ${\chi }_{\Sigma ,r}^{\prime }\left(G\right)=O\left({\Delta }^{r?1}\right)$ for $r\ge 2$. In particular, we show that ${\chi }_{\Sigma ,r}^{\prime }\left(G\right)\le 6{\Delta }^{r?1}$ if $r\ge 4$.     

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

A sharp bound on the expected number of upcrossings of an L2-bounded Martingale

For a martingale $M$ starting at $x$ with final variance ${\sigma }^2$, and an interval $(a,b)$, let $\Delta =\frac{b?a}{\sigma }$ be the normalized length of the interval and let $\delta =\frac{|x?a|}{\sigma }$ be the normalized distance from the initial point to the lower endpoint of the interval. The expected number of upcrossings of $(a,b)$ by $M$ is at most $\frac{\sqrt{1+{\delta }^2}?\delta }{2\Delta }$ if ${\Delta }^2\le 1+{\delta }^2$ and at most $\frac{1}{1+{(\Delta +\delta )}^2}$ otherwise. Both bounds are sharp, attained by Standard Brownian Motion stopped at appropriate stopping times. Both bounds also attain the Doob upper bound on the expected number of upcrossings of $(a,b)$ for submartingales with the corresponding final distribution. Each of these two bounds is at most $\frac{\sigma }{2(b?a)}$, with equality in the first bound for $\delta =0$. The upper bound $\frac{\sigma }{2}$ on the length covered by $M$ during upcrossings of an interval restricts the possible variability of a martingale in terms of its final variance. This is in the same spirit as the Dubins & Schwarz sharp upper bound $\sigma$ on the expected maximum of $M$ above $x$, the Dubins & Schwarz sharp upper bound $\sigma \sqrt{2}$ on the expected maximal distance of $M$ from $x$, and the Dubins, Gilat & Meilijson sharp upper bound $\sigma \sqrt{3}$ on the expected diameter of $M$.     

List 3-dynamic coloring of graphs with small maximum average degree

An $r$-dynamic $k$-coloring of a graph $G$ is a proper $k$-coloring such that for any vertex $v$, there are at least $min\{r,{deg}_G\left(v\right)\}$ distinct colors in $N_G\left(v\right)$. The $r$-dynamic chromatic number${\chi }_r^d\left(G\right)$ of a graph $G$ is the least $k$ such that there exists an $r$-dynamic $k$-coloring of $G$. The list$r$-dynamic chromatic number of a graph $G$ is denoted by $c{h}_r^d\left(G\right)$.Recently, Loeb et al. (0000) showed that the list $3$-dynamic chromatic number of a planar graph is at most 10. And Cheng et al. (0000) studied the maximum average condition to have ${\chi }_3^d\left(G\right)\le 4,5$, or $6$. On the other hand, Song et al. (2016) showed that if $G$ is planar with girth at least 6, then ${\chi }_r^d\left(G\right)\le r+5$ for any $r\ge 3$.In this paper, we study list 3-dynamic coloring in terms of maximum average degree. We show that $c{h}_3^d\left(G\right)\le 6$ if $mad\left(G\right)<\frac{18}{7}$, $c{h}_3^d\left(G\right)\le 7$ if $mad\left(G\right)<\frac{14}{5}$, and $c{h}_3^d\left(G\right)\le 8$ if $mad\left(G\right)<3$. All of the bounds are tight.     

A degree sum condition for graphs to be covered by two cycles

Let $G$ be a $k$-connected graph of order $n$. In [1], Bondy (1980) considered a degree sum condition for a graph to have a Hamiltonian cycle, say, to be covered by one cycle. He proved that if ${\sigma }_{k+1}\left(G\right)>(k+1)(n?1)/2$, then $G$ has a Hamiltonian cycle. On the other hand, concerning a degree sum condition for a graph to be covered by two cycles, Enomoto et al. (1995) [4] proved that if $k=1$ and ${\sigma }_3\left(G\right)\ge n$, then $G$ can be covered by two cycles. By these results, we conjecture that if ${\sigma }_{2k+1}\left(G\right)>(2k+1)(n?1)/3$, then $G$ can be covered by two cycles. In this paper, we prove the case $k=2$ of this conjecture. In fact, we prove a stronger result; if $G$ is 2-connected with ${\sigma }_5\left(G\right)\ge 5(n?1)/3$, then $G$ can be covered by two cycles, or $G$ belongs to an exceptional class.     

Matrix completion problems over integral domains: The case with a diagonal of prescribed blocks

Let $\mathfrak{R}$ be an arbitrary integral domain, let $\wedge =\{{\lambda }_1\text{,}\dots \text{,}{\lambda }_n\}$ be a multiset of elements of $\mathfrak{R}$, let $\sigma$ be a permutation of $\{1\text{,}\dots \text{,}k\}$ let $n_1\text{,}\dots \text{,}{n}_k$ be positive integers such that $n_1+?+n_k=n$, and for $r=1\text{,}\dots \text{,}k$ let $A_r\in {\mathfrak{R}}^{n_r\times n_{\sigma (r)}}$. We are interested in the problem of finding a block matrix $Q={\left[Q_{\mathit{rs}}\right]}_{r\text{,}s=1}^k\in {\mathfrak{R}}^{n\times n}$ with spectrum $\mathrm{\Lambda }$ and such that $Q_{r\sigma (r)}=A_r$ for $r=1\text{,}\dots \text{,}k$. Cravo and Silva completely characterized the existence of such a matrix when $\mathfrak{R}$ is a field. In this work we construct a solution matrix $Q$ that solves the problem when $\mathfrak{R}$ is an integral domain with two exceptions: (i) $k=2$; (ii) $k\ge 3$, $\sigma (r)=r$ and $n_r>n/2$ for some $r$.What makes this work quite unique in this area is that we consider the problem over the more general algebraic structure of integral domains, which includes the important case of integers. Furthermore, we provide an explicit and easy to implement finite step algorithm that constructs an specific solution matrix (we point out that Cravo and Silva’s proof is not constructive).     

A note on degree sum conditions for 2-factors with a prescribed number of cycles in bipartite graphs

Let $G$ be a balanced bipartite graph of order $2n\ge 4$, and let ${\sigma }_{1,1}\left(G\right)$ be the minimum degree sum of two non-adjacent vertices in different partite sets of $G$. In 1963, Moon and Moser proved that if ${\sigma }_{1,1}\left(G\right)\ge n+1$, then $G$ is hamiltonian. In this note, we show that if $k$ is a positive integer, then the Moon–Moser condition also implies the existence of a 2-factor with exactly $k$ cycles for sufficiently large graphs. In order to prove this, we also give a ${\sigma }_{1,1}$ condition for the existence of $k$ vertex-disjoint alternating cycles with respect to a chosen perfect matching in $G$.     

Quotients of the deformation of Veronesean dual hyperoval in PG(3d,2)

Let $d\ge 3$. In $PG(d(d+3)/2,2)$, there are four known non-isomorphic $d$-dimensional dual hyperovals by now. These are Huybrechts’ dual hyperoval by Huybrechts (2002) [4], Buratti-Del Fra’s dual hyperoval by Buratti and Del Fra (2003) [1], Del Fra and Yoshiara (2005) [3], Veronesean dual hyperoval by Thas and van Maldeghem (2004) [9], Yoshiara (2004) [12] and the dual hyperoval, which is a deformation of Veronesean dual hyperoval by Taniguchi (2009) [6].In this paper, using a generator $\sigma$ of the Galois group $Gal(GF\left(2^{dm}\right)/GF\left(2\right))$ for some $m\ge 3$, we construct a $d$-dimensional dual hyperoval $T_{\sigma }$ in $PG(3d,2)$, which is a quotient of the dual hyperoval of [6]. Moreover, for generators $\sigma ,\tau \in Gal(GF\left(2^{dm}\right)/GF\left(2\right))$, if $T_{\sigma }$ and $T_{\tau }$ are isomorphic, then we show that $\sigma =\tau$ or $\sigma ={\tau }^{?1}$ on $GF\left(2^d\right)$. Hence, we see that there are many non-isomorphic quotients in $PG(3d,2)$ for the dual hyperoval of [6] if $d$ is large.     

A note on panchromatic colorings

This paper studies the quantity $p(n,r)$, that is the minimal number of edges of an $n$-uniform hypergraph without panchromatic coloring (it means that every edge meets every color) in $r$ colors. If $r\le c\frac{n}{lnn}$ then all bounds have a type $A_1(n,lnn,r){\left(\frac{r}{r?1}\right)}^n\le p(n,r)\le A_2(n,r,lnr){\left(\frac{r}{r?1}\right)}^n$, where $A_1$, $A_2$ are some algebraic fractions. The main result is a new lower bound on $p(n,r)$ when $r$ is at least $c\sqrt{n}$; we improve an upper bound on $p(n,r)$ if $n=o\left(r^{3∕2}\right)$.Also we show that $p(n,r)$ has upper and lower bounds depending only on $n∕r$ when the ratio $n∕r$ is small, which cannot be reached by the previous probabilistic machinery.Finally we construct an explicit example of a hypergraph without panchromatic coloring and with ${(\frac{r}{r?1}+o\left(1\right))}^n$ edges for $r=o\left(\sqrt{\frac{n}{lnn}}\right)$.     

Some bounds and limits in the theory of Riemann’s zeta function

For any real $a>0$ we determine the supremum of the real $\sigma$ such that $\zeta (\sigma +it)=a$ for some real $t$. For $0<a<1$, $a=1$, and $a>1$ the results turn out to be quite different.We also determine the supremum $E$ of the real parts of the ‘turning points’, that is points $\sigma +it$ where a curve $\mathrm{Im}\zeta (\sigma +it)=0$ has a vertical tangent. This supremum $E$ (also considered by Titchmarsh) coincides with the supremum of the real $\sigma$ such that ${\zeta }^{\prime }(\sigma +it)=0$ for some real $t$.We find a surprising connection between the three indicated problems: $\zeta \left(s\right)=1$, ${\zeta }^{\prime }\left(s\right)=0$ and turning points of $\zeta \left(s\right)$. The almost extremal values for these three problems appear to be located at approximately the same height.