\documentclass[12pt]{article} \usepackage{e-jc} \usepackage{graphicx} \usepackage{amsmath} \usepackage{amsthm,amsfonts,amssymb,mathrsfs,amscd,amstext,amsbsy} \usepackage{paralist,enumerate} \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} \makeatletter \def\bbordermatrix#1{\begingroup \m@th \@tempdima 4.75\p@ \setbox\z@\vbox{% \def\cr{\crcr\noalign{\kern2\p@\global\let\cr\endline}}% \ialign{$##$\hfil\kern2\p@\kern\@tempdima&\thinspace\hfil$##$\hfil &&\quad\hfil$##$\hfil\crcr \omit\strut\hfil\crcr\noalign{\kern-\baselineskip}% #1\crcr\omit\strut\cr}}% \setbox\tw@\vbox{\unvcopy\z@\global\setbox\@ne\lastbox}% \setbox\tw@\hbox{\unhbox\@ne\unskip\global\setbox\@ne\lastbox}% \setbox\tw@\hbox{$\kern\wd\@ne\kern-\@tempdima\left[\kern-\wd\@ne \global\setbox\@ne\vbox{\box\@ne\kern2\p@}% \vcenter{\kern-\ht\@ne\unvbox\z@\kern-\baselineskip}\,\right]$}% \null\;\vbox{\kern\ht\@ne\box\tw@}\endgroup} \makeatother \theoremstyle{plain} \newtheorem{theorem}{Theorem}[section] \newtheorem{cor}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{conj}[theorem]{Conjecture} \newtheorem{cl}[theorem]{Claim} \newtheorem{theo}[theorem]{Theorem} \newtheorem{lem}[theorem]{Lemma} \newtheorem{pro}{Property} \newtheorem{prop}{Proposition} \newtheorem{obs}{Observation} \theoremstyle{definition} \newtheorem{dfn}[theorem]{Definition} \newtheorem{fact}[theorem]{Fact} \newtheorem{example}[theorem]{Example} \def\qed{\hfill \ifhmode\unskip\nobreak\fi\quad\ifmmode\Box\else$\Box$\fi\\ } \newcommand{\D}{\displaystyle} \newcommand{\EUP}{\mathrm{U}} \newcommand{\wEUP}{\mathrm{U}'} \newcommand{\EVP}{\mathrm{V}} \newcommand{\wEVP}{\mathrm{V}'} \def\VEC#1#2#3{#1_{#2},\ldots,#1_{#3}} \def\VECOP#1#2#3#4{#1_{#2}#4\cdots#4#1_{#3}} \def\FR#1#2{\frac{#1}{#2}} \def\FL#1{\left\lfloor{#1}\right\rfloor} \def\CL#1{\left\lceil{#1}\right\rceil} \def\NN{\mathbb{N}} \def\CH#1#2{\binom{#1}{#2}} \def\SE#1#2#3{\sum_{#1=#2}^{#3}} \begin{document} \title{Equicovering Subgraphs of Graphs and Hypergraphs} \author{Ilkyoo Choi\\ \small Mathematics Department\\[-0.8ex] \small University of Illinois\\[-0.8ex] \small Illinois, U.S.A.\\ \small\tt ichoi4@illinois.edu.\\ \and Jaehoon Kim\thanks{Research partially supported by the Arnold O. Beckman Research Award of the University of Illinois at Urbana-Champaign.}\\ \small Mathematics Department\\[-0.8ex] \small University of Illinois\\[-0.8ex] \small Illinois, U.S.A.\\ \small\tt kim805@illinois.edu.\\ \and Amelia Tebbe\\ \small Mathematics Department\\[-0.8ex] \small University of Illinois\\[-0.8ex] \small Illinois, U.S.A.\\ \small\tt tebbe2@illinois.edu.\\ \and Douglas B. West\thanks{Research partially supported by NSA Award H98230-10-1-0363.}\\ \small Mathematics Department\\[-0.8ex] \small Zhejiang Normal University and University of Illinois\\[-0.8ex] \small Illinois, U.S.A.\\ \small\tt west@math.uiuc.edu.} \date{\dateline{ }{ }\\ \small Mathematics Subject Classifications: 05C35, 05C65} \maketitle \begin{abstract} As a variation on the $t$-Equal Union Property ($t$-EUP) introduced by Lindstr\"om, we introduce the {\it $t$-Equal Valence Property} ($t$-EVP) for hypergraphs: a hypergraph satisfies the $t$-EVP if there are $t$ pairwise edge-disjoint subhypergraphs such that for each vertex $v$, the degree of $v$ in all $t$ subhypergraphs is the same. In the $t$-EUP, the subhypergraphs just have the same sets of vertices with positive degree. For both the $2$-EUP and the $2$-EVP, we characterize the graphs satisfying the property and determine the maximum number of edges in a graph not satisfying it. We also study the maximum number of edges in both $k$-uniform and general hypergraphs not satisfying the $t$-EVP. \end{abstract} \baselineskip 16pt \section{Introduction}%%%%%%%%%%%% INTRODUCTION We consider conditions for a hypergraph to have $t$ edge-disjoint subhypergraphs whose local behavior at vertices is somehow ``the same''. Such structures may be useful for fault-tolerance of communication protocols. Lindstr\"om~\cite{Lind72} introduced a precise notion of such a property. The {\it degree} (or {\it valence}) of a vertex $v$ in a hypergraph $H$, written $d_H(v)$, is the number of edges containing $v$. The {\it span} of $H$, written $S(H)$, is the set of vertices with positive degree. \begin{dfn} A hypergraph $H$ satisfies the \emph{$t$-Equal Union Property ($t$-EUP)} if $H$ has $t$ edge-disjoint distinct subhypergraphs $H_1,\ldots,H_t$ with the same span. If the spans are equal but $H_1,\ldots,H_t$ are not edge-disjoint, then $H$ satisfies the {\it weak $t$-EUP}. \end{dfn} When the $t$-EUP holds, the union of the edges is the same for each subhypergraph. Note that the hypergraph whose edges are the lines in the Fano plane does not satisfy the $2$-EUP. Lindstr\"om~\cite{Lind72} studied the number of edges needed in an $n$-vertex hypergraph to guarantee the $t$-EUP. Tverberg~\cite{Tver71} gave an algebraic proof of Lindstr\"om's result. \begin{theo}{\rm\cite{Lind72}} $n$-vertex hypergraphs with more than $n(t-1)$ edges satisfy the $t$-EUP. \end{theo} A hypergraph is {\it $k$-uniform} if every edge has size $k$. For $t=2$ and ordinary graphs ($2$-uniform hypergraphs) the bound is sharp, since when $n$ is odd an $n$-cycle has $n$ edges but does not satisfy the $2$-EUP. On the other hand, the existence of an even cycle is clearly sufficient, and we show in Theorem~\ref{t21} that a graph satisfies the $2$-EUP if and only if it has a even cycle or has a component containing two odd cycles. The Fano plane is a $3$-uniform hypergraph with seven vertices and seven edges that does not satisfy the $2$-EUP, thereby providing another sharpness example. It is natural to require more than equal span for the common behavior in each subgraph. We introduce the {\it $t$-Equal Valence Property} ($t$-EVP), more restrictive than the $t$-EUP. \begin{dfn} A hypergraph $H$ satisfies the {\it $t$-Equal Valence Property} ($t$-EVP) if $H$ has $t$ edge-disjoint distinct subhypergraphs $H_1,\ldots,H_t$ such that $d_{H_1}(v)=\dots=d_{H_t}(v)$ for each $v\in V(H)$. If the valence condition holds but $H_1,\ldots,H_t$ are not edge-disjoint, then $H$ satisfies the {\it weak $t$-EVP}. \end{dfn} Every hypergraph having $t$ perfect matchings satisfies the $t$-EVP; this includes $t$-regular $t$-edge-colorable graphs and the hypergraphs of resolvable designs (such as affine planes). %The $3$-uniform hypergraph with vertex set $\{a,b,c,x,y,z\}$ and edge set %$\{\{a,b,c\},\{x,y,z\},\{a,b,z\},\{a,y,c\},\{x,b,c\}\}$ %satisfies the $2$-EUP but not the $2$-EVP. \begin{example} {\it Projective planes satisfy the $2$-EUP but not the $2$-EVP.} A sufficient (but not necessary) condition for the $t$-EUP is existence of a $t$-coloring of the edges so that each vertex has at least one incident edge of each color. Although the Fano plane has no such coloring, larger projective planes do. A {\it projective plane} of order $q$ is a $(q+1)$-uniform hypergraph with $q^2+q+1$ points and $q^2+q+1$ edges (called {\it lines}), in which every two lines have exactly one common point, every two points appear in exactly one common line, and there exist four points among which no three appear in one line. Such hypergraphs exist whenever $q$ is a power of a prime. Given a projective plane, let $S$ be a fixed set of three points not on a common line. For each line $L$, give color $a$ to $L$, where $|L\cap S|\equiv a\mod 2$. It is easy to check that each point appears in lines of both colors. On the other hand, if a projective plane of order $q$ satisfies the $2$-EVP, then we have vertices $\VEC v1n$ (where $n=q^2+q+1$) and edge-disjoint subhypergraphs $H$ and $H'$ such that $d_H(v_i)=d_{H'}(v_i)=d_i$ for some numbers $\VEC d1n$. Since the hypergraph is uniform and the degree sum is the same, $|E(H)|=|E(H')|$; let $H$ and $H'$ both have $s$ edges. We claim first that $s^2=\SE i1n d_i^2$. Both sides equal $\sum |e\cap e'|$, summed over $e\in E(H)$ and $e'\in E(H')$. Each term equals $1$, and there are $s^2$ terms. On the other hand, since $v_i$ belongs to $d_i$ edges in $H$ and $d_i$ edges in $H'$, each vertex $v_i$ contributes exactly $d_i^2$ times. Next, we claim that $s(s-1)=\SE i1n d_i(d_i-1)$. Both sides equal $\sum|e_i\cap e_j|$, summed over ordered pairs of distinct edges in $H$. Again all terms equal $1$, and there are $s(s-1)$ terms. Since vertex $v_i$ appears in $d_i$ edges, it contributes $d_i(d_i-1)$ times. Subtracting now yields $s=\SE i1n d_i$, but $\SE i1n d_i=s(q+1)$, since each edge has size $q+1$. We conclude $q=0$, but there is no projective plane of order $0$. \end{example} We study the extremal problem posed by Lindstr\"om and the analogous extremal problem for equal valence, considering also the restrictions to $k$-uniform hypergraphs. Let $\EUP(n,t)$ denote the maximum number of edges in an $n$-vertex hypergraph not satisfying the $t$-EUP. Let $\EUP_k(n,t)$ denote the maximum number of edges in a $k$-uniform $n$-vertex hypergraph not satisfying the $t$-EUP. Let $\wEUP(n,t)$ and $\wEUP_k(n,t)$ denote the analogous maximum numbers of edges for avoiding the weak $t$-EUP (we avoid trivialities by not allowing two subhypergraphs to have exactly the same edge set). For the $t$-EVP, use $\EVP$ instead of $\EUP$ to define the corresponding extremal problems. By definition, $A(n,t)\ge A_k(n, t)$ for $A\in\{\EUP,\wEUP,\EVP,\wEVP\}$. \begin{center} \begin{tabular}{c||c|c||c|c} $n$-vertex & $t$-EUP & weak $t$-EUP & $t$-EVP & weak $t$-EVP \\ \hline graphs & $\EUP_2(n,t)$ & $\wEUP_2(n,t)$ & $\EVP_2(n,t)$ & $\wEVP_2(n,t)$\\ $k$-uniform hypergraphs & $\EUP_k(n,t)$ & $\wEUP_k(n,t)$ & $\EVP_k(n,t)$ & $\wEVP_k(n,t)$\\ general hypergraphs & $\EUP(n, t)$ & $\wEUP(n,t)$ & $\EVP(n,t)$ & $\wEVP(n,t)$ \end{tabular} \end{center} Like the $2$-EUP, the $2$-EVP has a simple characterization for graphs; we show in Theorem~\ref{t23} that a graph satisfies the $2$-EVP if and only if it contains an even circuit (a closed trail of even length). The characterizations in Section $2$ yield $\EUP_2(n,2)=\wEUP_2(n,2)=n$ and $\EVP_2(n,2)=\wEVP_2(n,2)=\lfloor{4\over 3}n\rfloor -1$. In Section $3$, we prove $\wEVP_2(n,3)=\lfloor{4\over 3}n\rfloor$ and $\left(t-1+{1\over 2(t-1)}\right)(n-1)-(t-2)^2\le\EVP_2(n,t)\le(2+o(1))(t-1)n$. In Section $4$, we consider $k$-uniform hypergraphs. We prove $\EVP_k(n,2)\in O(n)$ and $\EVP(n,2)\in O(n\log n)$. We also prove $\EVP(n,t),\EVP_k(n,t)\in O\left(n^2\left({\log n\over\log\log\log n}\right)^2\right)$ and obtain a lower bound for $\EVP_k(n,2)$. We close this introduction with several simple observations used in later proofs. \begin{obs} The weak $2$-EVP and the $2$-EVP are equivalent. Thus $\EVP(n,2)=\wEVP(n,2)$, and $\EVP_k(n, 2) = \wEVP_k(n,2)$ for $k\ge2$. \end{obs} \begin{proof} If subhypergraphs $H_1$ and $H_2$ witness the weak $2$-EVP, then $H_1-E(H_1)\cap E(H_2)$ and $H_2-E(H_1)\cap E(H_2)$ witness the $2$-EVP, since each vertex loses the same number of incident edges from $H_1$ and $H_2$. \end{proof} \vspace{-1pc} \begin{obs} $\wEUP(n,t) < n + \log_2 t \text{ and } \wEUP_k(n, t)<\log_2 \left(\sum_{i=k}^n{n\choose i}\right)+\log_2 t. $ \end{obs} \begin{proof} A hypergraph with $m$ edges has $2^m$ distinct subhypergraphs. An $n$-vertex hypergraph $H$ with $\lceil n+\log_2 t \rceil$ edges has at least $t2^n$ distinct subhypergraphs. Since there are only $2^n$ choices for the span of a subhypergraph of $H$, by the pigeonhole principle there are $t$ distinct subhypergraphs with the same span. Thus $H$ satisfies the weak $t$-EUP. The second statement uses the fact that the span of nonempty $k$-uniform subhypergraphs has size at least $k$. \end{proof} \vspace{-1pc} \begin{obs}\label{o3} $\EVP_k(n+1,t)\ge \EVP_{k-1}(n,t)$ for $k\ge3$. \end{obs} \begin{proof} Let $H$ be a $(k-1)$-uniform hypergraph not satisfying the $t$-EVP. Form $H'$ from $H$ by adding one vertex $x$ belonging to every edge. If $\VEC{H'}1t$ witness the $t$-EVP in $H'$, then deleting $x$ from each edge in each $H'_i$ yields $\VEC H1t$ witnessing the $t$-EVP in $H$. \end{proof} \vspace{-1pc} \begin{obs}\label{cutedge} If $H_1$ and $H_2$ have equal degree at every vertex of $G$, then their symmetric difference contains no cut-edge of $G$. \end{obs} \begin{proof} Let $e$ be a cut-edge of $G$ contained in $H_1$ but not $H_2$. Let $G'$ be a component of $G-e$. The sum of the degrees of the subgraphs of $H_1$ and $H_2$ in $G'$ differ by $1$. Hence one of them is a graph with odd degree sum, which does not exist. \end{proof} \vspace{-1pc} \begin{obs}\label{emptyfull} If $\VEC H1t$ witness the weak $t$-EVP in $G$, with degree $0$ at $v$ or degree $d_G(v)$ at $v$, then deleting $v$ yields graphs $\VEC {H'}1t$ witnessing the weak $t$-EVP in $G-v$. \end{obs} \begin{proof} Since the usage of edges incident to $v$ is the same in each $H_i$, ignoring those edges also contributes the same degree from all $t$ subgraphs at each of the remaining vertices. \end{proof} \section{The $2$-EUP and the $2$-EVP for Graphs}%%%%%%%%% SECTION 2 Our graphs have no repeated edges or loops. A {\it walk} in a graph is a list of vertices in which every two consecutive vertices are adjacent (edges may repeat). A {\it trail} is a walk that traverses each edge at most once (vertices may repeat). A walk or trail is {\it closed} if its first and last vertices are the same. A {\it circuit} is a closed trail. A {\it cycle} in a graph is a connected subgraph in which every vertex has degree $2$. The {\it length} of a walk, trail, circuit, or cycle is the number of edges it traverses, and the object is {\it even} or {\it odd} as its length is even or odd. We characterize the graphs satisfying the $2$-EUP (Theorem~\ref{t21}) and the graphs satisfying the $2$-EVP (Theorems~\ref{t23}--\ref{t24}). From the characterizations, we determine $\EUP_2(n,2)$, $\wEUP_2(n,2)$, $\EVP_2(n,2)$, and $\wEVP_2(n,2)$. \begin{theo}\label{t21} A graph $G$ satisfies the $2$-EUP if and only if $G$ has an even cycle or has a component containing two odd cycles. \end{theo} \begin{proof} {\it (Sufficiency)} Alternating edges along an even cycle gives two subgraphs witnessing the $2$-EUP. Now, let $G$ have a component containing odd cycles $C_1$ and $C_2$. If $C_1$ and $C_2$ share an edge, then $G$ has an even cycle. Otherwise, let $P$ be a shortest path joining $V(C_1)$ and $V(C_2)$, with endpoints $u\in V(C_1)$ and $v\in V(C_2)$. Let $T$ be a trail that starts at $u$, follows $C_1$, moves from $u$ to $v$ through $P$, and follows $C_2$. Alternating edges along $W$ gives two subgraphs with vertex set $V(C_1)\cup V(C_2)\cup V(P)$. {\it (Necessity)} Let $G_1$ and $G_2$ be two subgraphs of $G$ witnessing the $2$-EUP, and take $u_0u_1 \in E(G_1)-E(G_2)$. Since $u_1$ must be covered by both $E(G_1)$ and $E(G_2)$, there exists $u_1u_2 \in E(G_2)$. Iteratively, we find $u_iu_{i+1} \in E(G_1)$ and $u_{i+1}u_{i+2} \in E(G_2)$ for even $i$. Since $G$ is finite, $u_{k} = u_{k+r}$ for some $r$ and $k$. Taking the first such repetition, $u_k,\ldots,u_{k+r-1}$ form a cycle. If $r$ is even, then $G$ has an even cycle. If $r$ is odd, then by symmetry we may assume that $u_ku_{k+1}$ and $u_{k}u_{k+r-1}$ are both in $E(G_1)$. Since $G_1$ and $G_2$ have the same span, we find $v_1$ such that $u_kv_1 \in E(G_2)$. We now generate $v_1,v_2,\ldots$ as above, with $v_jv_{j+1}\in E(G_1)$ and $v_{j+1}v_{j+2}\in E(G_2)$ for odd $j$, until we obtain $v_{l}=v_{l+s}$ or $v_{l}=u_{s}$ for some $l$ and $s$ with $s>k$; consider the first such occurrence. (In particular, we ignore $\VEC u0{k-1}$, as if they had never been defined.) If $v_l=v_{l+s}$, then $v_l, \ldots, v_{l+s-1}$ form an even cycle when $s$ is even. If $s$ is odd, then $[v_l, \ldots, v_{l+s-1}]$ and $[u_k, \ldots, u_{k+r-1}]$ form two odd cycles in the same component of $G$. If $v_l=u_s$, then the edges we have discovered form three internally disjoint paths joining $u_k$ and $u_s$. The union of some two of them is an even cycle. \end{proof} \begin{cor}\label{c22} If a graph $G$ does not satisfy the $2$-EUP, then $|E(G)|\leq n$. Equality holds if and only if every component of $G$ has at most one cycle and all cycles in $G$ have odd length. Thus $\EUP_2(n,2)=n$. \end{cor} A {\it nontrivial graph} is a graph having an edge. \begin{theo} \label{t23} A graph $G$ satisfies the $2$-EVP if and only if it has an even circuit. \end{theo} \begin{proof} {\it (Sufficiency)} If $G$ has an even circuit, then alternating edges along it provides two subgraphs witnessing the $2$-EVP. {\it (Necessity)} Let $H_1$ and $H_2$ be two subgraphs witnessing the $2$-EVP in $G$. Since $H_1$ and $H_2$ have the same number of edges and have equal degree at each vertex, their union $H$ is a nontrivial graph whose components have an even number of edges and have even degree at each vertex. Hence $H$ decomposes into cycles. If any such cycle has even length, then $G$ contains an even circuit. Otherwise, all cycles in the decomposition of a nontrivial component of $H$ have odd length, and there are an even number of them. Since a connected union of cycles has no cut-edge, two such odd cycles $C$ and $C'$ are joined by two edge-disjoint paths $P$ and $P'$ in $H$. The endpoints of $P$ and $P'$ on $C$ are connected by two paths of opposite parity along $C$, and the same is true along $C'$. Hence the union of $P$, $P'$, and appropriate paths connecting them in $C$ and $C'$ is a subgraph traversed by an even circuit. \end{proof} A {\it cactus} is a connected graph in which every edge is in at most one cycle. A {\it strict odd cactus} is a cactus in which every cycle has odd length and no two cycles share a vertex. \begin{theo} \label{t24} A graph $G$ fails to satisfy the $2$-EVP if and only if every component is a strict odd cactus. \end{theo} \begin{proof} {\it (Sufficiency)} Theorem~\ref{t23} applies, since a strict odd cactus contains no even circuit. {\it (Necessity)} We use induction on $n$, where $n=|V(G)|$. Let $G$ be an $n$-vertex graph not satisfying the $2$-EVP. For $n\le 3$, the statement is true. For larger $n$, since every tree is a strict odd cactus, we may assume that $G$ has a cycle $C$; avoiding the $2$-EVP requires $C$ to be odd. If $G=C$, then $G$ is a strict odd cactus. Otherwise, both $G-V(C)$ and $C$ have fewer than $n$ vertices and do not satisfy the $2$-EVP. By the induction hypothesis, each component of $G-V(C)$ is a strict odd cactus. If at most one edge joins $V(C)$ to any such component $H$, then again every component of $G$ is a strict odd cactus. Finally, consider edges $xy$ and $x'y'$ with $x,x'\in V(C)$ and $y,y'\in V(H)$. Combining these two edges with a $y,y'$-path in $H$ yields an $x,x'$-path that is disjoint from $C$ except for its endpoints. Now adding one of the paths from $x$ to $x'$ along $C$ completes an even circuit, witnessing the $2$-EVP for $G$. Hence this possibility does not occur, and every component of $G$ is a strict odd cactus. \end{proof} \vspace{-1.5pc} \begin{theo} \label{t25} If an $n$-vertex graph $G$ does not satisfy the $2$-EVP, then $|E(G)|\leq \lfloor \frac{4}{3} n \rfloor -1 $. Also, the bound is sharp, so $\EVP_2(n,2) = \lfloor \frac{4}{3}n \rfloor -1$. \end{theo} \begin{proof} By Theorem~\ref{t24}, every component of $G$ is a strict odd cactus. A largest such graph on $n$ vertices is connected. If $G$ has $k$ cycles, then $k\le\FL{n/3}$, since each cycle has length at least $3$ and the cycles share no vertices. Also, deleting one edge from each cycle yields a tree. Hence $|E(G)|=n-1+k\le\FL{\FR43n}-1$. Equality holds for any strict odd cactus having $\FL{n/3}$ triangles and $j$ vertices not in triangles, where $n\equiv j\mod 3$ with $j\in\{0,1,2\}$. \end{proof} \section{The $t$-EVP for Graphs }%%% SECTION 3 In this section we study $\EVP_2(n,t)$. We give an upper bound in Theorem~\ref{t33} using a theorem of Alon, Friedland, and Kalai~\cite{AFK}. In Theorem~\ref{c34}, we construct a sequence of graphs to provide a lower bound. We close the section by determining $\wEVP_2(n,3)$ exactly in Theorem~\ref{t37}. We begin with two well-known facts. \begin{fact} \label{f1} Every graph $G$ has a bipartite subgraph $H$ with $|E(H)|\geq \frac{1}{2}|E(G)|$. \end{fact} \begin{fact} \label{f2} {\rm \cite{E32}} For $k\geq 2$, there exists a prime number $p$ such that $k\leq p < 2k$. \end{fact} For $q\in\NN$, a {\it $q$-divisible} graph is a graph where every vertex degree is a multiple of $q$. \begin{theo} \label{t32} {\rm \cite{AFK}} If $q$ is a prime power, then every $n$-vertex graph $G$ with $|E(G)|\geq (q-1)n +1$ contains a $q$-divisible subgraph. \end{theo} \begin{lem} \label{l31} Every $t$-divisible bipartite graph $G$ satisfies the $t$-EVP. \end{lem} \begin{proof} For $v\in V(G)$, let $c(v)=d_G(v)/t$. Form a graph $G'$ by expanding each vertex $v\in V(G)$ into an independent set of size $c(v)$ in which each vertex inherits $t$ of the edges incident to $v$. The graph $G'$ is $t$-regular and bipartite, so $G'$ decomposes into $t$ edge-disjoint perfect matchings. These perfect matchings correspond to $t$ edge-disjoint subgraphs $H_1, \ldots, H_t$ of $G$, each having degree $c(v)$ at $v$. Thus $\VEC H1t$ witness the $t$-EVP for $G$. \end{proof} \begin{theo} \label{t33} If $t$ is a prime power, then $\EVP_2(n,t)\le 2(t-1)n$. In general, $\EVP_2(n,t)\le 2.4(t-1)n$ and $\EVP_2(n,t)\le (2+o(1))(t-1)n$. \end{theo} \begin{proof} Let $G$ be an $n$-vertex graph. If $|E(G)|>m$ implies that $G$ satisfies the $t$-EVP, then $\EVP_2(n,t)\le m$. Suppose first that $t$ is a prime power and $|E(G)|>2(t-1)n$. By Fact~\ref{f1}, $G$ has a spanning bipartite subgraph $H$ such that $|E(H)|> (t-1)n$. By Theorem~\ref{t32}, $H$ contains a $t$-divisible subgraph $Q$. By Lemma~\ref{l31}, $Q$ satisfies the $t$-EVP, and hence $G$ does also. Consider general $t$ and $|E(G)|>2.4(t-1)n$. By the preceding paragraph, it suffices to find a prime power $q$ between $t$ and $1.2t$. By Fact \ref{f2} (Bertrand's Postulate), there is a prime number between $t$ and $2t-1$. For $t\ge25$, Nagura~\cite{N} proved that there is a prime between $t$ and $1.2t$. For $2\le t\le24$, there fails to be a prime in the desired range for $t\in\{4,8,14,24\}$. However, for these values there is a prime power in the desired range. Meanwhile, Iwaniec and Pintz~\cite{IP} proved that there exists $t_0\in\NN$ such that for $x>t_0$, there is a prime between $x-x^{23/42}$ and $x$. This yields $\EVP_2(n,t)\le (2+o(1))(t-1)n$ in the same way as above. The value $23/42$ was further reduced to $.525$ in~\cite{BHP}. \end{proof} %\vspace{-1pc} %\begin{center} %\begin{tabular}{c|ccccccc} %$t$& 6&10&12&14,15&18&20,21,22&24\\ %\hline %$q$& 7&11&13& 16 &19& 23 &25 %\end{tabular} %\end{center} Alon, Friedland, and Kalai~\cite{AFK} conjectured that the conclusion of Theorem~\ref{t32} holds even when $q$ is not a power of a prime. This would improve the upper bound on $\EVP_2(n,t)$ from $2.4(t-1)n$ to $2(t-1)n$. A graph is {\it $k$-degenerate} if every subgraph has a vertex of degree at most $k$. In a $(t-1)$-degenerate graph, every nontrivial subgraph has a vertex that cannot occur in the span of $t$ edge-disjoint subgraphs, so $(t-1)$-degenerate graphs cannot satisfy the $t$-EVP. There is an $n$-vertex $(t-1)$-degenerate graph with as many as $\CH t2+(t-1)(n-t)$ edges, so $\EVP_2(n,t)\geq (t-1)(n-t/2)$. We improve the leading coefficient. \begin{theo} \label{t35} \label{c34} $\EVP_2(n,t)\ge\left(t-1+\frac{1}{2t-2}\right)(n-1)-(t-2)^2$. \end{theo} \begin{proof} The {\it $k$-fold wheel} $W_{k,r}$ is obtained from the complete bipartite graph $K_{k,r}$ by adding the edges of a cycle through the $r$ vertices of degree $k$, giving them degree $k+2$. Call the vertices of degree $r$ {\it centers}, the vertices of degree $k+2$ {\it rim vertices}, and the edges joining central and rim vertices {\it spokes}. In any copy of $W_{k,r}$, specify two distinct rim vertices as the {\it head} and {\it tail}. Note that $W_{k,r}$ has $k+r$ vertices and $r(k+1)$ edges. For $t\ge2$, let $\VEC B1\ell$ be copies of $W_{t-2,t+1}$. Let $z_i$ denote the tail of $B_i$ (and $z_0$ denote the head of $B_1$). For $1\le i<\ell$, merge $z_i$ with the head of $B_{i+1}$. Add edges joining all centers of $B_i$ to all centers of $B_{i+1}$, for $1\le i<\ell$. Let $G_t^\ell$ be the resulting graph. Note that $G_t^\ell$ has $\ell(2t-2)+1$ vertices and $\ell (t+1)(t-1)+(\ell-1)(t-2)^2$ edges. Writing $n=\ell(2t-2)+1$, the number of edges becomes $(t-1+\FR1{2t-2})(n-1)-(t-2)^2$. Hence it suffices to show that $G^\ell_t$ does not satisfy the $t$-EVP. Suppose that $\VEC H1t$ are subgraphs of $G_t^\ell$ witnessing the $t$-EVP. Let $H=\VECOP H1t\cup$; each vertex degree in $H$ is a multiple of $t$. Say that the edges of $H$ are ``used''. The edges of $G^\ell_t$ that are not spokes form a $(t-2)$-degenerate graph, so some spoke must be used. Each rim vertex other than $\VEC z0\ell$ has degree $t$. Let $i$ be the least index such that some spoke in $B_i$ is used. If only spokes incident to $z_i$ are used, then some center of $B_i$ has degree between $1$ and $t-1$. Hence some spoke not incident to $z_i$ is used. Since rim vertices have degree $t$ in $B_i$ and form a connected subgraph, it follows that all edges of $B_i$ are used except possibly some spokes incident to $z_i$. If any spoke incident to $z_i$ is used, then its other endpoint has degree between $t+1$ and $2t-1$ in $H$ ($t+1$ rim vertices and up to $t-2$ centers in $B_{i+1}$). Hence no spoke of $B_i$ at $z_i$ is used, but all other edges of $B_i$ are used. Now $z_i$ has two neighbors in $H$ that are rim vertices of $B_i$, plus up to $t$ neighbors in $B_{i+1}$. Hence $d_H(z_i)=t$. This requires the rim edges of $B_i$ at $z_i$ to belong to $H_a$ and $H_b$ with $a\ne b$. The remaining vertices of $B_i$ have neighbors only in $V(B_i)$ in $H$, and hence $H_a$ must form a matching there. However, $|V(B_i)|=2t-1$, so no such matching is possible. When $n\not\equiv 1\mod 2(t-1)$, we may add one small complete graph and possibly one copy of $K_t$ to $G_t^\ell$ (where $\ell=\FL{n/(2t-2)}$) to reach $n$ vertices. \end{proof} The remainder of this section determines $\wEVP_2(n,3)$. We start with the lower bound. \begin{lem}\label{oneeven} A graph containing at most one even circuit does not satisfy the weak $3$-EVP. \end{lem} \begin{proof} Suppose that $G$ satisfies the weak $3$-EVP, witnessed by three distinct nontrivial subgraphs $H_1,H_2,H_3$ having equal degrees at each vertex. Since $H_1$ and $H_2$ are distinct and have the same vertex degrees, the symmetric difference of $H_1$ and $H_2$ is nontrivial, has even degree at each vertex, and has an even number of edges in each component (the same number from both $H_1$ and $H_2$). Hence each nontrivial component can be expressed as an even circuit. The same is true for $H_1$ and $H_3$, which cannot have the same components since $H_2$ and $H_3$ are distinct. Hence $G$ contains at least two even circuits. \end{proof} \begin{lem}\label{lower3evp} $\wEVP_2(n,3)\ge\lfloor\frac43n\rfloor$ for $n>3$. \end{lem} \begin{proof} Let $j$ be the congruence class of $n$ modulo $3$, with $j\in\{0,1,2\}$. Let $G$ be a maximal strict odd cactus with $n$ vertices. As computed in Theorem~\ref{t24}, $G$ has $\FL{\frac43n}-1$ edges and no even circuit; also $G$ has $\FL{n/3}$ triangles and $j$ vertices not in triangles. Further restrict $G$ when $n\equiv 2$ so that the vertices not in triangles are leaves with a common neighbor. In each case, we add one edge to $G$. When $j=1$, add one edge joining the vertex $v$ that lies in no triangle to a vertex of a nearest triangle; this creates one even circuit (of length 4). When $j=2$, add one edge joining the two leaves not in triangles, creating one even circuit (of length 6). By Lemma~\ref{oneeven}, the resulting graph does not satisfy the weak $3$-EVP. We construct an explicit example $G'$ for $n=6$, consisting of disjoint triangles on $abc$ and $xyz$ plus edges $ax$ and $by$. Every proper induced subgraph of $G'$ has at most one even circuit and does not satisfy the weak $3$-EVP, by Lemma~\ref{oneeven}. Hence by Lemma~\ref{emptyfull} subgraphs witnessing it have degree $1$ at $c$ and $z$ and have degree $1$ or $2$ at the other vertices. If all have degree $1$, then the subgraphs are perfect matchings, but $G'$ has only two perfect matchings. If all have degree $2$, then they omit a perfect matching, and again there are only two. Hence we may assume that exactly two vertices have degree $2$. By symmetry, consider cases for the degrees of $x$ and $y$, with $d(x)\ge d(y)$. If $d(x)>d(y)$, then $xz$ must appear in each subgraph. By reasoning as in Lemma~\ref{emptyfull}, $G'-z$ then satisfies the weak $3$-EVP, which it does not. If $d(x)=d(y)$, then in each case a subgraph with the specified degrees is determined by choosing $xz$ or $yz$, so again there are only two. %We construct an explicit example $G'$ for $n=6$. Let $G'$ consist of disjoint %triangles on $abc$ and $xyz$ plus edges from $a$ to $x$ and $y$. Every proper %induced subgraph of $G'$ has at most one even circuit, so subgraphs %$H_1,H_2,H_3$ witnessing the weak $3$-EVP must span all vertices. The edge %$bc$ cannot belong to all or none of them, because $G'-\{b,c\}$ does not %satisfy the weak $3$-EVP. Hence we may assume $bc\in E(H_1)-E(H_2)$ and %$ba,ac\in E(H_2)-E(H_1)$. Hence $xa,ay\in E(H_1)-E(H_2)$. Next, nonzero %degree at $z$ allows us to assume $zx\in E(H_1)$, by symmetry. Hence %$d_{H_i}(x)=2$, forcing $xz,xy\in E(H_2)$ and $xy\notin E(H_1)$. Also, $zy$ %appears in both or neither of $\{H_1,H_2\}$. When we now consider $H_3$, it %must agree with $H_1$ or $H_2$ on whether it includes $bc$. Comparing it with %the other yields the same argument as above, forcing $H_3$ to be the same as %$H_1$ or $H_2$. For larger multiples of $3$, we use this $6$-vertex subgraph $G'$ plus a maximal strict odd cactus $\hat G$ on $n-6$ vertices joined to $G'$ by a single cut-edge $e$. If there exist $H_1,H_2,H_3$ witnessing the weak $3$-EVP in $G$, then any two of them have equal degrees at all vertices. By Observation~\ref{cutedge}, the symmetric difference of any two cannot contain the cut-edge $e$. Hence all three agree on $e$. Hence $G-e$ satisfies the weak $3$-EVP. This requires the weak $3$-EVP to hold in $\hat G$ or $G'$, which it does not. \end{proof} The upper bound needs several lemmas. \begin{lem} \label{l36} Let $G$ be a graph. (a) If $G$ has $\lceil \log_2{t} \rceil $ edge-disjoint even circuits, then $G$ satisfies the weak $t$-EVP. (b) If $G$ has three edge-disjoint trails with the same endpoints whose lengths have the same parity, then $G$ satisfies the weak 3-EVP. \end{lem} \begin{proof} (a) Let $s= \lceil \log_2{t} \rceil$, so $2^s\geq t$, and let $C_1,\ldots, C_s$ be the given edge-disjoint even circuits. There are two ways to take alternating edges on each circuit. Hence at least $t$ distinct subgraphs of $C_1\cup\cdots\cup C_s$ have the same degrees at all vertices. (b) Consider three edge-disjoint $u,v$-trails. If all have even length, then take alternating edges in each trail, starting at $u$ in two of the trails. Each way of doing this yields the same degree at all vertices. The three ways to do it yield the weak $3$-EVP. If all have odd length, then the union of two form an even circuit. Take alternating edges from the other so that $u$ and $v$ are not covered, plus alternating edges along the circuit. The three ways to choose a pair of trails and two ways to choose edges along the circuit yield six subgraphs having the same degree at all vertices. Thus $G$ satisfies the weak $6$-EVP. \end{proof} \begin{lem}\label{reduce} If $G$ has a path through $w,x,y,z$ such that $d_G(x)=d_G(y)=2$, then $G$ satisfies the weak $t$-EVP if and only if $G'$ satisfies the weak $t$-EVP, where $G'= G-\{x,y\}\cup wz$. \end{lem} \begin{proof} If $\VEC {H'}1t$ witness the $t$-EVP in $G'$, then modify each $H'_i$ as follows. If $wz\in E(H'_i)$, then put $wx,yz\in E(H_i)$ and $xy\notin E(H_i)$, leaving the usage of all other edges the same. If $wz\notin E(H'_i)$, then put $xy\in E(H_i)$ and $wx,yz\notin E(H_i)$, again leaving other edges as in $H'_i$. In each $H_i$, the degree is $1$ at $x$ and at $y$, and at all other vertices it is the same as in $H'_i$, so $\VEC H1t$ witness the $t$-EVP in $G'$. For the converse, let $\VEC H1t$ witness the $t$-EVP in $G$. If each subgraph has degree $1$ at both $x$ and $y$, then the transformation above can be reversed. If the subgraphs all have degree $0$ or degree $2$ at $x$ or $y$, then they all have the same usage of each edge in $\{wx,xy,yz\}$. Now letting $H'_i=H_i-\{x,y\}$ for all $i$ yields subgraphs witnessing the $t$-EVP in $G'$ (they all omit the edge $wz$). \end{proof} We apply Lemma~\ref{reduce} to subdivisions of $K_4$ that arise in the proof of the upper bound. \begin{lem}\label{K4} Let $G$ be a subdivision of $K_4$, and call the paths joining branch vertices ``threads''. If $G$ has an odd cycle $C$ through three branch vertices, and the cycles through exactly two threads of $C$ all have even length, then $G$ satisfies the weak $3$-EVP. \end{lem} \begin{proof} By Lemma~\ref{reduce}, we may assume that every thread has length $1$ or $2$. When all threads in $C$ have length $1$, the three threads incident to the remaining vertex $z$ all have the same parity. If they are single edges, then use the decomposition of $K_4$ into three matchings $M_1,M_2,M_3$. Otherwise, the threads at $z$ each have length $2$. Each subgraph $H_i$ uses one edge incident to $z$ and a path of length $4$ joining the other two neighbors of $z$. If only one thread in $C$ has odd length, then the lengths of the two threads from its endpoints to $z$ have the same parity. If they have length $1$, then we can treat that cycle as $C$ above. If they have length $2$, then the other thread at $z$ has length $1$; now exactly two threads (with no shared endpoints) have odd length, and our graph $G$ is obtained from $K_4$ by subdividing the edges of a $4$-cycle. The $8$-cycle has two crossing chords; call them $uv$ and $u'v'$. Pairing $uv$ with each of the two perfect matchings in the $8$-cycle generates two subgraphs with the same vertex degrees. A third such subgraph uses $u'v'$ and the edges at $u$ and $v$ other than $uv$. Hence $G$ satisfies the weak $3$-EVP. \end{proof} \begin{theo}\label{t37} $\wEVP_2(n,3)=\lfloor\frac43n\rfloor$. That is, every $n$-vertex graph with more than $\FL{\frac43n}$ edges satisfies the weak $3$-EVP, and this is sharp. \end{theo} \begin{proof} We need only prove the upper bound. Let $G$ be an $n$-vertex graph with $\FL{\FR43n}+1$ edges. By using the component with largest average degree, we may take $G$ to be connected. Let $G'$ be a subgraph of $G$ with the most edges that contains no even circuit. Adding a cut-edge joining components does not create a circuit. Hence $G'$ is a strict odd cactus spanning all of $V(G)$, by Theorem~\ref{t23}. By Theorem~\ref{t24} and Theorem~\ref{t25}, $|E(G')|\leq \FL{\frac{4}{3}n}-1$. Thus $G'$ omits at least two edges of $G$; choose $e_1,e_2\in E(G)-E(G')$. By the definition of $G'$, adding $e_i$ to $G'$ creates an even circuit $C_i$. If $C_1$ and $C_2$ share no edge, then $G$ satisfies the weak $4$-EVP, by~Lemma \ref{l36}(a). Thus, we may assume that they share an edge. Shrinking the odd cycles of $G'$ into vertices yields a tree $T$. Call the vertices of $T$ {\it nodes} to distinguish them from vertices of $G'$; they correspond to vertices or odd cycles in $G'$. Note that $C_1-e_1$ and $C_2-e_2$ shrink to paths $P_1$ and $P_2$ in $T$. Since $C_1$ and $C_2$ are not edge-disjoint, $P_1$ and $P_2$ intersect in $T$. If the intersection is one node of $T$, then $C_1$ and $C_2$ intersect in a single nontrivial path in $G$. Since both circuits have even length, the endpoints of this path are joined by three edge-disjoint trails of the same parity. Hence $G$ satisfies the weak $3$-EVP, by Lemma~\ref{l36}(b). Hence we may assume that $P_1$ and $P_2$ intersect in a nontrivial path $P'$ in $T$; let $u$ and $w$ be its endnodes. Let $U$ and $W$ be the subgraphs of $G'$ corresponding to $u$ and $w$, they may be single vertices or odd cycles in $G'$. Let $Q_0$ be the subgraph of $G'$ corresponding to $P'$. Let $x_0$ and $y_0$ be the vertices of $U$ and $W$ with largest degree in $Q_0$, and let $Q_0'$ be an $x_0,y_0$-path through $Q_0$. For $i\in\{1,2\}$, let $Q_i$ be the trail obtained from $C_i$ by deleting $E(Q_0)$; note that $e_i\in E(Q_i)$. Let $x_i$ and $y_i$ be the endpoints of $Q_i$ in $U$ and $W$, respectively. If $Q_2$ visits an odd cycle $\hat C$ in $G'$, then let $x$ and $y$ be the vertices in $U$ and $W$ that are endpoints of $C_2-E(C_1)$. By traversing $\hat C$ appropriately, we obtain a trail whose length has the same parity as the two $x,y$-trails along $C_1$, and Lemma~\ref{l36}(b) applies. Hence we may assume that $Q_2$ (and similarly $Q_1$) visits no such cycle. Now combining $Q_1$ and $Q_2$ with appropriate traversals through $U$ and $W$ may yield an even circuit containing $Q_1$ and $Q_2$. If this happens, and $Q_0'$ visits an odd cycle in $G'$, then again Lemma~\ref{l36}(b) applies. Hence two cases remain. In one case, $x_0=x_1=x_2$ and $y_0=y_1=y_2$, these are the only vertices of $U$ and $W$, and $Q_1$ and $Q_2$ are paths with opposite parity. Now $Q_1\cup Q_2$ is an odd cycle that shares vertices with no odd cycles in $G'$. Letting $e'$ be the edge of $Q'_0$ incident to $U$, we now have $G'-e'\cup\{e_1,e_2\}$ as a subgraph of $G$ having no even circuit, contradicting the maximality of $G'$. In the remaining case, the interior nodes of $P'$ are single vertices in $G'$, not odd cycles. The $x_1,x_0$-path through $U$ in $C_1$ and the $x_2,x_0$-path through $U$ in $C_2$ may or may not overlap. If they overlap, then taking the complement within $U$ for each of these paths makes them disjoint but changes the parity of the circuits. However, if the same thing happens within $W$, then performing the complementations at both ends of $P'$ leaves us with two even cycles $C_1'$ and $C_2'$ in $G$ whose intersection is the single path $P'$, and Lemma~\ref{l36}(b) applies. The same holds if complementation was not needed on either end. We are left with the case where $C_1$ and $C_2$ both contain the $x_1,x_2$-path through $U$ that avoids $x_0$, while in $W$ they contain the edge-disjoint $y_0,y_1$-path and $y_0,y_2$-path. Deleting the edges and interior vertices of the $y_1,y_2$-path (if any exist), we obtain a subdivision of $K_4$. Three of the thread form the odd cycle $U$. Each of $C_1$ and $C_2$ is a union of four threads in this subdivision with total length even, omitting one of the threads in $U$. It follows that the circuit in the subgraph obtained by omitting the remaining thread in $U$ also has even length. Hence Lemma~\ref{K4} applies, and $G$ satisfies the weak $3$-EVP. \end{proof} \section{The Weak $t$-EVP and $t$-EVP for Hypergraphs} %%%%%%%%%%%% SECTION 4 In this section, we obtain further upper bounds. For the case $t=2$, recall that the $2$-EVP and weak $2$-EVP are equivalent. Write $\lg$ for $\log_2$. \begin{theo} \label{t41} If $k\ge3$, then $\wEVP_k(n,t) < (\lg k + 3\lg\lg k) n+\lg(t-1)$. In fact, more than this many edges forces the weak $t$-EVP for any hypergraph whose average edge-size is at most $k$. \end{theo} \begin{proof} It suffices to prove that an $n$-vertex hypergraph $H$ with $m$ edges of average size at most $k$ satisfies the weak $t$-EVP, where $m=\CL{(\lg k+3\lg\lg k)n+\lg(t-1)}$. Let $V(H)=\{\VEC v1n\}$, and let $d_i=d_H(v_i)$. For every subhypergraph $H'$, we have $d_{H'}(v_i)\le d_i$. Hence there are at most $\prod_{i=1}^n (d_i+1)$ degree lists of subhypergraphs. Since $\sum_{i=1}^n d_i = km$, it follows that $\prod_{i=1}^{n} (d_i+1)\leq \left(\frac{km}{n}+1\right)^n$. With $m$ edges in $H$, there are $2^m$ subhypergraphs of $H$. If $2^m> (t-1)\left(\frac{km}{n}+1\right)^n$, then some $t$ subhypergraphs have the same degree list. With $u=m/n$, we need $2^u>(t-1)^{1/n}ku+1$. It suffices to have $u\ge{\lg k+3\lg\lg k}+\lg(t-1)$. \end{proof} The constant $3$ can be decreased to a constant $1+c_k$ with $c_k>0$ by carefully considering lower-order terms. As $k\to\infty$, actually $c_k\to0$, but quite slowly. For $t=2$, still $c_k>0.01$ when $k=10^{42}$. Below we show $c_k$ and $m$ for small values of $k$ when $t=2$. \begin{center} \begin{tabular}{c||c|c|c|c|c|c} $k$ & $3$ & $4$ & $5$ & $6$ & $7$ & $8$ \\ \hline $c_k$ & $1.9389$ & $1.1314$ & $0.8569$ & $0.7162$ & $0.6296$ & $0.57041$ \\ $m$ & $< 3.5377 n$ & $< 4.1314n$ & $< 4.5787 n$ & $< 4.9364 n$ & $< 5.23417 n$ & $< 5.48904 n$ \end{tabular} \end{center} When we say nothing about the average size of edges, Theorem~\ref{t41} still gives an upper bound by setting $k=n$. \begin{cor} \label{t44} $\wEVP(n,t) < n(\lg n + 3 \lg\lg n)+ \lg (t-1)$. \end{cor} The upper bound in Theorem~\ref{t41} is not valid for $\EVP_k(n,t)$ when $t\ge3$ because the $t$ subhypergraphs found with the same degree lists need not have the same pairwise intersections. This means there is no set of edges to discard from them all that preserves equality of degrees. To avoid this problem, we use the fact that large families of sets contain large subfamilies with common pairwise intersections. \begin{dfn} \label{d3} A family of $r$ sets is an $r$-$\Delta$-system if the intersections of any two sets in the family are the same. Let $f(k,r)$ be the least integer $q$ such that every $k$-uniform family of $q$ sets contains an $r$-$\Delta$-system. Let $g(m,r)$ be the least integer $q$ such that every family of $q$ subsets of an $m$-element set contains an $r$-$\Delta$-system. \end{dfn} \begin{theo}[Kostochka~\cite{Kos96}] \label{t52} For $r\geq 3$ and $\alpha>1$, there exists $D(r,\alpha)$ such that $f(k,r) \leq D(r,\alpha) k! (\frac{(\log\log\log k)^2}{\alpha \log\log k})^k$. \end{theo} \begin{theo}[Erd\H{o}s and Szemer\'edi~\cite{ES78}]\label{t53} $g(m,3) \leq 2^{(m-.1\sqrt{m})} $. \end{theo} In proving this upper bound, Erd\H{o}s and Szemer\'edi used $f(k,3)\leq (1+o(1))k!$, which was the best known upper bound at the time. Kostochka's later improvement in Theorem \ref{t52} yields a better upper bound for $g(m,r)$ when $r$ is fixed and $m$ is large. The proof is the same as that in~\cite{ES78}, just invoking the improved bound on $f(k,r)$ at the appropriate point. \begin{lem} \label{l54} For $r\geq 3$ and $\epsilon >0$, there exists $N(r,\epsilon)$ such that $g(m,r)< 2^{m-(1-\epsilon)\sqrt{m}\log\log\log m}$ for $m\geq N(r,\epsilon)$. \end{lem} % Do we need to put proof here? Maybe not. % This proof almost completely mimics the proof of Theorem 2 in \cite{ES78}. % Take $n > N_{r,\epsilon}$. We later decide $N_{r,\epsilon}$. % Let $s= 2^{n - (1-\epsilon) \sqrt{n}\log\log\log n}$, and % $\{ A_i : 1\leq i\leq s, A_i\subset [n] \}$ be set system. There is an $l$ so % that $|A_i|=l$ for at least $\frac{s}{n}$ values of $i$. % Consider all subsets of $A_i$ of size $l- \frac{\sqrt{n}}{2}$. Treat % $\frac{\sqrt{n}}{2}$ as an integer. % The total number of these subsets counted with multiplicity is % $\frac{s}{n} { l \choose {\frac{\sqrt{n}}{2}}}$. %The number of subsets of size $l- \frac{\sqrt{n}}{2}$ is %${n\choose {l-\frac{\sqrt{n}}{2}}}$. Thus the same set occurs in at least $u$ %sets $A_i$, where %$u\ge \FR{s{l\choose{\FR{\sqrt{n}}{2}}}}{n{n\choose{l-\frac{\sqrt{n}}{2}}} } %\geq D(t,2)(\sqrt{n})! %(\frac{(\log\log\log \sqrt{n})^2}{2\log\log \sqrt{n}})^{\sqrt{n}} \geq %f(\frac{\sqrt{n}}{2} , t)$. $(1)$ % Denote this set by $B$. Consider $A_{a_i}-B$ for all $A_{a_i}$ that contain %$B$. We have $|A_{a_i} -B| = \frac{\sqrt{n}}{2}$. By the Theorem of %Erd\"os-Rado, there are $r$ $A_{a_i}$'s for which the sets $A_{a_i}-B$ form a %$\Delta$-subsystem and then clearly $A_{a_i}$s form a $\Delta$-subsystem. %Thus, if we verify $(1)$, the proof is done. % To verify $(1)$, we only have to show % $$\log s \geq \log( D(t,2) \frac{n {n\choose {l-\frac{\sqrt{n}}{2}}} % {(\frac{\sqrt{n}}{2})!}(\log\log\log \sqrt{n})^{2\sqrt{n}} } % { { l \choose {\frac{\sqrt{n}}{2}}} (2 \log\log \sqrt{n})^{\sqrt{n}} } ) = % \log( D(t,2)\frac{n\cdot n!(\frac{\sqrt{n}}{2}!)^2 % (\log\log\log \sqrt{n})^{2\sqrt{n}}}{l! (n-l+\frac{1}{2}\sqrt{n})! % (2 \log\log \sqrt{n})^{\sqrt{n}} } )$$ % By using Stirling's formula: % $\log( D(t,2) \frac{n \cdot n! (\frac{\sqrt{n}}{2}!)^2 % (\log\log\log \sqrt{n})^{2\sqrt{n}}}{l! (n-l+\frac{1}{2}\sqrt{n})! % (2 \log\log \sqrt{n})^{\sqrt{n} }} ) % \leq \log ( D(t,2) \frac{ n^2 n^{n+\frac{\sqrt{n}}{2}} % (\log\log\log \sqrt{n})^{2\sqrt{n}} }{ l^l % {(n-l+\frac{\sqrt{n}}{2} )}^{(n-l+\frac{\sqrt{n}}{2})} 2^{\sqrt{n}} % e^{\frac{\sqrt{n}}{2} }(2 \log\log \sqrt{n})^{\sqrt{n}} } )$ % $= \log D(t,2) + 2\log n + (n+\frac{\sqrt{n}}{2})\log n - l\log l - % (n-l+\frac{\sqrt{n}}{2})\log(n-l+\frac{\sqrt{n}}{2}) - \sqrt{n} % -\frac{\sqrt{n}\log e }{2} % + 2\sqrt{n}\log\log\log\log \sqrt{n} - \sqrt{n}\log(2\log\log\sqrt{n}) $ % $\leq n \log (\frac{n(n-l+ \frac{\sqrt{n}}{2})^{\frac{l}{n}}} % { l^{\frac{l}{n}}(n-l +\frac{\sqrt{n}}{2}) } ) + \frac{\sqrt{n}}{2} % \log (\frac{n}{n-l+\frac{\sqrt{n}}{2}}) - (1-o(1))\sqrt{n}\log\log\log n $ % This is maximized when $l= \frac{1}{2}n$, where the value is % $ n (\frac{1}{2} + \frac{1}{2}\log \frac{2\sqrt{n}}{\sqrt{n}+1} ) % +\frac{\sqrt{n}}{2} \log (\frac{n}{ \frac{n+ \sqrt{n}}{2}}) - % (1-o(1))\sqrt{n}\log\log\log n $ % $\leq n ( 1 - \frac{\log e}{\sqrt{n}+1} + \frac{\log e}{2 (\sqrt{n}+1)^2 }) % \frac{\sqrt{n}}{2} + \frac{1}{n+\sqrt{n}}- (1-o(1))\sqrt{n}\log\log\log n $ % $\leq n - (1-\epsilon) \sqrt{n}\log\log\log n = \log s $. % By choosing $N_r$ so that % $\log\log N_r > \frac{2}{\epsilon} D(t,2) (2 \log\log\log n)$, % all these inequalities hold. \begin{theo} \label{t51} If $t\geq 3$ and $\epsilon>0$, then $\EVP(n,t)<(4+\epsilon)n^2(\frac{\log n}{\log\log\log n})^2 $ for $n\geq N(t,\epsilon)$, where $N(t,\epsilon)$ is defined as in Lemma~\ref{l54}. \end{theo} \begin{proof} Let $H$ be an $n$-vertex hypergraph with $n\geq N(t,\epsilon)$ and $|E(H)|\ge (4+\epsilon) n^2 (\frac{\log n}{\log\log\log n})^2 $. We show that $H$ satisfies the $t$-EVP. As in Theorem~\ref{t41}, let $V(H)=\{\VEC v1n\}$ and $d_i=d_H(v_i)$. For every subhypergraph $H'$, we have $d_{H'}(v_i)\le d_i$. Again there are at most $\prod_{i=1}^n (d_i+1)$ degree lists of subhypergraphs. Since $0\le d_i\le m$ for all $i$, it follows that $\prod_{i=1}^{n} (d_i+1)\leq \left(m+1\right)^n$. With $m$ edges in $H$, there are $2^m$ subhypergraphs of $H$. Let $q=\CL{\frac{2^m}{(m+1)^n}}$; there are distinct subhypergraphs $\VEC H1q$ having the same degree list. Since $m=(4+\epsilon)n^2\left(\frac{\log n}{\log\log\log n}\right)^2$, Theorem~\ref{l54} yields \begin{eqnarray*} \log q &>& m-n\log ( m+1) ~>~ m-n\log \left( n^2\left( \frac{\log n}{\log\log\log n}\right)^2 \right)\\ &=& m-2n\log n-n\log\left( \left(\frac{\log n}{\log\log\log n}\right)^2\right)\\ &>& m - (1-\epsilon) \sqrt{m}\log\log\log m - o(\sqrt{m}) \\ &>& m - (1-\epsilon) \sqrt{m}\log\log\log m > \log g(m,t). \end{eqnarray*} Thus, $q\geq g(m,t)$, which implies that among $H_1,\ldots, H_q$, each viewed as a subset of the set of $m$ edges in $H$, there exists a $\Delta$-system of size $t$. That is, we obtain $t$ subhypergraphs that are pairwise disjoint except for the same set of edges shared by all of them. Deleting that common subset yields $t$ subhypergraphs witnessing the $t$-EVP. \end{proof} The same argument yields a bound when the average size of edges is at most $k$. As in Theorem~\ref{t41}, use $\prod_{i=1}^n(d_i+1)\le\left(\frac{km}n+1\right)^n$. \begin{theo} \label{t55} If $t\geq 3$, $k\ge2$, and $\epsilon>0$, then $\EVP_k(n,t)<(1+\epsilon)n^2\left(\frac{\log n}{\log\log\log n}\right)^2 $ for $n\geq \max\{k,N(t,\epsilon)\}$. \end{theo} If the upper bound in Lemma \ref{l54} can be improved to $(2-\epsilon_r)^n$, then we obtain an upper bound of $C_t n \log k$ for Theorem \ref{t55} and an upper bound of $C_t n\log n$ for Theorem \ref{t51}, where $C_t$ is a constant depending on $t$. Erd\"os and Rado conjectured that $f(n,t) \le (c_1(t))^n$. If this conjecture is true, then in Lemma~\ref{l54} it yields $g(n,t)\le 2^{n-c\sqrt{n}\log n}$, and in Theorem~\ref{t51} it yields $\EVP(n,t)\le c_2(t)n^2$, where $c_1(t)$ and $c_2(t)$ are functions of $t$. We close with a simple lower bound. \begin{lem}\label{union} Let $H'$ and $H''$ be disjoint $k$-uniform hypergraphs. Fix $s$ with $s\le{\lg k}$, and form a hypergraph $H$ by adding $s$ edges to $H'\cup H''$ so that the $i$th added edge has exactly $2^{i-1}$ vertices in $V(H')$. If both $H'$ and $H''$ fail the $2$-EVP, then also $H$ fails the $2$-EVP. \end{lem} \begin{proof} Let $F$ be the set of $s$ added edges. Since $H'$ and $H''$ fail the $2$-EVP, a pair $\{H_1,H_2\}$ witnessing the $2$-EVP in $H$ must use some edge in $F$. Since $H_1$ and $H_2$ share no edges, and the contributions by edges of $F$ to the total degree in $V(H')$ are distinct powers of $2$, the contributions by $E(H_1)\cap F$ and $E(H_2)\cap F$ to the total degree in $V(H')$ are distinct. Since $\SE i1{\FL{\lg k}}2^{i-1}