The (p,q) property in families of d-intervals and d-trees

Given integers $p\ge q>1$, a family of sets satisfies the $(p,q)$ property if among any $p$ members of it some $q$ intersect. We prove that for any fixed integer constants $p\ge q>1$, a family of $d$-intervals satisfying the $(p,q)$ property can be pierced by $O\left(d^{\frac{q}{q-1}}\right)$ points, with constants depending only on $p$ and $q$. This extends results of Tardos, Kaiser and Alon for the case $q=2$, and of Kaiser and Rabinovich for the case $p=q=\lceil lo{g}_2(d+2)\rceil$. We further show that similar bounds hold in families of subgraphs of a tree or a graph of bounded tree-width, each consisting of at most $d$ connected components, extending results of Alon for the case $q=2$. Finally, we prove an upper bound of $O\left(d^{\frac{1}{p-1}}\right)$ on the fractional piercing number in families of $d$-intervals satisfying the $(p,p)$ property, and show that this bound is asymptotically sharp.     

Separable discrete functions: Recognition and sufficient conditions

A discrete function of $n$ variables is a mapping $g:X_1\times \dots \times X_n\to A$, where $X_1,\dots ,X_n$, and $A$ are arbitrary finite sets. Function $g$ is called separable if there exist $n$ functions $g_i:X_i\to A$ for $i=1,\dots ,n$, such that for every input $x_1,\dots ,x_n$ the function $g(x_1,\dots ,x_n)$ takes one of the values $g_1\left(x_1\right),\dots ,g_n\left(x_n\right)$. Given a discrete function $g$, it is an interesting problem to ask whether $g$ is separable or not. Although this seems to be a very basic problem concerning discrete functions, the complexity of recognition of separable discrete functions of $n$ variables is known only for $n=2$. In this paper we will show that a slightly more general recognition problem, when $g$ is not fully but only partially defined, is NP-complete for $n\ge 3$. We will then use this result to show that the recognition of fully defined separable discrete functions is NP-complete for $n\ge 4$.The general recognition problem contains the above mentioned special case for $n=2$. This case is well-studied in the context of game theory, where (separable) discrete functions of $n$ variables are referred to as (assignable) $n$-person game forms. There is a known sufficient condition for assignability (separability) of two-person game forms (discrete functions of two variables) called (weak) total tightness of a game form. This property can be tested in polynomial time, and can be easily generalized both to higher dimension and to partially defined functions. We will prove in this paper that weak total tightness implies separability for (partially defined) discrete functions of $n$ variables for any $n$, thus generalizing the above result known for $n=2$. Our proof is constructive. Using a graph-based discrete algorithm we show how for a given weakly totally tight (partially defined) discrete function $g$ of $n$ variables one can construct separating functions $g_1,\dots ,g_n$ in polynomial time with respect to the size of the input function.     

Biased graphs. VI. synthetic geometry

A biased graph is a graph with a class of selected circles (“cycles”, “circuits”), called balanced, such that no theta subgraph contains exactly two balanced circles. A biased graph $\Omega$ has two natural matroids, the frame matroid $G\left(\Omega \right)$ and the lift matroid $L\left(\Omega \right)$, and their extensions the full frame matroid $G^{•}\left(\Omega \right)$ and the extended (or complete) lift matroid $L_0\left(\Omega \right)$. In Part IV we used algebra to study the representations of these matroids by vectors over a skew field and the corresponding embeddings in Desarguesian projective spaces. Here we redevelop those representations, independently of Part IV and in greater generality, by using synthetic geometry.     

Context-free grammars,generating functions and combinatorial arrays

Let ${\left[R_{n,k}\right]}_{n,k\ge 0}$ be an array of nonnegative numbers satisfying the recurrence relation $R_{n,k}=(a_{1}n+a_{2}k+a_3)R_{n-1,k}+(b_{1}n+b_{2}k+b_3)R_{n-1,k-1}+(c_{1}n+c_{2}k+c_3)R_{n-1,k-2}$ with $R_{0,0}=1$ and $R_{n,k}=0$ unless $0\le k\le n$. In this paper, we first prove that the array ${\left[R_{n,k}\right]}_{n,k\ge 0}$ can be generated by some context-free Grammars, which gives a unified proof of many known results. Furthermore, we present criteria for real rootedness of row-generating functions and asymptotical normality of rows of ${\left[R_{n,k}\right]}_{n,k\ge 0}$. Applying the criteria to some arrays related to tree-like tableaux, interior and left peaks, alternating runs, flag descent numbers of group of type $B$, and so on, we get many results in a unified manner. Additionally, we also obtain the continued fraction expansions for generating functions related to above examples. As results, we prove the strong $q$-log-convexity of some generating functions.     

Graphs are (1,Δ+1)-choosable

A graph $G$ is $(k,k^{\prime })$-choosable if the following holds: For any list assignment $L$ which assigns to each vertex $v$ a set $L\left(v\right)$ of $k$ real numbers, and assigns to each edge $e$ a set $L\left(e\right)$ of $k^{\prime }$ real numbers, there is a total weighting $?:V\left(G\right)\cup E\left(G\right)\to R$ such that $?\left(z\right)\in L\left(z\right)$ for $z\in V\cup E$, and ${\sum }_{e\in E\left(u\right)}?\left(e\right)+?\left(u\right)\ne {\sum }_{e\in E\left(v\right)}?\left(e\right)+?\left(v\right)$ for every edge $uv$. This paper proves that if $G$ is a connected graph of maximum degree $\Delta \ge 2$, then $G$ is $(1,\Delta +1)$-choosable.     

Branch-depth: Generalizing tree-depth of graphs

We present a concept called the branch-depth of a connectivity function, that generalizes the tree-depth of graphs. Then we prove two theorems showing that this concept aligns closely with the notions of tree-depth and shrub-depth of graphs as follows. For a graph $G=(V,E)$ and a subset $A$ of $E$ we let ${\lambda }_G\left(A\right)$ be the number of vertices incident with an edge in $A$ and an edge in $E\setminus A$. For a subset $X$ of $V$, let ${\rho }_G\left(X\right)$ be the rank of the adjacency matrix between $X$ and $V\setminus X$ over the binary field. We prove that a class of graphs has bounded tree-depth if and only if the corresponding class of functions ${\lambda }_G$ has bounded branch-depth and similarly a class of graphs has bounded shrub-depth if and only if the corresponding class of functions ${\rho }_G$ has bounded branch-depth, which we call the rank-depth of graphs.Furthermore we investigate various potential generalizations of tree-depth to matroids and prove that matroids representable over a fixed finite field having no large circuits are well-quasi-ordered by restriction.     

Fluctuation theory for level-dependent Lévy risk processes

A level-dependent Lévy process solves the stochastic differential equation $dU\left(t\right)=dX\left(t\right)??\left(U\left(t\right)\right)dt$, where $X$ is a spectrally negative Lévy process. A special case is a multi-refracted Lévy process with ${?}_k\left(x\right)={\sum }_{j=1}^k{\delta }_j{\mathbf{1}}_{\{x\ge b_j\}}$. A general rate function $?$ that is non-decreasing and locally Lipschitz continuous is also considered. We discuss solutions of the above stochastic differential equation and investigate the so-called scale functions, which are counterparts of the scale functions from the theory of Lévy processes. We show how fluctuation identities for $U$ can be expressed via these scale functions. We demonstrate that the derivatives of the scale functions are solutions of Volterra integral equations.     

Relation between the H-rank of a mixed graph and the rank of its underlying graph

Given a simple graph $G=(V_G,E_G)$ with vertex set $V_G$ and edge set $E_G$, the mixed graph $\stackrel{?}{G}$ is obtained from $G$ by orienting some of its edges. Let $H\left(\stackrel{?}{G}\right)$ denote the Hermitian adjacency matrix of $\stackrel{?}{G}$ and $A\left(G\right)$ be the adjacency matrix of $G$. The $H$-rank (resp. rank) of $\stackrel{?}{G}$ (resp. $G$), written as $rk\left(\stackrel{?}{G}\right)$ (resp. $r\left(G\right)$), is the rank of $H\left(\stackrel{?}{G}\right)$ (resp. $A\left(G\right)$). Denote by $d\left(G\right)$ the dimension of cycle space of $G$, that is $d\left(G\right)=\left|E_G\right|?\left|V_G\right|+\omega \left(G\right)$, where $\omega \left(G\right)$ denotes the number of connected components of $G$. In this paper, we concentrate on the relation between the $H$-rank of $\stackrel{?}{G}$ and the rank of $G$. We first show that $?2d\left(G\right)?rk\left(\stackrel{?}{G}\right)?r\left(G\right)?2d\left(G\right)$ for every mixed graph $\stackrel{?}{G}$. Then we characterize all the mixed graphs that attain the above lower (resp. upper) bound. By these obtained results in the current paper, all the main results obtained in Luo et al. (2018); Wong et al. (2016) may be deduced consequently.     

Minimum supports of functions on the Hamming graphs with spectral constraints

We study functions defined on the vertices of the Hamming graphs $H(n,q)$. The adjacency matrix of $H(n,q)$ has $n+1$ distinct eigenvalues $n(q-1)-q\cdot i$ with corresponding eigenspaces $U_i(n,q)$ for $0\le i\le n$. In this work, we consider the problem of finding the minimum possible support (the number of nonzeros) of functions belonging to a direct sum $U_i(n,q)\oplus U_{i+1}(n,q)\oplus \cdots \oplus U_j(n,q)$ for $0\le i\le j\le n$. For the case $i+j\le n$ and $q\ge 3$ we find the minimum cardinality of the support of such functions and obtain a characterization of functions with the minimum cardinality of the support. In the case $i+j>n$ and $q\ge 4$ we also find the minimum cardinality of the support of functions, and obtain a characterization of functions with the minimum cardinality of the support for $i=j$, $i>\frac{n}{2}$ and $q\ge 5$. In particular, we characterize eigenfunctions from the eigenspace $U_i(n,q)$ with the minimum cardinality of the support for cases $i\le \frac{n}{2}$, $q\ge 3$ and $i>\frac{n}{2}$, $q\ge 5$.     

Toughness condition for the existence of all fractional (a,b,k)-critical graphs

In this article, we obtain a sufficient condition related to toughness $\tau \left(G\right)$ for a graph to be all fractional $(a,b,k)$-critical. We prove that if $\tau \left(G\right)\ge \frac{(b^2?1)+ak}{a}$ for some nonnegative integers $a,b,k$, then $G$ is all fractional $(a,b,k)$-critical. Our result improves the known results in Liu and Zhang (2008) and Liu and Cai (2009).     

Degree powers in graphs with a forbidden forest

Given a positive integer $p$ and a graph $G$ with degree sequence $d_1,\dots ,d_n$, we define $e_p\left(G\right)={\sum }_{i=1}^n{d}_i^p$. Caro and Yuster introduced a Turán-type problem for $e_p\left(G\right)$: Given a positive integer $p$ and a graph $H$, determine the function ${\text{ex}}_p(n,H)$, which is the maximum value of $e_p\left(G\right)$ taken over all graphs $G$ on $n$ vertices that do not contain $H$ as a subgraph. Clearly, ${\text{ex}}_1(n,H)=2\text{ex}(n,H)$, where $\text{ex}(n,H)$ denotes the classical Turán number. Caro and Yuster determined the function ${\text{ex}}_p(n,P_{?})$ for sufficiently large $n$, where $p\ge 2$ and $P_{?}$ denotes the path on $?$ vertices. In this paper, we generalise this result and determine ${\text{ex}}_p(n,F)$ for sufficiently large $n$, where $p\ge 2$ and $F$ is a linear forest. We also determine ${\text{ex}}_p(n,S)$, where $S$ is a star forest; and ${\text{ex}}_p(n,B)$, where $B$ is a broom graph with diameter at most six.     

Constructing sparse Davenport–Schinzel sequences

For any sequence $u$, the extremal function $Ex(u,j,n)$ is the maximum possible length of a $j$-sparse sequence with $n$ distinct letters that avoids $u$. We prove that if $u$ is an alternating sequence $abab\dots$ of length $s$, then $Ex(u,j,n)=\Theta \left(s{n}^2\right)$ for all $j\ge 2$ and $s\ge n$, answering a question of Wellman and Pettie (2018) and extending the result of Roselle and Stanton that $Ex(u,2,n)=\Theta \left(s{n}^2\right)$ for any alternation $u$ of length $s\ge n$ (Roselle and Stanton, 1971).Wellman and Pettie also asked how large must $s\left(n\right)$ be for there to exist $n$-block $DS(n,s\left(n\right))$ sequences of length $\Omega \left(n^{2-o\left(1\right)}\right)$. We answer this question by showing that the maximum possible length of an $n$-block $DS(n,s\left(n\right))$ sequence is $\Omega \left(n^{2-o\left(1\right)}\right)$ if and only if $s\left(n\right)=\Omega \left(n^{1-o\left(1\right)}\right)$. We also show related results for extremal functions of forbidden 0–1 matrices with any constant number of rows and extremal functions of forbidden sequences with any constant number of distinct letters.     

Efficient counting of degree sequences

We present formulas to count the set $D_0\left(n\right)$ of degree sequences of simple graphs of order $n$, the set $D\left(n\right)$ of degree sequences of those graphs with no isolated vertices, and the set $D_{k\text{\_}con}\left(n\right)$ of degree sequences of those graphs that are $k$-connected for fixed $k$. The formulas all use a function of Barnes and Savage and the associated dynamic programming algorithms all run in time polynomial in $n$ and are asymptotically faster than previous known algorithms for these problems. We also show that $\left|D\left(n\right)\right|$ and $\left|D_{1\text{\_}con}\left(n\right)\right|$ are asymptotically equivalent but $\left|D\left(n\right)\right|$ and $\left|D_0\left(n\right)\right|$ as well as $\left|D\left(n\right)\right|$ and $\left|D_{k\text{\_}con}\left(n\right)\right|$ with fixed $k\ge 2$ are asymptotically inequivalent. Finally, we explain why we are unable to obtain the absolute asymptotic orders of these functions from their formulas.     

On three color Ramsey numbers R(C4,C4,K1,n)

For $k$ given graphs $G_1,G_2,\dots ,G_k$, $k\ge 2$, the $k$-color Ramsey number, denoted by $R(G_1,G_2,\dots ,G_k)$, is the smallest integer $N$ such that if we arbitrarily color the edges of a complete graph of order $N$ with $k$ colors, then it always contains a monochromatic copy of $G_i$ colored with $i$, for some $1\le i\le k$. Let $C_m$ be a cycle of length $m$ and $K_{1,n}$ a star of order $n+1$. In this paper, firstly we give a general upper bound of $R(C_4,C_4,\dots ,C_4,K_{1,n})$. In particular, for the 3-color case, we have $R(C_4,C_4,K_{1,n})\le n+?\sqrt{4n+5}?+3$ and this bound is tight in some sense. Furthermore, we prove that $R(C_4,C_4,K_{1,n})\le n+?\sqrt{4n+5}?+2$ for all $n={?}^2??$ and $?\ge 2$, and if $?$ is a prime power, then the equality holds.     

A note on Hadwiger’s conjecture for W5-free graphs with independence number two

The Hadwiger number of a graph $G$, denoted $h\left(G\right)$, is the largest integer $t$ such that $G$ contains $K_t$ as a minor. A famous conjecture due to Hadwiger in 1943 states that for every graph $G$, $h\left(G\right)\ge \chi \left(G\right)$, where $\chi \left(G\right)$ denotes the chromatic number of $G$. Let $\alpha \left(G\right)$ denote the independence number of $G$. A graph is $H$-free if it does not contain the graph $H$ as an induced subgraph. In 2003, Plummer, Stiebitz and Toft proved that $h\left(G\right)\ge \chi \left(G\right)$ for all $H$-free graphs $G$ with $\alpha \left(G\right)\le 2$, where $H$ is any graph on four vertices with $\alpha \left(H\right)\le 2$, $H=C_5$, or $H$ is a particular graph on seven vertices. In 2010, Kriesell subsequently generalized the statement to include all forbidden subgraphs $H$ on five vertices with $\alpha \left(H\right)\le 2$. In this note, we prove that $h\left(G\right)\ge \chi \left(G\right)$ for all $W_5$-free graphs $G$ with $\alpha \left(G\right)\le 2$, where $W_5$ denotes the wheel on six vertices.