TUHH Open Research (TORE)https://tore.tuhh.deTORE captures, stores, indexes, preserves, and distributes digital research material.Sat, 25 Mar 2023 10:50:01 GMT2023-03-25T10:50:01Z5051Maximum size of r-cross t-intersecting familieshttp://hdl.handle.net/11420/11551Title: Maximum size of r-cross t-intersecting families
Authors: Gupta, Pranshu; Mogge, Yannick; Piga, Simón; Schülke, Bjarne
Abstract: Given r families of subsets of a fixed n-set, we say that they are r-cross t-intersecting if for every choice of representatives, exactly one from each family, the common intersection of these representatives is of size at least t. We obtain a generalisation of a result by Hilton and Milner on cross intersecting families. In particular, we determine the maximum possible sum of the sizes of non-empty r-cross t-intersecting families in the case when all families are k-uniform and in the case when they are arbitrary subfamilies of the power set. Only some special cases of these results had been proved before. The method we use also yields more general results concerning measures of families instead of their sizes.
Sat, 01 May 2021 00:00:00 GMThttp://hdl.handle.net/11420/115512021-05-01T00:00:00ZFast strategies in waiter-client gameshttp://hdl.handle.net/11420/7720Title: Fast strategies in waiter-client games
Authors: Clemens, Dennis; Gupta, Pranshu; Hamann, Fabian; Haupt, Alexander; Mikalački, Mirjana; Mogge, Yannick
Abstract: Waiter-Client games are played on some hypergraph (X,��), where �� denotes the family of winning sets. For some bias b, during each round of such a game Waiter offers to Client b+1 elements of X, of which Client claims one for himself while the rest go to Waiter. Proceeding like this Waiter wins the game if she forces Client to claim all the elements of any winning set from ��. In this paper we study fast strategies for several Waiter-Client games played on the edge set of the complete graph, i.e. X=E(Kn), in which the winning sets are perfect matchings, Hamilton cycles, pancyclic graphs, fixed spanning trees or factors of a given graph.
Fri, 18 Sep 2020 00:00:00 GMThttp://hdl.handle.net/11420/77202020-09-18T00:00:00ZMinimal ramsey graphs with many vertices of small degreehttp://hdl.handle.net/11420/13496Title: Minimal ramsey graphs with many vertices of small degree
Authors: Boyadzhiyska, Simona; Clemens, Dennis; Gupta, Pranshu
Abstract: Given any graph H, a graph G is said to be q-Ramsey for H if every coloring of the edges of G with q colors yields a monochromatic subgraph isomorphic to H. Such a graph G is said to be minimal q-Ramsey for H if additionally no proper subgraph G′ of G is q-Ramsey for H. In 1976, Burr, Erdős, and Lovász initiated the study of the parameter sq(H), defined as the smallest minimum degree among all minimal q-Ramsey graphs for H. In this paper, we consider the problem of determining how many vertices of degree sq(H) a minimal q-Ramsey graph for H can contain. Specifically, we seek to identify graphs for which a minimal q-Ramsey graph can contain arbitrarily many such vertices. We call a graph satisfying this property sq-abundant. Among other results, we prove that every cycle is sq-abundant for any integer q ≥ 2. We also discuss the cases when H is a clique or a clique with a pendant edge, extending previous results of Burr and co-authors and Fox and co-authors. To prove our results and construct suitable minimal Ramsey graphs, we use gadget graphs, which we call pattern gadgets and which generalize earlier constructions used in the study of minimal Ramsey graphs. We provide a new, more constructive proof of the existence of these gadgets.
Sat, 01 Jan 2022 00:00:00 GMThttp://hdl.handle.net/11420/134962022-01-01T00:00:00ZOn extremal properties of minimal Ramsey graphs and cross intersecting familieshttp://hdl.handle.net/11420/14961Title: On extremal properties of minimal Ramsey graphs and cross intersecting families
Authors: Gupta, Pranshu
Abstract: Diese Arbeit ist in vier Teile gegliedert, von denen drei das Verhalten der Menge
der minimalen Ramsey-Graphen für einen bestimmten Graphen untersuchen. Im ersten
Teil untersuchen wir das Phänomen der Ramsey-simplicity für Zufallsgraphen Gn,p. Wir
zeigen die Existenz eines Schwellenwertes für die Anzahl der Farben, für die ein gegebener
Graph Ramsey-simple ist, und bestimmen verschiedene Schranken dafür. Im zweiten Teil
de nieren und analysieren wir die abundance von Graphen. Wir präsentieren viele un endliche Klassen von Graphen, die für eine bestimmte Anzahl von Farben abundant sind.
Der dritte Teil der Arbeit liefert einen Beweis für asymmetrische Paare von Graphen, die
Ramsey-äquivalent zueinander sind. Im letzten Teil dieser Arbeit bestimmen wir die max imale Summe der Gröÿen auf r-cross t-intersecting families in verschiedenen Situationen.; This thesis is divided into four parts, three out of which investigate the behaviour of
the set of minimal Ramsey graphs for a particular graph. In the rst part we investigate
the phenomena of Ramsey simplicity for random graphs, Gn,p. We show the existence of
a threshold value for the number of colours for which a given graph is Ramsey simple and
determine various bounds for it. In the second part we de ne and analyse the abundance
properties of graphs. We exhibit many in nite classes of graphs which are abundant for a
certain number of colours. The third part of the thesis provides an evidence of asymmetric
pairs of graphs which are Ramsey equivalent. In the last part of this thesis we determine
the maximum sum of the sizes of r-cross t-intersecting families in various settings.
Sun, 01 Jan 2023 00:00:00 GMThttp://hdl.handle.net/11420/149612023-01-01T00:00:00ZOn the minimum degree of minimal Ramsey graphs for cliques versus cycleshttp://hdl.handle.net/11420/15034Title: On the minimum degree of minimal Ramsey graphs for cliques versus cycles
Authors: Bishnoi, Anurag; Boyadzhiyska, Simona; Clemens, Dennis; Gupta, Pranshu; Lesgourgues, Thomas; Liebenau, Anita
Abstract: A graph G is said to be q-Ramsey for a q-tuple of graphs (H1,..., Hq), denoted by G →q (H1,..., Hq), if every q-edge-coloring of G contains a monochromatic copy of Hi in color i for some i ε [q]. Let sq(H1,..., Hq) denote the smallest minimum degree of G over all graphs G that are minimal q-Ramsey for (H1,..., Hq) (with respect to subgraph inclusion). The study of this parameter was initiated in 1976 by Burr, Erdos, and Lovasz, who determined its value precisely for a pair of cliques. Over the past two decades the parameter sq has been studied by several groups of authors, their main focus being on the symmetric case, where Hi ≅ H for all i ε [q]. The asymmetric case, in contrast, has received much less attention. In this paper, we make progress in this direction, studying asymmetric tuples consisting of cliques, cycles, and trees. We determine s2(H1, H2) when (H1, H2) is a pair of one clique and one tree, a pair of one clique and one cycle, and a pair of two different cycles. We also generalize our results to multiple colors and obtain bounds on sq(Cℓ,..., Cℓ, Kt,..., Kt) in terms of the size of the cliques t, the number of cycles, and the number of cliques. Our bounds are tight up to logarithmic factors when two of the three parameters are fixed.
Sun, 01 Jan 2023 00:00:00 GMThttp://hdl.handle.net/11420/150342023-01-01T00:00:00Z