Статті в журналах: "Kruskal-Katona theorem"

1

Bukh, Boris. "Multidimensional Kruskal–Katona Theorem." SIAM Journal on Discrete Mathematics 26, no. 2 (January 2012): 548–54. http://dx.doi.org/10.1137/100808630.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

2

Clements, G. F. "Another generalization of the kruskal—katona theorem." Journal of Combinatorial Theory, Series A 68, no. 1 (October 1994): 239–45. http://dx.doi.org/10.1016/0097-3165(94)90104-x.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

3

Frohmader, Andrew. "A Kruskal–Katona type theorem for graphs." Journal of Combinatorial Theory, Series A 117, no. 1 (January 2010): 17–37. http://dx.doi.org/10.1016/j.jcta.2009.04.003.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

4

Clements, G. F. "Yet another generalization of the Kruskal-Katona theorem." Discrete Mathematics 184, no. 1-3 (April 1998): 61–70. http://dx.doi.org/10.1016/s0012-365x(97)00161-1.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

5

Ku, Cheng Yeaw, and Kok Bin Wong. "A Kruskal–Katona type theorem for integer partitions." Discrete Mathematics 313, no. 20 (October 2013): 2239–46. http://dx.doi.org/10.1016/j.disc.2013.06.001.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

6

London, Eran. "A new proof of the colored Kruskal—Katona theorem." Discrete Mathematics 126, no. 1-3 (March 1994): 217–23. http://dx.doi.org/10.1016/0012-365x(94)90266-6.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

7

Bezrukov, S., and A. Blokhuis. "A Kruskal–Katona Type Theorem for the Linear Lattice." European Journal of Combinatorics 20, no. 2 (February 1999): 123–30. http://dx.doi.org/10.1006/eujc.1998.0274.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

8

D'Andrea, Alessandro, and Luca De Sanctis. "The Kruskal-Katona Theorem and a Characterization of System Signatures." Journal of Applied Probability 52, no. 2 (June 2015): 508–18. http://dx.doi.org/10.1239/jap/1437658612.

Повний текст джерела

Анотація:

We show how to determine if a given vector can be the signature of a system on a finite number of components and, if so, exhibit such a system in terms of its structure function. The method employs combinatorial results from the theory of (finite) simplicial complexes, and provides a full characterization of signature vectors using a theorem of Kruskal (1963) and Katona (1968). We also show how the same approach can provide new combinatorial proofs of further results, e.g. that the signature vector of a system cannot have isolated zeroes. Finally, we prove that a signature with all nonzero entries must be a uniform distribution.

Стилі APA, Harvard, Vancouver, ISO та ін.

9

D'Andrea, Alessandro, and Luca De Sanctis. "The Kruskal-Katona Theorem and a Characterization of System Signatures." Journal of Applied Probability 52, no. 02 (June 2015): 508–18. http://dx.doi.org/10.1017/s000186780001260x.

Повний текст джерела

Анотація:

We show how to determine if a given vector can be the signature of a system on a finite number of components and, if so, exhibit such a system in terms of its structure function. The method employs combinatorial results from the theory of (finite) simplicial complexes, and provides a full characterization of signature vectors using a theorem of Kruskal (1963) and Katona (1968). We also show how the same approach can provide new combinatorial proofs of further results, e.g. that the signature vector of a system cannot have isolated zeroes. Finally, we prove that a signature with all nonzero entries must be a uniform distribution.

Стилі APA, Harvard, Vancouver, ISO та ін.

10

D'Andrea, Alessandro, and Luca De Sanctis. "The Kruskal-Katona Theorem and a Characterization of System Signatures." Journal of Applied Probability 52, no. 02 (June 2015): 508–18. http://dx.doi.org/10.1017/s0021900200012602.

Повний текст джерела

Анотація:

We show how to determine if a given vector can be the signature of a system on a finite number of components and, if so, exhibit such a system in terms of its structure function. The method employs combinatorial results from the theory of (finite) simplicial complexes, and provides a full characterization of signature vectors using a theorem of Kruskal (1963) and Katona (1968). We also show how the same approach can provide new combinatorial proofs of further results, e.g. that the signature vector of a system cannot have isolated zeroes. Finally, we prove that a signature with all nonzero entries must be a uniform distribution.

Стилі APA, Harvard, Vancouver, ISO та ін.

11

Leck, Uwe. "Nonexistence of a Kruskal-Katona Type Theorem for Subword Orders." Combinatorica 24, no. 2 (April 1, 2004): 305–12. http://dx.doi.org/10.1007/s00493-004-0018-7.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

12

Budd, Samuel, and Adam Van Tuyl. "Newton Complementary Duals of -Ideals." Canadian Mathematical Bulletin 62, no. 02 (October 15, 2018): 231–41. http://dx.doi.org/10.4153/s0008439518000024.

Повний текст джерела

Анотація:

AbstractA square-free monomial ideal $I$ of $k[x_{1},\ldots ,x_{n}]$ is said to be an $f$ -ideal if the facet complex and non-face complex associated with $I$ have the same $f$ -vector. We show that $I$ is an $f$ -ideal if and only if its Newton complementary dual $\widehat{I}$ is also an $f$ -ideal. Because of this duality, previous results about some classes of $f$ -ideals can be extended to a much larger class of $f$ -ideals. An interesting by-product of our work is an alternative formulation of the Kruskal–Katona theorem for $f$ -vectors of simplicial complexes.

Стилі APA, Harvard, Vancouver, ISO та ін.

13

Bashov, Maksim. "Nonexistence of a Kruskal–Katona type theorem for double-sided shadow minimization in the Boolean cube layer." Acta Universitatis Sapientiae, Informatica 5, no. 1 (July 1, 2013): 53–62. http://dx.doi.org/10.2478/ausi-2014-0004.

Повний текст джерела

Анотація:

Abstract A double-sided shadow minimization problem in the Boolean cube layer is investigated in this paper. The problem is to minimize the size of the union of the lower and upper shadows of a k-uniform family of subsets of [n]. It is shown that if 3 ⋜ k ⋜ n−3, there is no total order such that all its initial segments have minimal double-sided shadow.

Стилі APA, Harvard, Vancouver, ISO та ін.

14

BOLLOBÁS, BÉLA, and TOM ECCLES. "Partial Shadows of Set Systems." Combinatorics, Probability and Computing 24, no. 5 (January 20, 2015): 825–28. http://dx.doi.org/10.1017/s0963548314000790.

Повний текст джерела

Анотація:

The shadow of a system of sets is all sets which can be obtained by taking a set in the original system, and removing a single element. The Kruskal-Katona theorem tells us the minimum possible size of the shadow of $\mathcal A$, if $\mathcal A$ consists of m r-element sets.In this paper, we ask questions and make conjectures about the minimum possible size of a partial shadow for $\mathcal A$, which contains most sets in the shadow of $\mathcal A$. For example, if $\mathcal B$ is a family of sets containing all but one set in the shadow of each set of $\mathcal A$, how large must $\mathcal B$ be?

Стилі APA, Harvard, Vancouver, ISO та ін.

15

CUTLER, JONATHAN, and A. J. RADCLIFFE. "Hypergraph Independent Sets." Combinatorics, Probability and Computing 22, no. 1 (October 11, 2012): 9–20. http://dx.doi.org/10.1017/s0963548312000454.

Повний текст джерела

Анотація:

The study of extremal problems related to independent sets in hypergraphs is a problem that has generated much interest. There are a variety of types of independent sets in hypergraphs depending on the number of vertices from an independent set allowed in an edge. We say that a subset of vertices isj-independentif its intersection with any edge has size strictly less thanj. The Kruskal–Katona theorem implies that in anr-uniform hypergraph with a fixed size and order, the hypergraph with the mostr-independent sets is the lexicographic hypergraph. In this paper, we use a hypergraph regularity lemma, along with a technique developed by Loh, Pikhurko and Sudakov, to give an asymptotically best possible upper bound on the number ofj-independent sets in anr-uniform hypergraph.

Стилі APA, Harvard, Vancouver, ISO та ін.

16

Liu, Xizhi, and Sayan Mukherjee. "Stability theorems for some Kruskal–Katona type results." European Journal of Combinatorics 110 (May 2023): 103666. http://dx.doi.org/10.1016/j.ejc.2022.103666.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

17

Nevo, Eran, та T. Kyle Petersen. "On γ-Vectors Satisfying the Kruskal–Katona Inequalities". Discrete & Computational Geometry 45, № 3 (6 лютого 2010): 503–21. http://dx.doi.org/10.1007/s00454-010-9243-6.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

18

Herzog, Jürgen, Satoshi Murai, Xinxian Zheng, Takayuki Hibi, and Ngô Viêt Trung. "Kruskal-Katona type theorems for clique complexes arising from chordal and strongly chordal graphs." Combinatorica 28, no. 3 (May 2008): 315–23. http://dx.doi.org/10.1007/s00493-008-2319-8.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

19

Bezrukov, Sergei L., and Uwe Leck. "Macaulay Posets." Electronic Journal of Combinatorics 1000 (January 17, 2005). http://dx.doi.org/10.37236/33.

Повний текст джерела

Анотація:

Macaulay posets are posets for which there is an analogue of the classical Kruskal-Katona theorem for finite sets. These posets are of great importance in many branches of combinatorics and have numerous applications. We survey mostly new and also some old results on Macaulay posets, where the intention is to present them as pieces of a general theory. In particular, the classical examples of Macaulay posets are included as well as new ones. Emphasis is also put on the construction of Macaulay posets, and their relations to other discrete optimization problems.

Стилі APA, Harvard, Vancouver, ISO та ін.

20

Cutler, Jonathan, and A. J. Radcliffe. "Extremal Problems for Independent Set Enumeration." Electronic Journal of Combinatorics 18, no. 1 (August 26, 2011). http://dx.doi.org/10.37236/656.

Повний текст джерела

Анотація:

The study of the number of independent sets in a graph has a rich history. Recently, Kahn proved that disjoint unions of $K_{r,r}$'s have the maximum number of independent sets amongst $r$-regular bipartite graphs. Zhao extended this to all $r$-regular graphs. If we instead restrict the class of graphs to those on a fixed number of vertices and edges, then the Kruskal-Katona theorem implies that the graph with the maximum number of independent sets is the lex graph, where edges form an initial segment of the lexicographic ordering. In this paper, we study three related questions. Firstly, we prove that the lex graph has the maximum number of weighted independent sets for any appropriate weighting. Secondly, we solve the problem of maximizing the number of independents sets in graphs with specified independence number or clique number. Finally, for $m\leq n$, we find the graphs with the minimum number of independent sets for graphs with $n$ vertices and $m$ edges.

Стилі APA, Harvard, Vancouver, ISO та ін.

21

Cutler, Jonathan, and Nicholas Kass. "Homomorphisms into Loop-Threshold Graphs." Electronic Journal of Combinatorics 27, no. 2 (May 29, 2020). http://dx.doi.org/10.37236/6207.

Повний текст джерела

Анотація:

Many problems in extremal graph theory correspond to questions involving homomorphisms into a fixed image graph. Recently, there has been interest in maximizing the number of homomorphisms from graphs with a fixed number of vertices and edges into small image graphs. For the image graph $H_\text{ind}$, the graph on two adjacent vertices, one of which is looped, each homomorphism from $G$ to $H_\text{ind}$ corresponds to an independent set in $G$. It follows from the Kruskal-Katona theorem that the number of homomorphisms to $H_\text{ind}$ is maximized by the lex graph, whose edges form an initial segment of the lex order. A loop-threshold graph is a graph built recursively from a single vertex, which may be looped or unlooped, by successively adding either a looped dominating vertex or an unlooped isolated vertex at each stage. Thus, the graph $H_\text{ind}$ is a loop-threshold graph. We survey known results for maximizing the number of homomorphisms into small loop-threshold image graphs. The only extremal homomorphism problem with a loop-threshold image graph on at most three vertices not yet solved is $H_\text{ind}\cup E_1$, where extremal graphs are the union of a lex graph and an empty graph. The only question that remains is the size of the lex component of the extremal graph. While we cannot give an exact answer for every number of vertices and edges, we establish the significance of and give bounds on $\ell(m)$, the number of vertices in the lex component of the extremal graph with $m$ edges and at least $m+1$ vertices.

Стилі APA, Harvard, Vancouver, ISO та ін.

Статті в журналах з теми "Kruskal-Katona theorem"

Оформте джерело за APA, MLA, Chicago, Harvard та іншими стилями