Relevant bibliographies by topics / Kruskal-Katona theorem / Journal articles

Journal articles on the topic 'Kruskal-Katona theorem'

To see the other types of publications on this topic, follow the link: Kruskal-Katona theorem.
Author: Grafiati
Published: 10 December 2022
Last updated: 29 January 2023

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the top 21 journal articles for your research on the topic 'Kruskal-Katona theorem.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Browse journal articles on a wide variety of disciplines and organise your bibliography correctly.

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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
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.

Full text
Abstract:
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, and other styles
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.

Full text
Abstract:
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, and other styles
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.

Full text
Abstract:
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, and other styles
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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
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.

Full text
Abstract:
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, and other styles
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.

Full text
Abstract:
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, and other styles
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.

Full text
Abstract:
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, and other styles
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.

Full text
Abstract:
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, and other styles
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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
17

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

Full text
APA, Harvard, Vancouver, ISO, and other styles
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.

Full text
APA, Harvard, Vancouver, ISO, and other styles
19

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

Full text
Abstract:
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, and other styles
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.

Full text
Abstract:
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, and other styles
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.

Full text
Abstract:
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, and other styles
We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!

To the bibliography