Keywords:   Employment, Entrepreneurship, Cash Transfers

JEL Codes:   O12, C93, J21

Study Information:   This study is registered with the AEA Trial Registry as Number AEARCTR-0004388, and is covered by Rwanda National Ethics Committee IRB 114/RNEC/2017, IPA-IRB:14609, and UCSD IRB 161112.  The research was paid for by USAID grant AID-0AA-A-13-00002 (SUB 00009051).  We thank the Education Development Center, GiveDirectly, USAID, and DIL/CEGA for their close collaboration in executing the study; Leodomir Mfura and Melissa Mahoro of Innovations for Poverty Action for outstanding management of the fieldwork; Sarait Cárdenas-Rodriguez, Grace Han, Atsuhiro Oguri, and Aruj Shukla for excellent research assistance; USAID Rwanda, DIV, and Google.org for funding.  This study is made possible by the support of the American People through the United States Agency for International Development (USAID.) The contents of this study are the sole responsibility of the authors and do not necessarily reflect the views of USAID or the United States Government.

§ INTRODUCTION

§ DESIGN

§ RESULTS

§ AGGREGATING IMPACTS OVER TIME

§ CONCLUSIONS

[Abadie et al.]Abadie, Chingos and West2018AbaChiWes18restat
Abadie, Alberto, Matthew M Chingos, and Martin R West, “Endogenous
stratification in randomized experiments,” Review of Economics and
Statistics, October 2018, 100 (4), 567–580.

[Ahmed et al.]Ahmed, Hoddinott, Roy, Sraboni, Quabili and
Ahmed, AU, JF Hoddinott, S Roy, E Sraboni, WR Quabili, and A Margolies,
“Which Kinds of Social Safety Net Transfers Work Best for the Ultra Poor in
Bangladesh,” Operation and Impacts of the Transfer Modality Research
Initiative, 2016.

[Aizer et al.]Aizer, Eli, Ferrie and
Aizer, Anna, Shari Eli, Joseph Ferrie, and Adriana Lleras-Muney, “The
long-run impact of cash transfers to poor families,” The American
Economic Review, 2016, 106 (4), 935–971.

Anderson, Michael L, “Multiple inference and gender differences in the
effects of early intervention: A reevaluation of the Abecedarian, Perry
Preschool, and Early Training Projects,” Journal of the American
statistical Association, 2008, 103 (484), 1481–1495.

[Araujo et al.]Araujo, Bosch and Schady2017araujo2017can
Araujo, M Caridad, Mariano Bosch, and Norbert Schady, “Can Cash
Transfers Help Households Escape an Inter-Generational Poverty Trap?,” in
“The Economics of Poverty Traps,” University of Chicago Press, 2017.

[Attanasio et al.]Attanasio, Kugler and
Attanasio, Orazio, Adriana Kugler, and Costas Meghir, “Subsidizing
vocational training for disadvantaged youth in Colombia: Evidence from a
randomized trial,” American Economic Journal: Applied Economics, 2011,
3 (3), 188–220.

[Baird et al.]Baird, McIntosh and Özler2019baird2019money
Baird, Sarah, Craig T McIntosh, and Berk Özler, “When the money runs
out: Do cash transfers have sustained effects on human capital
accumulation?,” Journal of Development Economics, 2019, 140.

[Balboni et al.]Balboni, Bandiera, Burgess, Ghatak and
Balboni, Clare, Oriana Bandiera, Robin Burgess, Maitreesh Ghatak, and
Anton Heil, “Why do people stay poor?,” Quarterly Journal of
Economics, May 2022, 137 (2), 785–844.

[Bandiera et al.]Bandiera, Elsayed, Smurra and
Bandiera, Oriana, Ahmed Elsayed, Andrea Smurra, and Céline Zipfel,
“Young Adults and Labor Markets in Africa,” The journal of economic
perspectives, 2022, 36 (1), 81–100.

[Barham et al.]Barham, Macours and
Barham, Tania, Karen Macours, and John A Maluccio, “Schooling, Learning,
and Earnings: Effects of a 3-Year Conditional Cash Transfer Program in
Nicaragua After 10 Years,” La Plata, Argentina: Centro para los
Estudios Distributivos, de Trabajo y Sociales. Disponible en: http://www.
cedlas-er. org/sites/default/files/aux_files/barham-maluccio-macours_.
pdf, 2014.

[Beaman et al.]Beaman, Karlan, Thuysbaert and
Beaman, Lori, Dean Karlan, Bram Thuysbaert, and Christopher Udry,
“Self-selection into credit markets: Evidence from agriculture in mali,”
Technical Report, National Bureau of Economic Research 2014.

[Blattman et al.]Blattman, Fiala and
Blattman, Christopher, Nathan Fiala, and Sebastian Martinez, “Generating
skilled self-employment in developing countries: Experimental evidence from
Uganda,” The Quarterly Journal of Economics, 2013, 129 (2),

[Blattman et al.]Blattman, Fiala and
, , and , “The long term impacts of grants on
poverty: 9-year evidence from Uganda's Youth Opportunities Program,”
Technical Report, National Bureau of Economic Research 2018.

[Blattman et al.]Blattman, Fiala and
, , and , “The Long-Term Impacts of Grants on
Poverty: Nine-Year Evidence from Uganda's Youth Opportunities Program,” American Economic Review: Insights, 2020, 2 (3), 287–304.

[Blattman et al.]Blattman, Dercon and
, Stefan Dercon, and Simon Franklin, “Impacts of industrial and
entrepreneurial jobs on youth: 5-year experimental evidence on factory job
offers and cash grants in Ethiopia,” Journal of Development Economics,
2022, p. 102807.

Bongaarts, John, “Development: Slow down population growth,” Nature News, 2016, 530 (7591), 409.

[Bouguen et al.]Bouguen, Huang, Kremer and
Bouguen, Adrien, Yue Huang, Michael Kremer, and Edward Miguel, “Using
randomized controlled trials to estimate long-run impacts in development
economics,” Annual Review of Economics, 2019, 11, 523–561.

[Brudevold-Newman et al.]Brudevold-Newman, Honorati, Jakiela and
Brudevold-Newman, Andrew Peter, Maddalena Honorati, Pamela Jakiela, and
Owen Ozier, “A firm of one's own: experimental evidence on credit
constraints and occupational choice,” World Bank Policy Research Working
Paper no. 7977 2017.

[Campos et al.]Campos, Frese, Goldstein, Iacovone, Johnson,
McKenzie and Mensmann2017Cam17science
Campos, Francisco, Michael Frese, Markus Goldstein, Leonardo Iacovone,
Hillary C. Johnson, David McKenzie, and Mona Mensmann, “Teaching personal
initiative beats traditional training in boosting small business in West
Africa,” Science, September 2017, 357 (63357), 1287–1290.

[Chowdhury et al.]Chowdhury, Collins, Ligon and
Chowdhury, Reajul, Elliott Collins, Ethan Ligon, and Kaivan Munshi,
“Valuing Assets Provided to Low-Income Households in South Sudan,” 2016.

[Cunha et al.]Cunha, De Giorgi and
Cunha, Jesse M, Giacomo De Giorgi, and Seema Jaychandran, “The price
effects of cash versus in-kind transfers,” Review of Economic Studies,

[Dhaliwal and Tulloch]Dhaliwal and
Dhaliwal, Iqbal and Caitlin Tulloch, “From research to policy: using
evidence from impact evaluations to inform development policy,” Journal
of Development Effectiveness, 2012, 4 (4), 515–536.

[Egger et al.]Egger, Miguel, Warren, Shenoy, Collins, Karlan,
Parkerson, Mobarak, Fink, Udry et al.2021egger2021falling
Egger, Dennis, Edward Miguel, Shana S Warren, Ashish Shenoy, Elliott
Collins, Dean Karlan, Doug Parkerson, A Mushfiq Mobarak, Günther Fink,
Christopher Udry et al., “Falling living standards during the COVID-19
crisis: Quantitative evidence from nine developing countries,” Science
advances, 2021, 7 (6), eabe0997.

[Fernald et al.]Fernald, Gertler and Neufeld2009fernald200910
Fernald, Lia CH, Paul J Gertler, and Lynnette M Neufeld, “10-year effect
of Oportunidades, Mexico's conditional cash transfer programme, on child
growth, cognition, language, and behaviour: a longitudinal follow-up study,”
The Lancet, 2009, 374 (9706), 1997–2005.

[Fox et al.]Fox, Senbet and Simbanegavi2016fox2016youth
Fox, Louise, Lemma W Senbet, and Witness Simbanegavi, “Youth employment
in Sub-Saharan Africa: challenges, constraints and opportunities,” Journal of African Economies, 2016, 25 (suppl_1), i3–i15.

[Gertler et al.]Gertler, Martinez and
Gertler, Paul J, Sebastian W Martinez, and Marta Rubio-Codina,
“Investing cash transfers to raise long-term living standards,” American Economic Journal: Applied Economics, 2012, 4 (1), 164–192.

[Haushofer and Shapiro]Haushofer and
Haushofer, Johannes and Jeremy Shapiro, “The short-term impact of
unconditional cash transfers to the poor: Experimental Evidence from Kenya,”
The Quarterly Journal of Economics, 2016, 131 (4), 1973–2042.

[Heckman et al.]Heckman, LaLonde and
Heckman, James J, Robert J LaLonde, and Jeffrey A Smith, “The economics
and econometrics of active labor market programs,” in “Handbook of labor
economics,” Vol. 3, Elsevier, 1999, pp. 1865–2097.

[Hidrobo et al.]Hidrobo, Hoddinott, Peterman, Margolies and
Hidrobo, Melissa, John Hoddinott, Amber Peterman, Amy Margolies, and
Vanessa Moreira, “Cash, food, or vouchers? Evidence from a randomized
experiment in northern Ecuador,” Journal of Development Economics,
2014, 107, 144–156.

[Hoddinott et al.]Hoddinott, Sandström and
Hoddinott, John, Susanna Sandström, and Joanna Upton, “The impact of
cash and food transfers: Evidence from a randomized intervention in Niger,”

[Hoynes et al.]Hoynes, Schanzenbach and
Hoynes, Hilary, Diane Whitmore Schanzenbach, and Douglas Almond,
“Long-run impacts of childhood access to the safety net,” The American
Economic Review, 2016, 106 (4), 903–934.

[Ibarrarán et al.]Ibarrarán, Kluve, Ripani and
Rosas Shady2019ibarraran2019experimental
Ibarrarán, Pablo, Jochen Kluve, Laura Ripani, and David Rosas Shady,
“Experimental evidence on the long-term effects of a youth training
program,” ILR Review, 2019, 72 (1), 185–222.

[Kluve et al.]Kluve, Puerto, Robalino, Romero, Rother, Stoeterau,
Weidenkaff and Witte2017kluve2017interventions
Kluve, Jochen, Susana Puerto, David Robalino, Jose Manuel Romero,
Friederike Rother, Jonathan Stoeterau, Felix Weidenkaff, and Marc Witte,
“Interventions to improve the labour market outcomes of youth: A systematic
review of training, entrepreneurship promotion, employment services and
subsidized employment interventions,” Campbell Systematic Reviews,
2017, 13 (1), 1–288.

[Leroy et al.]Leroy, Gadsden, Rodríguez-Ramírez and
De Cossío2010leroy2010cash
Leroy, Jef L, Paola Gadsden, Sonia Rodríguez-Ramírez, and
Teresa González De Cossío, “Cash and in-kind transfers in poor
rural communities in Mexico increase household fruit, vegetable, and
micronutrient consumption but also lead to excess energy consumption,” The Journal of nutrition, 2010, 140 (3), 612–617.

[Levin and McEwan]Levin and McEwan2001levin2001cost
Levin, Henry M and Patrick J McEwan, Cost-effectiveness analysis:
Methods and applications, Vol. 4, Sage, 2001.

[Levin et al.]Levin, McEwan, Belfield, Bowden and
, , Clive Belfield, A Brooks Bowden, and Robert Shand,
Economic evaluation in education: Cost-effectiveness and benefit-cost
analysis, SAGE publications, 2017.

[Mahmud and Riley]Mahmud and Riley2021mahmud2021household
Mahmud, Mahreen and Emma Riley, “Household response to an extreme shock:
Evidence on the immediate impact of the Covid-19 lockdown on economic
outcomes and well-being in rural Uganda,” World Development, 2021,
140, 105318.

[McIntosh and Zeitlin]McIntosh and
McIntosh, Craig and Andrew Zeitlin, “Using household grants to benchmark
the cost effectiveness of a USAID workforce readiness program,” Journal
of Development Economics, 2022, p. 102875.

McKenzie, David, “Small business training to improve management
practices ind eveloping countries: re-assessing the evidence for `training
doesn't work',” Oxford Review of Economic Policy, 2021, 37 (2),

[De Mel et al.]De Mel, McKenzie and Woodruff2012de2012one
Mel, Suresh De, David McKenzie, and Christopher Woodruff, “One-time
transfers of cash or capital have long-lasting effects on microenterprises in
Sri Lanka,” Science, 2012, 335 (6071), 962–966.

[La Porta and Shleifer]La Porta and
Porta, Rafael La and Andrei Shleifer, “Informality and development,”
Journal of economic perspectives, 2014, 28 (3), 109–26.

[Schwab et al.]Schwab et al.2013schwab2013form
Schwab, Benjamin et al., “In the form of bread? A randomized comparison
of cash and food transfers in Yemen,” in “Agricultural & Applied Economics
Association 2013 AAEA & CAES Joint Annual Meeting” 2013, pp. 4–6.

[Sedlmayr et al.]Sedlmayr, Shah and
Sedlmayr, Richard, Anuj Shah, and Munshi Sulaiman, “Cash-Plus: Poverty
impacts of alternative transfer-based approaches,” Journal of
Development Economics, May 2020, 144, 102418.

[Walls et al.]Walls, Tulloch and
Harris-Van Keuren2019walls2019costing
Walls, Elena, Caitlin Tulloch, and Christine Harris-Van Keuren, “Cost
Analysis Guidance for USAID-Funded Education Activities,” Technical Report

§ TABLES AND FIGURES

Results of Costing Exercise

Note:  The first column shows the ex-ante costing data on which study was designed; the core number is the HD cost around which the GD actual transfer amounts in column 2 were designed.  Column 3 shows the results of the ex post costing exercise.  Column 4 provides the share of spending that did not reach the beneficiaries either in cash or in direct training and materials costs.  Column 5 shows the compliance rates, and since all costs are averted for non-compliers then the final column shows the final cost per study subject for each arm that are the basis of the cost-equivalent comparisons.

Simple ITT, Primary Outcomes.

Note:  The six columns of the table provide the estimate on dummy variables for each of the treatment arms, compared to the control group.  The five primary outcomes are in rows.  Regressions include but do not report the lagged dependent variable, fixed effects for randomization blocks, and a set of LASSO-selected baseline covariates. Standard errors (in parentheses) are clustered at the household level to reflect the design effect, and $p$-values corrected for False Discovery Rates across all the outcomes in the table are presented in brackets.  Stars on coefficient estimates are derived from the FDR-corrected $p$-values, *=10%, **=5%, and ***=1% significance. Reported $p$-values in final three columns derived from $F$-tests of hypotheses that cost-benefit ratios are equal between: (a) GD Lower and HD; (b) GD Lower and GD Large; and (c) GD Large and Combined treatments. Employed is a dummy variable for spending more than 10 hours per week working for a wage or as primary operator of a microenterprise.  Productive hours are measured over prior 7 days in all activities other than own-farm agriculture.  Monthly income, productive assets, and household consumption are winsorized at 1% and 99% and analyzed in Inverse Hyperbolic Sine, meaning that treatment effects can be interpreted as percent changes.

Simple ITT, Secondary Outcomes: Wealth.

Notes:   Regressions include but do not report the lagged dependent variable, fixed effects for randomization blocks, and a set of LASSO-selected baseline covariates.  Standard errors are (in soft brackets) are clustered at the household level to reflect the design effect, and $p$-values corrected for False Discovery Rates across all the outcomes in the table are presented in hard brackets.  Stars on coefficient estimates are derived from the FDR-corrected $p$-values, *=10%, **=5%, and ***=1% significance.  Reported $p$-values in final three columns derived from $F$-tests of hypotheses that cost-benefit ratios are equal between: (a) GD Lower and HD; (b) GD Lower and GD Large; and (c) GD Large and Combined treatments.

ITT Employment Breakdown.

Notes: Panel A presents impacts on indicators for employment of any hours in the corresponding activity type in the preceding week.  Panel B presents impacts on an indicator for overall employment, using the reported threshold for minimum hours. Regressions include but do not report an indicator for lagged employment status, fixed effects for randomization blocks, and a set of LASSO-selected baseline covariates. Standard errors are (in soft brackets) are clustered at the household level to reflect the design effect, and $p$-values corrected for False Discovery Rates across outcomes in each panel are presented in hard brackets.  Stars on coefficient estimates are derived from unadjusted standard errors, *=10%, **=5%, and ***=1% significance.

Cost Equivalent Analysis, Primary Outcomes.

Note:  This table uses a linear adjustment of primary outcomes for program cost to compare HD and GD at exactly equivalent costs.  The Transfer value column estimates the marginal effect of spending an extra $100 through cash transfers.  The Cost-equivalent GD impact column is estimated as a dummy for either HD or GD treatment, and estimates the impact of cash at the exact cost of HD.  The Differential impact of HD column then estimates the differential effect of HD above cash at this benchmarked cost. Regressions include but do not report the lagged dependent variable, fixed effects for randomization blocks, and a set of LASSO-selected baseline covariates.  Standard errors are (in soft brackets) are clustered at the household level to reflect the design effect, and $p$-values corrected for False Discovery Rates across all the outcomes in the table are presented in hard brackets.  Stars on coefficient estimates are derived from the FDR-corrected $p$-values, *=10%, **=5%, and ***=1% significance.  Employed is a dummy variable for spending more than 10 hours per week working for a wage or as primary operator of a microenterprise.  Productive hours are measured over prior 7 days in all activities other than own-farm agriculture.  Monthly income, productive assets, and household consumption are winsorized at 1% and 99% and analyzed in Inverse Hyperbolic Sine, meaning that treatment effects can be interpreted as percent changes.

Benefit-Cost Ratios, Primary Outcomes.

Note:  Table gives the impact per $100 spent, which is calculated by dividing the estimated ITT impacts by the cost per arm in hundreds of dollars.  The standard errors in the table are similarly the ITT standard errors divided by costs.  Reported $p$-values in final three columns derived from $F$-tests of hypotheses that cost-benefit ratios are equal between: (a) joint test across all arms, (b) GD Lower and HD; (c) GD Lower and GD Large; and (d) GD Large and Combined arms.

Beneficiary Business Birth and Death.

Notes:  Table uses the panel of firms reported on in the beneficiary survey, totalling variables within each round.  The first two rows count the number of new firms in each round that had not existed in the prior round, by beneficiary, and then impute zeros for individuals who reported no firms in the survey.  Rows 3-5 then take the universe of individuals who reported on any firm in the midline, and count the outcomes for those firms at endline; whether they were no longer operational (died), existed but were inoperative, or were operative.  Standard errors are (in soft brackets) are clustered at the household level to reflect the design effect, and $p$-values corrected for False Discovery Rates across all the outcomes in the table are presented in hard brackets.  Stars on coefficient estimates are derived from the FDR-corrected $p$-values, *=10%, **=5%, and ***=1% significance.

Midline Beneficiary enterprise analysis.

Notes:  Table analyzes the results of the midline beneficiary enterprise survey, totalling variables across all businesses operated by a given beneficiary and then imputing zeros to survey respondents with no businesses.  Analysis is weighted using attrition weights. Standard errors are (in soft brackets) are clustered at the household level to reflect the design effect, and $p$-values corrected for False Discovery Rates across all the outcomes in the table are presented in hard brackets.  Stars on coefficient estimates are derived from the FDR-corrected $p$-values, *=10%, **=5%, and ***=1% significance.

Endline Beneficiary enterprise analysis.

Notes:  Table analyzes the results of the endline beneficiary enterprise survey, totalling variables across all businesses operated by a given beneficiary and then imputing zeros to survey respondents with no businesses.  Standard errors are (in soft brackets) are clustered at the household level to reflect the design effect, and $p$-values corrected for False Discovery Rates across all the outcomes in the table are presented in hard brackets.  Stars on coefficient estimates are derived from the FDR-corrected $p$-values, *=10%, **=5%, and ***=1% significance.

Aggregating cash flows over the study period.

Notes.  Table presents control means and estimated impacts on financial values, in dollars.  Flow consumption is measured in the survey monthly, and here we use the midline treatment effect for the first 12 months and the endline effect for the subsequent 28 months.  Inter-household flows are measured with an annual recall, and we take a similar approach, using midline estimates for the midline period and endline estimates for the period between midline and endline.   All other variables are stocks measured at follow-up. Total income is the sum of cash received, beneficiary income, and transfers received.  Total expenditure is the sum of household consumption, loans made, and transfers made.  Total stock values are the sum of  livestock values, other productive asset values, savings values, and the negative of debt values.  Randomization inference $p$-values, in brackets, from test of null of no cumulative effect of each arm on income. Share accounted is the ratio of the sum of total outflows plus stock values to total inflows.

Cost Equivalence versus Cost Effectiveness, Endline

Graphical Representation of Spillovers

Notes:  Each panel presents predicted outcomes under each of the four main treatment arms (Control, HD, GD Main, and GD Large), as the saturation level of a specific active treatment arm changes.  Rows correspond to the outcomes of employment, productive hours, and the inverse hyperbolic sine of monthly incomes, productive assets, and household consumption per adult-equivalent, respectively. Horizontal shaded bands highlight one standard deviation above and below the control mean.  Columns illustrate effects of variation in saturation rates in HD, GD-main, and GD-large, respectively.  All predicted outcomes evaluated at means of covariates used in the estimating equation.

Incidence of Covid-19 Shocks, by Treatment Arm

Evolution of control-group primary outcomes across survey rounds

Notes: Endline outcomes deflated to nominal midline Rwanda francs.

seccntformat#1Appendix the#1

§ APPENDIX TABLES

Study Design

Note :  This table gives the number of study individuals assigned to each treatment arm in each of the 13 sectors within which lotteries were conducted.  The lotteries were blocked so that fixed fractions of individuals are assigned to each arm.

Attrition:  Tracking at Endline by Treatment.

Notes:  Table examines overall attrition rates from the endline survey by treatment arm.  Sample is the entire baseline survey, outcome variable is a dummy for being successfully tracked at endline.  Covariates are the treatment arm for each individual.  Standard errors clustered at the household level, *=10%, **=5%, and ***=1% significance.

Attrition:  Tracking at Endline on Covariates.

Notes:   Table correlates attrition from the endline survey with baseline covariates.  Sample is the entire baseline survey, outcome variable is a dummy for being successfully tracked at endline.  Standard errors are (in soft brackets) are clustered at the household level to reflect the design effect, and $p$-values corrected for False Discovery Rates across all the outcomes in the table are presented in hard brackets.  Stars on coefficient estimates are derived from the FDR-corrected $p$-values, *=10%, **=5%, and ***=1% significance.

Balance using Endline Sample.

Notes:  Table examines balance of the experiment across treatment arms using baseline covariates and the attrited sample that is used for endline analysis.  Standard errors are (in soft brackets) are clustered at the household level to reflect the design effect, and $p$-values corrected for False Discovery Rates across all the outcomes in the table are presented in hard brackets.  Stars on coefficient estimates are derived from the FDR-corrected $p$-values, *=10%, **=5%, and ***=1% significance.

Simple ITT, Secondary Outcomes: Beneficiary welfare.

Notes:   Regressions include but do not report the lagged dependent variable, fixed effects for randomization blocks, and a set of LASSO-selected baseline covariates.  Standard errors are (in soft brackets) are clustered at the household level to reflect the design effect, and $p$-values corrected for False Discovery Rates across all the outcomes in the table are presented in hard brackets.  Stars on coefficient estimates are derived from the FDR-corrected $p$-values, *=10%, **=5%, and ***=1% significance.  Reported $p$-values in final three columns derived from $F$-tests of hypotheses that cost-benefit ratios are equal between: (a) GD Lower and HD; (b) GD Lower and GD Large; and (c) GD Large and Combined treatments.

Simple ITT, Secondary Outcomes: Skills.

Notes:   Regressions include but do not report the lagged dependent variable, fixed effects for randomization blocks, and a set of LASSO-selected baseline covariates.  Standard errors are (in soft brackets) are clustered at the household level to reflect the design effect, and $p$-values corrected for False Discovery Rates across all the outcomes in the table are presented in hard brackets.  Stars on coefficient estimates are derived from the FDR-corrected $p$-values, *=10%, **=5%, and ***=1% significance.  Reported $p$-values in final three columns derived from $F$-tests of hypotheses that cost-benefit ratios are equal between: (a) GD Lower and HD; (b) GD Lower and GD Large; and (c) GD Large and Combined treatments.

Moving across villages.

Notes:  Table analyzes the extent to which the beneficiary had moved across villages at midline (R2) or endline (R3).  `Urban' is a dummy variable indicating that the village in which the beneficiary resides in that round is classified as semi-urban, peri-urban, or urban (rather than rural).  `New Village' is a dummy for the village being a different one than the baseline village.  Standard errors are (in soft brackets) are clustered at the household level to reflect the design effect, and $p$-values corrected for False Discovery Rates across all the outcomes in the table are presented in hard brackets.  Stars on coefficient estimates are derived from the FDR-corrected $p$-values, *=10%, **=5%, and ***=1% significance.

Education and Time Use.

Notes:  Table analyzes endline education and time use variables.  Highest grade is an ordinal variable measuring completed schooling with the control mean representing one year of post-primary education.   `Hours in School' and `Hours Domestic Work' give the number of hours over the seven days prior to the endline that the respondent reports spending in each activity.  `Reservation wages' give the survey response to the daily wage the respendent said they would need to be paid to take a job in their village and in the nearest town, respectively (USD).  Standard errors are (in soft brackets) are clustered at the household level to reflect the design effect, and $p$-values corrected for False Discovery Rates across all the outcomes in the table are presented in hard brackets.  Stars on coefficient estimates are derived from the FDR-corrected $p$-values, *=10%, **=5%, and ***=1% significance.

Midline Household Enterprise Analysis.

Notes:  Table analyzes the results of the midline household enterprise survey, totalling variables across all businesses operated within the household (other than by the beneficiary) and then imputing zeros to households with no businesses.  Analysis is weighted using attrition weights. Standard errors are (in soft brackets) are clustered at the household level to reflect the design effect, and $p$-values corrected for False Discovery Rates across all the outcomes in the table are presented in hard brackets.  Stars on coefficient estimates are derived from the FDR-corrected $p$-values, *=10%, **=5%, and ***=1% significance.

Endline Household Enterprise Analysis.

Notes:  Table analyzes the results of the endline household enterprise survey, totalling variables across all businesses operated within the household (other than by the beneficiary) and then imputing zeros to households with no businesses.  Standard errors are (in soft brackets) are clustered at the household level to reflect the design effect, and $p$-values corrected for False Discovery Rates across all the outcomes in the table are presented in hard brackets.  Stars on coefficient estimates are derived from the FDR-corrected $p$-values, *=10%, **=5%, and ***=1% significance.

Endline Beneficiary Enterprise with Gender Interactions.

Notes: Table presents tests for heterogeneity of beneficiary enterprise effects by Gender.  Interacted coefficients  give the differential effect of each arm for women, `Female' gives the difference between women and men in the control group, and the uninteracted treatment terms give the impact of each arm for men.   Standard errors are (in soft brackets) are clustered at the household level to reflect the design effect, and $p$-values corrected for False Discovery Rates across all the outcomes in the table are presented in hard brackets.  Stars on coefficient estimates are derived from the FDR-corrected $p$-values, *=10%, **=5%, and ***=1% significance.

Standard Complementarities Test, Primary Outcomes.

Notes:  Table tests for complementarities of cash and training on Primary outcomes.  `HD' is a modified dummy for receiving HD, and `GD' cash, including those in the Combined arm as having received both interventions.  The Complementarity dummy, for the Combined arm only, therefore tests whether the Combined arm produces an outcome different from what we would expect based on the sum of the HD and GD impacts alone.  Standard errors are (in soft brackets) are clustered at the household level to reflect the design effect, and $p$-values corrected for False Discovery Rates across all the outcomes in the table are presented in hard brackets.  Stars on coefficient estimates are derived from the FDR-corrected $p$-values, *=10%, **=5%, and ***=1% significance.

Standard Complementarities Test, Secondary Outcomes.

Notes:  Table tests for complementarities of cash and training on Secondary outcomes.  `HD' is a modified dummy for receiving HD, and `GD' cash, including those in the Combined arm as having received both interventions.  The Complementarity dummy, for the Combined arm only, therefore tests whether the Combined arm produces an outcome different from what we would expect based on the sum of the HD and GD impacts alone.  Standard errors are (in soft brackets) are clustered at the household level to reflect the design effect, and $p$-values corrected for False Discovery Rates across all the outcomes in the table are presented in hard brackets.  Stars on coefficient estimates are derived from the FDR-corrected $p$-values, *=10%, **=5%, and ***=1% significance.

Complementarities Test, Midline Business Outcomes.

Notes:  Table tests for complementarities of cash and training on midline business outcomes.  `HD' is a modified dummy for receiving HD, and `GD' cash, including those in the Combined arm as having received both interventions.  The Complementarity dummy, for the Combined arm only, therefore tests whether the Combined arm produces an outcome different from what we would expect based on the sum of the HD and GD impacts alone.  Standard errors are (in soft brackets) are clustered at the household level to reflect the design effect, and $p$-values corrected for False Discovery Rates across all the outcomes in the table are presented in hard brackets.  Stars on coefficient estimates are derived from the FDR-corrected $p$-values, *=10%, **=5%, and ***=1% significance.

Complementarities Test, Endline Business Outcomes.

Notes:  Table tests for complementarities of cash and training on endline business outcomes.  `HD' is a modified dummy for receiving HD, and `GD' cash, including those in the Combined arm as having received both interventions.  The Complementarity dummy, for the Combined arm only, therefore tests whether the Combined arm produces an outcome different from what we would expect based on the sum of the HD and GD impacts alone.  Standard errors are (in soft brackets) are clustered at the household level to reflect the design effect, and $p$-values corrected for False Discovery Rates across all the outcomes in the table are presented in hard brackets.  Stars on coefficient estimates are derived from the FDR-corrected $p$-values, *=10%, **=5%, and ***=1% significance.

Cost Equivalent Analysis, Secondary Outcomes.

Note:  This table uses a linear adjustment of secondary outcomes for program cost to compare HD and GD at exactly equivalent costs.  The Transfer value column estimates the marginal effect of spending an extra $100 through cash transfers.  The Cost-equivalent GD impact column is estimated as a dummy for either HD or GD treatment, and estimates the impact of cash at the exact cost of HD.  The Differential impact of HD column then estimates the differential effect of HD above cash at this benchmarked cost.  Regressions include but do not report the lagged dependent variable, fixed effects for randomization blocks, and a set of LASSO-selected baseline covariates.  Standard errors are (in soft brackets) are clustered at the household level to reflect the design effect, and $p$-values corrected for False Discovery Rates across all outcomes within each family are presented in hard brackets.  Stars on coefficient estimates are derived from the FDR-corrected $p$-values, *=10%, **=5%, and ***=1% significance.

Midline Business Cost Equivalence.

Notes:  This table uses a linear adjustment of midline business outcomes for program cost to compare HD and GD at exactly equivalent costs.  The Transfer value column estimates the marginal effect of spending an extra $100 through cash transfers.  The Cost-equivalent GD impact column is estimated as a dummy for either HD or GD treatment, and estimates the impact of cash at the exact cost of HD.  The Differential impact of HD column then estimates the differential effect of HD above cash at this benchmarked cost.  Regressions include but do not report the lagged dependent variable, fixed effects for randomization blocks, and a set of LASSO-selected baseline covariates.  Standard errors are (in soft brackets) are clustered at the household level to reflect the design effect, and $p$-values corrected for False Discovery Rates across all outcomes within each family are presented in hard brackets.  Stars on coefficient estimates are derived from the FDR-corrected $p$-values, *=10%, **=5%, and ***=1% significance.

Endline Business Cost Equivalence.

Notes:  This table uses a linear adjustment of endline business outcomes for program cost to compare HD and GD at exactly equivalent costs.  The Transfer value column estimates the marginal effect of spending an extra $100 through cash transfers.  The Cost-equivalent GD impact column is estimated as a dummy for either HD or GD treatment, and estimates the impact of cash at the exact cost of HD.  The Differential impact of HD column then estimates the differential effect of HD above cash at this benchmarked cost.  Regressions include but do not report the lagged dependent variable, fixed effects for randomization blocks, and a set of LASSO-selected baseline covariates.  Standard errors are (in soft brackets) are clustered at the household level to reflect the design effect, and $p$-values corrected for False Discovery Rates across all outcomes within each family are presented in hard brackets.  Stars on coefficient estimates are derived from the FDR-corrected $p$-values, *=10%, **=5%, and ***=1% significance.

Robustness of Cost Equivalence Adjustment, Primary Outcomes.

Notes:  Table reports the coefficient on the differential effect of HD over cost-equivalent cash using seven different specifications.  Column 1 is the linear adjustment reported elsewhere.  Column 2 includes a quadratic, and column 3 a quadratic and cubic term in the cost deviations from Gikuriro.  Columns 4-7 leave out one of the cash treatment arms and repeat the linear cost adjustment.  Asterices denote significance at the 10, 5, and 1 percent levels, and are based on household-clustered standard errors, in parentheses.

Robustness of Cost Equivalence Adjustment, Secondary Outcomes.

Notes:  Table reports the coefficient on the differential effect of HD over cost-equivalent cash using seven different specifications.  Column 1 is the linear adjustment reported elsewhere.  Column 2 includes a quadratic, and column 3 a quadratic and cubic term in the cost deviations from Gikuriro.  Columns 4-7 leave out one of the cash treatment arms and repeat the linear cost adjustment.  Asterices denote significance at the 10, 5, and 1 percent levels, and are based on household-clustered standard errors, in parentheses.

Benefit-Cost Ratios, Secondary Outcomes.

Note:  Table gives the impact per $100 spent, which is calculated by dividing the estimated ITT impacts by the cost per arm in hundreds of dollars.  The standard errors in the table are similarly the ITT SEs divided by costs.  Reported $p$-values in final three columns derived from $F$-tests of hypotheses that cost-benefit ratios are equal between: (a) joint test across all arms, (b) GD Lower and HD; (c) GD Lower and GD Large; and (d) GD Large and Combined arms.

Heterogeneity Analysis by Gender.

Notes: Table presents tests for heterogeneity of treatment effects by Gender.  Uninteracted coefficients in the first four rows give the treatment effect of the program on men, and the next four rows test for the differential effect between women and men. Standard errors are (in soft brackets) are clustered at the household level to reflect the design effect, and $p$-values corrected for False Discovery Rates across all the outcomes in the table are presented in hard brackets.  Stars on coefficient estimates are derived from the FDR-corrected $p$-values, *=10%, **=5%, and ***=1% significance.  $p$-value in the last row from an F-test on whether treatments have a jointly differential effect by gender.

Heterogeneity Analysis by Age.

Notes: Table presents tests for heterogeneity of treatment effects by age.  First four rows give effect of treatment among young, and next four rows test for differential treatment effect for those 23 and over. Standard errors are (in soft brackets) are clustered at the household level to reflect the design effect, and $p$-values corrected for False Discovery Rates across all the outcomes in the table are presented in hard brackets.  Stars on coefficient estimates are derived from the FDR-corrected $p$-values, *=10%, **=5%, and ***=1% significance.  $p$-value in the last row from an F-test on whether treatments have a jointly differential effect by gender.

Heterogeneity Analysis by Baseline Consumption.

Notes: Table presents tests for heterogeneity of treatment effects by baseline Household Consumption.  Consumption demeaned before interaction so first four rows give effect of treatment at average value, and next four rows test for differential treatment effect by consumption. Standard errors are (in soft brackets) are clustered at the household level to reflect the design effect, and $p$-values corrected for False Discovery Rates across all the outcomes in the table are presented in hard brackets.  Stars on coefficient estimates are derived from the FDR-corrected $p$-values, *=10%, **=5%, and ***=1% significance.  $p$-value in the last row from an F-test on whether treatments have a jointly differential effect by gender.

Heterogeneity Analysis by Sector-level Employment.

Notes: Table presents tests for heterogeneity of treatment effects by baseline Employment Rates. Employment demeaned before interaction so first four rows give effect of treatment at average value, and next four rows test for differential treatment effect by employment rates. Standard errors are (in soft brackets) are clustered at the household level to reflect the design effect, and $p$-values corrected for False Discovery Rates across all the outcomes in the table are presented in hard brackets.  Stars on coefficient estimates are derived from the FDR-corrected $p$-values, *=10%, **=5%, and ***=1% significance.  $p$-value in the last row from an F-test on whether treatments have a jointly differential effect by gender.

Simple Spillover Analysis.

Notes:  Table analyzes spillover effects of the three main treatments (HD, GD Main, and GD Large) on the five primary outcomes.  The first three rows are dummy variables for own treatment status, and the next three are the saturation rates for the three treatments among others in the village, so measure the marginal effect of going from no one else treated to everyone else treated.  Regressions include but do not report the lagged dependent variable, fixed effects for randomization blocks, and a set of LASSO-selected baseline covariates, and are weighted to reflect intensive tracking.  Standard errors are (in soft brackets) are clustered at the household level to reflect the design effect, and $p$-values corrected for False Discovery Rates across all the outcomes in the table are presented in hard brackets.  Stars on coefficient estimates are derived from the FDR-corrected $p$-values, *=10%, **=5%, and ***=1% significance.  Bottom row is the $p$-value on an F-test of the joint significance of the three saturation terms.

Spillovers on Household Consumption.

Notes: Each column describes the direct and spillover effects of a specific treatment on Household Consumption (IHS); all results in the table are from a single estimation. Saturation mean and standard deviation correspond to the distribution of saturation rates for the treatment in question. Standard errors are (in soft brackets) are clustered at the household level to reflect the design effect, and $p$-values corrected for False Discovery Rates across all the outcomes in the table are presented in hard brackets.  Stars on coefficient estimates are derived from the FDR-corrected $p$-values, *=10%, **=5%, and ***=1% significance.  $p$-value in the last row corresponds to a test for whether the treatment in question has interference effects on any arm, including control.

Spillovers on Employment.

Notes: Each column describes the direct and spillover effects of a specific treatment on Employment; all results in the table  are from a single estimation. Saturation mean and standard deviation correspond to the distribution of saturation rates for the treatment in question.  Regressions include but do not report the lagged dependent variable, fixed effects for randomization blocks, and a set of LASSO-selected baseline covariates, and are weighted to reflect intensive tracking.  Standard errors are (in soft brackets) are clustered at the household level to reflect the design effect, and $p$-values corrected for False Discovery Rates across all the outcomes in the table are presented in hard brackets.  Stars on coefficient estimates are derived from the FDR-corrected $p$-values, *=10%, **=5%, and ***=1% significance.  $p$-value in the last row corresponds to a test for whether the treatment in question has interference effects on any arm, including control.

Spillovers on Monthly Income.

Notes: Each column describes the direct and spillover effects of a specific treatment on Monthly Income (IHS); all results in the table  are from a single estimation. Saturation mean and standard deviation correspond to the distribution of saturation rates for the treatment in question.  Regressions include but do not report the lagged dependent variable, fixed effects for randomization blocks, and a set of LASSO-selected baseline covariates, and are weighted to reflect intensive tracking. Standard errors are (in soft brackets) are clustered at the household level to reflect the design effect, and $p$-values corrected for False Discovery Rates across all the outcomes in the table are presented in hard brackets.  Stars on coefficient estimates are derived from the FDR-corrected $p$-values, *=10%, **=5%, and ***=1% significance.  $p$-value in the last row corresponds to a test for whether the treatment in question has interference effects on any arm, including control.

Spillovers on Productive Hours.

Notes: Each column describes the direct and spillover effects of a specific treatment on Productive Hours; all results in the table  are from a single estimation. Saturation mean and standard deviation correspond to the distribution of saturation rates for the treatment in question.  Regressions include but do not report the lagged dependent variable, fixed effects for randomization blocks, and a set of LASSO-selected baseline covariates, and are weighted to reflect intensive tracking. Standard errors are (in soft brackets) are clustered at the household level to reflect the design effect, and $p$-values corrected for False Discovery Rates across all the outcomes in the table are presented in hard brackets.  Stars on coefficient estimates are derived from the FDR-corrected $p$-values, *=10%, **=5%, and ***=1% significance.   $p$-value in the last corresponds to a test for whether the treatment in question has interference effects on any arm, including control.

Spillovers on Productive Asset Values.

Notes: Each column describes the direct and spillover effects of a specific treatment on Productive Assets (IHS); all results in the table  are from a single estimation. Saturation mean and standard deviation correspond to the distribution of saturation rates for the treatment in question.  Regressions include but do not report the lagged dependent variable, fixed effects for randomization blocks, and a set of LASSO-selected baseline covariates, and are weighted to reflect intensive tracking. Standard errors are (in soft brackets) are clustered at the household level to reflect the design effect, and $p$-values corrected for False Discovery Rates across all the outcomes in the table are presented in hard brackets.  Stars on coefficient estimates are derived from the FDR-corrected $p$-values, *=10%, **=5%, and ***=1% significance.  $p$-value in the last row corresponds to a test for whether the treatment in question has interference effects on any arm, including control.

Are treatments protective against measured Covid shocks?

Notes: This table proceeds in the following steps.  First, we use second-order polynomials in the cumulative shock indices to predict endline outcomes in the control group;  following <cit.>, we use a leave-one-out approach to omit each control-group observation from the regression on which its prediction is based. We then use predicted endline outcomes in the control group to predict counterfactual endline outcomes in other treatment arms, and interact the centered predictions with treatment indicators.  All specifications include controls for the baseline value of the outcome, as well as lasso-selected controls and block fixed effects, as in the ITT specification.  Predictive index is the predicted value of the endline outcome, based on plausibly exogenous covid shock measures, with model estimated by cross-validated lasso in the control group only.

Association between Covid-19 shock measures and endline outcomes in control group

Note:  Each column within each panel represents a separate regression.  All regressions control for baseline values of the corresponding outcome and for block fixed effects.

ITT Effects on Transfers.

Note:  Regressions include but do not report the lagged dependent variable, fixed effects for randomization blocks, and a set of LASSO-selected baseline covariates, and are weighted to reflect intensive tracking. Standard errors are (in soft brackets) are clustered at the household level to reflect the design effect, and $p$-values corrected for False Discovery Rates across all the outcomes in the table are presented in hard brackets.  Stars on coefficient estimates are derived from the FDR-corrected $p$-values, *=10%, **=5%, and ***=1% significance. Reported $p$-values in final three columns derived from $F$-tests of hypotheses that cost-benefit ratios are equal between: (a) GD Lower and HD; (b) GD Lower and GD Large; and (c) GD Large and Combined treatments.


# A proof of Frankl-Kupavskii’s conjecture on edge-union condition

Xuechun Zhang and Hongliang Lu
School of Mathematics and Statistics
Xi’an Jiaotong University
Xi’an, Shaanxi 710049, P.R.China

Abstract

A 3-graph $\mathcal{F}$ is _$U(s,2s+1)$_ if for any $s$ edges
$e_{1},...,e_{s}\in E(\mathcal{F})$, $|e_{1}\cup...\cup e_{s}|\leq 2s+1$.
Frankl and Kupavskii (2020) proposed the following conjecture: For any
$3$-graph $\mathcal{F}$ with $n$ vertices, if $\mathcal{F}$ is $U(s,2s+1)$,
then

$e(\mathcal{F})\leq\max\left\\{{n-1\choose 2},(n-s-1){s+1\choose
2}+{s+1\choose 3},{2s+1\choose 3}\right\\}.$

In this paper, we confirm Frankl and Kupavskii’s conjecture.

Keywords: stability; matching; matching number

##  1 Introduction

A _hypergraph_ $\mathcal{F}$ consists of a vertex set $V(\mathcal{F})$ and an
edge set $E(\mathcal{F})$, where every edge is a non-empty subset of
$V(\mathcal{F})$. A hypergraph $\mathcal{F}$ is _$k$ -uniform_ if all its
edges have size $k$ and we call it a $k$-graph for short. In particular,
2-graph is called graph. A _matching_ in a hypergraph $\mathcal{F}$ is a set
of pairwise disjoint edges in $\mathcal{F}$. A _perfect matching_ in a
$k$-graph is a matching that covers every vertex. A _maximum matching_ in a
$k$-graph is a matching of maximum size among all matchings in the graph. For
a $k$-graph $\mathcal{F}$, we use $\nu(\mathcal{F})$ to denote the size of a
maximum matching in $\mathcal{F}$. Let $G_{1}=(V_{1},E_{1})$ and
$G_{2}=(V_{2},E_{2})$ be two graphs such that $V_{1}\cap V_{2}=\emptyset$. The
_union_ of graphs $G_{1}$ and $G_{2}$ denoted by $G_{1}\cup G_{2}$ is the
graph with vertex set $V_{1}\cup V_{2}$ and edge set $E_{1}\cup E_{2}$. The
_join_ of graphs $G_{1}$ and $G_{2}$ denoted by $G_{1}\vee G_{2}$ is the graph
union $G_{1}\cup G_{2}$ together with all the edges joining $V_{1}$ and
$V_{2}$. For a graph $G$, we denote the complement of $G$ by $\overline{G}$.

We often identify $E(\mathcal{F})$ with $\mathcal{F}$ when there is no
confusion and in particular, $|\mathcal{F}|$ denotes the number of edges in
$\mathcal{F}$. Given $T\subseteq V(\mathcal{F})$, let $\mathcal{F}-T$ denote
the subgraph of $\mathcal{F}$ with vertex set $V(\mathcal{F})\setminus T$ and
edge set $\\{e\in\mathcal{F}\ :\ e\subseteq V(\mathcal{F})\setminus T\\}$.
Given a vertex set $X$ and integer $k\geq 1$, let ${X\choose k}=\\{S\subseteq
X\ |\ |S|=k\\}$. Let $n\geq 1$ be an integer and let $[n]=\\{1,\ldots,n\\}$.
For a $k$-graph $\mathcal{F}$ and $v\in\mathcal{F}$, let
$N_{\mathcal{F}}(v)=\\{e\in{V({\mathcal{F}})\choose k-1}\ |\ e\cup\\{v\\}\in
E(\mathcal{F})\\}$. When there is no confusion, we use $N_{\mathcal{F}}(v)$
denote the $(k-1)$-graph with vertex set $V({\mathcal{F}})-v$ and edge set
$N_{\mathcal{F}}(v)$. Let $m,i$ be two integers such that $1\leq i\leq
m\leq(n-2)/2$. Let $K^{0}_{i}$, $K^{1}_{2m-2i+1}$ and $K^{2}_{n-2m+i-1}$
denote complete graphs with vertex set $[i]$, $[2m-i+1]\setminus[i]$ and
$[n]\setminus[2m-i+1]$ respectively and let
$A^{i}_{n,m}:=K^{0}_{i}\vee(K^{1}_{2m-2i+1}\cup\overline{K^{2}_{n-2m+i-1}})$.
Let $A^{0}_{n,m}:=K^{1}_{2m+1}\cup\overline{K^{2}_{n-2m-1}}$.

Let $p$, $r$ be two positive integers such that $p\geq r$. Define

$\displaystyle\mathcal{A}_{p,r}:=\mathcal{A}(p,r,n,k):=\\{A\in{[n]\choose
k}:|A\cap[p]|\geq r\\}.$

Let $k,s,q$ be three integers such that $2\leq s$ and $2\leq k\leq q<sk$. A
$k$-graph $\mathcal{F}$ is said to have _property $U(s,q)$_ if

$\displaystyle|e_{1}\cup...\cup e_{s}|\leq q$ (1)

for any $s$ edges $e_{1},...,e_{s}\in E(\mathcal{F})$. For shorthand, we will
also say $\mathcal{F}$ is $U(s,q)$ to refer to this property.

Let

$\displaystyle\mathcal{F}_{1}:=\mathcal{A}(1,1,n,3),\ \
\mathcal{F}_{2}:=\mathcal{A}(s+1,2,n,3),\ \
\mathcal{F}_{3}:=\mathcal{A}(2s+1,3,n,3),$

we can calculate $|\mathcal{F}_{i}|$, $i\in\\{1,2,3\\}$ from these definition,

$\displaystyle|\mathcal{F}_{1}|={{n-1}\choose 2}=\frac{(n-1)(n-2)}{2},$ (2)

$\displaystyle|\mathcal{F}_{2}|={{s+1}\choose 2}(n-s-1)+{{s+1}\choose
3}=-\frac{1}{3}s^{3}+(\frac{n}{2}-1)s^{2}+(\frac{n}{2}-\frac{2}{3})s,$ (3)

$\displaystyle|\mathcal{F}_{3}|={{2s+1}\choose
3}=\frac{4}{3}s^{3}-\frac{1}{3}s.$ (4)

Frankl and Kupavskii [8] conjectured that the maximum boundary of
$|\mathcal{F}|$ when $k=3$ and $q=2s+1$.

######  Conjecture 1.1 (Frankl and Kupavskii, [8])

Let $\mathcal{F}$ be a 3-graph with vertex set $[n]$. If $\mathcal{F}$ is
$U(s,2s+1)$, then $|\mathcal{F}|\leq\max\\{|\mathcal{F}_{i}|\ |\ i\in[3]\\}$.

In this paper, we obtain the following result, which confirms Conjecture 1.1.

###### Theorem 1.2

Let $n,s$ be two integers such that $s\geq 2$ and $n\geq 2s+2$. Let
$\mathcal{F}$ be a 3-graph with vertex set $[n]$. If $\mathcal{F}$ is
$U(s,2s+1)$, then $|\mathcal{F}|\leq\max\\{|\mathcal{F}_{i}|\ |\ i\in[3]\\}$.

Let us recall some fundamental results of extremal set theory. Erdős, Ko and
Rado[3] proved that if $\mathcal{F}\subseteq{n\choose k}$ satisfying $|F\cap
F^{\prime}|\geq t$ for any $F$, $F^{\prime}\in\mathcal{F}$, then
$|\mathcal{F}|\leq{n-t\choose{k-t}}$ for $n>n_{0}(k,t)$. Moreover, they also
proved $n_{0}(k,1)=2k$. We call the conclusion as EKR Theorem in the following
for short. The smallest $n_{0}(k,t)$ of the EKR Theorem has been determined by
Frankl [4] for $t\geq 15$ and subsequently by Wilson [10] for all
$t:n_{0}(k,t)=(k-t+1)(t+1)$. Deza and Frankl [1] showed some new
generalizations and analogues of the EKR theorem. Frankl [5] added a union
condition $U(s,n-t)$ to $\mathcal{F}$ and gave a upper bound to
$|\mathcal{F}|$ when $t\leq{\frac{2^{k}k}{150}}$. Erdős [2] in 1965 made the
following conjecture: If $\mathcal{F}\subseteq{n\choose k}$,
$\nu(\mathcal{F})\leq s$, then
$|\mathcal{F}|\leq\max\\{|\mathcal{A}_{s,1}|,|\mathcal{A}_{(s+1)k-1,k}|\\}$.
It was one of the favourite problems of Erdős and attracted a lot of
attention.

The rest of the paper is organized as follows. In Section $2$, we first
introduce some fundamental definitions and prove several lemmas needed in our
proof. In Section $3$, we give the proof of Theorem 1.2.

##  2 Several Technical Lemma

Let $k\geq 2$ be an integer. Consider two sets
$F_{1}=(a_{1},a_{2},\ldots,a_{k})$ with $a_{1}<\cdots<a_{k}$ and
$F_{2}=(b_{1},b_{2},\ldots,b_{k})$ with $b_{1}<\cdots<b_{k}$. Then
$F_{1}\prec_{s}F_{2}$ iff $a_{i}\leq b_{i}$ for every $i\in[k]$. We say that a
family $\mathcal{F}\subseteq{[n]\choose k}$ is _shifted_ if
$F_{2}\in\mathcal{F}$ and $F_{1}\prec_{s}F_{2}$ implies $F_{1}\in\mathcal{F}$.
If $\mathcal{F}$ is shifted, we say $\mathcal{F}$ is _stable_.

###### Lemma 2.1

Let $G$ be a stable graph with vertex set $[n]$ and $\nu(G)=m$. Let
$r:=\max\\{i\ |\ \nu(G-\\{0,\ldots,i\\})=\nu(G)-i\\}$. Then $G$ is a subgraph
of $A_{n,m}^{r}$.

Proof. Let $\mathcal{M}=\\{\\{j,2m+3-j\\}\ |\ 1\leq j\leq m+1\\}$. Since
$\nu(G)=m$, then $\mathcal{M}$ is not a matching of $G$. So there exists
$j\in[m+1]$ such that $\\{j,2m+3-j\\}\notin G$. Since $G$ is stable, for any
edge $\\{u,v\\}\in G$ with $u<v$, either $u<j$ or $v<2m+3-j$. Thus $G$ is a
subgraph of $A_{n,m}^{j-1}$. We choose maximum $j$ such that $G$ is a subgraph
of $A_{n,m}^{j-1}$.

Next we show that $r=j-1$. Note that

$m+1-j=\nu(G)+1-j\leq\nu(G-[j-1])\leq\nu(A_{n,m}^{j-1}-[j-1])=m+1-j.$

Thus we have $\nu(G-[j-1])=\nu(G)-j+1$. Thus by the definition of $r$, we have
$r\geq j-1$. We claim $\\{\\{i+1,2m+2-i\\}|\ j\leq i\leq m\\}$ is a matching
of $G$. Otherwise, there exists $t\in[m]-[j-1]$ such that
$\\{t+1,2m+2-t\\}\notin G$. Hence for any $\\{a,b\\}\in G$ with $a<b$, either
$a\leq t$ or $b\leq 2m+1-t$. So $G$ is a subgraph of $A^{t}_{n,m}$,
contradicting the choice of $j$ since $j-1<t$. This completes the proof.
$\Box$

###### Lemma 2.2

Let $G$ be a stable graph with vertex set $[n]$ and $\nu(G)=s$. Then
$\\{\\{i,2s-i+1\\}\ |\ 1\leq i\leq s\\}$ is a matching of size $s$ in $G$.

Proof. By contradiction, suppose there exists $i\in[s]$ such that
$\\{i,2s-i+1\\}\notin E(G)$. We claim $\\{1,2s\\}\in E(G)$. Otherwise,
$E(G)\subseteq{[2s-1]\choose 2}$ since $G$ is stable and so we have
$\nu(G)\leq s-1$, a contradiction. So we may say $i\geq 2$. Note that for any
$v\in\\{2s-i+1,\ldots,n\\}$, $v$ is an isolated vertices in $G-[i-1]$ since
$G$ is stable. So we have
$\nu(G-[i-1])\leq\lfloor\frac{1}{2}(n-i+1-(n-2s+i))\rfloor=s-i$, which implies
that $\nu(G)\leq s-1$, a contradiction. $\Box$

A basic result of Frankl [6, 7] allows us to restrict our proof to stable
family.

###### Lemma 2.3

If the family $\mathcal{F}\subseteq{[n]\choose k}$ is $U(s,q)$, then there
exists a stable and $U(s,q)$ family $\mathcal{F}^{\prime}\subseteq{[n]\choose
k}$ such that $|\mathcal{F}|=|\mathcal{F}^{\prime}|$.

By lemma 2.3, we may assume that $\mathcal{F}$ is stable in our proof. We
denote the shadow of $\mathcal{F}$ by $\partial\mathcal{F}$.

$\displaystyle\partial\mathcal{F}=\\{G\in{[n]\choose{k-1}}:\exists
F\in\mathcal{F},G\subset F\\}$ (5)

When $k=3$, $\partial\mathcal{F}\subseteq{V(\mathcal{F})\choose 2}$ and so
$\partial\mathcal{F}$ can be seen as a graph. Note that if $\mathcal{F}$ is
stable, then $\partial\mathcal{F}$ is stable.

##  3 Proof of Theorem 1.2

If $\nu(\mathcal{F})=1$, then by EKR Theorem,
$|\mathcal{F}|\leq|\mathcal{F}_{1}|\leq\max\\{|\mathcal{F}_{i}|\ |\
i\in[3]\\}$. So we may assume that $\nu(\mathcal{F})\geq 2$. Note that
$\nu(\mathcal{F})\geq 2$ implies that $\mathcal{F}\subseteq{[n]\choose 3}$ is
not $U(2,5)$. So we have the following result.

###### Lemma 3.1

Let $n$ be an integer such that $n\geq 7$, If $\mathcal{F}\subseteq{[n]\choose
3}$ is $U(2,5)$, then $|\mathcal{F}|\leq\max\\{|\mathcal{F}_{i}|\ |\
i\in[3]\\}$.

Thus, we can restrict our proof to $s\geq 3$. By Lemma 2.3, we give the proof
of Theorem 1.2 by proving Lemmas 3.2, 3.3 and 3.5.

###### Lemma 3.2

Let $n,s$ be two integer such that $s\geq 3$ and $n\geq 2s+4$. Let
$\mathcal{F}$ be a stable 3-graph with vertex set $[n]$. If $\mathcal{F}$ is
$U(s,2s+1)$, $\nu(\mathcal{F})\geq 2$ and $\nu(\partial\mathcal{F})\geq s+2$,
then $|\mathcal{F}|\leq\max\\{|\mathcal{F}_{i}|\ |\ i\in[3]\\}$.

Proof. Since $\mathcal{F}$ is stable and $\nu(\mathcal{F})\geq 2$, we have
$\\{2,3,4\\}\in\mathcal{F}$. We first prove the following claim.

Claim 1.  $\nu(\partial\mathcal{F}-[4])\leq s-2$.

Otherwise, suppose that $\nu(\partial\mathcal{F}-[4])\geq s-1$. Then
$\partial\mathcal{F}-[4]$ has a matching of size $s-1$. Let $M$ be a matching
of size $s-1$ in $\partial\mathcal{F}-[4]$. Write
$M^{\prime}:=\\{e\cup\\{1\\}\ |\ e\in M\\}\cup\\{\\{2,3,4\\}\\}$. Since
$\mathcal{F}$ is stable, we have $M^{\prime}\subseteq\mathcal{F}$. One can see
that $|M^{\prime}|=s$ and $|\cup_{e\in M^{\prime}}e|=2s+2$, a contradiction
since $\mathcal{F}$ is $U(s,2s+1)$. This completes the proof of Claim 1.

Since $\nu(\partial\mathcal{F})\geq s+2$, by Claim 1, we have
$\nu(\partial\mathcal{F})=s+2$ and $\nu(\partial\mathcal{F}-[4])=s-2$.

Claim 2.  If $M_{0}$ is a matching of size $s$ in
$\partial\mathcal{F}-\\{1,2\\}$, then $N_{\mathcal{F}}(2)\cap
M_{0}=\emptyset$.

Otherwise, suppose that $N_{\mathcal{F}}(2)\cap M_{0}\neq\emptyset$. Let $e\in
M_{0}\cap N_{\mathcal{F}}(2)$ and $M_{0}^{\prime}=\\{f\cup\\{1\\}\ |\ f\in
M\setminus e\\}\cup\\{e\cup\\{2\\}\\}$. By the stability of $\mathcal{F}$, one
can see that $M_{0}^{\prime}\subseteq\mathcal{F}$ and
$|V(M_{0}^{\prime})|=2s+2$. So $\mathcal{F}$ is not $U(s,2s+1)$, a
contradiction. This completes the proof of Claim 2.

Claim 3.  $e=\\{2,3,2s+2\\}\notin\mathcal{F}$.

By contradiction. Suppose that $\\{2,3,2s+2\\}\in\mathcal{F}$. By Claim 1,
$\partial\mathcal{F}-[3]$ has a matching of size $s-1$. By Lemma 2.2,
$M_{1}:=\\{\\{i,2s+5-i\\}\ |\ 4\leq i\leq s+2\\}$ is matching of size $s-1$ in
$\partial\mathcal{F}-[3]$. Let $M_{1}^{\prime}=\\{f\cup\\{1\\}\ |\ f\in
M_{1}\\}\cup\\{\\{2,3,2s+2\\}\\}$. Then we have $|M_{1}^{\prime}|=s$,
$|V(M_{1}^{\prime})|=2s+2$. Since $M\subseteq N_{\mathcal{F}}(1)$, we have
$M_{1}^{\prime}\subseteq\mathcal{F}$. So $\mathcal{F}$ is not $U(s,2s+1)$, a
contradiction. This completes the proof of Claim 3.

Let $r=\max\\{i\ |\
\nu(\partial\mathcal{F}-[i])=\nu(\partial\mathcal{F})-i\\}$. From Claim 1 we
have $r\geq 4$. By Lemma 2.1, $\partial\mathcal{F}$ is a subgraph of
$K_{r}^{0}\vee(K_{2s-2r+5}^{1}\cup K_{n-2s+r-5}^{2})$. By Lemma 2.2,
$\\{\\{i,2s+5-i\\}\ |\ 3\leq i\leq s+2\\}$ is a matching of size $s$ in
$\partial\mathcal{F}-\\{1,2\\}$. One can see that
$\\{s+2,s+3\\}\in\partial\mathcal{F}$ and so by Claim 2, we have
$\\{s+2,s+3,2\\}\notin\mathcal{F}$. By the stability of $\mathcal{F}$, every
edge of $\mathcal{F}$ containing no $1$ intersects $[s+1]$ at least two
vertices, i.e., $\mathcal{F}-\\{1\\}$ is a subgraph of
$\mathcal{F}_{2}-\\{1\\}$. Thus we have

$\displaystyle|\mathcal{F}\setminus\mathcal{F}_{2}|$
$\displaystyle=|N_{\mathcal{F}}(1)\setminus N_{\mathcal{F}_{2}}(1)|$
$\displaystyle\leq\left|\left(({[n]-[1]\choose 2}\setminus{[n]-[r]\choose
2})\cup{[2s-r+5]-[r]\choose 2}\right)\setminus\left({[n]-[1]\choose
2}\setminus{[n]-[1+s]\choose 2}\right)\right|$ $\displaystyle={s-r+4\choose
2}$ $\displaystyle\leq{s\choose 2}\quad\mbox{(since $r\geq 4$)}.$

Note that $\mathcal{M}:=\\{\\{i+2,2s+3-i\\}\ |\ 1\leq i\leq s\\}$ is a
matching of size $s$ in $\partial\mathcal{F}-[2]$. By Claim 2, we have
$\mathcal{M}\cap N_{\mathcal{F}}(2)=\emptyset$.

Claim 4.  For any two distinct edges $e_{1},e_{2}\in\mathcal{M}$, ${e_{1}\cup
e_{2}\choose 3}\cap\mathcal{F}=\emptyset$.

Otherwise, suppose that ${e_{1}\cup e_{2}\choose
3}\cap\mathcal{F}\neq\emptyset$. Let $e\in{e_{1}\cup e_{2}\choose
3}\cap\mathcal{F}$ and let $v\in(e_{1}\cup e_{2})\backslash e$. Note that
$v\leq 2s+2$. So we have $\\{1,2,v\\}\in\mathcal{F}$. Let
$M_{2}=\\{e,\\{1,2,v\\}\\}\cup\\{f\cup\\{1\\}\ |\
f\in\mathcal{M}\backslash\\{e_{1},e_{2}\\}\\}$. Then we have $|M_{2}|=s$ and
$|V(M_{2})|=2s+2$. By the stability, One can see that
$M_{2}\subseteq\mathcal{F}$, contradicting that $\mathcal{F}$ is $U(s,2s+1)$.
This completes the proof of Claim 4.

Write $A=\\{\\{s+2,s+3\\},\\{3,2s+2\\}\\}$. Recall that $\mathcal{F}$ and
$\partial\mathcal{F}$ are stable. By Claims 2 and 4, $\\{i\\}\cup
e\notin\mathcal{F}$ for any $i\in\\{2,3\\}$ and $e\in\mathcal{M}\backslash A$.
By Claim 3, $\\{j\\}\cup e\notin\mathcal{F}$ for any $j\in[n]-[2s+1]$ and
$e\in{[s+1]-\\{1\\}\choose 2}$. Hence by Claim 4, we have

$\displaystyle|\mathcal{F}_{2}\setminus\mathcal{F}|$
$\displaystyle\geq\left|{\\{2,3\\}\choose 1}\right|\left|\mathcal{M}\backslash
A\right|+{s\choose 2}(n-2s-1)+{4\choose 3}\left|{\mathcal{M}\backslash
A\choose 2}\right|$ $\displaystyle=2(s-2)+{s\choose 2}(n-2s-1)+4{s-2\choose
2}$ $\displaystyle=2(s-2)^{2}+{s\choose 2}(n-2s-1)$ $\displaystyle>{s\choose
2}\quad\mbox{(since $n\geq 2s+4$)}.$

So we have
$|\mathcal{F}_{2}\setminus\mathcal{F}|>|\mathcal{F}\setminus\mathcal{F}_{2}|$,
which implies that $|\mathcal{F}_{2}|>|\mathcal{F}|$. This complete the proof.
$\Box$

###### Lemma 3.3

Let $n,s$ be two integer such that $s\geq 3$ and $n\geq 2s+2$. Let
$\mathcal{F}$ be a stable 3-graph with vertex set $[n]$. If $\mathcal{F}$ is
$U(s,2s+1)$ and $\nu(\partial\mathcal{F})\leq s$, then
$|{\mathcal{F}}|\leq\max\\{|\mathcal{F}_{i}|\ |\ i\in[3]\\}$.

Proof. Without loss of generality, we may assume that
$\nu(\partial\mathcal{F})=s$ since we may add some edges containing $1$ to
$\mathcal{F}$ such that $\nu(\partial\mathcal{F})=s$. Let $r:=\max\\{i\ |\
\nu(\partial\mathcal{F}-\\{0,\ldots,i\\})=\nu(\partial\mathcal{F})-i\\}$.

Since $\partial\mathcal{F}$ is stable and $\nu(\partial\mathcal{F})=s$, by
Lemma 2.1, $\partial\mathcal{F}$ is a subgraph of $A^{r}_{n,s}$. So for every
edge $e$ of $\mathcal{F}$, we have $|e\cap\\{2n-r+2,\ldots,n\\}|=1$ or
$e\subseteq[2s-r+1]$. Thus we have

$\displaystyle|\mathcal{F}|$ $\displaystyle\leq{r\choose
2}(n-2s+r-1)+{{2s-r+1}\choose 3}$
$\displaystyle=\frac{1}{3}r^{3}+(\frac{n}{2}-1)r^{2}-(\frac{n}{2}-s+2s^{2}-\frac{2}{3})r+\frac{4}{3}s^{3}-\frac{1}{3}s.$

Let
$f(r)=\frac{1}{3}r^{3}+(\frac{n}{2}-1)r^{2}-(\frac{n}{2}-s+2s^{2}-\frac{2}{3})r+\frac{4}{3}s^{3}-\frac{1}{3}s$.
Then $f(r)$ is a convex function on interval $[0,s]$ since
$f^{\prime\prime}(r)=2r+n-2\geq 0$ for $0\leq r\leq s$. Thus

$\displaystyle|\mathcal{F}|$ $\displaystyle\leq\max\\{f(0),f(s)\\}$
$\displaystyle=\max\\{{2s+1\choose 3},{s\choose 2}(n-s)+{s\choose 3}\\}$
$\displaystyle\leq\max\\{|\mathcal{F}_{2}|,|\mathcal{F}_{3}|\\}.$

This completes the proof. $\Box$

###### Lemma 3.4

Let $\mathcal{F}\subseteq{[6]\choose 3}$ such that
$e\cap\\{i,7-i\\}\neq\emptyset$ for all $e\in\mathcal{F}$, $1\leq i\leq 3$. If
$\nu(\mathcal{F})=1$, then $|\mathcal{F}|\leq 4$.

Proof. Let $M_{1}=\\{\\{1,2,3\\},\\{4,5,6\\}\\}$,
$M_{2}=\\{\\{1,2,4\\},\\{3,5,6\\}\\}$, $M_{3}=\\{\\{1,4,5\\},\\{2,3,6\\}\\}$
and $M_{4}=\\{\\{1,3,4\\},\\{2,5,6\\}\\}$. By the definition of $\mathcal{F}$,
we have $\mathcal{F}\subseteq\cup_{i=1}^{4}M_{i}$. Since $\nu(\mathcal{F})=1$,
then $|M_{i}\cap\mathcal{F}|\leq 1$ for $1\leq i\leq 4$. Thus
$|\mathcal{F}|\leq\sum_{i=1}^{4}|M_{i}\cap\mathcal{F}|\leq 4$. This completes
the proof. $\Box$

###### Lemma 3.5

Let $n,s$ be two integers such that $s\geq 3$ and $n\geq 2s+2$. Let
$\mathcal{F}$ be a stable 3-graph with vertex set $[n]$. If $\mathcal{F}$ is
$U(s,2s+1)$ and $\nu(\partial\mathcal{F})=s+1$, then
$|{\mathcal{F}}|\leq\max\\{|\mathcal{F}_{i}|\ |\ i\in[3]\\}$.

Proof. Let $r:=\max\\{i\ |\
\nu(\partial\mathcal{F}-\\{0,\ldots,i\\})=\nu(\partial\mathcal{F})-i\\}$. By
Lemma 2.1, $\partial\mathcal{F}$ is a subgraph of $A_{n,s}^{r}$. Now we
discuss four cases.

Case 1. $3\leq r\leq s+1$.

For every edge $e\in\mathcal{F}$, $e\subseteq[2s+3-r]$ or $|e\cap[r]|=2$. So
we have

$\displaystyle|\mathcal{F}|$ $\displaystyle\leq{r\choose
2}(n-2s+r-3)+{{2s-r+3}\choose 3}$
$\displaystyle=\frac{1}{3}r^{3}+(\frac{n}{2}-1)r^{2}-(\frac{n}{2}+2s^{2}+3s+\frac{1}{3})r+\frac{4}{3}s^{3}+4s^{2}+\frac{11}{3}s+1,$

Let
$g(r):=\frac{1}{3}r^{3}+(\frac{n}{2}-1)r^{2}-(\frac{n}{2}+2s^{2}+3s+\frac{1}{3})r+\frac{4}{3}s^{3}+4s^{2}+\frac{11}{3}s+1.$
Note that $g(r)$ is a convex function on interval $[3,s+1]$ since
$g^{\prime\prime}(r)=2r+n-2\geq 0$ for $3\leq r\leq s+1$. Thus

$\displaystyle|\mathcal{F}|$ $\displaystyle\leq\max\\{g(3),g(s+1)\\}$
$\displaystyle=\max\\{{2s\choose 3}+3(n-2s),{s+2\choose 3}+{s+1\choose
2}(n-s-2)\\}$ $\displaystyle=\max\\{{2s\choose 3}+3(n-2s),{s+1\choose
3}+{s+1\choose 2}(n-s-1)\\}$
$\displaystyle=\max\\{3n+\frac{4}{3}s^{3}-2s^{2}-\frac{16}{3}s,|\mathcal{F}_{2}|\\}.$

Next we discuss two subcases.

Subcase 1.1. $n\leq(2s^{2}+5s)/3$.

From (4) we have

$\displaystyle|\mathcal{F}_{3}|-g(3)$ $\displaystyle=-3n+2s^{2}+5s\geq 0.$

Hence, $g(3)\leq|\mathcal{F}_{3}|$. On the other hand,
$g(s+1)=|\mathcal{F}_{2}|$. So we have
$|\mathcal{F}|\leq\max\\{g(3),g(s+1)\\}\leq\max\\{|\mathcal{F}_{i}|\ |\
i\in[3]\\}$.

Subcase 1.2. $n>(2s^{2}+5s)/3$.

Note that $n>(2s^{2}+5s)/3>10s/3$. Thus we have

$\displaystyle g(s+1)-g(3)$
$\displaystyle=-\frac{5}{3}s^{3}+(\frac{n}{2}+1)s^{2}+(\frac{n}{2}+\frac{14}{3})s-3n$
$\displaystyle>-\frac{5}{3}s^{3}+(\frac{5}{3}s+1)s^{2}+(\frac{5}{3}s+\frac{14}{3})s-10s\quad\mbox{(since
$s\geq 3$)}$ $\displaystyle=\frac{8s}{3}(s-2)>0.$

Thus by (3), one can see that

$\displaystyle|\mathcal{F}|$
$\displaystyle\leq\max\\{g(3),g(s+1)\\}=g(s+1)=|\mathcal{F}_{2}|.$

Case 2. $r=0$.

Then $\partial\mathcal{F}$ is a subgraph of $K_{2s+3}$. Thus
$\mathcal{F}\subseteq{[2s+3]\choose 3}$. From the definition of $r$ we have
$\nu(\partial\mathcal{F}-\\{1\\})=\nu(\partial\mathcal{F})=s+1$, by Lemma 2.2,
$\mathcal{M}:=\\{\\{i+1,2s+4-i\ |\ 1\leq i\leq s+1\\}\\}$ is a matching of
size $s+1$ in $\partial\mathcal{F}$.

Claim 1. For any $e_{1},e_{2}\in\mathcal{M}$, ${e_{1}\cup e_{2}\choose
3}\cap\mathcal{F}=\emptyset$.

Otherwise, suppose that ${e_{1}\cup e_{2}\choose
3}\cap\mathcal{F}\neq\emptyset$. Let $f\in{e_{1}\cup e_{2}\choose
3}\cap\mathcal{F}$ and $e_{3}\in\mathcal{M}\setminus\\{e_{1},e_{2}\\}$. Write
$M=\\{f,e_{3}\cup\\{1\\}\\}\cup\\{e\cup\\{1\\}\ |\ e\in\mathcal{M}-\\{e_{i}\
|\ i\in[3]\\}\\}$. One can see that $M\subseteq\mathcal{F}$ and $|V(M)|=2s+2$,
contradicting that $\mathcal{F}$ is $U(s,2s+1)$. This complete the proof of
Claim 1.

Claim 2. For any three distinct edges $e_{1},e_{2},e_{3}\in\mathcal{M}$,
$\mathcal{F}[\cup_{i\in[3]}e_{i}\cup\\{1\\}]$ contains no matchings of size
two.

Otherwise, there exists $e_{1},e_{2},e_{3}\in\mathcal{M}$ such that
$\mathcal{F}[(\cup_{i\in[3]}e_{i})\cup\\{1\\}]$ contains a matching of size
two, say $\\{f_{1},f_{2}\\}$. Write $M:=\\{f_{1},f_{2}\\}\cup\\{e\cup\\{1\\}\
|\ e\in\mathcal{M}-\\{e_{i}\ |\ i\in[3]\\}\\}$. One can see that
$M\subseteq\mathcal{F}$ and $|V(M)|\geq 2s+2$, contradicting that
$\mathcal{F}$ is $U(s,2s+1)$. This complete the proof of Claim 2.

By Lemma 3.4, Claims 1 and 2, we have

$\displaystyle|\mathcal{F}|-|\mathcal{F}_{3}|$ $\displaystyle\leq{2s+3\choose
3}-\left|{\mathcal{M}\choose 2}\right|{4\choose 3}-4\left|{\mathcal{M}\choose
3}\right|-{2s+1\choose 3}$ $\displaystyle={2s+2\choose 2}+{2s+1\choose
2}-4{s+1\choose 2}-4{s+1\choose 3}$
$\displaystyle=-\frac{2}{3}s^{3}+2s^{2}+\frac{8}{3}s$
$\displaystyle\leq-\frac{2}{3}s^{2}+\frac{8}{3}s\leq 0\quad\mbox{(when $s\geq
4$)},$

i.e., $|\mathcal{F}|\leq|\mathcal{F}_{3}|$. Next we consider $s=3$. Then
$\mathcal{M}=\\{\\{i+1,10-i\\}\ |\ i\in[4]\\}$. If
$\\{1,6,7\\}\in\mathcal{F}$, by Claim 2, $\\{2,4,5\\}\notin\mathcal{F}$. By
the stability of $\mathcal{F}$, we have $\\{2,i,j\\}\notin\mathcal{F}$,
$i,j\in\\{4,5,\ldots,9\\}$, thus

$\displaystyle|\mathcal{F}|$ $\displaystyle\leq{9\choose
3}-\left|{[9]-[2]\choose 3}\right|-\left|{[9]-[3]\choose
2}\right|=34<35=|\mathcal{F}_{3}|.$

So we may assume that $\\{1,6,7\\}\notin\mathcal{F}$. By Claim 1,
$\\{2,5,6\\},\\{2,4,7\\}\notin\mathcal{F}$, and so by stability, we have
$\\{2,5,7\\},\\{2,5,8\\},\\{2,4,8\\}\notin\mathcal{F}$. Hence

$\displaystyle|\mathcal{F}|$ $\displaystyle\leq{9\choose 3}-\left|{[5]\choose
1}\right|\left|{[9]-[5]\choose 2}\right|-2\left|{\mathcal{M}\choose
2}\right|-\left|{[9]-[5]\choose 3}\right|-3$
$\displaystyle=35=|\mathcal{F}_{3}|.$

Case 3. $r=1$.

By Lemma 2.1, $\partial\mathcal{F}$ is a subgraph of $A_{n,s+1}^{1}$. So we
have $\mathcal{F}\subseteq{[2s+2]\choose 3}$. By Lemma 2.2,
$\mathcal{M}:=\\{\\{i,2s+3-i\\}\ |\ 1\leq i\leq s+1\\}$ is a matching of size
$s+1$. If $s\geq 4$, by Claim 2 and Lemma 3.4, we have

$\displaystyle|\mathcal{F}|-|\mathcal{F}_{3}|$ $\displaystyle\leq{2s+2\choose
3}-4\left|{\mathcal{M}\choose 3}\right|-{2s+1\choose 3}$
$\displaystyle=-\frac{2}{3}s^{3}+2s^{2}+\frac{5}{3}s$
$\displaystyle\leq-\frac{1}{3}(2s^{2}-5s)\quad\mbox{(since $s\geq 4$)}$
$\displaystyle<0.$

So we may assume that $s=3$. Then $\mathcal{M}:=\\{\\{i,9-i\\}\ |\ 1\leq i\leq
4\\}$. If $\\{1,2,8\\}\notin\mathcal{F}$, then we have
$\mathcal{F}\subseteq{[2s+1]\choose 3}$ and so
$|\mathcal{F}|\leq|\mathcal{F}_{3}|$. Hence we may assume
$\\{1,2,8\\}\in\mathcal{F}$. By Claim 2 and the stability of $\mathcal{F}$, we
have $\\{4,5,7\\},\\{4,5,8\\},\\{3,6,7\\},\\{3,6,8\\}\notin\mathcal{F}$.
Moreover, one can see that $|\\{\\{1,7,8\\},\\{2,3,6\\}\\}\cap\mathcal{F}|=1$
by Claim 2. Let $e\in\\{\\{1,7,8\\},\\{2,3,6\\}\\}$ such that
$e\notin\mathcal{F}$. Write

$M=\\{e,\\{4,5,7\\},\\{4,5,8\\},\\{3,6,7\\},\\{3,6,8\\}\\}.$

Thus we have

$\displaystyle|\mathcal{F}|-|\mathcal{F}_{3}|$ $\displaystyle\leq{8\choose
3}-{7\choose 3}-4{|\mathcal{M}|\choose 3}-|M|=0,$

and so $|\mathcal{F}|\leq|\mathcal{F}_{3}|$.

Case 4. $r=2$.

By Lemma 2.1, $\partial\mathcal{F}$ is a subgraph $A_{n,s+1}^{2}$. By the
definition of $r$, we have $\partial\mathcal{F}-[3]$ has a matching size
$s-1$. By Lemma 2.2, $\mathcal{M}:=\\{\\{i,2s+5-i\\}\ |\ 4\leq i\leq s+2\\}$
is a matching of $\partial\mathcal{F}-[3]$. If
$\\{1,2,2s+2\\}\notin\mathcal{F}$, then
$\partial\mathcal{F}\subseteq{[2s+1]\choose 2}$ and $\nu(\mathcal{F})\leq s$,
a contradiction. So we may assume that $\\{1,2,2s+2\\}\in\mathcal{F}$.

Claim 3. $\mathcal{M}\cap N_{\mathcal{F}}(3)=\emptyset$. In particular,
$\\{3,s+2,s+3\\}\notin\mathcal{F}$.

Otherwise, suppose that $e\in\mathcal{M}\cap N_{\mathcal{F}}(3)$. Let
$M:=\\{\\{3\\}\cup e,\\{1,2,2s+2\\}\\}\cup\\{f\cup\\{1\\}\ |\
f\in\mathcal{M}\setminus e\\}$. Since $\mathcal{F}$ is stable,
$M\subseteq\mathcal{F}$. Moreover, $|M|=s$ and $|V(M)|=2s+2$, contradicting
that $\mathcal{F}$ is $U(s,2s+1)$.

Write $A=\\{3,\ldots,s+2\\}$ and $B=[2s+1]-[s+2]$. By Claim 3, we have
$\\{3,4,2s+1\\}\notin\mathcal{F}$. So for any $\\{a,b\\}\in{A\choose 2}$,
$\\{a,b,2s+1\\}\notin\mathcal{F}$. Then by Claim 3, we have

$\displaystyle|\mathcal{F}|$ $\displaystyle\leq{2s+1\choose
3}+(n-2s-2)-{|A|\choose 1}{|B|\choose 2}-{|A|\choose 2}$
$\displaystyle={2s+1\choose 3}+(n-2s-2)-(s+1){s\choose 2}$
$\displaystyle={2s+1\choose 3}+n-\frac{1}{2}(s+1)(s^{2}-s+4),$

i.e.,

$\displaystyle|\mathcal{F}|\leq{2s+1\choose 3}+n-\frac{1}{2}(s+1)(s^{2}-s+4).$
(6)

Consider $n\leq\frac{1}{2}(s+1)(s^{2}-s+4)$. Then we have
$|\mathcal{F}|\leq|\mathcal{F}_{3}|$. So we may assume that
$n>\frac{1}{2}(s+1)(s^{2}-s+4)\geq 4(s+1)$ as $s\geq 3$. Then by (6),

$\displaystyle|\mathcal{F}|-|\mathcal{F}_{2}|$ $\displaystyle\leq{2s+1\choose
3}+n-\frac{1}{2}(s+1)(s^{2}-s+4)-{s+1\choose 2}(n-s-1)-{s+1\choose 3}$
$\displaystyle\leq{2s+1\choose
3}+4(s+1)-\frac{1}{2}(s+1)(s^{2}-s+4)-3{s+1\choose 2}(s+1)-{s+1\choose
3}\quad\mbox{(since $n\geq 4(s+1)$)}$
$\displaystyle=\frac{1}{3}s(4s^{2}-1)-(s+1)(2s^{2}+s-2)-\frac{1}{6}s(s^{2}-1)$
$\displaystyle\leq\frac{1}{3}s(4s^{2}-1)-2s^{3}-\frac{1}{6}s(s^{2}-1)\quad\mbox{(since
$s\geq 3$)}$ $\displaystyle=-\frac{5}{6}s^{3}-\frac{1}{6}s<0,$

i.e., $|\mathcal{F}|\leq|\mathcal{F}_{2}|$. This completes the proof. $\Box$

## References

  * [1] M. Deza and P. Frankl, Erdős-Ko-Rado theorem–22 years later, _SIAM J. Algebraic Discrete Meth._ , 4 (1983), 419-431.
  * [2] P. Erdős, A problem on independent $r$-tuples, _Ann. Univ. Sci. Budapest_ , 8 (1965), 93–95.
  * [3] P. Erdős, C. Ko and R. Rado, Intersection theorems for systems of finite sets, _Quart. J. Math. Oxford Ser._ , 12 (1961), 313–320.
  * [4] P. Frankl, The Erdős-Ko-Rado theorem is true for $n=ckt$, in: _Combinatorics_ (Proc. Fifth Hungarian Colloq. Keszthely, 1976), I, in: _Colloq. Math. Soc. János Bolyai_ , vol. 18, North-Holland, 1976, pp. 365-375.
  * [5] P. Frankl, Families of finite sets satisfying a union condition, _Discrete Math._ , 26 (1979), 111–118.
  * [6] P. Frankl, The shifting technique in extremal set theory, _Surveys in combinatorics_ , 123 (1987), 81–110.
  * [7] P. Frankl and A. Kupavskii, Simple juntas for shifted families. _Discrete Anal._ , 2020, 14507.
  * [8] P. Frankl and A. Kupavskii, Beyond the Erdős Matching Conjecture, _European J. Combin._ , 95 (2021), 103338.
  * [9] P. Frankl and A. Kupavskii, The Erdős Matching Conjecture and Concentration Inequalities, _J. Combin. Theory Ser. B_ , to appear.
  * [10] R. M. Wilson, The exact bound in the Erdős-Ko-Rado theorem, _Combinatorica_ , 4(1984), 247–257.


* Takei et al. (2018) Takei Y, et al. (2018) Vibration isolation system for cryocoolers of soft x-ray spectrometer on-board ASTRO-H (Hitomi). Journal of Astronomical Telescopes, Instruments, and Systems 4:011216, DOI 10.1117/1.JATIS.4.1.011216
  * Taralli et al. (2020) Taralli E, et al. (2020) Characterization of High Aspect-Ratio TiAu TES X-ray Microcalorimeter Array Under AC Bias. Journal of Low Temperature Physics 199(1-2):80–87, DOI 10.1007/s10909-019-02254-y
  * Taralli et al. (2021) Taralli E, et al. (2021) Ti/Au TES 32 × 32 Pixel Array: Uniformity, Thermal Crosstalk and Performance at Different X-Ray Energies. IEEE Transactions on Applied Superconductivity 31(5):3061022, DOI 10.1109/TASC.2021.3061022
  * Tashiro et al. (2018) Tashiro M, et al. (2018) Concept of the X-ray Astronomy Recovery Mission. In: SPIE, Society of Photo-Optical Instrumentation Engineers (SPIE) Conference Series, vol 10699, p 1069922, DOI 10.1117/12.2309455
  * The Lynx Team (2018) The Lynx Team (2018) The Lynx Mission Concept Study Interim Report. arXiv e-prints arXiv:1809.09642
  * Uhlig et al. (2013) Uhlig J, et al. (2013) Table-top ultrafast x-ray microcalorimeter spectrometry for molecular structure. Phys Rev Lett 110:138302
  * Ullom and Bennett (2015) Ullom JN, Bennett DA (2015) Review of superconducting transition-edge sensors for x-ray and gamma-ray spectroscopy. Superconductor Science Technology 28(8):084003, DOI 10.1088/0953-2048/28/8/084003
  * Ullom et al. (2003) Ullom JN, et al. (2003) A frequency-domain read-out technique for large microcalorimeter arrays demonstrated using high-resolution $\gamma$-ray sensors. IEEE Transactions on Applied Superconductivity 13(2):643–648, DOI 10.1109/TASC.2003.813981
  * Vaccaro et al. (2021) Vaccaro D, et al. (2021) Frequency Shift Algorithm: Application to a Frequency-Domain Multiplexing Readout of X-ray Transition-Edge Sensor Microcalorimeters. arXiv e-prints arXiv:2102.06092
  * Vaccaro et al. (2022a) Vaccaro D, et al. (2022a) Frequency domain multiplexing readout for large arrays of transition-edge sensors. arXiv e-prints arXiv:2208.12604, 2208.12604
  * Vaccaro et al. (2022b) Vaccaro D, et al. (2022b) Susceptibility study of TES micro-calorimeters for X-ray spectroscopy under FDM readout. arXiv e-prints arXiv:2208.10875, 2208.10875
  * Vaccaro et al. (2022c) Vaccaro D, et al. (2022c) Thermal Crosstalk of X-Ray Transition-Edge Sensor Micro-Calorimeters Under Frequency Domain Multiplexing Readout. IEEE Transactions on Applied Superconductivity 32(1):3128710, DOI 10.1109/TASC.2021.3128710
  * van der Hulst et al. (2021) van der Hulst P, et al. (2021) Frequency shift algorithm: Design of a baseband phase locked loop for frequency-domain multiplexing readout of x-ray transition-edge sensor microcalorimeters. Review of Scientific Instruments 92(7):073101, DOI 10.1063/5.0044968
  * van der Kuur et al. (2004) van der Kuur J, et al. (2004) Implementation of frequency domain multiplexing in imaging arrays of microcalorimeters. Nuclear Instruments and Methods in Physics Research A 520(1-3):551–554, DOI 10.1016/j.nima.2003.11.312
  * van der Kuur et al. (2016) van der Kuur J, et al. (2016) Optimising the multiplex factor of the frequency domain multiplexed readout of the TES-based microcalorimeter imaging array for the X-IFU instrument on the Athena x-ray observatory. In: den Herder JWA, Takahashi T, Bautz M (eds) Space Telescopes and Instrumentation 2016: Ultraviolet to Gamma Ray, Society of Photo-Optical Instrumentation Engineers (SPIE) Conference Series, vol 9905, p 99055R, DOI 10.1117/12.2232830
  * van Weers (2013) van Weers HJ (2013) Niobium flex cable for low temperature high density interconnects. Cryogenics 55:1–4, DOI 10.1016/j.cryogenics.2012.10.006
  * Walsh (1923) Walsh JL (1923) A closed set of normal orthogonal functions. American Journal of Mathematics 45(1):5–24
  * Wang et al. (2020) Wang Q, et al. (2020) Noise Measurements of a Low-Noise Amplifier in the FDM Readout System for SAFARI. Journal of Low Temperature Physics 199(3-4):817–823, DOI 10.1007/s10909-019-02328-x
  * Wegner et al. (2022) Wegner M, Enss C, Kempf S (2022) Analytical model of the readout power and squid hysteresis parameter dependence of the resonator characteristics of microwave squid multiplexers. Superconductor Science and Technology 35(7):075011
  * Wegner et al. (2018) Wegner M, et al. (2018) Microwave SQUID Multiplexing of Metallic Magnetic Calorimeters: Status of Multiplexer Performance and Room-Temperature Readout Electronics Development. Journal of Low Temperature Physics 193(3-4):462–475, DOI 10.1007/s10909-018-1878-3
  * Welty and Martinis (1991) Welty RP, Martinis JM (1991) A series array of dc squids. IEEE Transactions on Magnetics 27(2):2924–2926
  * Yamada et al. (2021) Yamada S, et al. (2021) Broadband high-energy resolution hard x-ray spectroscopy using transition edge sensors at spring-8. Review of Scientific Instruments 92(1):013103
  * Yoon et al. (2001) Yoon J, et al. (2001) Single superconducting quantum interference device multiplexer for arrays of low-temperature sensors. Applied Physics Letters 78(3):371, DOI 10.1063/1.1338963
  * Yoon et al. (2018) Yoon W, et al. (2018) Toward Large Field-of-View High-Resolution X-ray Imaging Spectrometers: Microwave Multiplexed Readout of 28 TES Microcalorimeters. Journal of Low Temperature Physics 193(3-4):258–266, DOI 10.1007/s10909-018-1917-0
  * Yu et al. (2020) Yu C, et al. (2020) An impedance-modulated code-division microwave SQUID multiplexer. Engineering Research Express 2(1):015011, DOI 10.1088/2631-8695/ab68a4
  * Zappe (1977) Zappe H (1977) Josephson quantum interference computer devices. IEEE Transactions on Magnetics 13(1):41–47