Do you want to publish a course? Click here

Komloss tiling theorem via graphon covers

115   0   0.0 ( 0 )
 Added by Jan Hladky
 Publication date 2016
  fields
and research's language is English




Ask ChatGPT about the research

Komlos [Komlos: Tiling Turan Theorems, Combinatorica, 2000] determined the asymptotically optimal minimum-degree condition for covering a given proportion of vertices of a host graph by vertex-disjoint copies of a fixed graph H, thus essentially extending the Hajnal-Szemeredi theorem which deals with the case when H is a clique. We give a proof of a graphon version of Komloss theorem. To prove this graphon version, and also to deduce from it the original statement about finite graphs, we use the machinery introduced in [Hladky, Hu, Piguet: Tilings in graphons, arXiv:1606.03113]. We further prove a stability version of Komloss theorem.



rate research

Read More

A fundamental result of Kuhn and Osthus [The minimum degree threshold for perfect graph packings, Combinatorica, 2009] determines up to an additive constant the minimum degree threshold that forces a graph to contain a perfect H-tiling. We prove a degree sequence version of this result which allows for a significant number of vertices to have lower degree.
132 - Dennis Eichhorn , Hayan Nam , 2018
In two papers, Little and Sellers introduced an exciting new combinatorial method for proving partition identities which is not directly bijective. Instead, they consider various sets of weighted tilings of a $1 times infty$ board with squares and dominoes, and for each type of tiling they construct a generating function in two different ways, which generates a $q$-series identity. Using this method, they recover quite a few classical $q$-series identities, but Eulers Pentagonal Number Theorem is not among them. In this paper, we introduce a key parameter when constructing the generating functions of various sets of tilings which allows us to recover Eulers Pentagonal Number Theorem along with an infinite family of generalizations.
Komlos conjectured in 1981 that among all graphs with minimum degree at least $d$, the complete graph $K_{d+1}$ minimises the number of Hamiltonian subsets, where a subset of vertices is Hamiltonian if it contains a spanning cycle. We prove this conjecture when $d$ is sufficiently large. In fact we prove a stronger result: for large $d$, any graph $G$ with average degree at least $d$ contains almost twice as many Hamiltonian subsets as $K_{d+1}$, unless $G$ is isomorphic to $K_{d+1}$ or a certain other graph which we specify.
128 - M. Connolly 2016
In this paper a closed form expression for the number of tilings of an $ntimes n$ square border with $1times 1$ and $2times1$ cuisenaire rods is proved using a transition matrix approach. This problem is then generalised to $mtimes n$ rectangular borders. The number of distinct tilings up to rotational symmetry is considered, and closed form expressions are given, in the case of a square border and in the case of a rectangular border. Finally, the number of distinct tilings up to dihedral symmetry is considered, and a closed form expression is given in the case of a square border.
55 - J. A. Thas , K. Thas 2020
In this paper, which is a sequel to cite{part1}, we proceed with our study of covers and decomposition laws for geometries related to generalized quadrangles. In particular, we obtain a higher decomposition law for all Kantor-Knuth generalized quadrangles which generalizes one of the main results in cite{part1}. In a second part of the paper, we study the set of all Kantor-Knuth ovoids (with given parameter) in a fixed finite parabolic quadrangle, and relate this set to embeddings of parabolic quadrangles into Kantor-Knuth quadrangles. This point of view gives rise to an answer of a question posed in cite{JATSEP}.
comments
Fetching comments Fetching comments
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا