We say that a function f:V→{0,1,...,diam(G)} is a broadcast if for every vertex v∈V, f(v)≤e(v), where diam(G) denotes the diameter of G and e(v) denotes the eccentricity of v. The cost of a broadcast is the value f(V)=∑v∈Vf(v). In this paper we introduce and study the minimum and maximum costs of several types of broadcasts in graphs, including dominating, independent and efficient broadcasts.

No description available.

The capacity of a directed hypergraph is a particular numerical quantity associated with a hypergraph. It is of interest because of certain important connections to longstanding conjectures in theoretical computer science related to fast matrix multiplication and perfect hashing as well as various longstanding conjectures in extremal combinatorics. We give an overview of the concept of the capacity of a hypergraph and survey a few basic results regarding this quantity. Furthermore, we discuss the Lovász number of an undirected graph, which is known to upper bound the capacity of the graph (and in practice appears to be the best such general purpose bound). We then elaborate on some attempted generalizations/modifications of the Lovász number to undirected hypergraphs that we have tried. It is not currently known whether these attempted generalizations/modifications upper bound the capacity of arbitrary hypergraphs. An important method for proving lower bounds on hypergraph capacity is to exhibit a large independent set in a strong power of the hypergraph. We examine methods for this and show a barrier to attempts to usefully generalize certain of these methods to hypergraphs. We then look at cap sets: independent sets in powers of a certain hypergraph. We examine certain structural properties of them with the hope of finding ones that allow us to prove upper bounds on their size. Finally, we consider two interesting generalizations of capacity and use one of them to formulate several conjectures about connections between cap sets and sunflower-free sets.

abstract: The primary focus of this dissertation lies in extremal combinatorics, in particular intersection theorems in finite set theory. A seminal result in the area is the theorem of Erdos, Ko and Rado which finds the upper bound on the size of an intersecting family of subsets of an n-element set and characterizes the structure of families which attain this upper bound. A major portion of this dissertation focuses on a recent generalization of the Erdos--Ko--Rado theorem which considers intersecting families of independent sets in graphs. An intersection theorem is proved for a large class of graphs, namely chordal graphs which satisfy an additional condition and similar problems are considered for trees, bipartite graphs and other special classes. A similar extension is also formulated for cross-intersecting families and results are proved for chordal graphs and cycles. A well-known generalization of the EKR theorem for k-wise intersecting families due to Frankl is also considered. A stability version of Frankl's theorem is proved, which provides additional structural information about k-wise intersecting families which have size close to the maximum upper bound. A graph-theoretic generalization of Frankl's theorem is also formulated and proved for perfect matching graphs. Finally, a long-standing conjecture of Chvatal regarding structure of maximum intersecting families in hereditary systems is considered. An intersection theorem is proved for hereditary families which have rank 3 using a powerful tool of Erdos and Rado which is called the Sunflower Lemma. / Dissertation/Thesis / Ph.D. Mathematics 2011

The problems we study in this thesis arise in computer science, extremal set theory and quantum computing. The first common feature of these problems is that each can be reduced to characterizing the independent sets of maximum size in a suitable graph. A second common feature is that the size of these independent sets meets an eigenvalue bound due to Delsarte and Hoffman. Thirdly, the graphs that arise belong to association schemes that have already been studied in other contexts. Our first problem involves covering arrays on graphs, which arises in computer science. The goal is to find a smallest covering array on a given graph <i>G</i>. It is known that this is equivalent to determining whether <i>G</i> has a homomorphism into a <i>covering array graph</i>, <i>CAG(n,g)</i>. Thus our question: Are covering array graphs cores? A covering array graph has as vertex set the partitions of <i>{1,. . . ,n}</i> into <i>g</i> cells each of size at least <i>g</i>, with two vertices being adjacent if their meet has size <i>g²</i>. We determine that <i>CAG(9,3)</i> is a core. We also determine some partial results on the family of graphs <i>CAG(g²,g)</i>. The key to our method is characterizing the independent sets that meet the Delsarte-Hoffman bound---we call these sets <i>ratio-tight</i>. It turns out that <i>CAG(9,3)</i> sits inside an association scheme, which will be useful but apparently not essential. We then turn our attention to our next problem: the Erdos-Ko-Rado theorem and its <i>q</i>-analogue. We are motivated by a desire to find a unifying proof that will cover both versions. The EKR theorem gives the maximum number of pairwise disjoint <i>k</i>-sets of a fixed <i>v</i>-set, and characterizes the extremal cases. Its <i>q</i>-analogue does the same for <i>k</i>-dimensional subspaces of a fixed <i>v</i>-dimensional space over <i>GF(q)</i>. We find that the methods we developed for covering array graphs apply to the EKR theorem. Moreover, unlike most other proofs of EKR, our argument applies equally well to the <i>q</i>-analogue. We provide a proof of the characterization of the extremal cases for the <i>q</i>-analogue when <i>v=2k</i>; no such proof has appeared before. Again, the graphs we consider sit inside of well-known association schemes; this time the schemes play a more central role. Finally, we deal with the problem in quantum computing. There are tasks that can be performed using quantum entanglement yet apparently are beyond the reach of methods using classical physics only. One particular task can be solved classically if and only if the graph &Omega;(<i>n</i>) has chromatic number <i>n</i>. The graph &Omega;(<i>n</i>) has as vertex set the set of all <i>?? 1</i> vectors of length <i>n</i>, with two vertices adjacent if they are orthogonal. We find that <i>n</i> is a trivial upper bound on the chromatic number, and that this bound holds with equality if and only if the Delsarte-Hoffman bound on independent sets does too. We are thus led to characterize the ratio-tight independent sets. We are then able to leverage our result using a recursive argument to show that <i>&chi;</i>(&Omega;(<i>n</i>)) > <i>n</i> for all <i>n</i> > 8. It is notable that the reduction to independent sets, the characterization of ratio-tight sets, and the recursive argument all follow from different proofs of the Delsarte-Hoffman bound. Furthermore, &Omega;(<i>n</i>) also sits inside a well-known association scheme, which again plays a central role in our approach.

The problems we study in this thesis arise in computer science, extremal set theory and quantum computing. The first common feature of these problems is that each can be reduced to characterizing the independent sets of maximum size in a suitable graph. A second common feature is that the size of these independent sets meets an eigenvalue bound due to Delsarte and Hoffman. Thirdly, the graphs that arise belong to association schemes that have already been studied in other contexts. Our first problem involves covering arrays on graphs, which arises in computer science. The goal is to find a smallest covering array on a given graph <i>G</i>. It is known that this is equivalent to determining whether <i>G</i> has a homomorphism into a <i>covering array graph</i>, <i>CAG(n,g)</i>. Thus our question: Are covering array graphs cores? A covering array graph has as vertex set the partitions of <i>{1,. . . ,n}</i> into <i>g</i> cells each of size at least <i>g</i>, with two vertices being adjacent if their meet has size <i>g²</i>. We determine that <i>CAG(9,3)</i> is a core. We also determine some partial results on the family of graphs <i>CAG(g²,g)</i>. The key to our method is characterizing the independent sets that meet the Delsarte-Hoffman bound---we call these sets <i>ratio-tight</i>. It turns out that <i>CAG(9,3)</i> sits inside an association scheme, which will be useful but apparently not essential. We then turn our attention to our next problem: the Erdos-Ko-Rado theorem and its <i>q</i>-analogue. We are motivated by a desire to find a unifying proof that will cover both versions. The EKR theorem gives the maximum number of pairwise disjoint <i>k</i>-sets of a fixed <i>v</i>-set, and characterizes the extremal cases. Its <i>q</i>-analogue does the same for <i>k</i>-dimensional subspaces of a fixed <i>v</i>-dimensional space over <i>GF(q)</i>. We find that the methods we developed for covering array graphs apply to the EKR theorem. Moreover, unlike most other proofs of EKR, our argument applies equally well to the <i>q</i>-analogue. We provide a proof of the characterization of the extremal cases for the <i>q</i>-analogue when <i>v=2k</i>; no such proof has appeared before. Again, the graphs we consider sit inside of well-known association schemes; this time the schemes play a more central role. Finally, we deal with the problem in quantum computing. There are tasks that can be performed using quantum entanglement yet apparently are beyond the reach of methods using classical physics only. One particular task can be solved classically if and only if the graph &Omega;(<i>n</i>) has chromatic number <i>n</i>. The graph &Omega;(<i>n</i>) has as vertex set the set of all <i>± 1</i> vectors of length <i>n</i>, with two vertices adjacent if they are orthogonal. We find that <i>n</i> is a trivial upper bound on the chromatic number, and that this bound holds with equality if and only if the Delsarte-Hoffman bound on independent sets does too. We are thus led to characterize the ratio-tight independent sets. We are then able to leverage our result using a recursive argument to show that <i>&chi;</i>(&Omega;(<i>n</i>)) > <i>n</i> for all <i>n</i> > 8. It is notable that the reduction to independent sets, the characterization of ratio-tight sets, and the recursive argument all follow from different proofs of the Delsarte-Hoffman bound. Furthermore, &Omega;(<i>n</i>) also sits inside a well-known association scheme, which again plays a central role in our approach.

The fields of statistical physics, discrete probability, combinatorics, and theoretical computer science have converged around efforts to understand random structures and algorithms. Recent activity in the interface of these fields has enabled tremendous breakthroughs in each domain and has supplied a new set of techniques for researchers approaching related problems. This thesis makes progress on several problems in this interface whose solutions all build on insights from multiple disciplinary perspectives. First, we consider a dynamic growth process arising in the context of DNA-based self-assembly. The assembly process can be modeled as a simple Markov chain. We prove that the chain is rapidly mixing for large enough bias in regions of Z^d. The proof uses a geometric distance function and a variant of path coupling in order to handle distances that can be exponentially large. We also provide the first results in the case of fluctuating bias, where the bias can vary depending on the location of the tile, which arises in the nanotechnology application. Moreover, we use intuition from statistical physics to construct a choice of the biases for which the Markov chain M_mon requires exponential time to converge. Second, we consider a related problem regarding the convergence rate of biased permutations that arises in the context of self-organizing lists. The Markov chain M_nn in this case is a nearest-neighbor chain that allows adjacent transpositions, and the rate of these exchanges is governed by various input parameters. It was conjectured that the chain is always rapidly mixing when the inversion probabilities are positively biased, i.e., we put nearest neighbor pair x<y in order with bias 1/2 <= p_{xy} <= 1 and out of order with bias 1-p_{xy}. The Markov chain M_mon was known to have connections to a simplified version of this biased card-shuffling. We provide new connections between M_nn and M_mon by using simple combinatorial bijections, and we prove that M_nn is always rapidly mixing for two general classes of positively biased {p_{xy}}. More significantly, we also prove that the general conjecture is false by exhibiting values for the p_{xy}, with 1/2 <= p_{xy} <= 1 for all x< y, but for which the transposition chain will require exponential time to converge. Finally, we consider a model of colloids, which are binary mixtures of molecules with one type of molecule suspended in another. It is believed that at low density typical configurations will be well-mixed throughout, while at high density they will separate into clusters. This clustering has proved elusive to verify, since all local sampling algorithms are known to be inefficient at high density, and in fact a new nonlocal algorithm was recently shown to require exponential time in some cases. We characterize the high and low density phases for a general family of discrete {it interfering binary mixtures} by showing that they exhibit a "clustering property' at high density and not at low density. The clustering property states that there will be a region that has very high area, very small perimeter, and high density of one type of molecule. Special cases of interfering binary mixtures include the Ising model at fixed magnetization and independent sets.

Submitted by Luciana Ferreira (lucgeral@gmail.com) on 2015-04-30T13:50:06Z No. of bitstreams: 2 Tese - Márcia Rodrigues Cappelle Santana - 2014.pdf: 631835 bytes, checksum: 92e31eb230a1e5640350250db336b352 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2015-04-30T13:54:17Z (GMT) No. of bitstreams: 2 Tese - Márcia Rodrigues Cappelle Santana - 2014.pdf: 631835 bytes, checksum: 92e31eb230a1e5640350250db336b352 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Made available in DSpace on 2015-04-30T13:54:17Z (GMT). No. of bitstreams: 2 Tese - Márcia Rodrigues Cappelle Santana - 2014.pdf: 631835 bytes, checksum: 92e31eb230a1e5640350250db336b352 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Previous issue date: 2014-10-01 / Fundação de Amparo à Pesquisa do Estado de Goiás - FAPEG / In this thesis, we present some results concerning about the sizes of maximal independent sets in graphs. We prove that for integers r and D with r 2 and D 3, there are only finitely many connected graphs of minimum degree at least 2, maximum degree at most D, and girth at least 7 that have maximal independent sets of at most r different sizes. Furthermore, we prove several results restricting the degrees of such graphs. These contributions generalize known results on well-covered graphs. We study the structure and recognition of the well-covered graphs G with order n(G) without an isolated vertex that have independence number n(G)􀀀k 2 for some non-negative integer k. For k = 1, we give a complete structural description of these graphs, and for a general but fixed k, we describe a polynomial time recognition algorithm. We consider graphs G without an isolated vertex for which the independence number a(G) and the independent domination number i(G) satisfy a(G) 􀀀 i(G) k for some non-negative integer k. We obtain a upper bound on the independence number in these graphs. We present a polynomial algorithm to recognize some complementary products, which includes all complementary prisms. Also, we present results on well-covered complementary prisms. We show that if G is not well-covered and its complementary prism is well-covered, then G has only two consecutive sizes of maximal independent sets. We present an upper bound for the quantity of sizes of maximal independent sets in complementary prisms and other wellcovered concerning results. We present a lower bound for the quantity of different sizes of maximal independent sets in Cartesian products of paths and cycles. / Nesta tese, apresentamos alguns resultados relacionados, principalmente, aos tamanhos de conjuntos independentes maximais em alguns grafos. Mostramos que para inteiros r e D, com r 2 e D 3, há um número finito de grafos conexos de grau mínimo pelo menos 2, grau máximo até D e cintura pelo menos 7 que têm tamanhos de conjuntos independentes maximais de até r tamanhos diferentes. Além disso, provamos outros resultados que restringem os graus de tais grafos e que generalizam resultados já conhecidos sobre grafos bem-cobertos. Foram estudados a estrutura e o reconhecimento dos grafos bem-cobertos G de ordem n(G) sem vértice isolado que têm número de independência n(G)􀀀k 2 , para algum inteiro não negativo k. Para k = 1, apresentamos uma descrição estrutural completa destes grafos e para um k geral, porém fixo, descrevemos um algoritmo de complexidade polinomial de tempo para o reconhecimento de tais grafos. Consideramos grafos G sem vértice isolado cuja diferença entre o maior e o menor conjuntos independentes maximais é no máximo k, para algum inteiro k não negativo. Obtivemos um limite superior sobre o número de independência destes grafos. Apresentamos um algoritmo de complexidade polinomial de tempo para reconhecimento de alguns produtos complementares, o qual inclui todos os prismas complementares. Apresentamos também alguns resultados sobre prismas complementares bem-cobertos. Mostramos que se G não é um grafo bem-coberto e seu prisma complementar é bem-coberto, então G tem somente dois tamanhos de conjuntos independentes maximais que são consecutivos. Apresentamos um limite superior para a quantidade de tamanhos de conjuntos independentes maximais em prismas complementares e também outros resultados relacionados à bem-cobertura. Apresentamos um limite inferior para a quantidade de conjuntos independentes maximais de tamanhos diferentes em produtos Cartesianos de caminhos e ciclos.