Global ETD Search

Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.

Results

Showing 1 to 20 of 29 for “"Kneser"”.

  1. Dominating sets in Kneser graphs

    This thesis investigates dominating sets in Kneser graphs as well as a selection of other topics related to graph domination. Dominating sets in Kneser graphs, especially those of minimum size, often correspond to interesting combinatorial incidence structures. We begin with background on the …

    waterloo Repository record for Dominating sets in Kneser graphs (opens in a new tab)

  2. Sobre coloração total de grafos Kneser e de grafos produto direto de completos e de ciclos

    … number in three classes of graphs is studied: Kneser graphs, direct product of complete graphs and direct product of cycle graphs. In the class of Kneser graphs K(n, s), we show that the most sparse connected K(2k − 1, k − 1), known as Odd Graphs, are Type 1 and we prove that the dense Kneser …

    brazil-uerj Repository record for Sobre coloração total de grafos Kneser e de grafos produto direto de completos e de ciclos (opens in a new tab)

  3. Graph Homomorphisms and Vector Colorings

    … several important families of graphs, including Kneser graphs, Quantum Kneser graphs, and Hamming graphs, are shown to be uniquely vector colorable. Next, a relationship between locally injective vector colorings and cores is examined, providing a sufficient condition for a graph to be a core. As …

    south-carolina Repository record for Graph Homomorphisms and Vector Colorings (opens in a new tab)

  4. The Graphs of HU+00E4ggkvist & Hell

    … These graphs are an extension of the idea of Kneser graphs, and as such share many attributes with them. A variety of original results on many different properties of these graphs are given. We begin with an examination of the transitivity and structural properties of HU+00E4ggkvist & Hell …

    waterloo Repository record for The Graphs of HU+00E4ggkvist & Hell (opens in a new tab)

  5. Colouring Subspaces

    … space analogues. The vertices of the <em>q</em>-Kneser graph are the <em>k</em>-dimensional subspaces of a vector space of dimension <em>v</em> over F<sub><em>q</em></sub>, and two <em>k</em>-subspaces are adjacent if they have trivial intersection. The new results in this thesis involve …

    waterloo Repository record for Colouring Subspaces (opens in a new tab)

  6. Problems in extremal combinatorics

    … the chromatic number of the subgraphs of the Kneser graph $\textrm{KG}(n,k)$ induced by the family the $s$-stable sets in $\binom{[n]}{k}$. We prove a conjecture of Meunier that $\chi(\textrm{KG}(n,k)_{3\text{-stable}})=n-3(k-1)$ for large enough $n$. To this end, we also prove a …

    iastate Repository record for Problems in extremal combinatorics (opens in a new tab)

  7. Language models for automatic speech recognition : construction and complexity control

    … methods specialized on selecting the n-grams for Kneser-Ney smoothed n-gram models are presented, one for pruning and one for growing the model. The methods are compared with entropy-based pruning and Kneser pruning. Experiments on Finnish and English text corpora show that the proposed pruning …

    aalto Repository record for Language models for automatic speech recognition : construction and complexity control (opens in a new tab)

  8. Coloring of Metric Spaces and L(2,1)-Labeling of Graphs

    … graph. We also bound lambda(G) when G is the Kneser graph K(2k + 1, k).

    uiuc Repository record for Coloring of Metric Spaces and L(2,1)-Labeling of Graphs (opens in a new tab)

  9. Higher Order Random Walks, Local Spectral Expansion, and Applications

    … as a random walk on a sparse version of the Kneser graph. First, we give a sharp bound for the spectral gap of the down-up walks in terms of the local spectral expansion. Using this bound, we argue that the natural Markov chains for (i) sampling a random independent of fixed size s of a graph …

    waterloo Repository record for Higher Order Random Walks, Local Spectral Expansion, and Applications (opens in a new tab)

  10. Non-unique solutions of first order ordinary differential equations

    … of the first order by Kamke, Osgood, Montel, Kneser, Fukunara, Naguno and others. In general these writers have considered differential equations in which the slope is a continuous function of the variables. Many of the results which the above mentioned authors have obtained under the …

    texas Repository record for Non-unique solutions of first order ordinary differential equations (opens in a new tab)

  11. Attractors for nonlinear and non-autonomous parabolic PDES in unbounded domains

    … Cauchy, es interesante considerar la Propiedad Kneser para este problema, es decir, la compacidad y conexión del conjunto de valores alcanzados por las soluciones en cualquier instante de tiempo. En este sentido, asumiendo una condición adicional en las hipótesis del término no lineal f, en la …

    sevilla Repository record for Attractors for nonlinear and non-autonomous parabolic PDES in unbounded domains (opens in a new tab)

  12. Selecting pairs of non-transitive dice

    … and discuss some theoretical aspects by use of Kneser graphs.</p>

    iastate Repository record for Selecting pairs of non-transitive dice (opens in a new tab)

  13. Hamiltonian cycles in subset and subspace graphs.

    … Inequalities Related to the Hamiltonicity of the Kneser Graphs and their Q-Analogues," we defined subset graphs, subspace graphs, and their associated bipartite graphs. The main emphasis of this dissertation is to describe those graphs and study their Hamiltonicity. The results on subset graphs …

    unt Repository record for Hamiltonian cycles in subset and subspace graphs. (opens in a new tab)

  14. Ehrhart Theory and Unimodular Decompositions of Lattice Polytopes

    … and other polyhedra. More generally, Betke and Kneser proved that every lattice polytope in $\mathscr{P}(\mathbb{R}^d)$ (or the sub-algebra $\mathscr{P}(\mathbb{Z}^d)$, spanned by lattice polytopes) admits a unimodular decomposition; it can be expressed as a formal sum of unimodular simplices. …

    waterloo Repository record for Ehrhart Theory and Unimodular Decompositions of Lattice Polytopes (opens in a new tab)

  15. TOPOLOGICAL AND COMBINATORIAL PROPERTIES OF NEIGHBORHOOD AND CHESSBOARD COMPLEXES

    … that the neighborhood complex of the stable Kneser graph SGn,k is homotopy equivalent to a k-sphere. Further, for n = 2 they showed that the neighborhood complex deformation retracts to a subcomplex isomorphic to the associahedron. They went on to ask whether or not, for all n and k, the …

    uky-thes Repository record for TOPOLOGICAL AND COMBINATORIAL PROPERTIES OF NEIGHBORHOOD AND CHESSBOARD COMPLEXES (opens in a new tab)

  16. Extremal problems in graph theory

    … radius and find the domination number of the Kneser graph $K(n,k)$ when $n\ge{3\over4}k\sp2\pm k,$ depending on whether k is even or odd. The path chromatic number $\chi\sb{P}(G)$ of a graph G is the least number of colors with which the vertices of G can be colored so that each color class …

    uiuc Repository record for Extremal problems in graph theory (opens in a new tab)

  17. The Local Chromatic Number

    … was sparked by Lovász's original proof of the Kneser conjecture, using topological tools to give lower bounds on the chromatic number, and see how it is applicable to give lower bounds on the local chromatic number as well. The local chromatic number lies between the fractional chromatic number …

    waterloo Repository record for The Local Chromatic Number (opens in a new tab)

  18. Topics In Probabilistic Combinatorics

    … Stirling numbers. Chapter 5 introduces the Kneser Graph. The exact expected value and variance of the distance between [n] and a vertex chosen uniformly at random is given. An asymptotic formula for the expectation is found.

    siu-theses Repository record for Topics In Probabilistic Combinatorics (opens in a new tab)

Page 1 of 2