搜索结果: 106-120 共查到“知识库 组合数学”相关记录451条 . 查询时间(0.609 秒)
Maximum spectral radius of graphs with given connectivity and minimum degree
connectivity spectral radius Combinatorics
2011/9/21
Abstract: Shiu, Chan and Chang [On the spectral radius of graphs with connectivity at most $k$, J. Math. Chem., 46 (2009), 340-346] studied the spectral radius of graphs of order $n$ with $\kappa(G) \...
The size of a hypergraph and its matching number
hypergraph its matching number Combinatorics
2011/9/22
Abstract: More than forty years ago, Erd\H{o}s conjectured that for any T <= N/K, every K-uniform hypergraph on N vertices without T disjoint edges has at most max{\binom{KT-1}{K}, \binom{N}{K} - \bin...
The adjacency matroid of a graph
adjacency delta-matroid interlace polynomial local complement matroid minor Tutte polynomial
2011/9/22
Abstract: If $G$ is a looped graph, then its adjacency matrix represents a binary matroid $M_{A}(G)$ on $V(G)$. $M_{A}(G)$ may be obtained from the delta-matroid represented by the adjacency matrix of...
Invariant number triangles, eigentriangles and Somos-4 sequences
Invariant number triangles eigentriangles Somos-4 sequences Combinatorics
2011/9/22
Abstract: Using the language of Riordan arrays, we look at two related iterative processes on matrices and determine which matrices are invariant under these processes. In a special case, the invarian...
Abstract: Extending Furstenberg's ergodic theoretic proof for Szemer\'edi's theorem on arithmetic progressions, Furstenberg and Weiss (2003) proved the following qualitative result. For every d and k,...
Monochromatic cycles and the monochromatic circumference in 2-coloured graphs
Monochromatic cycles monochromatic circumference 2-coloured graphs
2011/9/21
Abstract: Li, Nikiforov and Schelp conjectured that a 2-edge coloured graph G with order n and minimal degree strictly greater than 3n/4 contains a monochromatic cycle of length l, for all l at least ...
Abstract: Let $S$ be a set of $n$ points in the unit square $[0,1]^2$, one of which is the origin. We construct $n$ pairwise interior-disjoint axis-aligned empty rectangles such that the lower left co...
The Mobius function of generalized subword order
Chebyshev polynomial discrete Morse theory homotopy type minimal skipped interval Mobius function
2011/9/20
Abstract: Let P be a poset and let P* be the set of all finite length words over P. Generalized subword order is the partial order on P* obtained by letting u \le w if and only if there is a subword u...
Factor frequencies in generalized Thue-Morse words
Factor frequencies generalized Thue-Morse words Combinatorics
2011/9/20
Abstract: We describe factor frequencies of the generalized Thue-Morse word t_{b,m} defined for integers b greater than 1, m greater than 0 as the fixed point starting in 0 of the morphism \phi_{b,m} ...
On a Greedy 2-Matching Algorithm and Hamilton Cycles in Random Graphs with Minimum Degree at Least Three
Greedy 2-Matching Algorithm Hamilton Cycles Random Graphs Minimum Degree
2011/9/20
Abstract: We describe and analyse a simple greedy algorithm \2G\ that finds a good 2-matching $M$ in the random graph $G=G_{n,cn}^{\d\geq 3}$ when $c\geq 15$. A 2-matching is a spanning subgraph of ma...
On a sparse random graph with minimum degree {three}: Likely Posa's sets are large
random sparse graphs degrees longest path Posa sets
2011/9/20
Abstract: We consider the likely size of the endpoint sets produced by Posa rotations, when applied to a longest path in a random graph with $cn,\,c\geq 2.7$ edges that is conditioned to have minimum ...
Counterexamples to a Monotonicity Conjecture for the Threshold Pebbling Number
combinatorics probability theory graph theory graph pebbling pebbling number pebbling threshold
2011/9/20
Abstract: Graph pebbling considers the problem of transforming configurations of discrete pebbles to certain target configurations on the vertices of a graph, using the so-called pebbling move. This p...
A Wowzer Type Lower Bound for the Strong Regularity Lemma
Wowzer Type Lower Bound Regularity Lemma
2011/9/20
Abstract: The regularity lemma of Szemeredi asserts that one can partition every graph into a bounded number of quasi-random bipartite graphs. In some applications however, one would like to have a st...
Ehrhart polynomials of integral simplices with prime volumes
Integral simplex Ehrhart polynomial δ-vector
2011/9/20
Abstract: For an integral convex polytope $\Pc \subset \RR^N$ of dimension $d$, we call $\delta(\Pc)=(\delta_0, \delta_1,..., \delta_d)$ its $\delta$-vector and $\vol(\Pc)=\sum_{i=0}^d\delta_i$ its no...
Normalized graph Laplacians for directed graphs
Normalized graph Laplacians directed graphs Combinatorics
2011/9/20
Abstract: We consider the normalized Laplacian for directed graphs with positive and negative edge weights. We derive basic spectral properties of the normalized Laplacian and identify extremal eigenv...