Search

One field of research that is gathering attention today is statistical machine learning that aims to apply analytical data to realworld problems. Conventional analysis has mainly used methods that manually set the scale and parameters of a statistical model or training model based on the data given and that involve costly tuning. These methods, however, incur massive amounts of time and labor, so using them to analyze data that will only continue to expand from here on is difficult. To solve this problem, there is a strong demand for a new technique that automatically adjusts model scale and parameters according to the quality and volume of data. In this article, we talked with NTT Distinguished Researcher Masahiro Nakano about his research on Bayesian nonparametric methods for solving problems faced by today's data society. [ABSTRACT FROM AUTHOR]

A matching of a graph is a set of its edges that pairwise do not have common vertices. An important parameter of graphs, which is used in mathematical chemistry, is the Hosoya index, defined as the number of their matchings. Previously, the problems of maximizing this index were considered and completely solved for -vertex trees with two, three and four leaves for any sufficiently large . In the present paper, a similar problem is completely solved for 5-leaved trees with and for 6-leaved trees with . [ABSTRACT FROM AUTHOR]

Bukh and Conlon used random polynomial graphs to give effective lower bounds on ex(n,Tℓ) $\text{ex}(n,{{\mathscr{T}}}^{\ell })$, where Tℓ ${{\mathscr{T}}}^{\ell }$ is the ℓ $\ell $th power of a balanced rooted tree T $T$. We extend their result to give effective lower bounds on ex(Gn,p,Tℓ) $\text{ex}({G}_{n,p},{{\mathscr{T}}}^{\ell })$, which is the maximum number of edges in a Tℓ ${{\mathscr{T}}}^{\ell }$‐free subgraph of the random graph Gn,p ${G}_{n,p}$. Analogous bounds for generalized Turán numbers in random graphs are also proven. [ABSTRACT FROM AUTHOR]

We call an edge-colored graph rainbow if all of its edges receive distinct colors. An edge-colored graph γ is called H-rainbow saturated if γ does not contain a rainbow copy of H and adding an edge of any color to γ creates a rainbow copy of H. The rainbow saturation number sat(n,R (H)) is the minimum number of edges in an n-vertex H-rainbow saturated graph. Gir\ao, Lewis, and Popielarz conjectured that sat(n,\scrR (Kr)) = 2(r 2)n + O(1) for fixed r \geq 3. Disproving this conjecture, we establish that for every r \geq 3, there exists a constant α r such that r+\Omega (r1/3) \leq \alpha r \leq r+r1/2 and sat(n,\scrR (Kr)) =αrn+O(1). Recently, Behague, Johnston, Letzter, Morrison, and Ogden independently gave a slightly weaker upper bound which was sufficient to disprove the conjecture. They also introduced the weak rainbow saturation number and asked whether this is equal to the rainbow saturation number of Kr, since the standard weak saturation number of complete graphs equals the standard saturation number. Surprisingly, our lower bound separates the rainbow saturation number from the weak rainbow saturation number, answering this question in the negative. The existence of the constant αr resolves another of their questions in the affirmative for complete graphs. Furthermore, we show that the conjecture of Gir\ao, Lewis, and Popielarz is true if we have an additional assumption that the edge-colored Kr-rainbow saturated graph must be rainbow. As an ingredient of the proof, we study graphs which are Kr-saturated with respect to the operation of deleting one edge and adding two edges. [ABSTRACT FROM AUTHOR]

A family of subsets of [ n ] is intersecting if every pair of its sets intersects. Determining the structure of large intersecting families is a central problem in extremal combinatorics. Frankl–Kupavskii and Balogh–Das–Liu–Sharifzadeh–Tran showed that for n ≥ 2 k + c k ln ⁡ k , almost all k -uniform intersecting families are stars. Improving their result, we show that the same conclusion holds for n ≥ 2 k + 100 ln ⁡ k. Our proof uses, among others, the graph container method and the Das–Tran removal lemma. [ABSTRACT FROM AUTHOR]

Let A and B be two families of sets. A is t -intersecting if | A 1 ∩ A 2 | ≥ t for all A 1 , A 2 ∈ A. A and B are cross-intersecting if A ∩ B ≠ 0̸ for all A ∈ A and B ∈ B. Let n , k , t ≥ 1 be non-negative integers with n ≥ 2 k + t − 1. Let A ⊆ [ n ] k + t − 1 and B ⊆ [ n ] k . Frankl proved that if A is t -intersecting and | A | ≥ 1 , then | A | + | B | ≤ n k − n − k − t + 1 k + 1. In this paper, we sharpen Frankl's inequality when | A | ≥ 2 , that is, if A is t -intersecting and | A | ≥ 2 , then | A | + | B | ≤ n k − n − k − t + 1 k − n − k − t k − 1 + 2 for k ≥ 3. Furthermore, we also characterize all extremal families achieving the extremal bounds. [ABSTRACT FROM AUTHOR]

Every generic linear functional (Formula presented.) on a convex polytope (Formula presented.) induces an orientation on the graph of (Formula presented.). From the resulting directed graph one can define a notion of (Formula presented.) -arborescence and (Formula presented.) -monotone path on (Formula presented.), as well as a natural graph structure on the vertex set of (Formula presented.) -monotone paths. These concepts are important in geometric combinatorics and optimization. This paper bounds the number of (Formula presented.) -arborescences, the number of (Formula presented.) -monotone paths, and the diameter of the graph of (Formula presented.) -monotone paths for polytopes (Formula presented.) in terms of their dimension and number of vertices or facets.

For r ≥ 1, the r-neighbor bootstrap process in a graph G starts with a set of infected vertices and, in each time step, every vertex with at least r infected neighbors becomes infected. The initial infection percolates if every vertex of G is eventually infected. We exactly determine the minimum cardinality of a set that percolates for the 3-neighbor bootstrap process when G is a three-dimensional grid with minimum side-length at least 11. We also characterize the integers a and b for which there is a set of cardinality ab+a+b/3 that percolates for the 3-neighbor bootstrap process in the a × b grid; this solves a problem raised by Benevides et al. [HAL Research Report 03161419v4, 2021]. [ABSTRACT FROM AUTHOR]

In this paper we initiate a systematic study of the Turán problem for edge-ordered graphs. A simple graph is called edge-ordered if its edges are linearly ordered. This notion allows us to study graphs (and in particular their maximum number of edges) when a subgraph is forbidden with a specific edge-order but the same underlying graph may appear with a different edge-order. We prove an Erdős-Stone-Simonovits-type theorem for edge-ordered graphs—we identify the relevant parameter for the Turán number of an edge-ordered graph and call it the order chromatic number. We establish several important properties of this parameter. We also study Turán numbers of edge-ordered paths, star forests and the cycle of length four. We make strong connections to Davenport-Schinzel theory, the theory of forbidden submatrices, and show an application in discrete geometry. [ABSTRACT FROM AUTHOR]

An animal is a planar shape formed by attaching congruent regular polygons along their edges. Usually, these polygons are a finite subset of tiles of a regular planar tessellation. These tessellations can be parameterized using the Schläfli symbol { p , q } , where p denotes the number of sides of the regular polygon forming the tessellation and q is the number of edges or tiles meeting at each vertex. If (p - 2) (q - 2) > 4 , = 4 , or < 4 , then the tessellation corresponds to the geometry of the hyperbolic plane, the Euclidean plane, or the sphere, respectively. In 1976, Harary and Harborth studied animals defined on regular tessellations of the Euclidean plane, finding extremal values for their vertices, edges, and tiles, when any one of these parameters is fixed. They named animals attaining these extremal values as extremal animals. Here, we study hyperbolic extremal animals. For each { p , q } corresponding to a hyperbolic tessellation, we exhibit a sequence of spiral animals and prove that they attain the minimum numbers of edges and vertices within the class of animals with n tiles. We also give the first results on enumeration of extremal hyperbolic animals by finding special sequences of extremal animals that are unique extremal animals, in the sense that any animal with the same number of tiles which is distinct up to isometries cannot be extremal. [ABSTRACT FROM AUTHOR]

The minimum total dominating set (MTDS) of a graph is a vertex subset of minimum cardinality such that every vertex of the graph is adjacent to at least one vertex of . In this paper we obtain a sharp upper bound for the number of MTDSs in the class of -vertex 2-caterpillars. We also show that for all every -vertex tree has less than MTDSs. [ABSTRACT FROM AUTHOR]

Robust sunflowers are a generalization of combinatorial sunflowers that have applications in monotone circuit complexity Rossman (SIAM J. Comput. 43:256–279, 2014), DNF sparsification Gopalan et al. (Comput. Complex. 22:275–310 2013), randomness extractors Li et al. (In: APPROX-RANDOM, LIPIcs 116:51:1–13, 2018), and recent advances on the Erdős-Rado sunflower conjecture Alweiss et al. (In: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC. Association for Computing Machinery, New York, NY, USA, 2020) Lovett et al. (From dnf compression to sunflower theorems via regularity, 2019) Rao (Discrete Anal. 8,2020). The recent breakthrough of Alweiss, Lovett, Wu and Zhang Alweiss et al. (In: Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC. Association for Computing Machinery, New York, NY, USA, 2020) gives an improved bound on the maximum size of a w-set system that excludes a robust sunflower. In this paper, we use this result to obtain an exp (n 1 / 2 - o (1)) lower bound on the monotone circuit size of an explicit n-variate monotone function, improving the previous best known exp (n 1 / 3 - o (1)) due to Andreev (Algebra and Logic, 26:1–18, 1987) and Harnik and Raz (In: Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, ACM, New York, 2000). We also show an exp (Ω (n)) lower bound on the monotone arithmetic circuit size of a related polynomial via a very simple proof. Finally, we introduce a notion of robust clique-sunflowers and use this to prove an n Ω (k) lower bound on the monotone circuit size of the CLIQUE function for all k ⩽ n 1 / 3 - o (1) , strengthening the bound of Alon and Boppana (Combinatorica, 7:1–22, 1987). [ABSTRACT FROM AUTHOR]

In this article, constant dimension subspace codes whose codewords have subspace distance in a prescribed set of integers, are considered. The easiest example of such an object is a junta (Combin Probab Comput 18(1–2):107–122, 2009); i.e. a subspace code in which all codewords go through a common subspace. We focus on the case when only two intersection values for the codewords, are assigned. In such a case we determine an upper bound for the dimension of the vector space spanned by the elements of a non-junta code. In addition, if the two intersection values are consecutive, we prove that such a bound is tight, and classify the examples attaining the largest possible dimension as one of four infinite families. [ABSTRACT FROM AUTHOR]

For fixed integers $n$ and $b\geq k$ , let $A(b,k,n)$ the largest size of a subset of $\{1,2,\ldots,b\}^{n}$ such that, for any $k$ distinct elements in the set, there is a coordinate where they all differ. Bounding $A(b,k,n)$ is a problem of relevant interest in information theory and computer science, relating to the zero-error capacity with list decoding and to the study of $(b, k)$ -hash families of functions. It is known that, for fixed $b$ and $k$ , $A(b,k,n)$ grows exponentially in $n$. In this paper, we determine new exponential upper bounds for different values of $b$ and $k$. A first bound on $A(b,k,n)$ for general $b$ and $k$ was derived by Fredman and Komlós in the ’80s and improved for certain $b\neq k$ by Körner and Marton and by Arikan. Only very recently better bounds were derived for general $b$ and $k$ by Guruswami and Riazanov, while stronger results for small values of $b=k$ were obtained by Arikan, by Dalai, Guruswami and Radhakrishnan, and by Costa and Dalai. In this paper, we strengthen the bounds for some specific values of $b$ and $k$. Our contribution is a new computational method for obtaining upper bounds on the values of a quadratic form defined over discrete probability distributions in arbitrary dimensions, which emerged as a central ingredient in recent works. The proposed method reduces an infinite-dimensional problem to a finite one, which we manage to further simplify by means of a series of optimality conditions. [ABSTRACT FROM AUTHOR]

Given a planar straight-line graph G = (V , E) in R 2 , a circumscribing polygon of G is a simple polygon P whose vertex set is V, and every edge in E is either an edge or an internal diagonal of P. A circumscribing polygon is a polygonization for G if every edge in E is an edge of P. We prove that every arrangement of n disjoint line segments in the plane has a subset of size Ω (n) that admits a circumscribing polygon, which is the first improvement on this bound in 20 years. We explore relations between circumscribing polygons and other problems in combinatorial geometry, and generalizations to R 3 . We show that it is NP-complete to decide whether a given graph G admits a circumscribing polygon, even if G is 2-regular. Settling a 30-year old conjecture by Rappaport, we also show that it is NP-complete to determine whether a geometric matching admits a polygonization. [ABSTRACT FROM AUTHOR]

For any n and l , we completely describe trees with the maximum and minimum numbers of maximal independent sets among all n -vertex trees with l leaves. [ABSTRACT FROM AUTHOR]

We describe a general and safe computational framework that provides integer programming results with the degree of certainty that is required for machine-assisted proofs of mathematical theorems. At its core, the framework relies on a rational branch-and-bound certificate produced by an exact integer programming solver, SCIP, in order to circumvent floating-point round-off errors present in most state-of-the-art solvers for mixed-integer programs. The resulting certificates are self-contained and checker software exists that can verify their correctness independently of the integer programming solver used to produce the certificate. This acts as a safeguard against programming errors that may be present in complex solver software. The viability of this approach is tested by applying it to finite cases of Chvátal's conjecture, a long-standing open question in extremal combinatorics. We take particular care to verify also the correctness of the input for this specific problem, using the Coq formal proof assistant. As a result, we are able to provide the first machine-assisted proof that Chvátal's conjecture holds for all downsets whose union of sets contains seven elements or less. [ABSTRACT FROM AUTHOR]

Given a finite relational language L , a hereditary L -property is a class H of finite L -structures closed under isomorphism and substructure. The speed of H is the function which sends an integer n ≥ 1 to the number of distinct elements in H with underlying set { 1 ,... , n }. In this paper we give a description of many new jumps in the possible speeds of a hereditary L -property, where L is any finite relational language. In particular, we characterize the jumps in the polynomial and factorial ranges, and show they are essentially the same as in the case of graphs. The results in the factorial range are new for all examples requiring a language of arity greater than two, including the setting of hereditary properties of k -uniform hypergraphs for k > 2. Further, adapting an example of Balogh, Bollobás, and Weinreich, we show that for all k ≥ 2 , there are hereditary properties of k -uniform hypergraphs whose speeds oscillate between functions near the upper and lower bounds of the penultimate range, ruling out many natural functions as jumps in that range. Our theorems about the factorial range use model theoretic tools related to the notion of mutual algebraicity. [ABSTRACT FROM AUTHOR]

The present paper offers, in its first part, a unified approach for the derivation of families of inequalities for set functions which satisfy sub/supermodularity properties. It applies this approach for the derivation of information inequalities with Shannon information measures. Connections of the considered approach to a generalized version of Shearer's lemma, and other related results in the literature are considered. Some of the derived information inequalities are new, and also known results (such as a generalized version of Han's inequality) are reproduced in a simple and unified way. In its second part, this paper applies the generalized Han's inequality to analyze a problem in extremal graph theory. This problem is motivated and analyzed from the perspective of information theory, and the analysis leads to generalized and refined bounds. The two parts of this paper are meant to be independently accessible to the reader. [ABSTRACT FROM AUTHOR]

The Hosoya index is an important topological index of graphs defined as the number of their matchings. At present, for any and , all connected graphs with vertices and edges that have a maximum value of the Hosoya index among all such graphs have been described (in the case for ). This paper proposes a new proof for the case for based on a decomposition of the Hosoya index by subsets of separating vertices and local graph transformations induced by them. This approach is new in the search for graphs with extreme value of the Hosoya index, where many standard techniques are usually employed. The new proof is more combinatorial, shorter, and less technical than the original proof. [ABSTRACT FROM AUTHOR]

For a graph G, let f(G) denote the size of the maximum cut in G. The problem of estimating f(G) as a function of the number of vertices and edges of G has a long history and was extensively studied in the last Fifty years. In this paper we propose an approach, based on semidefinite programming, to prove lower bounds on f(G). We use this approach to find large cuts in graphs with few triangles and in Kr-free graphs. [ABSTRACT FROM AUTHOR]

Two families A and B are called cross t -intersecting if | A ∩ B | ≥ t for all A ∈ A , B ∈ B. Let n , k , t be positive integers and A , B ⊆ ( n k ). Pyber proved that if A and B are cross 1-intersecting, then | A | | B | ≤ ( n − 1 k − 1 ) 2 for all n ≥ 2 k , and equality holds if and only if A = B = { A ∈ ( [ n ] k ) : x ∈ A } for some x ∈ [ n ] whenever n > 2 k. Frankl and Kupavskii sharpened Pyber's inequality to | A | | B | ≤ (( n − 1 k − 1 ) + ( n − i k − i + 1 )) (( n − 1 k − 1 ) − ( n − i k − 1 )) under the assumption that | B | ≥ ( n − 1 k − 1 ) + ( n − i k − i + 1 ). In this paper, firstly, we show that the families that attain this bound are unique for n ≥ 2 k + 1. Secondly, combining the result of Frankl and Kupavskii, we show that if A ⊆ ( [ n ] k ) and B ⊆ ( [ n ] k ) are cross 1-intersecting with ∩ B ∈ B B = ∅ , then | A | | B | ≤ (( n − 1 k − 1 ) − ( n − k − 1 k − 1 )) (( n − 1 k − 1 ) + 1). Lastly, we generalize the above result to cross t -intersecting families for all large n. [ABSTRACT FROM AUTHOR]

The present paper offers, in its first part, a unified approach for the derivation of families of inequalities for set functions which satisfy sub/supermodularity properties. It applies this approach for the derivation of information inequalities with Shannon information measures. Connections of the considered approach to a generalized version of Shearer’s lemma, and other related results in the literature are considered. Some of the derived information inequalities are new, and also known results (such as a generalized version of Han’s inequality) are reproduced in a simple and unified way. In its second part, this paper applies the generalized Han’s inequality to analyze a problem in extremal graph theory. This problem is motivated and analyzed from the perspective of information theory, and the analysis leads to generalized and refined bounds. The two parts of this paper are meant to be independently accessible to the reader.

We introduce a fractal dimension for a metric space defined in terms of the persistent homology of extremal subsets of that space. We exhibit hypotheses under which this dimension is comparable to the upper box dimension; in particular, the dimensions coincide for subsets of R 2 whose upper box dimension exceeds 1.5. These results are related to extremal questions about the number of persistent homology intervals of a set of n points in a metric space. [ABSTRACT FROM AUTHOR]

Recently, Croot, Lev and Pach (Ann Math 185:331–337, 2017) and Ellenberg and Gijswijt (Ann Math 185:339–443, 2017) developed a new polynomial method and used it to prove upper bounds for three-term arithmetic progression free sets in Z 4 n and F 3 n , respectively. Their approach was later summarized by Tao and is now known as the slice rank method. In this paper, we apply this method to obtain a new upper bound on the cardinality of subsets of F q n which contain no right angles. More precisely, let q be a fixed odd prime power and x · y be the standard inner product of two vectors x , y ∈ F q n , and we prove that the maximum cardinality of a subset A ⊆ F q n without three distinct elements x , y , z ∈ A satisfying (z - x) · (y - x) = 0 is at most n + q q - 1 + 3 . For sufficiently large n, our result significantly improves the previous upper bound of Bennett (Eur J Combin 70:155–163, 2018), who showed that | A | = O (q n + 2 3) . [ABSTRACT FROM AUTHOR]

Graph burning is a discrete-time process on graphs, where vertices are sequentially burned, and burned vertices cause their neighbours to burn over time. We consider extremal properties of this process in the new setting where the underlying graph is also changing at each time-step. The main focus is on the possible densities of burning vertices when the sequence of underlying graphs are growing grids in the Cartesian plane, centred at the origin. If the grids are of height and width 2 c n + 1 at time n, then all values in 1 2 c 2 , 1 are possible densities for the burned set. For faster growing grids, we show that there is a threshold behaviour: if the size of the grids at time n is ω (n 3 / 2) , then the density of burned vertices is always 0, while if the grid sizes are Θ (n 3 / 2) , then positive densities are possible. Some extensions to lattices of arbitrary but fixed dimension are also considered. [ABSTRACT FROM AUTHOR]

We consider the Turán-type problem of bounding the size of a set M ⊆ F 2 n that does not contain a linear copy of a given fixed set N ⊆ F 2 k , where n is large compared to k. An Erdős-Stone type theorem [5] in this setting gives a bound that is tight up to a o (2 n) error term; our first main result gives a stability version of this theorem, showing that such an M that is close in size to the upper bound in [5] is close to the obvious extremal example in the sense of symmetric difference. Our second result shows that the error term in [5] is exactly controlled by the solution to one of a class of 'sparse' extremal problems, and gives some examples where the error term can be eliminated completely to give a sharp upper bound on | M |. [ABSTRACT FROM AUTHOR]

Let n be a positive integer, q a power of a prime, and ℒ n (q) the poset of subspaces of an n-dimensional vector space over a field with q elements. This poset is a normalized matching poset and the set of subspaces of dimension ⌊n/2⌋ or those of dimension ⌈n/2⌉ are the only maximum-sized antichains in this poset. Strengthening this well-known and celebrated result, we show that, except in the case of ℒ 3 (2) , these same collections of subspaces are the only maximum-sized families in ℒ n (q) that avoid both a ∧ and a ∨ as a subposet. We generalize some of the results to brooms and forks, and we also show that the union of the set of subspaces of dimension k and k + 1, for k = ⌊n/2⌋ or k = ⌈n/2⌉ − 1, are the only maximum-sized families in ℒ n (q) that avoid a butterfly (definitions below). [ABSTRACT FROM AUTHOR]

The presents information on author's dissertation about various problems in extreme combinatorics, and discusses two results related to graph theory in extremal combinatorics which is lively area of mathematics. Topics include links to fields like theory of probability, the discrete Geometry and analytic number theory, as well as too to theoretical computer science; and doctoral thesis examines various problems in extremal combinatorics and in particular form of probability theory and algebra.

For a positive integer d, a set of points in d-dimensional Euclidean space is called almost-equidistant if for any three points from the set, some two are at unit distance. Let f(d) denote the largest size of an almost-equidistant set in d-space. It is known that f (2) = 7 , f (3) = 10 , and that the extremal almost-equidistant sets are unique. We give independent, computer-assisted proofs of these statements. It is also known that f (5) ≥ 16 . We further show that 12 ≤ f (4) ≤ 13 , f (5) ≤ 20 , 18 ≤ f (6) ≤ 26 , 20 ≤ f (7) ≤ 34 , and f (9) ≥ f (8) ≥ 24 . Up to dimension 7, our work is based on various computer searches, and in dimensions 6–9, we give constructions based on the known construction for d = 5 . For every dimension d ≥ 3 , we give an example of an almost-equidistant set of 2 d + 4 points in the d-space and we prove the asymptotic upper bound f (d) ≤ O (d 3 / 2) . [ABSTRACT FROM AUTHOR]

We find previously unknown families of sets which ensure Frankl's conjecture holds for all families that contain them using an algorithmic framework. The conjecture states that for any nonempty finite union-closed (UC) family there exists an element of the ground set in at least half the sets of the considered UC family. Poonen's Theorem characterizes the existence of weights which determine whether a given UC family implies the conjecture for all UC families which contain it. We design a cutting-plane method that computes the explicit weights which satisfy the existence conditions of Poonen's Theorem. This method enables us to answer several open questions regarding structural properties of UC families, including the construction of a counterexample to a conjecture of Morris from 2006. [ABSTRACT FROM AUTHOR]

For any n, in the set of n-vertex trees such that any two leaves have no common adjacent vertex, we describe the trees with the smallest number of maximal independent sets. [ABSTRACT FROM AUTHOR]

A famous conjecture of Ryser states that every r-partite hypergraph has vertex cover number at most r 1 times the matching number. In recent years, hypergraphs meeting this conjectured bound, known as r-Ryser hypergraphs, have been studied extensively. It was proved by Haxell, Narins, and Szabo that all 3-Ryser hypergraphs with matching number nu > 1 are essentially obtained by taking nu disjoint copies of intersecting 3-Ryser hypergraphs. Abu-Khazneh showed that such a characterization is false for r = 4 by giving a computer generated example of a 4-Ryser hypergraph with nu = 2 whose vertex set cannot be partitioned into two sets such that we have an intersecting 4-Ryser hypergraph on each of these parts. Here we construct first infinite families of r-Ryser hypergraphs, for any fixed matching number nu > 1, that are truly nonintersecting in the sense that they do not contain two vertex disjoint intersecting r-Ryser subhypergraphs. [ABSTRACT FROM AUTHOR]

The classical problem of estimating the number of edges in a subgraph of a special distance graph is considered. Old results are significantly improved. [ABSTRACT FROM AUTHOR]

Possibility theory is applied to introduce and reason about the fundamental notion of a key for uncertain data. Uncertainty is modeled qualitatively by assigning to tuples of data a degree of possibility with which they occur in a relation, and assigning to keys a degree of certainty which says to which tuples the key applies. The associated implication problem is characterized axiomatically and algorithmically. Using extremal combinatorics, we then characterize the families of non-redundant possibilistic keys that attain maximum cardinality. In addition, we show how to compute for any given set of possibilistic keys a possibilistic Armstrong relation, that is, a possibilistic relation that satisfies every key in the given set and violates every possibilistic key not implied by the given set. We also establish an algorithm for the discovery of all possibilistic keys that are satisfied by a given possibilistic relation. It is shown that the computational complexity of computing possibilistic Armstrong relations is precisely exponential in the input, and the decision variant of the discovery problem is NP-complete as well as W[2]-complete in the size of the possibilistic key. Further applications of possibilistic keys in constraint maintenance, data cleaning, and query processing are illustrated by examples. The computation of possibilistic Armstrong relations and discovery of possibilistic keys from possibilistic relations have been implemented as prototypes. Extensive experiments with these prototypes provide insight into the size of possibilistic Armstrong relations and the time to compute them, as well as the time it takes to compute a cover of the possibilistic keys that hold on a possibilistic relation, and the time it takes to remove any redundant possibilistic keys from this cover. [ABSTRACT FROM AUTHOR]