Diagonalization in proof complexity

Jan Krajíček

Displaying similar documents to “Diagonalization in proof complexity”

On a number theoretic conjecture on positive integral points in a 5-dimensional tetrahedron and a sharp estimate of the Dickman–De Bruijn function

Ke-Pao Lin, Xue Luo, Stephen S.-T. Yau, Huaiqing Zuo (2014)

Journal of the European Mathematical Society

Similarity:

It is well known that getting the estimate of integral points in right-angled simplices is equivalent to getting the estimate of Dickman-De Bruijn function $ψ (x, y)$ which is the number of positive integers $\leq x$ and free of prime factors $> y$ . Motivating from the Yau Geometry Conjecture, the third author formulated the Number Theoretic Conjecture which gives a sharp polynomial upper estimate that counts the number of positive integral points in n-dimensional ( $n \geq 3$ ) real right-angled simplices. In this...

Selection principles and upper semicontinuous functions

Masami Sakai (2009)

Colloquium Mathematicae

Similarity:

In connection with a conjecture of Scheepers, Bukovský introduced properties wQN* and SSP* and asked whether wQN* implies SSP*. We prove it in this paper. We also give characterizations of properties S₁(Γ,Ω) and $S_{f i n} (Γ, Ω)$ in terms of upper semicontinuous functions

On coarse embeddability into $ℓ_{p}$ -spaces and a conjecture of Dranishnikov

Piotr W. Nowak (2006)

Fundamenta Mathematicae

Similarity:

We show that the Hilbert space is coarsely embeddable into any $ℓ_{p}$ for 1 ≤ p ≤ ∞. It follows that coarse embeddability into ℓ₂ and into $ℓ_{p}$ are equivalent for 1 ≤ p < 2.

Results related to Huppert’s $ρ$ - $σ$ conjecture

Xia Xu, Yong Yang (2023)

Czechoslovak Mathematical Journal

Similarity:

We improve a few results related to Huppert’s $ρ$ - $σ$ conjecture. We also generalize a result about the covering number of character degrees to arbitrary finite groups.

On the domination of triangulated discs

Noor A&amp;#039;lawiah Abd Aziz, Nader Jafari Rad, Hailiza Kamarulhaili (2023)

Mathematica Bohemica

Similarity:

Let $G$ be a $3$ -connected triangulated disc of order $n$ with the boundary cycle $C$ of the outer face of $G$ . Tokunaga (2013) conjectured that $G$ has a dominating set of cardinality at most $\frac{1}{4} (n + 2)$ . This conjecture is proved in Tokunaga (2020) for $G - C$ being a tree. In this paper we prove the above conjecture for $G - C$ being a unicyclic graph. We also deduce some bounds for the double domination number, total domination number and double total domination number in triangulated discs.

The generalized Hodge and Bloch conjectures are equivalent for general complete intersections

Claire Voisin (2013)

Annales scientifiques de l'École Normale Supérieure

Similarity:

We prove that Bloch’s conjecture is true for surfaces with $p_{g} = 0$ obtained as $0$ -sets $X_{σ}$ of a section $σ$ of a very ample vector bundle on a variety $X$ with “trivial” Chow groups. We get a similar result in presence of a finite group action, showing that if a projector of the group acts as $0$ on holomorphic $2$ -forms of $X_{σ}$ , then it acts as $0$ on $0$ -cycles of degree $0$ of $X_{σ}$ . In higher dimension, we also prove a similar but conditional result showing that the generalized Hodge conjecture for general $X_{σ}$ ...

Lower semicontinuous envelopes in $W^{1, 1} \times L^{p}$

Ana Margarida Ribeiro, Elvira Zappale (2014)

Banach Center Publications

Similarity:

The lower semicontinuity of functionals of the type $\int_{Ω} f (x, u, v, \nabla u) d x$ with respect to the $(W^{1, 1} \times L^{p})$ -weak* topology is studied. Moreover, in absence of lower semicontinuity, an integral representation in $W^{1, 1} \times L^{p}$ for the lower semicontinuous envelope is also provided.

On a conjecture of Dekking : The sum of digits of even numbers

Iurie Boreico, Daniel El-Baz, Thomas Stoll (2014)

Journal de Théorie des Nombres de Bordeaux

Similarity:

Let $q \geq 2$ and denote by $s_{q}$ the sum-of-digits function in base $q$ . For $j = 0, 1, \dots, q - 1$ consider $# {0 \leq n < N : s_{q} (2 n) \equiv j (mod q)} .$ In 1983, F. M. Dekking conjectured that this quantity is greater than $N / q$ and, respectively, less than $N / q$ for infinitely many $N$ , thereby claiming an absence of a drift (or Newman) phenomenon. In this paper we prove his conjecture.

Lower bounds for the largest eigenvalue of the gcd matrix on ${1, 2, \dots, n}$

Jorma K. Merikoski (2016)

Czechoslovak Mathematical Journal

Similarity:

Consider the $n \times n$ matrix with $(i, j)$ ’th entry $gcd (i, j)$ . Its largest eigenvalue $λ_{n}$ and sum of entries $s_{n}$ satisfy $λ_{n} > s_{n} / n$ . Because $s_{n}$ cannot be expressed algebraically as a function of $n$ , we underestimate it in several ways. In examples, we compare the bounds so obtained with one another and with a bound from S. Hong, R. Loewy (2004). We also conjecture that $λ_{n} > 6 π^{- 2} n log n$ for all $n$ . If $n$ is large enough, this follows from F. Balatoni (1969).

A tight quantitative version of Arrow’s impossibility theorem

Nathan Keller (2012)

Journal of the European Mathematical Society

Similarity:

The well-known Impossibility Theorem of Arrow asserts that any generalized social welfare function (GSWF) with at least three alternatives, which satisfies Independence of Irrelevant Alternatives (IIA) and Unanimity and is not a dictatorship, is necessarily non-transitive. In 2002, Kalai asked whether one can obtain the following quantitative version of the theorem: For any $ϵ > 0$ , there exists $δ = δ (ϵ)$ such that if a GSWF on three alternatives satisfies the IIA condition and its probability of...

Upper bounds for the domination numbers of toroidal queens graphs

Christina M. Mynhardt (2003)

Discussiones Mathematicae Graph Theory

Similarity:

We determine upper bounds for $γ (Q n^{t})$ and $i (Q ₙ^{t})$ , the domination and independent domination numbers, respectively, of the graph $Q ₙ^{t}$ obtained from the moves of queens on the n×n chessboard drawn on the torus.

Characterization of the alternating groups by their order and one conjugacy class length

Alireza Khalili Asboei, Reza Mohammadyari (2016)

Czechoslovak Mathematical Journal

Similarity:

Let $G$ be a finite group, and let $N (G)$ be the set of conjugacy class sizes of $G$ . By Thompson’s conjecture, if $L$ is a finite non-abelian simple group, $G$ is a finite group with a trivial center, and $N (G) = N (L)$ , then $L$ and $G$ are isomorphic. Recently, Chen et al. contributed interestingly to Thompson’s conjecture under a weak condition. They only used the group order and one or two special conjugacy class sizes of simple groups and characterized successfully sporadic simple groups (see Li’s PhD dissertation)....

A geometric construction for spectrally arbitrary sign pattern matrices and the $2 n$ -conjecture

Dipak Jadhav, Rajendra Deore (2023)

Czechoslovak Mathematical Journal

Similarity:

We develop a geometric method for studying the spectral arbitrariness of a given sign pattern matrix. The method also provides a computational way of computing matrix realizations for a given characteristic polynomial. We also provide a partial answer to $2 n$ -conjecture. We determine that the $2 n$ -conjecture holds for the class of spectrally arbitrary patterns that have a column or row with at least $n - 1$ nonzero entries.

On upper bounds for total $k$ -domination number via the probabilistic method

Saylí Sigarreta, Saylé Sigarreta, Hugo Cruz-Suárez (2023)

Kybernetika

Similarity:

For a fixed positive integer $k$ and $G = (V, E)$ a connected graph of order $n$ , whose minimum vertex degree is at least $k$ , a set $S \subseteq V$ is a total $k$ -dominating set, also known as a $k$ -tuple total dominating set, if every vertex $v \in V$ has at least $k$ neighbors in $S$ . The minimum size of a total $k$ -dominating set for $G$ is called the total $k$ -domination number of $G$ , denoted by $γ_{k t} (G)$ . The total $k$ -domination problem is to determine a minimum total $k$ -dominating set of $G$ . Since the exact problem is in general quite difficult...