Dartmouth College Computer Science Technical Report series 
CS home TR home TR listserv 

By author:  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z  
By number:  2020, 2019, 2018, 2017, 2016, 2015, 2014, 2013, 2012, 2011, 2010, 2009, 2008, 2007, 2006, 2005, 2004, 2003, 2002, 2001, 2000, 1999, 1998, 1997, 1996, 1995, 1994, 1993, 1992, 1991, 1990, 1989, 1988, 1987, 1986 
Abstract:
This work is motivated by the open conjecture concerning the size of a minimum vertex cover in a partitioned hypergraph. In an runiform rpartite hypergraph, the size of the minimum vertex cover C is conjectured to be related to the size of its maximum matching M by the relation (C<= (r1)M). In fact it is not known whether this conjecture holds when M = 1. We consider rpartite hypergraphs with maximal matching size M = 1, and pose a novel algorithmic approach to finding a vertex cover of size (r  1) in this case. We define a reactive hypergraph to be a backandforth algorithm for a hypergraph which chooses new edges in response to a choice of vertex cover, and prove that this algorithm terminates for all hypergraphs of orders r = 3 and 4. We introduce the idea of optimizing the size of the reactive hypergraph and find that the reactive hypergraph terminates for r = 5...20. We then consider the case where the intersection of any two edges is exactly 1. We prove bounds on the size of this 1intersecting hypergraph and relate the 1intersecting hypergraph maximization problem to mutually orthogonal Latin squares. We propose a generative algorithm for 1intersecting hypergraphs of maximal size for prime powers r1 = pd under the constraint pd+1 is also a prime power of the same form, and therefore pose a new generating algorithm for MOLS based upon intersecting hypergraphs. We prove this algorithm generates a valid set of mutually orthogonal Latin squares and prove the construction guarantees certain symmetric properties. We conclude that a conjecture by Lovasz, that the inequality in Ryser's Conjecture cannot be improved when (r1) is a prime power, is correct for the 1intersecting hypergraph of prime power orders.
Note:
Senior Honors Thesis. Advisor: Deeparnab Chakrabarty.
Bibliographic citation for this report: [plain text] [BIB] [BibTeX] [Refer]
Or copy and paste:
Anna E. Dodson,
"Towards Ryser's Conjecture: Bounds on the Cardinality of Partitioned Intersecting Hypergraphs."
Dartmouth Computer Science Technical Report TR2020902,
June 2020.
Notify me about new tech reports.
To receive paper copy of a report, by mail, send your address and the TR number to reports AT cs.dartmouth.edu
Copyright notice: The documents contained in this server are included by the contributing authors as a means to ensure timely dissemination of scholarly and technical work on a noncommercial basis. Copyright and all rights therein are maintained by the authors or by other copyright holders, notwithstanding that they have offered their works here electronically. It is understood that all persons copying this information will adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.
Technical reports collection maintained by David Kotz.