\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}<k$, the difference between the two
amounts is less than $k$.  However, the total degree contributed by
edges in $H'$ is a multiple of $k$ (for both $H_1$ and $H_2$).  Hence the total
degrees in $V(H')$ for $H_1$ and $H_2$ are distinct, so they cannot witness
the $2$-EVP.
\end{proof}

\begin{cor}
If $k\ge3$, then $\EVP_k(n+k-3,2)\ge\FR{11n-31}7$.
\end{cor}
\begin{proof}
By Observation~\ref{o3}, it suffices to prove $\EVP_3(n,2)\ge\FR{11n-31}7$.

By exhaustive computer search, we know that the $7$-vertex $3$-uniform
hypergraph with $10$ edges whose incidence matrix appears below does not 
satisfy the $2$-EVP.  Starting with $r$ copies of this hypergraph, $r-1$
applications of Lemma~\ref{union} adds $r-1$ edges (since $\FL{\lg 3}=1$)
and produces a $3$-uniform hypergraph with $7r$ vertices and $11r-1$ edges.
Similarly, we can add one edge for each vertex beyond a multiple of $7$.
Letting $n=7r+j$ with $0\le j\le 6$, we obtain
$\EVP_3(n,2)\ge11{\FR{n-j}7}-1+j\ge\FR{11n-31}7$.
\end{proof}

\vspace{-1pc}
$$
\bbordermatrix{
        ~&1&2&3&4&5&6&7\cr
\{1,2,3\}&1&1&1&0&0&0&0\cr
\{1,2,4\}&1&1&0&1&0&0&0\cr
\{1,2,5\}&1&1&0&0&1&0&0\cr
\{1,3,4\}&1&0&1&1&0&0&0\cr
\{1,5,6\}&1&0&0&0&1&1&0\cr
\{1,6,7\}&1&0&0&0&0&1&1\cr
\{2,3,6\}&0&1&1&0&0&1&0\cr
\{2,4,7\}&0&1&0&1&0&0&1\cr
\{3,5,7\}&0&0&1&0&1&0&1\cr
\{4,5,6\}&0&0&0&1&1&1&0}
$$

\bigskip
\bigskip


\section*{Acknowledgment}

We thank Robert Jamison for suggesting the study of this problem.

\begin{thebibliography}{1}
\bibitem{AH73}
H.L. Abbot and D. Hanson,
\newblock On Finite $\Delta$-Systems,
\newblock {\em Discrete Mathematics} 8 (1974), 1--12.

\bibitem{AH77}
H.L. Abbot and D. Hanson,
\newblock On Finite $\Delta$-Systems II,
\newblock {\em Discrete Mathematics} 17 (1977), 121--126.

\bibitem{AFK}
N. Alon, S. Friedland, and G. Kalai,
\newblock Regular Subgraphs of Almost Regular Graphs,
\newblock {\em Journal of Discrete Algorithms } 37 (1984), 79--91.

\bibitem{BHP}
R.C. Baker, G. Harman, and J. Pintz, 
\newblock The difference between consecutive primes, II.
\newblock {\em Proc. London Math. Soc. (3)} 83 (2001), 532--562.

\bibitem{E32}
P. Erd\H{o}s, 
\newblock Beweis eines Satzes von Tschebyschef,
\newblock {\em Acta Sci. Math. }(Szeged) 5 (1930--1932), 194--198.

\bibitem{ER60}
P. Erd\H{o}s and R. Rado,
\newblock Intersection theorems for systems of sets,
\newblock {\em J. London Math. Soc.} 35 (1960),  85--90.

\bibitem{ES78}
P. Erd\H{o}s and E. Szemer\'edi,
\newblock Combinatorial Properties of Systems of Sets,
\newblock {\em J. Combin. Theory. (A) } 24 (1978), 308--313.

\bibitem{IP}
H. Iwaniec and J. Pintz, 
\newblock Primes in short intervals,
\newblock {\em Monatsh. Math.} 98 (1984), 115--143.

\bibitem{JJ01}
D.P. Jacobs and R.E. Jamison,
\newblock A note on equal unions in families of sets,
\newblock {\em Discrete Mathematics} 241 (2001), 387--393.

\bibitem{JJ05}
D.P. Jacobs and R.E. Jamison,
\newblock Polynomial recognition of equal unions in hypgergraphs with few vertices of large degree,
\newblock {\em Journal of Discrete Algorithms } 4 (2006), 201--208.

\bibitem{Kos96}
A.V. Kostochka,
\newblock An intersection Theorem for Systems of Sets,
\newblock {\em Random Struct. Algor.} 9 (1996), 213--221.

\bibitem{Lind72}
B. Lindstr\"om,
\newblock A theorem on families of sets,
\newblock {\em J. Combin. Theory (A) } 13 (1972), 274--277.

\bibitem{N}
J. Nagura,
\newblock On the interval containing at least one prime number,
\newblock {\em Proc. Japan Academy (A)} 28 (1952), 177--181.

\bibitem{Tver71}
H. Tverberg,
\newblock On equal unions of sets, in:
\newblock {\em  Studies in Pure Mathematics}, L. Mirsky, ed.,
(Academic Press, 1971), 249--250.

\end{thebibliography}

\end{document}

